This is my reseach project for the course "Gameplay Programming" at Howest University of Applied Sciences. The whole project is written in c++ and is made using the Elite-Engine. The list of the files added by me can be found at the bottom of this readme.
In my research I'm figuring out how to make different formations using flocking and steering behaviours. My goal was to create shapes without having to offset the position by fixed values, I wanted a system for more organic shapes.
The second part of my project was finding a way to make the units traverse the world together. I did this by calculating only one common path for the formation.
I started with a little setup: Every RTS-like game needs a way of selecting units and the location where the units should go. When you hold the left mouse button, you can move your mouse in any direction to create a selection rectangle. The units are assigned to the formation after releasing the button. I did this by checking if the middle position of any of my agents is inside the currently selected rectangle.
The size and direction of the formation can also be adjusted by holding and dragging right mouse button at any location. If you just click at a location, the size and rotation will stay the same. The camera movement was already implemented in the engine, only thing I changed there was setting the middle mouse button for this purpose.
After that I started to work on the movement itself. Based on what I read online, calculating a path for every unit is not always the best solution. The main problems are that the units sometimes split in two separate groups and this solution also requires a lot more computing power. I decided to calculate one common path, but every unit gets its own steering behaviour.
So, what are steering behaviours about? These are functions that calculate the linear and angular velocities of an agent based on the given target. The most common ones are "Seek" and "Face", they are respectivelly used for seeking a target and facing at it.
Other usefull steerings are so called "Flocking steerings", some examples are "Separation", "Cohesion" and "Velocity matching". This type of steering takes position and/or velocity of the neighboring agents into account.
The last type of steering behaviours that I use are "Combined steerings", with those behaviours you can easily combine multiple steerings together. I only use the "blended steering" in this research. As it allows you to set how much influence every steering has on the end result.
As I said, I wanted an organic formation, in other words without predictated positions. For this approach I decided to give my group only the target position where it should go, the right vector with magnitude equal to half of the size of the desired formation and formation type.
I started with implementing the line formation: my first idea was to "seek" the position on the line perpendicular to my agent. For this implementation I used the following math: dot product of perpendicular vector equals 0 and every position on a line can be described with: Begin point + (End point - Begin point) * t where 0 <= t <= 1.
I wanted to prevent clustering, so I blended my seek with separation and added face behaviour on top of that. This gave me a really promising result, but the problem was still there.
I thought that adding a seek to the furthest point would help and it did, I quite liked the result, so I let it in the final program under "Loose movement" button. After that I tried a similar technique with a circle. The math for that is: direction where agent comes from = current agent position - center of the circle. So, the desired seek position is: the center + normalized direction * radius of the circle. This ended up in an even larger clustering issue.
Adding a seek to the opposite side helped a lot, but the code started to look too complicated. I came to the idea that I could use the current group center as the formation center and add another seek towards the end target. I combined both of the circle implementations for the "Loose movement".
There after I searched for a way to implement the "Seek desired location" in the line formation, I simply replaced the Begin and End positions by an offseted position from the current group center. The result was really great.
Next step was implementing more than one line, the first method was to place the units in front of the center position in the first row and the others in the second row. This did not work out very wel, the main troubles were that the rows must contain the same amount of agents, otherwise the whole group got pulled back. (the average position was pulled towards the larger group)
A second approach was to split the group in two separate groups, therefore I needed to create a manager, the "Formation" class. Once one of the settings in the UI is changed, the agents are redistributed to the best fittng group. I achieve this by sorting all agents by a criterium, for example how much forward. The math that helps in sorting like this is: dot product of the direction from an agent to the formation center with the forward vector of the formation, if this result is larger, it means the agent is in front, otherwise it is in the back. The center of our formation becomes the average position of the centers of the groups.
The formation class gave me the posibility to create custom formations with circles and lines, but there seemed to be one problem. The middle position of the formation is not always where we want it to be. This results in not reaching the target position and due to this the formation never reaches the end destination.
I found two fixes for this issue, setting the formations so that they are somehow symetrical (for example all circles have the same center) or selecting a leader group, the center of this group becomes the center of whole formation. I played a little bit around with this and did an attempt to create an arrow with a leader in front of it. (This implementation does not work 100%, as a single unit is much faster than a line formation)
We already implemented A* path finding with a small optimisation during the semester, but it was not 100% suitable for my needs. The problem was that the basic implementation doesn't account for the size of the group. My solution for that was to crop the portals by the size of the group. This worked in cases when a group was not too large. My second approach for the problem was to offset the final path point perpendicular to the direction where the agents will come from. As you can see below, this works nice for single line formations, but not for larger groups. Althought it isn't the perfect solution, I will let this for now.
Notice that we need to use 90 degrees or -90 degrees from our direction based on the fact that the obstacle is at the left or right side. Figuring out how to deal with it took me a while. I found that when we calculate the next direction, we can compare it to the current direction and see if it turns left or right. For this purpose we can use the cross product. In our case a negative result means -90 degrees and a positive result 90 degrees. We can calculate the needed vector by using the next formula: 90 degrees rotated vector = {-vector.y,vector.x}.
I'm really happy with the results, you can view them below!
My conclusion is that this system is fun to play with and after some polishing it could be used in a real game. While making the project I found out that dot and cross products are very usefull and finally understood how to use them correctly.
If you want, you can do a follow up project based on my work. I would recommend to work on the things where I did not have time to finish:
- Correct offset when moving next to obstacles. (The path finder self could also take the formation width into account)
- Subgroups of the formation should always keep a relative position to eachother. Other also interesting features would be:
- Creating more basic shapes, for example by means of bezier-curves.
- The formations could rotate to match the moving direction.
https://www.gamedeveloper.com/programming/group-pathfinding-movement-in-rts-style-games https://marclafr.github.io/Research-Group-Movement-RTS-/ https://github.com/EezehDev/AI-Formations https://www.gamedeveloper.com/programming/coordinated-unit-movement
"projects/Movement/FormationMovement/UnitAgent.h" "projects/Movement/FormationMovement/Group.h" "projects/Movement/FormationMovement/Formation.h" "projects/Movement/SteeringBehaviors/Steering/SteeringBehaviors.h" "projects/Movement/SteeringBehaviors/CombinedSteering/CombinedSteeringBehaviors.h" "projects/Movement/SteeringBehaviors/Flocking/FlockingSteeringBehaviors.h" "projects/Movement/Pathfinding/NavMeshGraph/App_NavMeshGraph.h"