How To Implement A* Pathfinding with Swift

Update 8/3/15: In iOS 9, Apple introduces a new GameplayKit that includes a pathfinding API. This tutorial does not cover that; it covers a way to add pathfinding without GameplayKit.

Note: This tutorial was update to Swift and Sprite Kit by Gabriel Hauber. The original Cocos2D tutorial was written by Johann Fradj.

In this tutorial, you’ll learn how to add the A* Pathfinding algorithm into a simple Sprite Kit game. A* lets you calculate a navigable path between two points, and is especially useful for 2D tile-based games such as CatMaze, which you’ll work on in this tutorial.

If you’re not familiar with the A* algorithm itself, you should read Introduction to A* Pathfinding first for all the details on how it works. This tutorial will cover the implementation of the algorithm into an existing Sprite Kit game.

To go through this tutorial, it’s helpful if you have prior knowledge of the Sprite Kit framework on iOS or OS X. If you need a refresher there, check out our Sprite Kit Tutorials to take you all the way from core concepts to complete games!

Find the shortest path to your keyboard, and begin! :]

Getting Started

Start by downloading the starter project. It’s a simple Sprite Kit based game configured with both iOS and OS X targets. Build and run the project for your platform of choice. If you run the OS X version, you should see the following:

Cat Maze: A simple tile-based Sprite Kit game for iOS and OS X

Cat Maze: A simple tile-based Sprite Kit game for iOS and OS X

In this game, you take the role of a cat thief trying to make your way through a dungeon guarded by dangerous dogs. If you try to walk through a dog they will eat you – unless you can bribe them with a bone! You need to traverse the dungeon in the correct order so you have enough bones when you need them to get through a dog blocking your way as you make your way to the exit.

Note that the cat can only move vertically or horizontally (not diagonally), and will move from one tile center to another. Each tile can be either walkable or unwalkable.

Try out the game, and see if you can reach the exit! When you tap or click somewhere on the map, the cat will jump to an adjacent tile in the direction of your tap. (On the OS X version you can also use the cursor keys to move around).

Cat Maze and A* Overview

In this tutorial you will modify this so that the cat will automatically move all the way to the tile you tapped using the most efficient route, much like many RPGs or point-and-click adventure games.

Open Cat.swift and take a look at the implementation of moveToward(_:). You will see that it calls moveInDirection(_:) with a direction based on the cat’s current position and the target position.

You will change this so that instead of moving one tile at a time, the cat will find the shortest path to the target, and make its way along that path.

First, replace the moveToward(_:) implementation with the following:

func moveToward(target: CGPoint) {
  let toTileCoord = gameScene.tileMap.tileCoordForPosition(target)
  moveTo(toTileCoord)
}

Build and run the game now and make a move; the cat will teleport to the selected location. Well, that’s the end result you’re looking for so congratulations! ;]

The actual move algorithm is in moveTo(_:), which is where you’ll to calculate the shortest path using the A* algorithm, and make the cat follow it.

A Reusable Pathfinder

The A* pathfinding algorithm is the same whether it is finding the best path for a cat in a maze full of dogs, or for a warrior in a dungeon full of monsters. Because of this, the pathfinder you create in this tutorial will be reusable in other projects.

The pathfinding algorithm is going to need to know the following pieces of information from the game:

• Given a map location, what map locations next to it are valid locations to move to?
• What is the movement cost between two map locations?

In the project navigator, right-click on the Shared group, and select New File…. Choose the iOS\Source\Swift File template and click Next. Name the file AStarPathfinder and select the Shared directory as the location in which to create the file. Ensure both CatMaze and CatMaze Mac targets are selected and click Create.

Add the following code to the file you just created:

protocol PathfinderDataSource: NSObjectProtocol {
  func walkableAdjacentTilesCoordsForTileCoord(tileCoord: TileCoord) -> [TileCoord]
  func costToMoveFromTileCoord(fromTileCoord: TileCoord, toAdjacentTileCoord toTileCoord: TileCoord) -> Int
}

/** A pathfinder based on the A* algorithm to find the shortest path between two locations */
class AStarPathfinder {
  weak var dataSource: PathfinderDataSource?

  func shortestPathFromTileCoord(fromTileCoord: TileCoord, toTileCoord: TileCoord) -> [TileCoord]? {
    // placeholder: move immediately to the destination coordinate
    return [toTileCoord]
  }
}

The PathfinderDataSource protocol describes the two requirements listed above: available (walkable) adjacent tiles, and the movement cost. This will be used by the AStarPathfinder, which you’ll fill out with the algorithm later.

Setting up the Game to Use the Pathfinder

In order to use the pathfinder, the Cat object will need to create an instance of it. But what is a good candidate for the pathfinder’s data source?

You have two choices:

1. The GameScene class. It knows about the map, and so is a candidate for supplying information such as movement costs and what tiles are walkable, and so on.
2. The Cat class, but why would you choose this? Imagine a game which has multiple moveable character types, each of which has its own rules as to what is a walkable tile and movement costs. For example, a Ghost character may be able to move through walls, but it costs more to do so.

Because you are such a fan of good design, you choose the second option :]

Open Cat.swift and add the following class extension to the bottom of the file so it conforms to PathfinderDataSource:

extension Cat: PathfinderDataSource {
  func walkableAdjacentTilesCoordsForTileCoord(tileCoord: TileCoord) -> [TileCoord] {
    let adjacentTiles = [tileCoord.top, tileCoord.left, tileCoord.bottom, tileCoord.right]
    return adjacentTiles.filter { self.gameScene.isWalkableTileForTileCoord($0) }
  }

  func costToMoveFromTileCoord(fromTileCoord: TileCoord, toAdjacentTileCoord toTileCoord: TileCoord) -> Int {
    return 1
  }
}

As you can see, finding the adjacent tiles is really simple: create an array with the tile coordinates around the given tile coordinate, then filter the array to return only walkable tiles.

Because you can’t move diagonally and because terrain is just walkable or unwalkable the cost is always the same. In your other apps, perhaps diagonal movement costs more or there are different terrain types such as swamps, hills, etc.

Now that you’ve implemented the pathfinder’s data source, it’s time to create a pathfinder instance. Add the following properties to the Cat class:

let pathfinder = AStarPathfinder()
var shortestPath: [TileCoord]?

In the initializer, set up the cat as the pathfinder’s data source immediately after the call to super.init():

pathfinder.dataSource = self

In moveTo(_:), find the two lines of code that update the cat’s position and state:

position = gameScene.tileMap.positionForTileCoord(toTileCoord)
updateState()

Replace those two lines with the following:

shortestPath = pathfinder.shortestPathFromTileCoord(fromTileCoord, toTileCoord: toTileCoord)

Once you fill out the pathfinding algorithm, this property will store the list of steps needed to get from point A to point B.