Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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). – delnan Nov 25 '11 at 17:21
Wow, that pdf has some nice solutions for this problem – Khanser Nov 25 '11 at 23:44
up vote 1 down vote accepted

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 :(

share|improve this answer

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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.