Hi all, I was studying steering behaviours and came across flocking. I have read that a way to reduce CPU usage implementing group cohesion, spacing or alignment is partitioning the space in a grid made up by cells of a predefined size. What about an octree? Could somebody point to an article or tell something about advantages and disadvantages ? Many thanks.

Both schemes seem good ideas.
Look for generic literature and code about spatial indexing data structures: there is nothing specific about accelerating neighbour search (usually all within a certain distance or the N nearest ones or all adjacent entities in the Delaunay graph) for the purpose of flocking, except perhaps that approximate algorithms might cause behaviour glitches.

I agree that trimming down the number of neighbors to look at for your alignment, speed, etc. would speed up the calculations. There is actually a biological merit to that as well. Someone studied starlings and determined that they look at about 7 of their neighbors at one time even when they are in groups of hundreds.

However, from a compuational point, you have to be careful that your algorithm for determining those neighbors is not more costly than just taking into account the entire group.

I am trying both grid and octree using them in order to avoid all of the agents to check terrain proximity (the number of agent's neighbours is cut down just checking their relative squared distance)
and I am not noticing differences in performance (I am measuring the whole AI update method which updates all of the agents AI).
I was trying and use space partitioning also to find each agent neighbours but this was more expensive than just checking their squared distance as mentioned above.

So the question still remains unresolved, but I think that there is not a clear choice between grid and octree: each peculiar case should be evaluated and measured carefully especially if there are memory space allocation problems, or small CPU cache size and so forth...

I am going with octree just because it looks more "cool" since uses recursive functions :-)

Thanks.

Computational-cost-wise, the grid should almost always be no worse than a tree, except in pathological cases of cache thrashing.


Full updates with dynamic entities should be O(n), while for the tree it would be O(n log n)

Lookup should also approach O(1), while for the tree it would be O(log n)


This potential saving comes at the cost of larger memory overhead, tho.

For a more complex problem where multiple grids would be considered, the balance shifts quickly towards tree's which are more general purpose (no fine tuning for entity sizes and so forth)

Quote: Original post by Thunder0ne
I am trying both grid and octree using them in order to avoid all of the agents to check terrain proximity (the number of agent's neighbours is cut down just checking their relative squared distance) and I am not noticing differences in performance (I am measuring the whole AI update method which updates all of the agents AI).

I was trying and use space partitioning also to find each agent neighbours but this was more expensive than just checking their squared distance as mentioned above.

Hmm sounds like you are doing the grid partitioning scheme incorrectly. In a proper grid partitioning or spatial hashing scheme you need never do squared distance check to find neighbors. Neighbors are simply objects in the same grid cells or neighboring cells. So, finding neighbors within X grid squares is essentially O(1). Implemented correctly it should be incredibly faster than N^2 distance checks between all objects.