# RPG – like formation algorithm

Well, it’s about time I wrote something Unity-related, eh? This time, from the depths of my disk, I’m pulling out a thing called a formation algorithm. For the sake of simplicity it’s designed for a team of three characters. Ok, you got me – for the sake of simplicity and also because that’s how I’m doing it in my amateur project π

To let you visualize what I mean and how it works: the player has a team of three game characters. Skullkrusherr is the main guy here, Bonebreaker is the guy to his left and Gravedancer is the one to his right. When the player clicks on the plane, we want to move our team, so that its “shape” looks like the image below:

In other words, when the team is requested to move anywhere on the plane, the formation shape should be preserved, or at least mostly preserved (mostly, because sometimes the move position is too close to a wall; in this case some team members are able to move according to the calculations, but one of them needs to have their goal adjusted). Maybe some of you have already come up with an idea on how to do it? If you’re thinking about some circle calculations, then you are on the right track. I’ll start by describing the algorithm class starting from its constructor and field declarations

``````private const int DefaultRingsCount = 3;
private const int BufferMultiplier = 3;

public CircularFormation(
float actorSize,
int startFromAngle,
FormationDirection direction,
bool breakWhenMinPointsOnSideReached,
bool halfCircle,
bool includeOrigin) {

_actorSizeWithBuffer = actorSize * BufferMultiplier;
_startFromAngle = startFromAngle;
_direction = (int)direction;
_rings = DefaultRingsCount;
_breakWhenMinPointsOnSideReached = breakWhenMinPointsOnSideReached;
_halfCircle = halfCircle;
_includeOrigin = includeOrigin;
}
``````

Starting from the top:

1. `DefaultRingsCount` constant tells the rest of the code how many rings of moves it should calculate before giving up. We need it in case the player clicks on a tight spot – like a small cave passage.
2. `BufferMultiplier`, `_actorSizeWithBuffer` – these two work together and that becomes more obvious when you look at the constructor. There, the `_actorSizeWithBuffer` field is set. It is what the name claims that it is – I wanted to have some buffers around my characters, so the field’s value is just a simple equation that says “multiply the given agent size by the value of `BufferMultiplier`“.
3. `_startFromAngle`– this one makes sense only if you set the `halfCircle` flag to `true`. In short, if I ever come up with the idea that the formation should be rotated, then that’s how I’ll tell the algorithm what the desired rotation is.
4. `_direction` – in my project, I have two formation directions – forward and backward. I guess it could be passed as an integer or even a boolean value as well , but I think having the constructor parameter as enum, makes it a bit more understandable, because you know you’re passing the backwards direction and not just a magical -1 or 1. But you already know that, I hope π
5. `_rings` – looks useless, right? It’s not, because there’s one more constructor not setting it to the default value. I’m omitting it here for the sake of brevity.
6. `_breakWhenMinPointsOnSideReached` – you can tell the algorithm, that it should stop its calculations on a given “side” (we’ll get back to that) when it reaches a certain threshold.
7. `_halfCircle` – in the case of a bigger team, we may want to have a full circle, in which case you could imagine two more dots under the image above.
8. `_includeOrigin` – this flag simply tells the algorithm whether or not it should include the point that is the origin of the calculation (the main character position).

Now we can start going into the core of the logic starting with the `CalculateMoves` method presented below:

``````public IReadOnlyList<Vector3> CalculateMoves(Vector3 goal, Vector3 currentPosition, int minPointsOnSideOrQuarter) {
var relativePos = goal - currentPosition;
var localRotation = Quaternion.LookRotation(relativePos);
var vectors = CalculateMoveVectors(goal, localRotation, _startFromAngle, minPointsOnSideOrQuarter);

return vectors;
}``````

Three things are calculated here: first the move direction, then the rotation which has to be made by the team in order to face the goal (the place on the plane where the user has clicked) and then the movement vectors:

``````private IReadOnlyList<Vector3> CalculateMoveVectors(Vector3 origin, Quaternion localRotation, int startFromDegree, int minPointsOnSideOrQuarter) {
var leftDegrees = Range(startFromDegree, _halfCircle ? 10 : 20, 10 * _direction);
var rightDegrees = Range(-startFromDegree, _halfCircle ? 10 : 20, -10 * _direction);
var leftPoints = FindPoints(origin, localRotation, leftDegrees, minPointsOnSideOrQuarter);
var rightPoints = FindPoints(origin, localRotation, rightDegrees, minPointsOnSideOrQuarter);
var result = new List<Vector3>();
var longerList = leftPoints.Count > rightPoints.Count ? leftPoints : rightPoints;

if (_includeOrigin) {

return result;
}

}

for (var i = 0; i < longerList.Count; i++) {
if (i < leftPoints.Count) {
}
if (i < rightPoints.Count) {
}
}

return result;
}``````

The `Range` method (not present here because it’s so simple, I will put it into the github repo) produces a range of degrees to be used by the `FindPoints` method underneath. This means that for example if I only want to have two degrees on each side (which would result in a tight “movement cone”), I give it a value of 2 in each call. It’s called two times in case the user wants to do a `_halfCircle`. In the case of a full circle, those two ranges are the same. The rest of the method is easily understandable on its own, so let’s `FindPoints` !

``````private List<Vector3> FindPoints(Vector3 origin, Quaternion localRotation, IEnumerable<int> degrees, int pointsCount) {
var result = new List<Vector3>();

for (var i = 0; i < _rings; i++) {
foreach (var degree in degrees) {
var vector = MoveVector(origin, localRotation, degree, i + 1);

if (closest == Vector3.zero) {
continue;
}

if (result.Count >= pointsCount && _breakWhenMinPointsOnSideReached) {
break;
}
}
}

return result;
}``````

When iterating over each given movement ring, this method also goes through all the degrees calculated before. In the inner loop, the `MoveVector` method will create (to no one’s surprise) a movement vector! π The `AdjustGoal` method is used to check if the calculated vector is reachable and if not, it’s moved around so that it is. If it can’t be adjusted, the returned value is equal to `Vector3.zero` and ignored.

The last two methods are the ones mentioned in the previous paragraph. Starting from the most important one, declaration below:

``````private Vector3 MoveVector(Vector3 origin, Quaternion localRotation, int degree, int ring) {
var teamRotation = Quaternion.AngleAxis(degree, Vector3.up) * localRotation;
var nextPoint = origin + new Vector3(0, 0, _actorSizeWithBuffer * ring);
var direction = nextPoint - origin;
var rotatedDirection = teamRotation * direction;
var movedVector = rotatedDirection + origin;

return movedVector;
}``````

Now, I have to remind you of one fact here. Have you been to the “about me” section? That’s where I tell you that I’m not a pro when it comes to Unity programming, which also involves quaternion math, so my explanation of this specific bit of code may sound kind of amateurish π The reason for that is the fact that I can’t remember the moment when I came up with the idea of it, which tells me I got it from somewhere, either in this form, or I had to tweak it a little.

The `teamRotation` variable contains a rotation the team needs to make to face any point on a virtual line along the directional vector going from the team’s origin into the infinite. The calculation you see in the first line of the described method is saying basically “adjust the team rotation calculated previously for the new origin with an absolute rotation of `degree` degrees”. The bold part here refers to the `LookRotation` that was calculated in the first method discussed in this post (apart from the constructor) – it was the “rotation needed to be made by the team in order to face the goal”. In essence we had a rotation that had to be made to face the place that was clicked, but now we are adjusting it, so that it moves X degrees to a given side.

Next, the code calculates an initial move vector. It does so by adding `Z` units to the origin (moves the origin forward). Then, the `teamRotation` calculated above is applied to the direction vector (remember, at this point the direction vector is pointing from the origin to the spot clicked by the player, not the place we need to move to). Having the `rotatedDirection` calculated, the only thing left to do here is to create the actual `movedVector`, which means one of the candidate vectors the algorithm may direct the player characters to go to.

Finally, we get to the `AdjustGoal` method. It’s much more straightforward and easier on the eye, than the previous one was π

``````public Vector3 AdjustGoal(Vector3 point) {
if (NavMesh.SamplePosition(point, out NavMeshHit hit, _actorSizeWithBuffer, NavMesh.AllAreas)) {
return hit.position;
}

return Vector3.zero;
}``````

Its goal is to consult the Unity `NavMesh` if the calculated position is actually present on the `NavMesh` if it’s not, it tries to adjust it by `_actorSizeWithBuffer` and returns zero if the sampling was unsuccessful.

Whew, that was a lot for me! Anyway, you can find the code on github, as always (and please let me know if you found out an easier way of doing what I’m trying to do here):