D20 RPG – Enemy Pathfinding

“Run Away! Run Away!” – King Arthur and His Knights, Monty Python and the Holy Grail.

Overview

Battle is feeling a lot more complete, with one last glaring issue. The monsters don’t move. In this lesson, I will update their A.I. well enough that if they can attack, they will, and otherwise they will move toward the hero. The real focus of this lesson though, is pathfinding. We now have a Giant Rat, and handling “Size” within pathfinding adds a good deal of new challenges. For example, I have to check that Entities can actually “fit” at each position they path through. Although I imagine that for the most part the player will only be controlling medium sized units (which occupy a single tile), I also want to make A.I. flexible enough that it can work with units of any size. Rather than having A.I. path to a target’s position, I would need to consider all of the spaces the target occupies.

Getting Started

Feel free to continue from where we left off, or download and use this project here. It has everything we did in the previous lesson ready to go.

Monster Action Flow

In the future I think it might be nice to have some sort of A.I. “Brain” asset that controls the strategy of what actions an Entity uses and how or when it uses them. In part these decisions can be made by the way I assemble the actions themselves (you will see a little of that in this lesson). For now, the overall “plan” of an A.I. will just be a simplified gambit system. This means that I will iterate over its list of actions and perform the first one that can be performed.

Open the MonsterActionFlow script and modify its Play method to the following:

public async UniTask<CombatResult?> Play()
{
    var current = ITurnSystem.Resolve().Current;
    ICombatSelectionIndicator.Resolve().Mark(current);
    bool didAct = false;
    foreach (var actionName in current.EncounterActions.names)
    {
        var action = await ICombatActionAssetSystem.Resolve().Load(actionName);
        if (action.CanPerform(current) && current.HitPoints > 0)
        {
            await action.Perform(current);
            didAct = true;
            break;
        }
    }

    if (!didAct)
        ITurnSystem.Resolve().TakeAction(3, false);

    return ICombatResultSystem.Resolve().CheckResult();
}

The first change I added is that I want to let the Combat Selection Indicator “Mark” the current entity. This is because the camera focuses on this indicator (even if it is invisible). While testing the ability of A.I. to move, I noticed that I would often move far away from the monsters so they could pursue me, and I wanted to be able to watch them on their turn.

Next I set up the basic gambit. I have a flag indicating whether or not I have taken an action. In the event that none of the actions activate, I can choose instead just to end the entity’s turn.

I use a foreach to loop over the EncounterActions just as I had said above. For each action, I first Load it, then verify whether or not it can be performed. Note that our temporary solution from the previous lesson remains, that keeps defeated enemies from attacking us. In the future I will probably move that check elsewhere, such as per action along with whatever other kinds of rules need to be checked. When we find an action that can be performed, we perform it, mark a flag that we have taken an action, and break out of the loop.

The result of this code based on our current setup of the “EncounterActions”, is that a monster will first try to “Bite” and then if no opponent is within range, will next attempt to “Stride” to come within range of a target.

Party Extensions

Open the PartySystem script and add the following to the interface:

Party OpposingParty(Party party);

Then add the following implementation to the class:

public Party OpposingParty(Party party)
{
    return party == Party.Hero ? Party.Monster : Party.Hero;
}

This simple method provides a quick way to return the opposite of a party. The opposing party to a hero is the monster and vice versa.

For convenience, add the following extension:

public static class PartyExtensions
{
    public static Party OpposingParty(this Party party)
    {
        return IPartySystem.Resolve().OpposingParty(party);
    }
}

Entity Filter System

I want to make some changes to the EntityFilterSystem so open its script. Our first change is a pretty small one. I want to change the signature of our method so that it uses IEnumerable rather than List so that it can work with Sets as well.

// Change from this:
List<Entity> Apply(EntityFilter filter, Entity entity, List<Entity> entities);

// To this:
List<Entity> Apply(EntityFilter filter, Entity entity, IEnumerable<Entity> entities);

Make sure to make the above change in both the interface and class.

Next, add the following to the interface:

List<Entity> Fetch(EntityFilter filter, Entity entity);

Add the implementation to the class:

public List<Entity> Fetch(EntityFilter filter, Entity entity)
{
    // Start with a set of all entities that have a size and position
    var candidates = new HashSet<Entity>(ISizeSystem.Resolve().Table.Keys);
    candidates.IntersectWith(IPositionSystem.Resolve().Table.Keys);

    // Then return a filtered list
    return Apply(filter, entity, candidates);
}

I decided it would be nice to have a simple way to find all entities that match the requirements of a given EntityFilter. I start out by grabbing the set of all Entity that have an associated “Size” and then filter it to only include the entities that also have a “Position”. I intentionally went broad like this because in the future I may want actions to look for non-combatants, such as if I want to be able to pick up an item from the ground. Finally, I “Apply” the filter to the set of entities and return the result.

For convenience, add the following to the EntityFilterExtensions:

public static List<Entity> Fetch(this EntityFilter filter, Entity entity)
{
    return IEntityFilterSystem.Resolve().Fetch(filter, entity);
}

Pathfinding

The current version of our pathfinding system is great for the hero, because I will select intelligent locations to path toward myself. The A.I. doesn’t have intelligence built-in, so when I try to tell it, “move toward this hero”, it isn’t going to just “know” which heroes are nearby or even which of its adjacent tiles is the best option to move to.

Even worse is that our current iteration of the pathfinder does not include blocked tiles in its path map, so as it is now, I can’t see a path to an opponent. The pathfinder is only built to support creatures that are the size of a single tile. Our “Giant Rat” takes up a 2×2 area, so I will need to verify that every step it takes is legal, not only at its origin, but also at each of the spaces it would occupy if it were to move there. If it can’t fit in an opening, it will have to go around.

An additional change I would like to make during this lesson is that I would like to be able to path through other units, but mark where they are. This way you can move through an ally’s space, but not stop there. In the future I may add an action such as “Tumble” which could allow you to try moving through opponent spaces, and on success rolls, have shorter paths than going around the enemies, so I like the idea that I can customize how these dynamic options are treated.

Board Highlight System

Open the BoardHighlightSystem script. Like with the EntityFilterSystem, I want to change the signature of one of our methods so that it uses IEnumerable rather than List:

// Change from this:
void Highlight(List<Point> points, Color color);

// To this:
void Highlight(IEnumerable<Point> points, Color color);

Make the type change in the interface as well as in the class.

Space System

Part of determining where pathfinding can go is to consider the dynamic locations (and spaces occupied) of all of the units on the board. Go ahead and open the SpaceSystem script. Add the following to the interface:

HashSet<Point> OccupiedSpaces(IEnumerable<Entity> entities);
void AddOccupiedSpaces(Entity entity, HashSet<Point> set);
List<Point> AdjacentSpaces(Entity entity, Entity target);

Then add the following snippets to the class:

public HashSet<Point> OccupiedSpaces(IEnumerable<Entity> entities)
{
    var result = new HashSet<Point>();
    foreach (var entity in entities)
    {
        AddOccupiedSpaces(entity, result);
    }
    return result;
}

First we have “OccupiedSpaces” which accepts a collection of Entity for which we want to return a set of all the spaces occupied by all of the entities. This method creates its own set which it will return, and appends the occupied space of each entity.

public void AddOccupiedSpaces(Entity entity, HashSet<Point> set)
{
    var tileSpace = entity.Size.ToTiles();
    for (int y = 0; y < tileSpace; ++y)
    {
        for (int x = 0; x < tileSpace; ++x)
        {
            var pos = entity.Position + new Point(x, y);
            set.Add(pos);
        }
    }
}

Next we have "AddOccupiedSpaces" which adds the occupied spaces for a single entity to the provided set.

public List<Point> AdjacentSpaces(Entity entity, Entity target)
{
    int entitySpace = ISpaceSystem.Resolve().SpaceInTiles(entity.Size);
    int targetSpace = ISpaceSystem.Resolve().SpaceInTiles(target.Size);

    int xStart = target.Position.x - entitySpace;
    int xEnd = target.Position.x + targetSpace;
    int yStart = target.Position.y - entitySpace;
    int yEnd = target.Position.y + targetSpace;

    List<Point> result = new List<Point>();
    for (int y = yStart; y <= yEnd; ++y)
    {
        for (int x = xStart; x <= xEnd; ++x)
        {
            if (x == xStart || x == xEnd || y == yStart || y == yEnd)
                result.Add(new Point(x, y));
        }
    }
    return result;
}

I also added "AdjacentSpaces" which is designed to return the locations that would allow an entity to be next to a target entity. It takes the size of both entities into account, such that a large entity would need to be further to the left of any target, or such that any entity would need to be farther to the right of a large target. I will use this to help make decisions for A.I. units.

Path Node

Open the PathNode script and add the following:

// NOTE: cases should be ordered from least to most restricted
public enum Traversal
{
    Open, // Can move through or stop here
    Pass, // Can move through but not stop here
    Block, // A point on the board, but can not move through or stop here
    OffBoard, // A point not even on the board
}

This new enum will help mark each node on the board with extra notes related to pathfinding:

  • Open - any regular tile that is unoccupied and can be moved through or stopped upon.
  • Pass - a tile which the unit could normally traverse, but which is currently occupied. While you can move through the tile, you can not end here.
  • Block - a tile which the unit can not traverse (could be because the type of terrain is incompatible, or because an opponent is there).
  • OffBoard - used to represent a point that is outside the bounds of the board.

I also added a comment to the enum indicating that my intention was to order the enum cases from least to most restricted. This will make it easier for me later on when I am doing pathfinding for large units, so that I can mark a tile based on the most restrictive tile of all of the spaces that a unit would occupy when placed at that tile.

Next, add a new field to the PathNode of our new enum type:

public Traversal traversal;

Finally, modify the constructor so that it accepts and assigns a traversal type:

public PathNode(Point point, int moveCost, bool diagonalActive, PathNode previous, Traversal traversal)
{
    this.point = point;
    this.moveCost = moveCost;
    this.diagonalActive = diagonalActive;
    this.previous = previous;
    this.traversal = traversal;
}

Land Traverser

Open the LandTraverser script. We will be making a lot of changes, so I have provided the whole script so you can just replace what was there:

using System.Collections.Generic;

public struct LandTraverser : ITraverser
{
    const int landTile = 1;
    const int hillTile = 2;

    HashSet<Point> passable;
    HashSet<Point> block;

    IBoardSystem system;

    public LandTraverser(HashSet<Point> passable, HashSet<Point> block)
    {
        this.passable = passable;
        this.block = block;
        system = IBoardSystem.Resolve();
    }

    public bool TryMove(Point fromPoint, Point toPoint, Size size, out int cost, out Traversal traversal)
    {
        if (size.ToTiles() > 1)
            traversal = SizeTraversal(size, toPoint);
        else
            traversal = SingleTraversal(toPoint);

        cost = int.MaxValue;
        if (traversal != Traversal.OffBoard)
        {
            var type = system.GetTileType(toPoint);
            cost = (type == landTile) ? 5 : 10;
            return true;
        }
        else
        {
            return false;
        }
    }

    Traversal SingleTraversal(Point point)
    {
        if (!system.IsPointOnBoard(point))
            return Traversal.OffBoard;
        if (block != null && block.Contains(point))
            return Traversal.Block;
        var type = system.GetTileType(point);
        if (!(type == landTile || type == hillTile))
            return Traversal.Block;
        if (passable != null && passable.Contains(point))
            return Traversal.Pass;
        return Traversal.Open;
    }

    Traversal SizeTraversal(Size size, Point point)
    {
        Traversal result = Traversal.Open;
        var range = size.ToTiles();
        for (int y = point.y; y < point.y + range; ++y)
        {
            for (int x = point.x; x < point.x + range; ++x)
            {
                var check = SingleTraversal(new Point(x, y));
                result = (int)check > (int)result ? check : result;
            }
        }
        return result;
    }
}

Originally this script had a HashSet marking "obstacles" on the board. I have replaced that with two new sets, one called "passable" and one called "block". The passable positions are a sort of "soft" obstacle - in that you can traverse through that point but you can't stop there. The block positions are a "hard" obstacle - because you can't move through or stop there. The constructor for the class is modified to accept these two new sets.

The TryMove method signature was updated so that you can now pass a "Size" to consider during traversal. It also has a second "out" parameter which will be filled with "Traversal" information about the attempted move. In the body of the method, we branch based on the "size" - most units will only ever fill a single tile, and so they can use the faster SingleTraversal branch. Special larger units will need to use the SizeTraversal branch. Regardless of the conditional branch chosen, we now have "traversal" information about the destination point. Assuming the point is actually on the board (and any space that could be occupied based on size), then we give the movement a cost based on the type of terrain at that point. Note that the return value is also handled slightly differently. Before, we would return true only if the terrain was something the unit could actually walk on, now, we return true for any traversal that is still on the board. This allows pathfinding to continue so A.I. can make decisions about how to approach a destination even if it can't occupy it.

The SingleTraversal method makes checks from the most restrictive traversal type to the least restrictive. So it first checks that the specified point is actually on the game board. Then it checks if the tile is blocked and so on, until it finally determines a tile is open.

The SizeTraversal method loops over all the tiles that would be occupied by an Entity of a given size if it were placed at the specified point. For each of its spaces, we call the SingleTraversal method. If the current "check" point has a traversal type with a higher value (because I sorted the Traversal enum from least to most restrictive) then I assign that value to the final "result". Therefore the most restrictive traversal of all the spaces that could be occupied is the result that is returned from this method.

Path Map

Open the PathMap script and add the following methods to the interface:

PathNode this[Point point] { get; }
bool TryGetNode(out PathNode node, Point point);
List<Point> OpenPoints(int range);
Point NearestOpen(Point point, int range);

Add the following implementations to the class:

public PathNode this[Point point]
{
    get { return map[point]; }
}

This indexer allows us to grab a PathNode from the map given a Point. Note that it should only be used in situations where you already know the map "has" a node for the specified point. If you aren't certain, then you should use the next option...

public bool TryGetNode(out PathNode node, Point point)
{
    if (map.ContainsKey(point))
    {
        node = map[point];
        return true;
    }
    node = null;
    return false;
}

I added the new TryGetNode so I could have a way to check whether or not the PathMap has data on a specified Point. Remember that points could be excluded because they may be outside the range that was provided to the pathfinding system, or because the pathfinding system will not continue FROM a blocked traversal tile (even though the blocked tile itself will be in the map).

public List<Point> OpenPoints(int range)
{
    List<Point> result = new List<Point>();
    foreach (var entry in map)
    {
        var node = entry.Value;
        if (node.traversal == Traversal.Open && node.moveCost <= range)
            result.Add(entry.Key);
    }
    return result;
}

The OpenPoints method will return every point within the map whose node has a traversal type of "Open" and whose cost is within the specified range. This will be useful when I wish to highlight tiles that our hero can "stop" on, rather than simply the tiles he can "reach" - it will let me indicate that they should not try to move to a tile occupied by another ally. It can also be useful during A.I. logic, to help filter decisions based on where the entity can go.

public Point NearestOpen(Point point, int range)
{
    var node = map[point];
    while (node.moveCost > range || node.traversal != Traversal.Open)
    {
        node = node.previous;
    }
    return node.point;
}

The NearestOpen method will return the Point that is nearest to a specified Point from the perspective of the pathfinder (rather than by linear distance). It takes into consideration an allowed range and requires that the node's traversal type be "Open". This will be useful when I wish to direct a monster "toward" something. I can do a "search" on the whole board so that it can be sure to find a hero, but then use this method to reduce the path to the range that the monster can move in a single stride action. This way even if it can't reach the hero, it can at least pursue him.

Pathfinding System

Open the PathfindingSystem script. Once again there will be a variety of small changes. They are easy, but are scattered throughout, so to make sure my intentions are clear I have once again provided the whole script. Replace the old version with the following:

using System.Collections.Generic;

public interface ITraverser
{
    bool TryMove(Point fromPoint, Point toPoint, Size size, out int cost, out Traversal traversal);
}

public interface IPathfindingSystem : IDependency<IPathfindingSystem>
{
    IPathMap Map(Point start, int range, Size size, ITraverser traverser);
}

public class PathfindingSystem : IPathfindingSystem
{
    Point[] offsets = new Point[]
    {
        new Point(0, 1),
        new Point(1, 0),
        new Point(0, -1),
        new Point(-1, 0),
        new Point(1, 1),
        new Point(1, -1),
        new Point(-1, -1),
        new Point(-1, 1)
    };

    public IPathMap Map(Point start, int range, Size size, ITraverser traverser)
    {
        List<Point> checkNow = new List<Point>();
        HashSet<Point> checkNext = new HashSet<Point>();
        Dictionary<Point, PathNode> map = new Dictionary<Point, PathNode>();
        map[start] = new PathNode(start, 0, false, null, Traversal.Open);
        checkNow.Add(start);

        while (checkNow.Count > 0)
        {
            foreach (var point in checkNow)
            {
                var node = map[point];
                foreach (var offset in offsets)
                {
                    var nextPoint = point + offset;

                    int moveCost;
                    Traversal traversal;
                    if (!traverser.TryMove(point, nextPoint, size, out moveCost, out traversal))
                        continue;

                    var isDiagonal = offset.x != 0 && offset.y != 0;
                    var diagonalPenalty = isDiagonal && node.diagonalActive;
                    var diagonalActive = isDiagonal ? !node.diagonalActive : node.diagonalActive;
                    if (diagonalPenalty)
                        moveCost += 5;

                    moveCost += node.moveCost;
                    if (moveCost > range)
                        continue;

                    if (!map.ContainsKey(nextPoint))
                    {
                        map[nextPoint] = new PathNode(nextPoint, moveCost, diagonalActive, node, traversal);
                        if (traversal != Traversal.Block)
                            checkNext.Add(nextPoint);
                    }
                    else if (moveCost < map[nextPoint].moveCost)
                    {
                        map[nextPoint].moveCost = moveCost;
                        map[nextPoint].diagonalActive = diagonalActive;
                        map[nextPoint].previous = node;
                        if (traversal != Traversal.Block)
                            checkNext.Add(nextPoint);
                    }
                }
            }

            checkNow.Clear();
            checkNow.AddRange(checkNext);
            checkNext.Clear();
        }
        return new PathMap(map);
    }
}

If you compare this version of the script with the old version, you should see that most of the changes revolve around adding support for the Size of the Entity, and to support the Traversal information that can be returned by the traverser. One bit that is important to point out, is that when adding or updating nodes, I add "Block" positions to the map, but do not allow the search to continue FROM that point. This allows me to make decisions about how to reach an opponent position, but only if I can move up to that point. If I could NEVER reach a position (such as because an Entity is too large to fit through a portion of the map) then those positions will still not make it into the path map.

Stride System

Open the StrideSystem so we can make a quick change. I only want to "Present" the action if the Entity's position actually changes:

public async UniTask Apply(StrideInfo info)
{
    // TODO: Check for act of opportunity before leaving current square
    if (info.entity.Position != info.path[info.path.Count - 1])
        await Present(info);
    Perform(info);
    // TODO: Check for act of opportunity after arriving at new square
}

Stride Presenter

Open the StridePresenter for a couple more fixes. I want the camera to follow entities during their stride action, and an easy way to do that is to move the combat selection indicator at each step of the path. In addition, I want to update the combatant view so that the layer is sorted based on the y-axis (so that units toward the bottom of the screen render on top of units further up the screen). Swap the body of the "for loop" inside the Present method with the following:

var next = info.path[i];
ICombatSelectionIndicator.Resolve().SetPosition(next);
await view.transform.MoveTo(next, moveSpeed).Play();
ICombatantViewSystem.Resolve().SetLayerOrder(combatant, next.y);
previous = next;

Stride

Once again I will be making multiple additions and changes, this time for the Stride script. Replace the contents of that script with the following:

using UnityEngine;
using Cysharp.Threading.Tasks;

public interface IStridePositionSelector
{
    Point SelectPosition(Entity entity, IPathMap map);
}

public class Stride : MonoBehaviour, ICombatAction
{
    [SerializeField] EntityFilter passFilter;
    [SerializeField] EntityFilter blockFilter;

    public bool CanPerform(Entity entity)
    {
        return true;
    }

    public async UniTask Perform(Entity entity)
    {
        var pass = ISpaceSystem.Resolve().OccupiedSpaces(passFilter.Fetch(entity));
        var block = ISpaceSystem.Resolve().OccupiedSpaces(blockFilter.Fetch(entity));
        var traverser = new LandTraverser(pass, block);
        var range = entity.Party == Party.Hero ? entity.Speed : int.MaxValue;

        var map = IPathfindingSystem.Resolve().Map(
            entity.Position,
            range,
            entity.Size,
            traverser);

        Point position;
        if (entity.Party == Party.Hero)
            position = await UserSelection(entity, map);
        else
            position = ComputerSelection(entity, map);

        var info = new StrideInfo
        {
            entity = entity,
            path = map.GetPathToPoint(position)
        };

        await IStrideSystem.Resolve().Apply(info);
    }

    async UniTask<Point> UserSelection(Entity entity, IPathMap map)
    {
        var openPoints = map.OpenPoints(entity.Speed);
        IBoardHighlightSystem.Resolve().Highlight(
            openPoints,
            new Color(0, 1, 1, 0.5f));

        Point position;
        while (true)
        {
            position = await IPositionSelectionSystem.Resolve().Select(entity.Position);
            if (openPoints.Contains(position))
                break;
        }
        
        IBoardHighlightSystem.Resolve().ClearHighlights();
        return position;
    }

    Point ComputerSelection(Entity entity, IPathMap map)
    {
        var selector = GetComponent<IStridePositionSelector>();
        if (selector != null)
            return selector.SelectPosition(entity, map);
        return entity.Position;
    }
}

Our first change was to add a new interface, IStridePositionSelector. This will come into play for A.I. units as the logic about what position should be selected after the Stride action has been chosen. It can be based on any kind of "motivation" such as to pursue, flee, wander, etc. In practice it will be implemented as another Monobehaviour component attached to the same asset that Stride is attached to, which will make it easy to compose a large variety of behaviors in the inspector.

Next, I added two new fields to the Stride class. We use an EntityFilter to indicate what kinds of entities can be moved through ("passFilter"), and what kinds of entities can not be moved through ("blockFilter"). You will see these used at the beginning of the Perform method, where we "fetch" entities for each and then get the occupied spaces for the result. Finally we pass the sets of "pass" and "block" positions to the Traverser so that it can handle them.

Next, when creating our PathMap, I will use a different "range" depending on whether the Entity is player controlled or A.I. controlled. For the A.I. I want information about the "whole" (reachable) board with which to make decisions, whereas for the player, I merely need to highlight reachable tiles and they can make their own decisions on where to go.

We once again branch depending on who is controlling the entity - UserSelection for human controlled entities and ComputerSelection for A.I. controlled entities.

The UserSelection highlights the reachable tiles, like it did before, except this time it uses the new "OpenPoints" method from our PathMap. Then we await a selected tile position from the position selection system. I put this inside a "while loop" so that it would be necessary to select from one of the "Open" positions, thus serving as a validator for the player's choice.

The ComputerSelection method will attempt to get a component off of the same GameObject that is of type IStridePositionSelector. If found, it will use that component to pick a move target from the PathMap. As a fallback, I just return the entity's current position - it won't move anywhere. You might prefer a different fallback behavior, but generally speaking my expectation is that there WILL be a selector component on any stride action asset.

Move To Nearest Target

Now we will create our first implementation of the new IStridePositionSelector interface. This goal of this selector is simple - it will try and move the A.I. to the nearest of a specified type of target. We will be targeting opponents.

Create a new script at Scripts -> Combat -> Actions named MoveToNearestTarget and add the following:

using UnityEngine;
using System.Collections.Generic;

public class MoveToNearestTarget : MonoBehaviour, IStridePositionSelector
{
    [SerializeField] EntityFilter filter;

    public Point SelectPosition(Entity entity, IPathMap map)
    {
        // Step 1: Fetch a list of all valid targets
        var targets = filter.Fetch(entity);

        // Step 2: Grab the adjacent tiles for each target
        var adjacentSpaces = new HashSet<Point>();
        foreach (var target in targets)
        {
            var spaces = ISpaceSystem.Resolve().AdjacentSpaces(entity, target);
            adjacentSpaces.UnionWith(spaces);
        }

        // Step 3: Filter the tiles to only include "open" positions
        var positions = new HashSet<Point>(adjacentSpaces);
        var openPositions = map.OpenPoints(int.MaxValue);
        positions.IntersectWith(openPositions);

        // Step 4: If none of the adjacent positions are "open"
        // fallback to any "known" position
        if (positions.Count == 0)
        {
            positions.UnionWith(adjacentSpaces);
            positions.IntersectWith(map.AllPoints());
        }

        // Step 5: Pick the nearest position
        var bestPosition = entity.Position;
        var bestCost = int.MaxValue;
        foreach (var position in positions)
        {
            var cost = map[position].moveCost;
            if (cost < bestCost)
            {
                bestPosition = position;
                bestCost = cost;
            }
        }

        // Step 6: Return a tile within range of the entity's speed
        var destination = map.NearestOpen(bestPosition, entity.Speed);
        return destination;
    }
}

The script is already mostly self-documented thanks to the comments. I don't use comments that often, but when I have a long-ish method like this, I think it helps break it up into understandable sections. Sometimes I would move those bits into a well-named method (even though I am not reusing the logic) as another way to make the code easier to read. Either way is fine.

The general strategy of this script is to first grab a list of all of the valid target entities, then grab adjacent tile locations to each of the targets. If there is an "open" position near a target, then we would want to path toward it. Otherwise, as a fallback, we will use any position that is found within the path-map as a fallback. Regardless of if we are using "open" or "known" positions, we will pick the nearest (by moveCost). This is our "Goal" position, but it is still possible that the Entity can't reach the "Goal" with a single Stride Action, therefore we use the "NearestOpen" method to "clamp" our choice to a position that is within range of the Entity's movement speed. This also is necessary in an event where the position was within range of the Entity's speed, but there were not adjacent open spaces.

I actually made several versions of this script before settling on the one you see here. I originally had something simpler, where I simply looped over the list of targets, and picked the nearest by moveCost, then returned a "NearestOpen" position. There are two main reasons I abandoned the simple version:

  1. It did not take into account that a target could occupy more than one space
  2. If another monster was already adjacent to the target, and was in the most direct path to the target, then another monster following the path would stop behind the first monster, rather than continue moving up to another open spot.

Stride Asset

Open the asset at Assets -> Objects -> CombatAction -> Stride. On the Stride script component assign the following:

  • Pass Filter: Ally
  • Block Filter: Living, Opponent

Attach the MoveToNearestTarget script to the asset, and configure its "Filter" to use "Living, Opponent". Save the project.

Demo

Great job on making it this far! Now would be a great time to play the game. Notice that you can no longer move through the opponent's spaces. Try moving out of range of the rats and watch them chase you. If they come within range, they will attack. Feel free to experiment by changing the board to make areas where the Giant Rat can't go, or by seeing if you can get them to move through each others space.

Summary

In this lesson we created a simple gambit setup for computer controlled entities so that they could both move and attack. We refactored and added code so that we could let the A.I. use pathfinding to make choices about where to go. We also added some new pathfinding features like support for larger units and the ability to move through ally spaces.

If you got stuck along the way, feel free to download the finished project for this lesson here.

If you find value in my blog, you can support its continued development by becoming my patron. Visit my Patreon page here. Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *