How To Implement A* Pathfinding with Swift

Getting the Cat on the Path

The last thing to do is to go through the shortestPath array and animate the cat to follow the path.

Add the following method to the Cat class:

func popStepAndAnimate() {
  if shortestPath == nil || shortestPath!.isEmpty {
    // done moving, so stop animating and reset to "rest" state (facing down)
    removeActionForKey("catWalk")
    texture = SKTexture(imageNamed: "CatDown1")
    return
  }

  // get the next step to move to and remove it from the shortestPath
  let nextTileCoord = shortestPath!.removeAtIndex(0)
  println(nextTileCoord)
  // determine the direction the cat is facing in order to animate it appropriately
  let currentTileCoord = gameScene.tileMap.tileCoordForPosition(position)

  // make sure the cat is facing in the right direction for its movement
  let diff = nextTileCoord - currentTileCoord
  if abs(diff.col) > abs(diff.row) {
    if diff.col > 0 {
      runAnimation(facingRightAnimation, withKey: "catWalk")
    } else {
      runAnimation(facingLeftAnimation, withKey: "catWalk")
    }
  } else {
    if diff.row > 0 {
      runAnimation(facingForwardAnimation, withKey: "catWalk")
    } else {
      runAnimation(facingBackAnimation, withKey: "catWalk")
    }
  }

  runAction(SKAction.moveTo(gameScene.tileMap.positionForTileCoord(nextTileCoord), duration: 0.4), completion: {
    let gameOver = self.updateState()
    if !gameOver {
      self.popStepAndAnimate()
    }
  })
}

This method pops one step off the array and animates the movement of the cat to that position. The cat has a walking animation too, so the method will start and stop that as appropriate in addition to ensuring the cat is facing in the correct direction.

At the end of the method inside the runAction(_:duration:completion:) call, you need to update the game's state to check for dogs, bones, etc. and then schedule another call to popStepAndAnimate() if there's another step along the path.

Finally, change the code in moveToward(_:) to call popStepAndAnimate() instead of printing out the steps:

if let shortestPath = shortestPath {
  popStepAndAnimate()
}

Build and run, and. . .

The cat automatically moves to the final destination that you touch, collects bones and vanquishes menacing dogs! :]

Note: As you play the game, you'll see that if you select a new location before it has reached the previous one, the cat moves strangely. That's because the current movement path is interrupted and another one started. Since this tutorial isn't focused on gameplay, we'll gloss over this for now although the final project download at the end of this tutorial has this issue fixed – in Cat.swift look for references to currentStepAction and pendingMove.

Congratulations! You have now implemented A* pathfinding in a simple Sprite Kit game from scratch! :]

Bonus: Diagonal Movement

What if you also want to let the cat move diagonally?

You just have to update two functions:

• walkableAdjacentTilesCoordForTileCoord(_:): include the diagonal tiles as well.
• costToMoveFromTileCoord(_:toAdjacentTileCoord:): calculate an appropriate movement cost for diagonal movement.

You might wonder how you should compute the cost for diagonal movement. This is actually quite easy with some simple math!

The cat is moving from the center of a tile to another, and because the tiles are squares, A, B and C form a right-angled triangle as in the diagram below:

According to the Pythagorean Theorem, C² = A² + B², so:

C = √(A² + B²)
with A = B = 1 (The movement cost to move from a square to another = G cost)
C = √(2)
C ≈ 1.41

So the cost to move diagonally is 1.41. In comparison, moving left then up costs 2, so diagonal movement is clearly better!

Now, computing with integers is more efficient than floats, so instead of using floats to represent the cost of a diagonal move, you can simply multiply the costs by 10 and round them. So horizontal and vertical moves will cost 10, and diagonal moves 14.

Time to try this out! First replace costToMoveFromTileCoord(_:toAdjacentTileCoord:) in Cat.swift:

func costToMoveFromTileCoord(fromTileCoord: TileCoord, toAdjacentTileCoord toTileCoord: TileCoord) -> Int {
  return (fromTileCoord.col != toTileCoord.col) && (fromTileCoord.row != toTileCoord.row) ? 14 : 10
}

In order to add the diagonals to the walkable adjacent tiles, first add some new helper properties to the TileCoord class in TileMap.swift:

/** coordinate top-left of self */
var topLeft: TileCoord {
  return TileCoord(col: col - 1, row: row - 1)
}
/** coordinate top-right of self */
var topRight: TileCoord {
  return TileCoord(col: col + 1, row: row - 1)
}
/** coordinate bottom-left of self */
var bottomLeft: TileCoord {
  return TileCoord(col: col - 1, row: row + 1)
}
/** coordinate bottom-right of self */
var bottomRight: TileCoord {
  return TileCoord(col: col + 1, row: row + 1)
}

Back in Cat.swift, modify walkableAdjacentTilesForTileCoord(_:) to return the diagonally adjacent squares:

func walkableAdjacentTilesCoordsForTileCoord(tileCoord: TileCoord) -> [TileCoord] {
  var canMoveUp = gameScene.isWalkableTileForTileCoord(tileCoord.top)
  var canMoveLeft = gameScene.isWalkableTileForTileCoord(tileCoord.left)
  var canMoveDown = gameScene.isWalkableTileForTileCoord(tileCoord.bottom)
  var canMoveRight = gameScene.isWalkableTileForTileCoord(tileCoord.right)

  var walkableCoords = [TileCoord]()

  if canMoveUp {
    walkableCoords.append(tileCoord.top)
  }
  if canMoveLeft {
    walkableCoords.append(tileCoord.left)
  }
  if canMoveDown {
    walkableCoords.append(tileCoord.bottom)
  }
  if canMoveRight {
    walkableCoords.append(tileCoord.right)
  }

  // now the diagonals
  if canMoveUp && canMoveLeft && gameScene.isWalkableTileForTileCoord(tileCoord.topLeft) {
    walkableCoords.append(tileCoord.topLeft)
  }
  if canMoveDown && canMoveLeft && gameScene.isWalkableTileForTileCoord(tileCoord.bottomLeft) {
    walkableCoords.append(tileCoord.bottomLeft)
  }
  if canMoveUp && canMoveRight && gameScene.isWalkableTileForTileCoord(tileCoord.topRight) {
    walkableCoords.append(tileCoord.topRight)
  }
  if canMoveDown && canMoveRight && gameScene.isWalkableTileForTileCoord(tileCoord.bottomRight) {
    walkableCoords.append(tileCoord.bottomRight)
  }

  return walkableCoords
}

Note that the code to add the diagonals is a bit more complicated than for horizontal/vertical movement. Why is this?

The code enforces the rule that if the cat is to move, say, diagonally to the tile to the bottom-left, it must also be able to move in both the down and left directions. This prevents the cat from walking through walls. The following diagram illustrates this:

In the diagram,

• O = Origin
• T = Top
• B = Bottom
• L = Left
• R = Right
• TL = Top - Left
• ...

Take for example the case shown in the top left of the above image.

The cat wants to go from the origin (O) to the bottom left diagonal square. If there is a wall to the left or below (or both), then moving diagonally would cut through the corner of a wall (or two). So the bottom-left direction is open only if there is no wall to the left or below.

Tip: You can simulate different type of terrain by updating costToMoveFromTileCoord(_:toAdjacentTileCoord:) to take the terrain type into consideration. Lowering the cost will result in the cat preferring those squares; increasing it will cause the cat to tend to avoid the squares if a better route is available.

Build and run your project. Verify that the cat does, indeed, take the diagonal when it can.