# Searching for entity awareness in 3D space algorithm and data structure

I'm trying to do some huge AI system just for the fun and I've come to this problem. How can I let the AI entities know about each other without getting the CPU to perform redundant and costly work? Every entity has a spatial awareness zone and it has to know what's inside when it has to decide what to do.

First thoughts, for every entity test if the other entities are inside the first's reach. Ok, so it was the first try and yep, that is redundant and costly. We are working with real time AI over 10000+ entities so this is not a solution.

Second try, calculate some grid over the awareness zone of every entity and test whether in this zones are entities (we are working with 3D entities with float x,y,z location coordinates) testing every point in the grid with the indexed-by-coordinate entities. Well, I don't like this because is also costly, but not as the first one.

Third, create some multi linked lists over the x's and y's indexed positions of the entities so when we search for an interval between x,y and z,w positions (this interval defines the square over the spatial awareness zone) over the multi linked list, we won't have 'voids'. This has the problem of finding the nearest proximity value if there isn't one at the position where we start the search.

I'm not convinced with any of the ideas so I'm searching for some enlightening. Do you people have any better ideas?

• Cutting out the context may help harvesting progress on existing, more general problems. I believe this problem can be reduced to some neighbor search problem (perhaps Fixed-radius near neighbors).
– user7043
Commented Nov 25, 2011 at 17:21
• Wow, that pdf has some nice solutions for this problem Commented Nov 25, 2011 at 23:44

Binary space partitions is one scalable option. It can be parallelized if you do it correctly as well; there's an article on GPU Gems that explains how.

Another one is Bounding Volume Hierarchies.

A lot of applications and games actually combine the two, making BSP trees of BVH trees.

Interesting that you ask this question though, I asked a question on SO yesterday regarding the implementation of BVHs... having a bit of trouble figuring it out :(

I'm not sure if I understood your problem but you may try to partition your space into an octree.

This will help making your search for near elements more efficient (see an example of octree search here).