🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Flocking Question

Started by
5 comments, last by cucumba 4 years, 1 month ago

Hello! This may be a rare question, but is there a way to make self-steering 2D Boids form into a specific shape? Precision is not necessary, I only need an idea of how to make them form into basic shapes, like a circle, a straw, or an arrow.
If you know of any techniques related to this, please let me know. Thanks!

None

Advertisement

To approximate a shape with a formation of N boids, you should:

  • Choose N points on the shape such that, if each has a boid very close to it, the boid formation approximates the shape (for example, to form a ring you could choose the vertices of a N sided regular polygon of appropriate center and size).
  • Assign each of the N points to one of the N boids as a target to reach (the traditional “arrival” behaviour).
  • Animate the N target points as the “specific shape” moves and morphs.
  • Add or remove target points as boids are added or removed.

Of course boids will only track their targets if fast enough, if not assigned conflicting behaviour (such as following a leader, which doesn't probably make sense, or aligning with and/or matching velocity with other boids going somewhere else), if minimum separation distances are sufficiently smaller than the gaps between target points (to avoid obstructions), etc.

There are rather general algorithms to compute good target points: for example

  • If the shape is a smooth curve with an arc-length parametrization and a known length L you can pick evenly spaced points along it (at lengths 0, L/(N-1), 2L/(N-1), …, L if it's open or at lengths 0, L/N, 2L/N, …, (N-1)L/N if it's closed).
  • If the shape is a convex region you can remove random points and add random points in the interior as N changes and repeatedly push the target points away from their neighbours in the Delaunay triangulation to make them more evenly spaced and to fill the whole shape.

Omae Wa Mou Shindeiru

Another way is to simply take the pre-calculated shape points as attractors but not strong enough that they override the separation from other boids. That way, everyone is trying to move to nearby points that aren't already crowded by other boids. The advantage of this is that, if the “formation” turns, then everyone goes to the nearest available point rather than to one they were assigned to that may all of a sudden be on the other side of the flock.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

IADaveMark said:
The advantage of this is that, if the “formation” turns, then everyone goes to the nearest available point rather than to one they were assigned to that may all of a sudden be on the other side of the flock.

The nearest target could be the same for more than one boid, which is likely to be a worse problem than selecting suboptimal targets. Assigning targets to boids is a traditional graph problem, weighted bipartite matching (unless one wants to be very sophisticated, with a complete graph and with costs given by boid-target distances).

When careless arbitrary target assignments aren't good enough, computing an optimal bipartite matching from time to time would ensure that every boid has a good target, with some appearance of coordination, regardless of crowding and disruptions.

Omae Wa Mou Shindeiru

Yeah, I didn't bother to go in depth on that.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Thank you both very much!

None

This topic is closed to new replies.

Advertisement