Blog » Making Grass, part 4: Pathfinding

Making Grass, part 4: Pathfinding

2019-05-08

Pathfinding

I want to control my character using mouse (or touchscreen) by just pointing to the destination. To do that, I need to compute the path around obstacles: walls, trees, or even enemies.

I implemented Dijkstra's algorithm and then A*. I won't be explaining these in detail, but Red Blob Games does it very well.

A* vs. Dijkstra

I wanted to see the difference between Dijkstra's algorithm and A*, so I added a visualisation. The algorithms find out a "previous" cell for each cell visited, so I drew a line to the previous cell. Here is how it looks like:

As you can see, Dijkstra's algorithm explores every reachable cell before it reaches the destination. The A* algorithm uses a distance heuristic that allows it to go "in the direction" of the target, so while it still explores a fair amount of cells in the vicinity, it doesn't even touch the left part of the map.

(The above pictures show a somewhat more difficult case because we have to go around the trees. If there is a straight path to the target, A* doesn't explore almost any unnecessary cells).

The downside is that A* is basically one-off: you compute it for a single source and destination. For the Dijkstra algorithm, you could compute a Dijkstra map for a single source and all possible destinations, and then read any path you want from it. The paths work both ways, so you could compute a Dijkstra map for the player's position, and use it for all monsters that want to find their way to the player.

A Dijkstra map be used for all kind of clever behavior. For more information, read The Incredible Power of Dijkstra Maps over at RogueBasin, and take a look at some pretty visualisations.

Tweaking the algorithm

In my game, diagonal movement takes the same amount of time as going horizontally and vertically. You might say that the game uses the maximum distance instead of the standard Euclidean distance:

function distance(a, b) {
  return Math.max(a.x - b.x, a.y - b.y);
}

The pathfinding code uses the same metric. One consequence is that a straight-line path has the same cost as one using diagonals:

While the second path is just as good according to game rules, it doesn't look like it's the best one. What's worse, because there are many equivalent paths, the algorithm is not stable:

The game recalculates the remaining path after every move. This looks great when your character reacts to changes in environment. However, recalculating (and displaying) the path makes the instability much more visible.

The solution to both problems (weird diagonal paths, and instability) is to break the equivalence between paths. I do that by imposing a small penalty for the diagonal movement:

const eps = 1 / 16;

const NEIGHBORS = [
    // horizontal and vertical movement cost: 1
    [1, 0, 1],
    [-1, 0, 1],
    [0, 1, 1],
    [0, -1, 1],
    // diagonal movement cost: 1 + eps
    [-1, -1, 1 + eps],
    [-1, 1, 1 + eps],
    [1, -1, 1 + eps],
    [1, 1, 1 + eps]
]

This makes the path stay in place.