Enemy Pathfinding

Introduction

Enemy pathfinding allows enemies to navigate through complex levels. This can be used to move to a target position (such as a patrol point) or follow an entity (such as enemies chasing a player). This tutorial shows how to create a pathfinding enemy. Specifically, it covers the following topics:

  • Creating a TileNodeNetwork which defines the walkable parts of a map

  • Creating an input device which is used to control the enemy so it follows its desired path

  • Creating line-of-sight pathing for more natural movement

Creating a TileNodeNetwork

First we'll create a TileNodeNetwork. This is defined in our GameScreen, but will use the Map for each level. For a more thorough walkthrough of creating a TileNodeNetwork, see the TileNodeNetwork page.

To create the TileNodeNetwork:

  1. Select the GameScreen

  2. Click the Add Object to GameScreen under Quick Actions, or right-click on GameScreen and select Add Object

  3. Select the TileNodeNetwork type

  4. Enter a name such as WalkingNodeNetwork

  5. Click OK

Next we'll define a tile to use for pathfinding. To do this:

  1. Open any of your levels in Tiled

  2. Select the Tileset that you use for your GameplayLayer. By default this is called TiledIcons

  3. Click the wrench to edit the Tiles

  4. Select a tile that you would like to use for pathfinding

  5. Change the Class for that tile to WalkableTile

  6. Save your tileset (TSX)

Next, select your current level (such as Level1Map) and paint the WalkableTile onto the GameplayLayer. Note that if you would like to be able to walk on areas which already have other tiles, you can create a new layer specifically for Tiles.

Be sure to save both your level and the tileset.

Finally, we can indicate that the WalkableTile should be used to populate the nodes in the Tile:

  1. Select the WalkingNodeNetwork Object under GameScreen

  2. Click the TileNodeNetwork Properties

  3. Select the From Type option

  4. Select Map as the Source TMX File/Object

  5. Select WalkableTile as the Type

Optionally, you may want to also set the Visible variable to true so the TileNodeNetwork shows up in your game.

The game should now show the TileNodeNetwork. Note that you can also make the GameplayLayer invisible in Tiled so that the TileNodeNetwork is easier to see in game.

Notice that the links between nodes are either vertical or horizontal. We will discuss diagonal movement later in the tutorial.

Creating Enemy InputDevice

Now that we have a TileNodeNetwork defined, we can create an input device. Of course, we need to have an Enemy defined. For this tutorial I'll use a simple enemy with the following characteristics:

  • It is named EnemyBase - this naming convention is used so that the enemy could be used as a base Entity for derived variants. Larger games would likely need multiple enemy types so this sets up to expand easily.

  • The Enemy has a single Circle collision. More complex games may include multiple types of collision, but it's important to note which collidable object will be used as the solid collision - we'll use this for line-of-sight pathfinding later in this tutorial.

  • The enemy uses the Top-Down movement types, just like the Player.

  • The enemy's InputDevice is set to None. As indicated in the FRB Editor, this must be assigned in code or the game will crash.

Next we'll define the InputDevice. You may be familiar with the InputDevice as hardware input which can control the movement of the Player (such as the Keyboard or Xbox360GamePad). Although these are common implementations of the input device (IInputDevice interface), the concept of an InputDevice is something which can be read by an Entity (such as the Enemy) to determine how it should move.

In this case the InputDevice will not be tied to actual hardware. Instead, we will return input values which move the EnemyBase through the map by following the path obtained from the WalkingNodeNetwork.

Fortunately, the TopDownAiInput class is an InputDevice which automatically returns these movement values according to a desired path.

First, we will assign this InputDevice in the EnemyBase's CustomInitialize:

TopDownAiInput<EnemyBase> topDownAiInput;

private void CustomInitialize()
{
    topDownAiInput = new TopDownAiInput<EnemyBase>(this);

    // This helps us visualize the path the EnemyBase takes to get to
    // the player
    topDownAiInput.IsPathVisible = true;
    // Use a darker color so it stands out over the bright level tiles
    topDownAiInput.PathColor = Color.Purple;
    this.InitializeTopDownInput(topDownAiInput);
}

void CustomDestroy()
{
    // The top down input path must be made invisible so it cleans up
    // any shapes it creates in the path:
    topDownAiInput.IsPathVisible = false;     
}

Notice that the topDownAiInput is defined at class scope - this lets us access it in other methods without needing to cast the InputDevice every time. Also, the IsPathVisible and PathColor properties can be used to control the appearance of the path that the EnemyBase is going to take to get to the player. We will enable this to show the path. Also, it may be worth turning off the WalkingNodeNetwork visibility so that the EnemyBase path can be seen more clearly.

Initializing TopDownAiInput

Next, we'll create a method to set up the node network and target player. Add the following to EnemyBase.cs:

public void InitializePathfinding(Player player, TileNodeNetwork nodeNetwork)
{
    topDownAiInput.FollowingTarget = player;
    topDownAiInput.NodeNetwork = nodeNetwork;
}

For this tutorial we assume a single player which never changes. A multiplayer game may require changing the target based on which player last hit the enemy, proximity, or whether the current target is dead.

Also, note that this method must be called by the GameScreen. We will add the code to call this method later in this tutorial.

Finally, we can set the path to follow the player in CustomActivity.

// initialize it to a large negative number so the path updates immediately
double lastTimePathUpdates = -999;
// how often the path should update. We do this to improve performance
double pathUpdateFrequency = 1;
private void CustomActivity()
{
    if(TimeManager.CurrentScreenSecondsSince(lastTimePathUpdates) > pathUpdateFrequency)
    {
        lastTimePathUpdates = TimeManager.CurrentScreenTime;
        topDownAiInput.UpdatePath();
    }
    // We only call UpdatePath once every second since that doesn't need
    // to update too requently, but this should be called every frame so the
    // enemy's movement values are updated according to its path.
    topDownAiInput.DoTargetFollowingActivity();
}

Notice that this code only updates the path every second. Updating the path is a fairly quick operation, but it can be expensive if the game includes hundreds of EnemyBase instances. We'll check once per second to prepare for a larger game.

Now that our EnemyBase has the code it needs to pathfind to the player, we can add code to the GameScreen to call InitializePathfinding.

EnemyBase instances can be created both before and after GameScreen.CustomInitialize is called, so we must handle both cases.

To handle EnemyBase instances created before CustomInitialize is called (if they have been added directly to a level in the FRB Editor or live edit), we can loop thorugh EnemyBaseList and call InitializePathfinding.

To handle EnemyBaseInstances created after CustomInitialize (if they are added using a factory or variant object such as through a spawner) we can subscribe to the factory method. Note that a game which has derived enemy variants must subscribe to all derived variant factories to handle creation.

Modify the GameScreen.cs to include the following code:

void CustomInitialize()
{
    // This foreach handles enemies created before the screen's initialize.
    foreach(var enemy in EnemyBaseList)
    {
        PrepareEnemyPathfinding(enemy);
    }
    // This event handler handles enemies created after the screen's initialize.
    Factories.EnemyBaseFactory.EntitySpawned += PrepareEnemyPathfinding;
}

private void PrepareEnemyPathfinding(EnemyBase enemy)
{
    // This assumes Player1 is already created. If your game
    // creates its Player instances later, you need to make sure
    // the Player instance has already been created before this is
    // called.
    enemy.InitializePathfinding(Player1, WalkingNodeNetwork);
}

Finally, we can add the following code to GameScreen to create EnemyBase instances when clicking with the mouse.

void CustomActivity(bool firstTimeCalled)
{
    FlatRedBallServices.Game.IsMouseVisible = true;
    if(GuiManager.Cursor.PrimaryClick)
    {
        Factories.EnemyBaseFactory.CreateNew(GuiManager.Cursor.WorldPosition);
    }
}

We can now click to place EnemyBase instances. Each EnemyBase instance follows the player according to pathfinding along the WalkingNodeNetwork and the position of the Player.

Notice that the EnemyBase moves fairly quickly - the same speed as the Player. You may want to reduce the EnemyBase's movement speed to make it easier to test pathfinding.

Customizing Pathfinding Behavior

So far we can create an EnemyBase by clicking in the game. The enemy base instance follows the player using the WalkingNodeNetwork. We have lots of options for customizing the way the enemy follows the player.

First, you may nave noticed that the enemy follows the player on a path by only moving horizontally or vertically. The reason for this is because our WalkingNodeNetwork is set up to only have four links per node: up, down, left, and right. we can include diagonal nodes to allow the enemy to also move diagonally.

Some games, such as the Legend of Zelda on the NES and the 2D Final Fantasy games do not allow the player, NPC, or enemies to move diagonally. If this limitation matches your game, then you can keep this default setup.

However, if your game requires diagonal movement, you can enable it in the TileNodeNetwork properties for the WalkingNodeNetwork.

Now our EnemyBase instance can travel diagonally.

You may have noticed that at times the EnemyBase backtracks - in other words at times the enemy seems to walk backwards rather than following its path. This can happen when the path is re-evaluated. The new path requires the enemy to move backwards slightly to move to its next node.

To help explain this problem we can visualize a simple path that an enemy may take. It's important to remember that each node in the TileNodeNetwork is always placed at the center of the tile. The following image shows an example path. The blue circles represent the node positions, the red circle represents the enemy, and the purple lines represent the path the Enemy takes.