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!
🎉 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
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.
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.
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.