When coding various AI systems, very often I find myself writing queries to find various entities within a certain distance of a point. Until now, I'd always used a brute-force search to do this because the number of entities I'm concerned with is so low. However, I can see a point of time in which that will become a performance problem if the number of entities increases or the more systems issue such queries per frame. I've found a lot of information about various spatial data structures(kd-trees, bsps, octrees, quadtrees, etc), but everything I've found has been in relation to either rendering or physics, so they're requirements are quite different from what the AI needs. For physics and rendering there are usually hundreds or thousands of entities, most of which are not moving. For the AI, at least in my circumstances, there are only dozens of entities(ai agents, projectiles, etc), but most of them are moving all the time. The other difference is that for physics or rendering, the structure will be used all the time. For AI, the structure might be used dozens of times in one frame, then not at all for the next 50 frames. It all depends on what the AI is doing at the time. Because the requirements are different, I'm unsure whether one of the above algorithms would be suitable or not, or if there is a better algorithm available. The key I think would be extremely low overhead for updating the structure each frame, since there's no guarantee that it'll be used enough during that frame to cover the overhead. Does anyone have any suggestions?

Have you considered a spatial hash?
Or something like a grid of linked lists, where entities can be quickly added and removed when they enter/leave a square on the grid.

I use something like this when my "entities" are points without a bounding area.

Queries can be performed on the grid boxes, If a grid box falls completely within the query area, you know all the entities in the linked list are within the query.

It sounds like you have a lot of static entities. I suppose you could put 2 linked lists (or another data structure) in every box, one for dynamic entities, and 1 for the static world stuff that doesn't move.

A "loose" quadtree (or octtree, since it's the same basic idea) might be a good fit. The idea is that the various nodes are expanded so they overlap somewhat which means that moving objects tend to stay in the same node for longer so most of the time maintaining the tree is trivial. Keeping the quadtree quite coarse (ie. the leaf nodes are still reasonably big) will cut down on the time spent updating the tree as well, but should still provide a good rough culling of objects.

Quote: Original post by Nohup
Have you considered a spatial hash?
Or something like a grid of linked lists, where entities can be quickly added and removed when they enter/leave a square on the grid.

I use something like this when my "entities" are points without a bounding area.

Queries can be performed on the grid boxes, If a grid box falls completely within the query area, you know all the entities in the linked list are within the query.

It sounds like you have a lot of static entities. I suppose you could put 2 linked lists (or another data structure) in every box, one for dynamic entities, and 1 for the static world stuff that doesn't move.

Would you mind explaining what you mean by a spatial hash? The pages I found through a google search for that term seemed to be related to relate to other topics.

I did think about a grid, but it might end up wasting a lot of space in the kind of levels I'm using. A lot of them are long and twisting, so the x/y bounds are both very large, but the actual space used by the level is a tiny fraction of that space.

For the other part of your response, I actually don't have any static entities really, which is why the standard solutions for rendering/physics didn't seem to fit. The only thing I intend to put in this structure are the ai agents and projectiles, which for the most part are always moving.

Quote: Original post by OrangyTang
A "loose" quadtree (or octtree, since it's the same basic idea) might be a good fit. The idea is that the various nodes are expanded so they overlap somewhat which means that moving objects tend to stay in the same node for longer so most of the time maintaining the tree is trivial. Keeping the quadtree quite coarse (ie. the leaf nodes are still reasonably big) will cut down on the time spent updating the tree as well, but should still provide a good rough culling of objects.

It's definitely a possibility. I assume what I would do to find the potential set of objects within a circle in the quadtree is to recursively iterate through the tree. At each node, do a square/circle intersection test for the node against the circle, then recurse through the children if that test is positive.

Two questions though, if you don't mind:

1. My guess is that to update the tree, each entity would have its current position in the tree stored. Then when updating, it would calculate its position in the tree for its new location. If it's still the same, nothing is done. Otherwise, it's removed from it's current location(possibly deleting that node or nodes), and added to the new location(possibly creating a node or nodes). Or is there a better way to do this, potentially without having to have each entity store its current location in the tree?

2. In relation to what I posted above, about recursing through the tree dong square/circle tests. If the restriction was made that all objects are held only in leaf nodes at a specific depth in the tree(i.e. all objects are stored at nodes with a depth of 5), is there any faster way to calculate the intersecting nodes? With this restriction, it would be less of a quadtree and more of a sparse grid, so it seems like there should be some optimizations possible, but I might just be imagining it.

Quote: Original post by Dean Harris
1. My guess is that to update the tree, each entity would have its current position in the tree stored. Then when updating, it would calculate its position in the tree for its new location. If it's still the same, nothing is done. Otherwise, it's removed from it's current location(possibly deleting that node or nodes), and added to the new location(possibly creating a node or nodes). Or is there a better way to do this, potentially without having to have each entity store its current location in the tree?

That's how I'd do it. If your entity knows which node within the tree then it can do more intelligent/efficient updates. First you check it's current node to see if it is still within the same node and nothing needs to be done. If it doesn't fit then you can recursivly check the parent nodes until you find one which fits. That should be better than starting from the root node every time.

Quote: 2. In relation to what I posted above, about recursing through the tree dong square/circle tests. If the restriction was made that all objects are held only in leaf nodes at a specific depth in the tree(i.e. all objects are stored at nodes with a depth of 5), is there any faster way to calculate the intersecting nodes? With this restriction, it would be less of a quadtree and more of a sparse grid, so it seems like there should be some optimizations possible, but I might just be imagining it.

I don't like storing objects only in leaf nodes, since it means that you either have to store large entities in multiple leaf nodes (awkward to update and maintain) or you have to impose hard limits on the size of your entities (which may or may not be acceptable for you).

A quadtree is the most general solution, so it deals with pretty much anything (particularly entities of vastly different sizes). If you've got extra restrictions you can use them to cut corners and optimise. Personally since you havn't got any sort of spatial tree I'd be inclined to start with something standard (like a quadtree or sorted x/y lists) and look into optimising it once you can actually benchmark it and see where it's spending it's CPU time.

Quick description of my understanding of a spatial hash...

An object is at (X, Y) (we'll just consider a mostly flat 2D world)
Lets put 2 objects in the game, their locations are (100,200) and (300,400)
To "hash" thier spatial positions, I would divide their coordinates by, say 100, and drop the remainder.

That puts the 2 objects into the boxes (1,2) and (3,4)

That's just the hashing part. So, a 3'rd object at (123, 234) will "hash" into (1,2) as well, right alongside the (100,200) object.


Now, the actual data structure you would use to hold these items is a 2D array of set<object> or linked list, or vector<object>, or whatever data struct suits your purposes.

Then, whenever an object moves, say goes from (199, 250) to (200,250), you will remove the object from the set<object> at (1,2), and move it into (2,2)

When you want to see if another object is close, you would search through the set<object> which holds the querying object, and other nearby sets to find neighbors.

You should never have to "rebuild" this sort of a system, just update it whenever something moves.

The positives to this system are very fast insertion, deletion, and updating.
It's memory requirements are small, and it is very easy to make the "boxes" bigger and smaller (by adjusting your hashing number), to optimize the performance.

The downside, is that this system works best with points. When an object is located at (199,299), if probably overlaps into another "box". Sometimes, this isn't a problem, but sometimes it is. It depends on what you're doing with it.
Loose quadtrees would probably be better to use if your AI system has to take the "size" of objects into account.

Another downside, is that a sparsely populated array of linked lists, will probably not provide the most optimal performance. You'll be looking through quite a few lists that don't have any objects in them. This could be helped with a "empty" flag for empty boxes, but I doubt that would help too much.

It's all about trade-offs. Try to think of the best/worst/general case, and keep things generic, so you can switch out a different data structure if you need to.

"Game Programming Gems 6, section 1.4" has an excellent article on this sort of thing called "Geographic Grid Registration of Game Ojbects" It focuses more on objects that have a "size", and register themselves with all the grids they occupy. It's not quite the same thing, but the same basic idea.

keep googling, and good luck.

I've used spatial hashing in several projects nearly the way Nohup describes above. Except:

- In one I used a C++ vector, not a linked list, in each grid square.

- In another I used a standard C# array the size of the max number of objects. If you only have a few hundred objects it isn't much memory really.

In both cases, all grid squares have an "object count" variable, so you never examine them if they are empty.

I used the methods described in this paper:

http://www.cs.ucf.edu/~hastings/papers/hashing-sim.zip

The illustrations in the paper are decent, and will give you a good idea of how to apply grid-based spatial hashing. The simulation in the paper does object-object, object-terrain, frustum culling and a simple AI routine on 10,000 mobile objects at 60+ FPS on 4 year old hardware.