Jump to content
  • Advertisement
Sign in to follow this  
daniel_i_l

flocking

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

I have a question about implementing a flocking algorithm. It seems that in every frame you have to take into account the positions and speeds of the units closest to the unit that you're updateing. How do you find those units, for every unit do you have to loop through all the other units and find which ones are close to the one that your updateing? Also, how are formations implemented with flocking? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
I have not done flocking myself yet,
However, since collision detection for my game potentially has to deal with similar problems, I think I will watch this thread.

One thing you can do is space partitioning. Rather than looping thru Every unit, space would be partitioned into sectors and you'd only loop thru the units that are in the same or adjacent sector to the one unit currently selected.
Partitioning of space can be done with either some regular grid structure, or some kind of search tree.
In my own case, partitioning is a property of the level datastructure.


Id also suggest, that for flocking the closests units probably don't change very often, since everyone is moving in a flock...
You can probably get away with not updating that info every frame, also keep in mind that even when the closest unit moves away, one of his old closest units is probably your new closest.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster



Optimizations of the NxM distance check -- you only have to do half the square
as the distance between object A and B is the same as between B and A (and distance between A and A is always 0).

Another possibility is that you dont have to calculate the distance every render/move cycle if the positions change only a little every cycle -- you can spread out the processing over many cycles using a 'round robin' methedology.


If you have huge numbers of objects to compare, some kind of subsetting method can be used to decrease the number of comparisons needed. (a subdivision grid based on coordinates...)

An alternative could be to maintain a magnitude range between object that will flag less frequent recalculation between objects that are outside of a certain distance threshold (ie- when greater than range X only recheck distance every 10th cycle -- or somesuch andchange the flag if it comes within the threshold).



If you have a small set of objects it often is simply faster to use a brute force method rather than another method that hasa high overhead.


Oh and another oldy/goodie -- lazy evaluation using rough estimations for distance (ie- crude distance is the greater of the differences of each coordinate XYZ of the 2 objects -- no expensive Square root to do unless you need a more accurate distance value).

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!