Jump to content
  • Advertisement
Sign in to follow this  
Thunder0ne

Flocking optimisation: grid or octree partitioning?

This topic is 3624 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!