Boids - a simple algorithm for moving groups of units
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 close the units one by one and move them in a straight line. But it didn’t look very fun, and besides, it was necessary to somehow bypass the planets. After a quick look at the group movement algorithms, I decided to try Boids. The result was this:
Under the cut description of the algorithm with code examples.
')
The Boids algorithm was created by Craig Reynolds in 1986 as a model for moving flocks of birds. It is based on the following three rules:
As a supplement to them, I used two more:
For each unit you need to store the stored coordinates and speed. You also need to know the coordinates of the goal and obstacles. During the recalculation of the game world (recalculation can be done, for example, 20 times per second), you need to define a new coordinate and speed for all units. To do this, you need to determine the new speed of the unit and move it.
Each of the rules listed above allow you to get some of the speed. The total speed of the unit is the sum of the speeds obtained after the application of the rules and the previous speed of the unit itself.
So that the unit does not accelerate strongly - it is recommended to limit the speed. Spawning units departing from one point is best 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 a certain coefficient) or limited. Limitations and coefficients are selected experimentally to achieve the best result.
And now some code. The main code that deals with the movement of all units (Ships - we are talking about space ships): pastebin.com/jeHCWr8u In addition to the above, the collision of units with planets and departure beyond the world is also checked. Speed limit - normalized vector (representing a direction) multiplied by the limiting coefficient: pastebin.com/a57hh76V
Implementation of the rules: pastebin.com/YDSTDh3t Features of the implementation - part of the rules apply only to units from the current group (belonging to the same player and having the same goal). Distance - distance in a geometric sense.
Spawn ships implemented as follows. Each planet has a queue of ships awaiting spawnning. When a player gives a command - several ships are created (from 1st to ~ 20, depending on the amount of energy) and entered into the planet's queue: pastebin.com/FprtwTy4 And then, every 50 milliseconds, one ship will spawn: pastebin.com/Tq4cvNbB
The algorithm is more suitable for the simulation of "live" units. It is good to use in cases where the "swarm" behavior of the group is permissible. In case it is necessary to organize a more strict movement of units, you will most likely have to use another algorithm (or one of the modifications). I also did not manage to organize the passage of one group of units through another when they were perpendicularly moving - either one group started pushing another from the trajectory (and eventually avoided it from the side) - or units of one group began to pass through the units from the second (almost skirting them) . On a collision course, the situation is better - sometimes one group divided the second into two and ran through the center, and sometimes went alongside it. In general, by repeatedly experimenting with parameters, Boids will allow you to achieve good-looking results that are suitable for different situations.
en.wikipedia.org/wiki/Boids - description of the algorithm in Wikipedia
www.kfish.org/boids/pseudocode.html - boids pseudocode - with descriptions 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 - source (implementation boids in server / world.cpp)
Under the cut description of the algorithm with code examples.
')
Description
The Boids algorithm was created by Craig Reynolds in 1986 as a model for moving flocks of birds. It is based on the following three rules:
- Cohesion - units try to stay as close as possible to each other
- Separation - units seek to disperse in order to keep apart from each other
- Alignment of speeds - units from one group tend to move at the same speed
As a supplement to them, I used two more:
- Going to the goal - the units are trying to move towards the target
- Avoiding obstacles - units aim in the opposite direction from obstacles
About implementation
For each unit you need to store the stored coordinates and speed. You also need to know the coordinates of the goal and obstacles. During the recalculation of the game world (recalculation can be done, for example, 20 times per second), you need to define a new coordinate and speed for all units. To do this, you need to determine the new speed of the unit and move it.
Each of the rules listed above allow you to get some of the speed. The total speed of the unit is the sum of the speeds obtained after the application of 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 accelerate strongly - it is recommended to limit the speed. Spawning units departing from one point is best in turn, at short intervals.
The rules are implemented as follows:
- Cohesion - it is necessary to find the center of mass (the arithmetic average 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.
- Alignment of speeds - it is necessary to find the average speed of all units.
- Going to the goal is a vector directed from the unit towards the goal.
- Avoiding obstacles - coincides with the second, except for the fact that the direction should be sought away from the nearest obstacles.
In practice, the speeds issued by each of the rules must be reduced (by dividing by a certain coefficient) or limited. Limitations and coefficients are selected experimentally to achieve the best result.
Code
And now some code. The main code that deals with the movement of all units (Ships - we are talking about space ships): pastebin.com/jeHCWr8u In addition to the above, the collision of units with planets and departure beyond the world is also checked. Speed limit - normalized vector (representing a direction) multiplied by the limiting coefficient: pastebin.com/a57hh76V
Implementation of the rules: pastebin.com/YDSTDh3t Features of the implementation - part of the rules apply only to units from the current group (belonging to the same player and having the same goal). Distance - distance in a geometric sense.
Spawn ships implemented as follows. Each planet has a queue of ships awaiting spawnning. When a player gives a command - several ships are created (from 1st to ~ 20, depending on the amount of energy) and entered into the planet's queue: pastebin.com/FprtwTy4 And then, every 50 milliseconds, one ship will spawn: pastebin.com/Tq4cvNbB
Advantages and disadvantages
The algorithm is more suitable for the simulation of "live" units. It is good to use in cases where the "swarm" behavior of the group is permissible. In case it is necessary to organize a more strict movement of units, you will most likely have to use another algorithm (or one of the modifications). I also did not manage to organize the passage of one group of units through another when they were perpendicularly moving - either one group started pushing another from the trajectory (and eventually avoided it from the side) - or units of one group began to pass through the units from the second (almost skirting them) . On a collision course, the situation is better - sometimes one group divided the second into two and ran through the center, and sometimes went alongside it. In general, by repeatedly experimenting with parameters, Boids will allow you to achieve good-looking results that are suitable for different situations.
Links
en.wikipedia.org/wiki/Boids - description of the algorithm in Wikipedia
www.kfish.org/boids/pseudocode.html - boids pseudocode - with descriptions 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 - source (implementation boids in server / world.cpp)
Source: https://habr.com/ru/post/212721/
All Articles