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;

private readonly float _actorSizeWithBuffer;
private readonly int _startFromAngle;
private readonly int _direction;
private readonly int _rings;
private readonly bool _breakWhenMinPointsOnSideReached;
private readonly bool _halfCircle;
private readonly bool _includeOrigin;

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) {
        var adjustedOrigin = AdjustGoal(origin);

        if (adjustedOrigin == Vector3.zero) {
            return result;
        }

        result.Add(adjustedOrigin);
    }

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

    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);
            var closest = AdjustGoal(vector);

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

            result.Add(closest);

            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):

https://github.com/mostlyunity/unit-formations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s