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!
Flocking Behavior
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.
this just came from the top of my head, i have implemented flocking with this sort of approach.
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.
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.
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.
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.
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.
Author
Hmm, I think I shall give it a try on grid based approach ...
Thanks for all the suggestions :)
Appreciate it
Thanks for all the suggestions :)
Appreciate it
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
