Find the shortest path with A* and other pathfinding algorithms

Find the shortest path in your JavaScript game with A* pathfinding. Draw a level with walls and mud, then watch breadth-first search, Dijkstra's algorithm, greedy best-first search and A* race to the goal. You'll also learn how to add diagonal moves, smooth the path and send a whole swarm after the player.

Draw your own level below and watch the bee find its way to the flower. Pick what to draw, and drag across the grid to draw it. Mud is slow to cross. With Dijkstra's algorithm and A*, the bee only goes through it when the way around is much longer. You can also drag the bee and the flower to move them, and try each of the four algorithms you'll build in this tutorial:

What is pathfinding?

Pathfinding is finding a route from one place to another, around everything that's in the way. Games are full of it. An enemy walks around a table to get to the player, a unit in a strategy game finds its way across the map, and a character walks to the spot where you clicked.

So why not just walk straight toward the goal? That works fine in an open field. But as soon as there's a wall in the way, things go wrong. In the demo below, the bee flies straight at the flower, right into the U-shaped wall:

The bee gets stuck at the back of the U, because every step toward the flower runs into the wall. To get out, it would first have to fly away from the flower, and a bee that only looks at the goal never does that. A pathfinding algorithm looks ahead. It explores the level step by step until it finds a route, and only then does the bee start to move.

Turn your level into a grid

Before you can search for a path, the level needs to be in a form that a computer can search. The simplest one is a grid: rows and columns of square cells. A cell is either open or a wall, and you can step from a cell to the cells right next to it.

You can write a small level as an array of strings, one string per row. A dot is an open cell, a # is a wall, S is the start and G is the goal. Draw some walls in the demo below by clicking or tapping a cell and dragging, and you'll see the array change as you draw. You can also drag the bee and the flower:

Live demo The code updates as you play around

let level = [
    '...............',
    '...............',
    '.....#.........',
    '..S..#.....G...',
    '.....#.........',
    '.....######....',
    '...............',
    '...............'
];

Strings are easy to type, but a search needs to keep track of every cell it finds, and later in this tutorial, cells also get a cost. So turn every character into a cell object with its position and whether it's a wall. The cells go into a two-dimensional array called grid, so grid[y][x] is the cell in row y and column x. Along the way, the loop remembers the start and the goal:

let rows = level.length;
let columns = level[0].length;
let grid = [];
let start;
let goal;

for (let y = 0; y < rows; y++) {
    grid[y] = [];
    for (let x = 0; x < columns; x++) {
        let cell = {x: x, y: y, wall: level[y][x] == '#'};
        grid[y][x] = cell;
        if (level[y][x] == 'S') {
            start = cell;
        } else if (level[y][x] == 'G') {
            goal = cell;
        }
    }
}

Every pathfinding algorithm in this tutorial asks the same question over and over: where can I go from here? getNeighbors() answers it. It looks at the four cells next to a cell, in the order of the directions array below: right, left, down and up. Then it keeps the ones that are inside the grid and aren't walls:

const directions = [
    {x: 1, y: 0},
    {x: -1, y: 0},
    {x: 0, y: 1},
    {x: 0, y: -1}
];

function getNeighbors(cell) {
    let neighbors = [];
    for (let direction of directions) {
        let x = cell.x + direction.x;
        let y = cell.y + direction.y;
        let inside = x >= 0 && x < columns && y >= 0 && y < rows;
        if (inside && !grid[y][x].wall) {
            neighbors.push(grid[y][x]);
        }
    }
    return neighbors;
}

On a computer, move your mouse over the demo above to see the neighbors of each cell. A cell in the open has four, and a cell in a corner or next to a wall has fewer. To draw walls with the mouse in your own code, find the cell under the mouse and flip its wall value. toggleWall() in the complete code at the end of this tutorial does exactly that, and the tutorial on Conway's Game of Life in JavaScript explains how to find the cell under the mouse.

Explore the grid with breadth-first search

The first algorithm is breadth-first search, or BFS for short. It begins at the start cell and explores outward, one ring of cells at a time. First all cells one step away, then all cells two steps away, and so on, until it has seen every cell it can reach.

BFS keeps a list of cells it has found but hasn't explored yet. That list is called the frontier. BFS takes the oldest cell from the frontier, adds its neighbors, and repeats. A Set called reached remembers which cells it has already found, so no cell gets added twice:

function breadthFirstSearch(start) {
    let frontier = [start];
    let reached = new Set([start]);

    while (frontier.length > 0) {
        let current = frontier.shift();
        for (let next of getNeighbors(current)) {
            if (!reached.has(next)) {
                frontier.push(next);
                reached.add(next);
            }
        }
    }
    return reached;
}

push() adds a cell to the end of the frontier, and shift() takes one from the front. That makes the frontier a queue: first in, first out, just like the line at a supermarket. Because the oldest cells go first, the search spreads out evenly in every direction.

Watch it happen in the demo below. Red cells are in the frontier. The demo also counts the steps: each explored cell shows how many steps it takes to get there from the bee, one more than the number in the cell it was found from. Click Step to explore one cell at a time, Play to run the search, and Reset to start over. You can draw walls and drag the bee here too:

The numbers grow by one with every ring. Where a wall is in the way, the numbers flow around it, because BFS can only reach the cells behind it the long way.

Follow the trail back to the start

BFS now knows which cells it can reach, but not how to get there. To find the way, every cell has to remember where it came from. Swap the Set for a Map called cameFrom. A Map stores a value for every key, so cameFrom.get(cell) gives you the cell you stepped from to get to cell. And cameFrom.has(cell) now does the job of reached. It tells you whether a cell has already been found:

function breadthFirstSearch(start, goal) {
    let frontier = [start];
    let cameFrom = new Map();
    cameFrom.set(start, null);

    while (frontier.length > 0) {
        let current = frontier.shift();
        // Stop as soon as you reach the goal
        if (current == goal) {
            break;
        }
        for (let next of getNeighbors(current)) {
            if (!cameFrom.has(next)) {
                frontier.push(next);
                cameFrom.set(next, current);
            }
        }
    }
    return cameFrom;
}

The start has null as its value, because it didn't come from anywhere. There's one more change: the loop stops as soon as it takes the goal from the frontier. You only need the path to the goal, so there's no reason to explore the rest of the grid. This is called an early exit, and on a big level it saves a lot of work.

The demo below leaves out the early exit, so it explores the whole grid. Each cell has an arrow that points to the cell it came from. Follow the arrows from any cell, and they lead you back to the bee. Drag the flower around to see the path to it, or move your mouse over a cell to see the path from there:

To turn the arrows into a path, start at the goal and keep following cameFrom until you reach the start, whose value is null. That gives you the path backward, from the goal to the start, so reverse it at the end:

function getPath(cameFrom, goal) {
    // The search never reached the goal
    if (!cameFrom.has(goal)) {
        return [];
    }
    let path = [];
    let cell = goal;
    while (cell) {
        path.push(cell);
        cell = cameFrom.get(cell);
    }
    return path.reverse();
}

let path = getPath(breadthFirstSearch(start, goal), goal);

Now path is an array of cells, from the start to the goal. If the goal is walled off, the search runs out of cells without ever reaching it, and you get an empty array.

Find the cheapest path with Dijkstra's algorithm

So far, every step costs the same. But in a game, some ground is harder to cross than other ground. Walking through mud should take longer than walking on grass. Give every cell a cost: 1 for grass, written as a dot in the level, and 5 for mud, written as a ~. In the loop that builds the grid, create each cell like this:

let cell = {
    x: x,
    y: y,
    wall: level[y][x] == '#',
    cost: level[y][x] == '~' ? 5 : 1
};

BFS doesn't care about the cost. It finds the path with the fewest steps, even if that path goes straight through the mud. Dijkstra's algorithm finds the path with the lowest total cost instead. The computer scientist Edsger Dijkstra came up with it in 1956.

The idea is the same as in BFS, with two changes. The algorithm keeps track of what it costs to get to each cell from the start, in a Map called costSoFar. And instead of the oldest cell, the algorithm always takes the frontier cell that's cheapest to reach. To do that, each item in the frontier gets a priority, and the frontier is sorted by priority, lowest first. For now, the priority is the cost so far. Call the new function findPath(), because later in this tutorial you'll turn it into the other two algorithms too:

function findPath(start, goal) {
    let frontier = [{cell: start, priority: 0}];
    let cameFrom = new Map();
    let costSoFar = new Map();
    cameFrom.set(start, null);
    costSoFar.set(start, 0);

    while (frontier.length > 0) {
        // Take the cell with the lowest priority
        frontier.sort((a, b) => a.priority - b.priority);
        let current = frontier.shift().cell;
        if (current == goal) {
            break;
        }
        for (let next of getNeighbors(current)) {
            let newCost = costSoFar.get(current) + next.cost;
            let isNew = !costSoFar.has(next);
            if (isNew || newCost < costSoFar.get(next)) {
                costSoFar.set(next, newCost);
                let priority = newCost;
                frontier.push({cell: next, priority: priority});
                cameFrom.set(next, current);
            }
        }
    }
    return cameFrom;
}

newCost is the cost to reach the current cell plus the cost of stepping onto next. With Dijkstra's algorithm on this grid, the first route it finds to a cell is always the cheapest, because the cheapest cells come out of the frontier first. But once you turn findPath() into greedy best-first search or A*, or add diagonal moves, a cell can be found again later through a cheaper route.

That's why the check isn't just whether the cell is new: if newCost is lower than what you found before, you update the cost and add the cell to the frontier again. The old item for that cell is still in the frontier too. When it comes out later, the loop looks at the same neighbors again, but none of them gets cheaper, so nothing changes.

In the demo below, a band of mud has a narrow strip of grass at the top. Switch between BFS and Dijkstra and compare the path cost in the corner. Click or tap the grid to draw or remove mud, and drag the bee and the flower to try other routes:

BFS walks straight through the mud, because that's the route with the fewest steps. Dijkstra's algorithm takes the detour over the grass, which is longer but cheaper. Both explore most of the grid before they reach the flower, though.

Head for the goal with greedy best-first search

BFS and Dijkstra's algorithm spread out in every direction, even away from the goal. That's a lot of wasted work when you know where the goal is. Greedy best-first search uses that knowledge. It always explores the cell that looks closest to the goal first.

The algorithm can't know the real distance to the goal until it has found a path, so it makes an estimate. That estimate is called the heuristic. On a grid where you move in four directions, a good estimate is the Manhattan distance: the number of columns plus the number of rows between the cell and the goal. It's named after the streets of Manhattan, where you can't cut across the blocks:

function heuristic(a, b) {
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

To turn findPath() into greedy best-first search, change one line. The priority becomes the estimate, and the cost so far no longer counts toward the priority. findPath() still keeps track of it, so it knows when it finds a cheaper way to a cell:

let priority = heuristic(next, goal);

The demo below has two long walls. The first one is open at the top and at the bottom, and the second one only at the top. Switch from Dijkstra to Greedy, and compare the number of explored cells and the path cost:

Greedy best-first search explores far fewer cells. But at the first wall, the gap at the bottom looks just as close to the flower as the gap at the top, and greedy best-first search picks the bottom one. That's because directions lists the step down before the step up, so the cell below goes into the frontier first. sort() keeps cells with the same priority in the order they were added, so that cell also comes out first. Past the first wall, it heads for the flower until it runs into the second wall, and then it has to go all the way back up. It doesn't care how far it has already walked, so it finds a path quickly, but not always the shortest one.

Combine Dijkstra and greedy search with A*

Dijkstra's algorithm always finds the cheapest path, but it explores a lot. Greedy best-first search explores little, but its paths can be bad. A*, pronounced "A star," combines the best of both. Its priority is the cost so far plus the estimated cost to the goal:

let priority = newCost + heuristic(next, goal);

A cell with a low priority is cheap to reach and close to the goal. A* explores in the direction of the goal like greedy best-first search, but a detour makes the cost so far go up, so it doesn't follow a bad route for long. As long as the heuristic never overestimates the real cost to the goal, A* always finds the cheapest path, just like Dijkstra's algorithm. Manhattan distance is safe here. It's the fewest steps you could possibly need to reach the goal, and no step costs less than 1, so the real cost can never be lower than the estimate. Peter Hart, Nils Nilsson and Bertram Raphael published A* in 1968, and it's still the most widely used pathfinding algorithm in games.

Here's something you might have noticed by now. If you write them the way findPath() is written, BFS, Dijkstra's algorithm, greedy best-first search and A* are all the same loop. The only differences are how they calculate the priority and, for BFS, what a step costs. Choose an algorithm in the demo below, and the code shows the lines that change:

Live demo The code updates as you play around

Algorithm

BFS Dijkstra Greedy A*

// A*: the cost so far plus the estimate
let newCost = costSoFar.get(current) + next.cost;
// ...
let priority = newCost + heuristic(next, goal);

The level in this demo has six rooms with doors between them, and two patches of mud. BFS and greedy best-first search walk right through the mud, so their paths cost more. Dijkstra's algorithm and A* find the same cheap path, but A* explores only about a third as many cells.

BFS is the odd one out in the code: it's Dijkstra's algorithm where every step costs 1. When every step costs 1, the oldest cell in the frontier always has the fewest steps, so you don't need to sort: a simple queue does the job.

Compare BFS, Dijkstra, greedy search and A*

The demo below runs all four algorithms on the same level, at the same speed. Every explored cell takes the same amount of time, so the algorithm that explores the fewest cells finishes first. Draw on any of the four grids, and all four change. Click Restart to start the race again, or Random maze to try them on a maze:

Here's what each algorithm is good at, and when you'd use it:

• Breadth-first search - Finds the path with the fewest steps, and ignores the cost of the ground. It's the simplest of the four, and the right choice when every step costs the same.
• Dijkstra's algorithm - Finds the cheapest path, but explores in every direction. Use it when there's no single goal, like when you're looking for the nearest of several coins: the first coin that comes out of the frontier is the nearest. It's also the one to use when you want the cost to every cell at once, like in the flow field further down.
• Greedy best-first search - Explores the fewest cells, but the path can be far from the best. Good enough for an enemy that only needs to look busy.
• A* - Finds the cheapest path, and usually explores far fewer cells than Dijkstra's algorithm. Use it when you know where the goal is, which in a game is almost always.

The more walls there are in the way, the more cells A* explores, until it explores almost as many as Dijkstra's algorithm. The estimate ignores walls, so every wall puts it further below the real cost, and A* has to try more cells before it finds a way around. Try a random maze in the race above to see that happen.

Generate a random maze with depth-first search

Drawing levels by hand takes a while, so let the computer build one. A classic way is to generate a maze with depth-first search. Where breadth-first search explores ring by ring, depth-first search goes as deep as it can first. From the room you're in, dig a tunnel to a random room next to it that you haven't visited yet, and keep going. When you get stuck, go back along your tunnel until you find a room with a neighbor you haven't visited.

The rooms are single cells: the cells where both x and y are odd. The cells in between start as walls. That's why the code below looks two cells away: that's the room you dig to, and the cell in between is the wall you dig through. A room you haven't visited yet is still a wall, a # in the code. A stack keeps track of your tunnel: push() adds a cell to the end when you dig, and pop() takes the last one off when you go back:

function generateMaze(columns, rows) {
    // Start with a wall on every cell
    let maze = [];
    for (let y = 0; y < rows; y++) {
        maze.push(new Array(columns).fill('#'));
    }
    let stack = [{x: 1, y: 1}];
    maze[1][1] = '.';

    while (stack.length > 0) {
        let cell = stack[stack.length - 1];
        let dug = false;
        for (let direction of shuffle(directions.slice(0, 4))) {
            let x = cell.x + direction.x * 2;
            let y = cell.y + direction.y * 2;
            let inside =
                x > 0 && x < columns - 1 &&
                y > 0 && y < rows - 1;
            if (inside && maze[y][x] == '#') {
                // Dig through the wall in between, and into the room
                maze[cell.y + direction.y][cell.x + direction.x] = '.';
                maze[y][x] = '.';
                stack.push({x: x, y: y});
                dug = true;
                break;
            }
        }
        // A dead end: go back one step along your tunnel
        if (!dug) {
            stack.pop();
        }
    }
    return maze;
}

Use an odd number of columns and rows, like 29 by 15, so there's a wall all around the maze. shuffle() puts the four directions in a random order, so every maze is different. It changes the order of the array you give it, so give it a copy: directions.slice(0, 4) is a copy of the first four directions, the straight ones. That way, directions itself keeps its order for getNeighbors(). And later in this tutorial, when you add four diagonal directions to directions, the maze still only digs in straight lines. shuffle() is the Fisher-Yates shuffle from the tutorial on random numbers:

function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    return array;
}

A maze like this has exactly one route between any two cells. That's nice for a puzzle, but boring for pathfinding: every algorithm finds the same path. Knock out a few extra walls between rooms, and the algorithms have a choice again. A room has an odd x and an odd y, so a wall between two rooms has one odd and one even coordinate, and the two add up to an odd number. The cells where both are even never share a side with a room, so they stay walls:

function addLoops(maze, chance) {
    for (let y = 1; y < maze.length - 1; y++) {
        for (let x = 1; x < maze[y].length - 1; x++) {
            let betweenRooms = (x + y) % 2 == 1;
            if (betweenRooms && Math.random() < chance) {
                maze[y][x] = '.';
            }
        }
    }
}

With a chance of 0.1, about one in ten of those walls disappears. Put an S and a G in two rooms, join each row into a string with join(''), and you have a level just like the array of strings in the section on turning your level into a grid.

In the demo below, the red cell digs the maze, and the light red cells are the tunnel on the stack. When the maze is done, A* finds the way from the bee to the flower. Click New maze for another one, and turn on Loops to knock out extra walls:

Choose a heuristic

The heuristic decides how well A* performs. It's an estimate of the cost from a cell to the goal, and there are three common ones for a grid:

• Manhattan distance - The columns plus the rows between the cell and the goal. Exactly right on an empty grid where you move in four directions.
• Euclidean distance - The length of the straight line between the cell and the goal, calculated with the Pythagorean theorem. It's the same formula as for the distance between two circles in collision detection.
• Octile distance - The length of the shortest route when you can also move diagonally: as many diagonal steps as possible, and straight steps for the rest.

In code, with dx and dy as the number of columns and rows between the cell and the goal:

let dx = Math.abs(a.x - b.x);
let dy = Math.abs(a.y - b.y);

// Manhattan distance
let manhattan = dx + dy;
// Euclidean distance
let euclidean = Math.sqrt(dx * dx + dy * dy);
// Octile distance
let octile = dx + dy - (2 - Math.SQRT2) * Math.min(dx, dy);

Octile distance takes as many diagonal steps as it can, which is the smaller of dx and dy. Each one replaces a step left or right and a step up or down, which together cost 2, with a single step of about 1.4. So for each diagonal step, it subtracts 2 - √2, about 0.6, from the Manhattan distance.

The one rule for a heuristic: it must never overestimate the real cost. A heuristic like that is called admissible, and with it, A* always finds the cheapest path. An estimate that's too low is safe, but A* explores more than it needs to. The closer the estimate is to the real cost, the fewer cells A* explores.

Try the three heuristics below on the level with the two walls. With four directions, A* explores the fewest cells with Manhattan distance, because it's the most accurate. Euclidean and octile distance are lower, so they're still admissible, but A* explores a few more cells. Then try a Heuristic weight higher than 1:

Live demo The code updates as you play around

Heuristic

Manhattan Euclidean Octile

Heuristic weight

1 1.5 3

function heuristic(a, b) {
    let dx = Math.abs(a.x - b.x);
    let dy = Math.abs(a.y - b.y);
    // Manhattan distance
    return dx + dy;
}

A weight makes the estimate too high on purpose: heuristic() multiplies its result by the weight, as the code under the demo shows. A* then trusts the estimate more than the cost so far, and behaves more like greedy best-first search. It explores fewer cells, but the path isn't always the cheapest anymore. With a weight of 3, A* takes the gap at the bottom of the first wall, just like greedy best-first search. This is called weighted A*, and it's a common trick when a game needs a lot of paths fast and a slightly longer one is fine.

Move diagonally without cutting corners

A character that can only move in four directions looks stiff. Add the four diagonal directions to directions, and cells have eight neighbors instead of four. A diagonal step is longer than a straight one, though. By the Pythagorean theorem, it's √2 times as long, which is about 1.4. So in findPath(), multiply the cost of a diagonal step by Math.SQRT2:

let diagonal = next.x != current.x && next.y != current.y;
let step = diagonal ? Math.SQRT2 : 1;
let newCost = costSoFar.get(current) + next.cost * step;

The heuristic has to change too. With diagonal steps, Manhattan distance is too high, because it counts 2 for a diagonal step that only costs 1.4. Use octile distance instead.

There's one more catch. With diagonal moves, a path can squeeze between two walls that only touch at a corner, or cut the corner of a wall. A character would have to walk through the wall for a moment to do that. So only allow a diagonal step if both cells it passes between are open:

const directions = [
    {x: 1, y: 0},
    {x: -1, y: 0},
    {x: 0, y: 1},
    {x: 0, y: -1},
    {x: 1, y: 1},
    {x: -1, y: 1},
    {x: 1, y: -1},
    {x: -1, y: -1}
];

function isWall(x, y) {
    let inside = x >= 0 && x < columns && y >= 0 && y < rows;
    return !inside || grid[y][x].wall;
}

function getNeighbors(cell) {
    let neighbors = [];
    for (let direction of directions) {
        let x = cell.x + direction.x;
        let y = cell.y + direction.y;
        if (isWall(x, y)) {
            continue;
        }
        // A diagonal step must not cut the corner of a wall
        let diagonal = direction.x != 0 && direction.y != 0;
        if (diagonal && (isWall(x, cell.y) || isWall(cell.x, y))) {
            continue;
        }
        neighbors.push(grid[y][x]);
    }
    return neighbors;
}

In the demo below, the wall in the middle is a diagonal line of cells that only touch at their corners. Turn on Diagonal moves, and then Cut corners, to see the path slip right through it:

Cut corners skips the corner check in getNeighbors(), so it only does something when Diagonal moves is on. With both on, the path is shorter, but no real character could follow it.

Speed up A* with a binary heap

Every time around the loop, findPath() sorts the whole frontier just to take the cheapest cell. On a small level, that's no problem. On a big one, the frontier can hold hundreds of cells, and sorting them over and over again adds up.

A binary heap is a better fit. It keeps the items in a tree, where every item has up to two items below it. The item directly above another item is called its parent, and a parent never has a higher priority than the items below it. So the lowest priority is always at the top, without sorting everything. Adding an item or taking the top one only takes a few swaps, even with thousands of items.

Here's a small heap for cells. It keeps the tree in a plain array, row by row: the top item at index 0, the two items below it at 1 and 2, the four items below those at 3 through 6, and so on. So the item at index i has the two items below it at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2, rounded down:

class MinHeap {
    constructor() {
        this.items = [];
    }

    get size() {
        return this.items.length;
    }

    push(cell, priority) {
        let items = this.items;
        items.push({cell: cell, priority: priority});
        // Move the new item up while its parent has a higher priority
        let i = items.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (items[parent].priority <= items[i].priority) {
                break;
            }
            [items[parent], items[i]] = [items[i], items[parent]];
            i = parent;
        }
    }

    pop() {
        let items = this.items;
        let top = items[0];
        let last = items.pop();
        if (items.length > 0) {
            // Move the last item to the top, and then down
            items[0] = last;
            let i = 0;
            while (true) {
                let left = i * 2 + 1;
                let right = left + 1;
                let lowest = i;
                if (
                    left < items.length &&
                    items[left].priority < items[lowest].priority
                ) {
                    lowest = left;
                }
                if (
                    right < items.length &&
                    items[right].priority < items[lowest].priority
                ) {
                    lowest = right;
                }
                if (lowest == i) {
                    break;
                }
                [items[lowest], items[i]] = [items[i], items[lowest]];
                i = lowest;
            }
        }
        return top.cell;
    }
}

push() adds the new item to the end of the array and swaps it up until its parent has a lower priority. pop() takes the top item, moves the last item to the top in its place, and swaps that one down until the items below it have a higher priority.

[a, b] = [b, a] swaps two items in one line. size is a getter, so you read it like a property: frontier.size, without parentheses. In findPath(), a few lines change, and the line with sort() is gone:

let frontier = new MinHeap();
frontier.push(start, 0);
// ...
while (frontier.size > 0) {
    let current = frontier.pop();
    // ...
            frontier.push(next, priority);

A list that always gives you the item with the lowest priority is called a priority queue. Unlike the queue in BFS, it goes by priority, not by which item was added first. The frontier of findPath() is a priority queue, and a binary heap is the usual way to build one.

The demo below uses the A* code from this tutorial to find the same path 20 times, from the top-left corner to the bottom-right corner of a grid of 150 by 80 cells, full of walls and mud. Pick Array or Binary heap, click Find 20 paths, and compare the times:

The heap is usually around ten times faster here. The exact times depend on your device.

Move a character along the path

A path is just a list of cells. To make a character follow it, give the character a position in pixels, a speed in pixels per second and a path:

let bee = {x: 100, y: 100, speed: 150, angle: 0, path: []};

Then turn every cell of the path into a point in pixels, in the middle of the cell. cellSize is the size of a cell on the canvas:

function toPoints(path) {
    return path.map(function (cell) {
        return {
            x: (cell.x + 0.5) * cellSize,
            y: (cell.y + 0.5) * cellSize
        };
    });
}

To send the bee to a cell goal, like the one you clicked, search for a path from the cell the bee is in. getCellAt() gives you the cell at a point in pixels, like the position of the bee or of a click:

function getCellAt(x, y) {
    return grid[Math.floor(y / cellSize)][Math.floor(x / cellSize)];
}

let path = getPath(findPath(getCellAt(bee.x, bee.y), goal), goal);
bee.path = toPoints(path);

Every frame, the bee flies toward the first point in its path. When it gets there, that point is removed, and the bee flies on to the next one. The distance it covers in a frame is its speed times secondsPassed, the time since the last frame, so it flies at the same speed whether the screen shows 60 or 144 frames per second. If you're not sure where secondsPassed comes from, the tutorial on the JavaScript game loop explains it:

function moveAlongPath(bee, secondsPassed) {
    let distanceLeft = bee.speed * secondsPassed;
    while (bee.path.length > 0 && distanceLeft > 0) {
        let target = bee.path[0];
        let dx = target.x - bee.x;
        let dy = target.y - bee.y;
        let distance = Math.sqrt(dx * dx + dy * dy);
        if (distance <= distanceLeft) {
            // Reached this point: on to the next one
            bee.x = target.x;
            bee.y = target.y;
            bee.path.shift();
            distanceLeft -= distance;
        } else {
            bee.x += dx / distance * distanceLeft;
            bee.y += dy / distance * distanceLeft;
            bee.angle = Math.atan2(dy, dx);
            distanceLeft = 0;
        }
    }
}

dx / distance and dy / distance give you the direction to the next point, as an arrow with a length of 1. Multiply them by distanceLeft, and the bee moves exactly that far.

The while loop matters when the bee is fast. If it reaches a point halfway through a frame, it uses the rest of that frame to fly on toward the next point, instead of stopping for a moment at every corner. bee.angle is the direction it's flying in, so you can rotate the bee image to face the way it's going.

Click or tap anywhere in the demo below, and the bee flies there. The bee in the demo uses A* with diagonal moves, and turns a little at a time instead of all at once:

Smooth the path

A path on a grid zigzags. Even with diagonal moves, a route at a slight angle becomes a staircase of straight and diagonal steps. Real characters don't walk like that. They walk in a straight line until they have to turn.

You can fix that afterward. Walk along the path, and skip a point whenever there's a clear straight line from the last point you kept to the point after it. This is called path smoothing:

function smoothPath(path) {
    // A path of one or two cells, or no path at all: nothing to skip
    if (path.length < 3) {
        return path;
    }
    let smooth = [path[0]];
    let current = path[0];
    for (let i = 1; i < path.length - 1; i++) {
        if (!hasLineOfSight(current, path[i + 1])) {
            current = path[i];
            smooth.push(current);
        }
    }
    smooth.push(path[path.length - 1]);
    return smooth;
}

hasLineOfSight() checks whether the straight line between two cells is clear. It takes small steps along the line, a quarter of a cell each, and checks the cell under every step. A character isn't a dot, though, so the function checks the four corners of a small square around each step. isWall() is the function from the section on diagonal moves. radius is half the width of the character, in cells:

const radius = 0.3;
const corners = [[-1, -1], [1, -1], [-1, 1], [1, 1]];

function hasLineOfSight(a, b) {
    let distance = Math.hypot(b.x - a.x, b.y - a.y);
    let steps = Math.ceil(distance * 4);
    for (let i = 0; i <= steps; i++) {
        let x = a.x + (b.x - a.x) * i / steps;
        let y = a.y + (b.y - a.y) * i / steps;
        for (let corner of corners) {
            let cornerX = Math.round(x + corner[0] * radius);
            let cornerY = Math.round(y + corner[1] * radius);
            if (isWall(cornerX, cornerY)) {
                return false;
            }
        }
    }
    return true;
}

hasLineOfSight() works in cells, not pixels, and it treats the x and y of a cell as its middle. The line runs from the middle of a to the middle of b. A point on the line belongs to the cell whose x and y are nearest, and Math.round() gives you that cell. Pixels work differently: a cell starts at its x times cellSize, which is why getCellAt() rounds down with Math.floor().

Turn on Smoothing in the demo below, and click or tap somewhere to compare the dashed grid path with the smooth one:

Chase a moving target

So far, the goal hasn't moved. An enemy that chases the player has a goal that moves all the time. You could search for a new path every frame, but with a few enemies at 60 frames per second, that's a lot of searches for paths that hardly change.

Instead, give every enemy a timer, and let it search for a new path a few times per second. In between, it follows the path it already has. The player won't notice the difference, but your game does less work:

wasp.timer -= secondsPassed;
if (wasp.timer <= 0) {
    // A new path a few times per second, not every frame
    wasp.timer = 0.3;
    let from = getCellAt(wasp.x, wasp.y);
    let target = getCellAt(bee.x, bee.y);
    let path = getPath(findPath(from, target), target);
    wasp.path = toPoints(smoothPath(path));
}
moveAlongPath(wasp, secondsPassed);

wasp is an object like bee, with an extra timer in seconds. getCellAt() and toPoints() are the functions from the section on moving a character along the path. Start every enemy with a slightly different timer, so they don't all search in the same frame.

In the demo below, three wasps chase the bee. Click or tap to send the bee somewhere, and drag to draw walls and keep the wasps away. The wasps find a way around every wall you draw, as long as there is one:

The wasps fly a little slower than the bee, or there would be no escape. If you wall the bee in completely, the wasps can't find a path anymore. getPath() returns an empty array, smoothPath() returns it unchanged, and the wasps stay where they are.

Guide a whole swarm with a flow field

A* finds one path for one character. But what if a hundred enemies all want to reach the same spot, like in a tower defense game? A hundred searches is a lot of work. There's a smarter way: search once, from the goal.

Run Dijkstra's algorithm from the goal, without an early exit, so it reaches every cell of the level. Now costSoFar tells you, for every cell, what it costs to get there from the goal. That map of costs is called a flow field. From any cell, keep stepping to the neighbor with the lowest cost, and you end up at the goal:

function buildFlowField(goal) {
    let frontier = new MinHeap();
    let costSoFar = new Map();
    frontier.push(goal, 0);
    costSoFar.set(goal, 0);

    while (frontier.size > 0) {
        let current = frontier.pop();
        for (let next of getNeighbors(current)) {
            let diagonal = next.x != current.x && next.y != current.y;
            let step = diagonal ? Math.SQRT2 : 1;
            let newCost = costSoFar.get(current) + next.cost * step;
            let isNew = !costSoFar.has(next);
            if (isNew || newCost < costSoFar.get(next)) {
                costSoFar.set(next, newCost);
                frontier.push(next, newCost);
            }
        }
    }
    return costSoFar;
}

function getDirection(costSoFar, cell) {
    let best = cell;
    for (let next of getNeighbors(cell)) {
        if (costSoFar.get(next) < costSoFar.get(best)) {
            best = next;
        }
    }
    return {x: best.x - cell.x, y: best.y - cell.y};
}

The flow field holds the cost from the goal to each cell, but the enemies fly the other way. Is the cost the same in that direction? Almost. You pay for each cell you step onto, so going the other way, you don't pay for the cell you start on, but you do pay for the goal cell. That changes the cost, but it hardly ever changes which route is cheapest, so it's good enough for a swarm.

Every enemy looks up the cell it's in and flies in the direction that getDirection() returns. In the code below, costSoFar is the flow field that buildFlowField() returns. A diagonal direction like {x: 1, y: -1} is longer than a straight one, so divide its x and y by its length to keep the speed the same, just like in moveAlongPath():

let cell = getCellAt(enemy.x, enemy.y);
let direction = getDirection(costSoFar, cell);
let length = Math.hypot(direction.x, direction.y);
// At the goal, there's nowhere left to go
if (length > 0) {
    enemy.x += direction.x / length * enemy.speed * secondsPassed;
    enemy.y += direction.y / length * enemy.speed * secondsPassed;
}

That's a few comparisons per enemy, no matter how many there are. You only build the flow field again when the goal moves to another cell.

In the demo below, the flower is the player, and the swarm of bees is after it. Move your mouse over the demo, or drag your finger across it, and the flower follows, with the swarm right behind. Pick Arrows to see the direction in every cell, or Costs to see the cost to the flower, from dark near the flower to light far away:

The bees in the demo also keep a little distance from each other, so they don't all end up in the same spot. Pathfinding gets them around the walls, and a small push away from nearby bees does the rest. That push is the separation rule from the tutorial on flocking with boids in JavaScript.

The complete pathfinding code

Here's a complete example in a single HTML file. It builds the grid from an array of strings with walls and mud, finds the cheapest path with A*, and draws it. Click a cell to add or remove a wall, and the path updates right away. Save it as an .html file and open it in your browser:

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">

    <title>Pathfinding Tutorial | Spicy Yoghurt</title>
</head>

<body>
    <canvas
        id="canvas"
        width="750"
        height="400"
        style="border:1px solid lightgray;"
    >
        Your browser does not support the HTML5 canvas tag.
    </canvas>
    <script>
        'use strict';

        // '#' is a wall, '~' is mud, 'S' is the start and 'G' is the goal
        const level = [
            '..............................',
            '..............................',
            '.......#..............~~~.....',
            '.......#.............~~~~~....',
            '..S....#.............~~~~~..G.',
            '.......#..............~~~.....',
            '.......#......................',
            '.......#######.......#####....',
            '.............#...........#....',
            '.............#...........#....',
            '.....~~~~....#...........#....',
            '....~~~~~~...#...........#....',
            '.....~~~~....#................',
            '..............................',
            '..............................',
            '..............................'
        ];
        const cellSize = 25;
        const directions = [
            {x: 1, y: 0},
            {x: -1, y: 0},
            {x: 0, y: 1},
            {x: 0, y: -1}
        ];

        let canvas;
        let context;
        let rows = level.length;
        let columns = level[0].length;
        let grid = [];
        let start;
        let goal;

        window.onload = init;

        function init() {
            canvas = document.getElementById('canvas');
            context = canvas.getContext('2d');
            createGrid();
            canvas.addEventListener('pointerdown', toggleWall);
            draw();
        }

        function createGrid() {
            for (let y = 0; y < rows; y++) {
                grid[y] = [];
                for (let x = 0; x < columns; x++) {
                    let cell = {
                        x: x,
                        y: y,
                        wall: level[y][x] == '#',
                        cost: level[y][x] == '~' ? 5 : 1
                    };
                    grid[y][x] = cell;
                    if (level[y][x] == 'S') {
                        start = cell;
                    } else if (level[y][x] == 'G') {
                        goal = cell;
                    }
                }
            }
        }

        function getNeighbors(cell) {
            let neighbors = [];
            for (let direction of directions) {
                let x = cell.x + direction.x;
                let y = cell.y + direction.y;
                let inside = x >= 0 && x < columns && y >= 0 && y < rows;
                if (inside && !grid[y][x].wall) {
                    neighbors.push(grid[y][x]);
                }
            }
            return neighbors;
        }

        function heuristic(a, b) {
            return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
        }

        // A*: returns, for every cell it reached, the cell it came from
        function findPath(start, goal) {
            let frontier = [{cell: start, priority: 0}];
            let cameFrom = new Map();
            let costSoFar = new Map();
            cameFrom.set(start, null);
            costSoFar.set(start, 0);

            while (frontier.length > 0) {
                // Take the cell with the lowest priority
                frontier.sort((a, b) => a.priority - b.priority);
                let current = frontier.shift().cell;
                if (current == goal) {
                    break;
                }
                for (let next of getNeighbors(current)) {
                    let newCost = costSoFar.get(current) + next.cost;
                    let isNew = !costSoFar.has(next);
                    if (isNew || newCost < costSoFar.get(next)) {
                        costSoFar.set(next, newCost);
                        let priority = newCost + heuristic(next, goal);
                        frontier.push({cell: next, priority: priority});
                        cameFrom.set(next, current);
                    }
                }
            }
            return cameFrom;
        }

        // Walk back from the goal to the start
        function getPath(cameFrom, goal) {
            if (!cameFrom.has(goal)) {
                return [];
            }
            let path = [];
            let cell = goal;
            while (cell) {
                path.push(cell);
                cell = cameFrom.get(cell);
            }
            return path.reverse();
        }

        // Click a cell to add or remove a wall
        function toggleWall(event) {
            let rect = canvas.getBoundingClientRect();
            let x = (event.clientX - rect.left) / rect.width * columns;
            let y = (event.clientY - rect.top) / rect.height * rows;
            x = Math.floor(x);
            y = Math.floor(y);
            if (x < 0 || x >= columns || y < 0 || y >= rows) {
                return;
            }
            let cell = grid[y][x];
            if (cell != start && cell != goal) {
                cell.wall = !cell.wall;
                draw();
            }
        }

        function draw() {
            let path = getPath(findPath(start, goal), goal);

            // Walls, mud and grass
            for (let row of grid) {
                for (let cell of row) {
                    if (cell.wall) {
                        context.fillStyle = '#303030';
                    } else if (cell.cost > 1) {
                        context.fillStyle = '#a8835e';
                    } else {
                        context.fillStyle = 'white';
                    }
                    let x = cell.x * cellSize;
                    let y = cell.y * cellSize;
                    context.fillRect(x, y, cellSize, cellSize);
                }
            }

            // The path, through the middle of each cell
            context.strokeStyle = '#0099b0';
            context.lineWidth = 6;
            context.lineJoin = 'round';
            context.beginPath();
            for (let cell of path) {
                let x = (cell.x + 0.5) * cellSize;
                let y = (cell.y + 0.5) * cellSize;
                context.lineTo(x, y);
            }
            context.stroke();

            drawCircle(start, '#0099b0');
            drawCircle(goal, '#ff8080');
        }

        function drawCircle(cell, color) {
            let x = (cell.x + 0.5) * cellSize;
            let y = (cell.y + 0.5) * cellSize;
            context.fillStyle = color;
            context.beginPath();
            context.arc(x, y, cellSize * 0.4, 0, Math.PI * 2);
            context.fill();
        }
    </script>
</body>

</html>

Expandto show all 210 lines

Say thanks with a coffeeCollapse

draw() searches for a new path every time it runs, so there's no extra code for when the level changes. To try the other algorithms, change the lines that set newCost and priority, as in the live demo in the section on A*. For diagonal moves or smoothing, add the code from the sections above. A moving bee also needs a game loop that calls moveAlongPath() every frame, like the one in the tutorial on the JavaScript game loop.

Conclusion

Pathfinding comes down to one loop. Take a cell from the frontier, add its neighbors, and remember where each cell came from. The priority decides which cell goes first, and how you calculate it turns the loop into breadth-first search, Dijkstra's algorithm, greedy best-first search or A*. You've also learned how to move diagonally without cutting corners, speed up the search with a binary heap, smooth the path, and send a whole swarm after the player with a flow field.

That's all for now. If you have any questions, feel free to ask them in the comment section. Built a maze that A* has a hard time with? Tell us about it in the comments. You can download the example code here.

If you'd like to support Spicy Yoghurt, please share our articles or follow us on social media.