Advanced Pathfinding

In Rifle Storm I had to solve pathfinding problems like jumping, avoiding enemies, and allowing movement through friendlies. I want to share my unique solution.

Finding a path from one tile to an other in a tile-based game is easy. It's been solved before via the A* pathfinding algorithm. However, what if:

• There are obstacles in the way.
• These obstacles can move or some times can be ignored.
• It's also possible for a character not have enough jump to reach higher tiles.

By the way I originally got this jump idea from Final Fantasy Tactics.

A Simple Pathfind

Path finds in Rifle Storm typically look like this:

// MoveStrategy.cs

// setup pathfinding
pathProps.MoveCheck(currentEntity, currentEntity.iso.tile, targetPos, ignoreWalls);

path = pathFind.Search(pathProps);

// Assert.IsNotNull(path, "Path not found " + pathProps.startPos + " " + pathProps.endPos);

if (path == null) {
    moveSignal.pathLength = 0;
    Finish();
    return;
}

// currently on this tile, so skip it
path.RemoveFromBack();

moveSignal.pathLength = path.Count;
_signalBus.Fire(new EntityStartMoveSignal(){entity=currentEntity});

SetNextTarget();

pathProps is an instance object which holds all the configuration for the type of pathfind I want to search for. Keeping it contained in this class allows me to keep the pathfinding checks centralized. Move on this later.

After that the path find algorithm is ran and either a path is found or it can fail and return null.

From there on the found path with be followed.

Let's dig into the MoveCheck method and see how it found this path.

Is This Tile Walkable?

The MoveCheck method looks like this:

// TileSearchProps.cs

public void MoveCheck(IEntity currentEntity, Vector2 startPos, Vector2 endPos, bool ignoreWalls = false) {
    Reset();

    costLimit = currentEntity.equip.JumpLimit;
    this.pathLimit = 0;
    this.startPos = startPos;
    this.endPos = endPos;

    bool moveThroughEnemies = currentEntity.HasGadget(GadgetType.BarbedWire);

    OnCheck = (tile, par) => {
        if (ignoreWalls) {
            if (tile == endPos) {
                // allow final tile to have an entity
                // because not stopping there (see dialogue)
                return tileUtil.IsWalkable(tile, (e) => true);
            }

            // avoid all entities in path to prevent stopping on one
            return tileUtil.IsWalkable(tile, (e) => e == currentEntity);
        }

        if (tile == endPos) {
            // ensure final tile is free from any entity
            return tileUtil.IsWalkable(tile);
        }

        return tileUtil.IsWalkable(tile, (en) => en.IsTeammate(currentEntity) || en.IsDead || moveThroughEnemies);
    };

    OnCost = (pos, par) => {
        if (ignoreWalls) return 0;
        if (par.x == -1) return 0;

        int cost = tileUtil.JumpCost(pos, par);

        if (currentEntity.equip.HasVal(Stat.UnlimitedJump)) return 0;

        return tileUtil.JumpCost(pos, par);
    };
}

It will first Reset() it's state and set all the needed values, pathLimit, start position, end position etc. It will also set two methods OnCheck and OnCost.

OnCheck

• Get's called for every tile scanned.
• If true is returned it's an acceptable tile to move through, if not false.
• tile is the tile position.
• par is the position of the parent tile (the direction the path is being created from).

OnCost

• Get's called for every tile scanned.
• A number must be returned back to determine the travel cost of moving there.
• pos is the tile position.
• par is the position of the parent tile (the direction the path is being created from).

Avoiding Obstacles

So how are enemies avoided? What if an enemy is in front of my soldier? I don't want him to run through him like he's a ghost. He needs to move around him.

The magic code is here:

OnCheck = (tile, par) => {
    if (tile == endPos) {
        // ensure final tile is free from any entity
        return tileUtil.IsWalkable(tile);
    }

    return tileUtil.IsWalkable(tile, (en) => en.IsTeammate(currentEntity) || en.IsDead || moveThroughEnemies);
};

A method tileUtil.IsWalkable is called and returns a true or false if the tile can be walked on. As well it takes a Predicate. Let's show that method.

// TileUtil.cs

public bool IsWalkable(Vector2 tile, Predicate<IEntity> method = null) {
    IEntity entity = teamList.FindEntityAt(tile);

    if (method == null) {
        if (entity != null) {
            return false;
        }
    } else if (entity != null && !method(entity)) {
        return false;
    }

    if (!tileMap.IsWalkable(tile.x, tile.y)) return false;

    return true;
}

This method handles a few cases:

• If a method was given and there is an entity occupying it and the method returned false, therefore the tile is not walkable.
• If no method was given and there is an entity occupying it, then technically the tile is not walkable by an other entity.
• Lastly, if the tileMap has an unwalkable tile, then it's not walkable.

Avoiding Enemies And Moving Through Friendlies

How is this used to avoid enemies? Let's look again at the OnCheck method.

return tileUtil.IsWalkable(tile, (en) => en.IsTeammate(currentEntity) || en.IsDead || moveThroughEnemies);

The logic runs like so:

• Is the tile walkable? Continue, else ignore it.
• Does it also have an entity?
• Is this entity a teammate? Can pass through, else ignore it.
• Is this entity an enemy and it's dead? Can pass through.
• Is this entity an enemy that's not dead? Ignore it.

Can I Jump This High?

To determine if a soldier can jump to a higher tile (like a building) or a lower tile (like jumping down a cliff), this OnCost does all the work.

costLimit = currentEntity.equip.JumpLimit; // (int)(TileUtil.jumpStep * JumpRange);

OnCost = (pos, par) => {
    if (ignoreWalls) return 0;
    if (par.x == -1) return 0;

    if (currentEntity.equip.HasVal(Stat.UnlimitedJump)) return 0;

    return tileUtil.JumpCost(pos, par);
};
}

First it needs to know how high the entity can jump, this is the costLimit. Once this is reached the entity can't jump any higher and any path with higher tiles will get ignored.

Next as each tile in the path is walked through, the OnCost method is called and whatever value it returns will get reduced from the original cost limit.

Calculating The Cost

The cost for jumping is as such:

public int JumpCost(Vector2 pos, Vector2 par) {
    float heightDiff = tileMap.GetHeight(pos) - tileMap.GetHeight(par);

    // limit reached
    if (heightDiff < -maxJumpDown) {
        return -1;
    }

    // jumping down is free
    if (heightDiff < 0) return 0;

    return (int)heightDiff;
}

It compares the height of the current tile and the wanted to reach tile. It will then return a value for how much it'll cost to reach. I decided jumping down shouldn't cost anything.

Conclusion

This is how I did pathfinding in Rifle Storm. Feel free to use this in your own games. Here is one of my favourite sites to get more info.