Sign in to follow this  

Flocking Behavior

This topic is 2549 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

Recently I'm doing a game like Galcon
http://www.galcon.com/flash/ << this is flash version

But I'm struggling with the units flocking part. I wonder how Galcon implement the flocking in the game? I tried before with thousands of units moving around the map and it's still very smooth. I try to implement my own flocking and the result is sucks! I can't even support more than 300 or 400 hundreds of units flocking around.
My flocking complexity should be O(n^2) >.< Loop inside a loop...

Is there any good reference for efficient flocking implementation?

Thank You!

Share this post


Link to post
Share on other sites
you have to reduce the amount of comparisons. e.g. use a grid based approach, where only the objects within a grid and it's neighbours are compared. if the objects are spread out far enough and you have a large grid, the algorithm will have a cost of O(n*9). one grid must be at least as wide as the largest influence radius you use for flocking behaviour.

this just came from the top of my head, i have implemented flocking with this sort of approach.

Share this post


Link to post
Share on other sites
I cannot give a precise citation out of the back of my head, but there is research that birds and fish only ever look at very few of their neighbours (less than a dozen).

There are software implementations of flocking behaviour which simply pick 10 (or fewer) random units out of the crowd, and the simulations look 99% good at a fraction of the computional cost.

Share this post


Link to post
Share on other sites
With Starlings, it was about 7 neighbors.

This can be a result of the grid-based approach or there are other ways to do it. You can, for example, measure the distances are regular intervals, sort a list by that distance and then take measurements from the top N neighbors. Keeping that list up to date, however, not to mention resorting it all the time, can get costly.

You don't have to sort and use the top N neighbors. You can just set a radius that you are concerned with and only include agents that are inside that radius. If you set that radius in conjunction with your preferred separation distance, you can get an estimate of how many neighbors the calculations will ever have to account at the maximum.

Because the distance bit is just an arbitrary cut-off, this can be done by regularly but less frequently running distance checks and storing them in a table. That way, you only have to traverse the row representing the agent you are checking to see if each neighbor is inside the radius.

So much of the choice of how to do it is based on exactly the behavior that you want to represent and the environment you are in. It's hard to give an exact answer on how to approach it.

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
With Starlings, it was about 7 neighbors.


Furthermore, it wasnt just the 7 closest neighbours but always the same seven ones (for a while). I guess they switch those that are hard to see and track in the flock, but distance wasnt the deciding factor.

Additionally, I believe they used the static set of seven for steering not for positioning, where I, speculating again, presume they would use the closest ones to avoid collisions.

My memory is cloudy though.


Share this post


Link to post
Share on other sites

This topic is 2549 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this