February 16, 2014 at 15:32Boids - a simple algorithm for moving unit groups
During the development of a clone of one toy, I needed to move groups of units from one planet to another. The first thing that came to mind was to spawn units one by one and move them in a straight line. But it didn’t look very funny, besides - it was necessary to somehow go around the planets. After a quick look at group moving algorithms, I decided to try Boids. The result is this:
Under cat description of the algorithm with code examples.
The Boids algorithm was created by Craig Reynolds in 1986 as a model for moving a flock of birds. It is based on the following three rules:
As an addition to them, I used two more:
For each unit, it is necessary to store the coordinates and speed. You also need to know the coordinates of the target and obstacles. During the recalculation of the game world (recounting can be done, for example, 20 times per second), you need to determine the new coordinate and speed for all units. To do this, you need to determine the new unit speed and move it.
Each of the rules listed above allows you to get part of the speed. Unit general speed - the sum of the speeds obtained after applying the rules and the previous speed of the unit itself.
So that the unit does not overclock much - it is recommended to limit the speed. It is best to spawn units flying from one point in turn, at short intervals.
The rules are implemented as follows:
In practice, the speeds issued by each of the rules must be reduced (by dividing by some factor) or limited. Limitations and coefficients are selected experimentally to achieve the best result.
And now a little code. The main code for moving all units (Ships - we are talking about spaceships): pastebin.com/jeHCWr8u In addition to the above, the collision of units with planets and flight outside the world are also checked here. Speed limit - normalized vector (representing the direction) multiplied by the limiting coefficient: pastebin.com/a57hh76V
Implementation of rules: pastebin.com/YDSTDh3t Implementation features - some of the rules apply only to units from the current group (belonging to one player and having one and the same the same goal). Distance - the distance in the geometric sense.
Ship spawning is implemented as follows. Each planet has a queue of ships awaiting spawning. When a player gives a command, several ships are created (from 1 to ~ 20, depending on the amount of energy) and are added to the planet's queue: pastebin.com/FprtwTy4 And then, every 50 milliseconds it spawns one ship: pastebin.com/Tq4cvNbB
The algorithm is more suitable for simulating "living" units. It is good to apply in cases where the "swarm" behavior of the group is permissible. If it is necessary to organize a more stringent movement of units, most likely you will have to use another algorithm (or some of the modifications). Also, I was not able to organize the passage of one group of units through another during their perpendicular movement - either one group began to push the other from the trajectory (and eventually circumvented it from the side) - or the units of one group began to pass through units from the second (almost without going around them) . In the oncoming courses, the situation is better - sometimes one group divided the second into two and passed in the center, and sometimes passed next to it. In general, by repeatedly experimenting with parameters, Boids will achieve good looking results,
en.wikipedia.org/wiki/Boids - description of the algorithm on Wikipedia
www.kfish.org/boids/pseudocode.html - pseudo-code boids - with a description of some heuristics
habrahabr.ru/post/105639 - description of boids and its various variations (more theoretical )
github.com/bakwc/ozifi/tree/master/projects/space_capture - sources (implementation of boids in server / world.cpp)
Under cat description of the algorithm with code examples.
Description
The Boids algorithm was created by Craig Reynolds in 1986 as a model for moving a flock of birds. It is based on the following three rules:
- Cohesion - units try to stay as close to each other as possible.
- Separation - units tend to disperse in order to stay at a certain distance from each other
- Speed equalization - units from the same group tend to move at the same speed
As an addition to them, I used two more:
- Movement to the goal - units try to move to the set goal
- Avoid obstacles - units tend to the opposite side of obstacles
About implementation
For each unit, it is necessary to store the coordinates and speed. You also need to know the coordinates of the target and obstacles. During the recalculation of the game world (recounting can be done, for example, 20 times per second), you need to determine the new coordinate and speed for all units. To do this, you need to determine the new unit speed and move it.
Each of the rules listed above allows you to get part of the speed. Unit general speed - the sum of the speeds obtained after applying the rules and the previous speed of the unit itself.
v1 = Rule1();
v2 = Rule2();
v3 = Rule3();
unit.v = v1 + v2 + v3 + unit.v;
unit.pos = unit.pos + unit.v;
So that the unit does not overclock much - it is recommended to limit the speed. It is best to spawn units flying from one point in turn, at short intervals.
The rules are implemented as follows:
- Cohesion - it is necessary to find the center of mass (arithmetic mean of the coordinates of all units) and determine the vector directed from the current unit to the center of mass.
- Separation - you need to determine the average direction from all the nearest units.
- Speed equalization - you need to find the average speed of all units.
- Movement to the goal - a vector directed from the unit towards the goal.
- Avoidance of obstacles - coincides with the second, except that the direction must be sought away from the nearest obstacles.
In practice, the speeds issued by each of the rules must be reduced (by dividing by some factor) or limited. Limitations and coefficients are selected experimentally to achieve the best result.
The code
And now a little code. The main code for moving all units (Ships - we are talking about spaceships): pastebin.com/jeHCWr8u In addition to the above, the collision of units with planets and flight outside the world are also checked here. Speed limit - normalized vector (representing the direction) multiplied by the limiting coefficient: pastebin.com/a57hh76V
Implementation of rules: pastebin.com/YDSTDh3t Implementation features - some of the rules apply only to units from the current group (belonging to one player and having one and the same the same goal). Distance - the distance in the geometric sense.
Ship spawning is implemented as follows. Each planet has a queue of ships awaiting spawning. When a player gives a command, several ships are created (from 1 to ~ 20, depending on the amount of energy) and are added to the planet's queue: pastebin.com/FprtwTy4 And then, every 50 milliseconds it spawns one ship: pastebin.com/Tq4cvNbB
Pros and cons
The algorithm is more suitable for simulating "living" units. It is good to apply in cases where the "swarm" behavior of the group is permissible. If it is necessary to organize a more stringent movement of units, most likely you will have to use another algorithm (or some of the modifications). Also, I was not able to organize the passage of one group of units through another during their perpendicular movement - either one group began to push the other from the trajectory (and eventually circumvented it from the side) - or the units of one group began to pass through units from the second (almost without going around them) . In the oncoming courses, the situation is better - sometimes one group divided the second into two and passed in the center, and sometimes passed next to it. In general, by repeatedly experimenting with parameters, Boids will achieve good looking results,
References
en.wikipedia.org/wiki/Boids - description of the algorithm on Wikipedia
www.kfish.org/boids/pseudocode.html - pseudo-code boids - with a description of some heuristics
habrahabr.ru/post/105639 - description of boids and its various variations (more theoretical )
github.com/bakwc/ozifi/tree/master/projects/space_capture - sources (implementation of boids in server / world.cpp)