Rafi Andi
Back

Game Pathfinding Explained: DFS, BFS, Dijkstra, and A*

12 min read

Game Pathfinding Explained: DFS, BFS, Dijkstra, and A*

Have you ever wondered how enemies in a game navigate a complex maze to find the player, or how a strategy game unit figures out the best route around obstacles? The answer lies in Pathfinding algorithms.

In this guide, we'll explore the four most common pathfinding algorithms used in game development, from the simplest to the industry standard.

1. The World as a Graph or Grid

Before an algorithm can find a path, it needs to understand the game world. Most games represent the walkable world as a Grid (squares, hexagons) or a NavMesh (polygons). These can all be boiled down to a Graph: a series of points (nodes) connected by lines (edges).

Our goal is simple: find a sequence of nodes from the start point to the target point.

2. Depth-First Search (DFS)

Imagine walking through a maze. You pick a path, follow it until you hit a dead end, backtrack to the last intersection, and try another path. This is exactly how Depth-First Search works.

  • How it works: It dives as "deep" as possible into the graph before backtracking.
  • Pros: Uses very little memory.
  • Cons: It does not guarantee the shortest path. In a wide open grid, DFS might take a wild zigzagging route hitting every corner before finding the target.
  • Best for: Procedural maze generation or checking if a path exists, but terrible for actual character movement.

Example Code (Grid-based):

function dfs_grid(grid, start, target) {
  let stack = [start];
  let visited = new Set();
  
  while (stack.length > 0) {
    let current = stack.pop(); // Pop from top (LIFO)
    let key = `${current.x},${current.y}`;
    
    if (current.x === target.x && current.y === target.y) return true; // Found
    
    if (!visited.has(key)) {
      visited.add(key);
      let neighbors = getNeighbors(grid, current); // e.g., up, down, left, right
      for (let neighbor of neighbors) stack.push(neighbor);
    }
  }
  return false;
}

3. Breadth-First Search (BFS)

Unlike DFS, BFS explores the world symmetrically. Imagine dropping a stone in a pond; the ripples expand outwards in all directions equally.

  • How it works: It checks all immediate neighbors first, then the neighbors of those neighbors, expanding outwards step by step.
  • Pros: It guarantees the shortest path, provided every step has the same cost (unweighted graph).
  • Cons: It explores everywhere in all directions. It doesn't care where the target is until it accidentally bumps into it. Thus, it is slow and wastes memory.
  • Best for: Finding the shortest path on a simple, flat grid where every tile takes the same effort to walk on (e.g., standard tile-based puzzle games).

Example Code (Grid-based):

function bfs_grid(grid, start, target) {
  let queue = [start];
  let visited = new Set();
  visited.add(`${start.x},${start.y}`);
  
  while (queue.length > 0) {
    let current = queue.shift(); // Remove from front (FIFO)
    
    if (current.x === target.x && current.y === target.y) return true; // Found
    
    let neighbors = getNeighbors(grid, current);
    for (let neighbor of neighbors) {
      let key = `${neighbor.x},${neighbor.y}`;
      if (!visited.has(key)) {
        visited.add(key);
        queue.push(neighbor);
      }
    }
  }
  return false;
}

4. Dijkstra's Algorithm

What if the world isn't flat? What if walking through a swamp takes twice as much energy as walking on a road? BFS assumes every step costs the same (cost = 1). Dijkstra's Algorithm fixes this by introducing movement costs (weighted graphs).

  • How it works: It keeps track of the "accumulated cost" from the start node to all explored nodes. It always prioritizes exploring the next node with the lowest accumulated cost.
  • Pros: It guarantees the lowest-cost (shortest or easiest) path in any world with varied terrain (mountains, roads, water).
  • Cons: Like BFS, it expands in all directions (favoring the easy terrain first). It doesn't "aim" toward the target. In a large map, this is computationally expensive.
  • Best for: Strategy games with varied terrain types, but only if the target's location isn't known or if calculating routes to many targets at once.

Example Code (Grid-based with varied weights):

function dijkstra_grid(grid, start, target) {
  // Using an array and sorting it to simulate a Priority Queue (Min-Heap)
  let pq = [{ node: start, cost: 0 }];
  let costs = {};
  costs[`${start.x},${start.y}`] = 0;
  
  while (pq.length > 0) {
    pq.sort((a, b) => a.cost - b.cost); // Always process cheapest cost node first
    let current = pq.shift().node;
    
    if (current.x === target.x && current.y === target.y) return true; // Found
    
    let currentCost = costs[`${current.x},${current.y}`];
    let neighbors = getNeighbors(grid, current);
    
    for (let item of neighbors) { // item contains .node and .weight (terrain difficulty)
      let nextNode = item.node;
      let newCost = currentCost + item.weight; 
      let key = `${nextNode.x},${nextNode.y}`;
      
      // If unvisited or a cheaper path is found
      if (!(key in costs) || newCost < costs[key]) {
        costs[key] = newCost;
        pq.push({ node: nextNode, cost: newCost });
      }
    }
  }
  return false;
}

5. A* (A-Star) Search Algorithm

Dijkstra is smart, but it's blind to the target. A* takes Dijkstra's Algorithm and gives it a compass. This is the undisputed king of pathfinding in the game industry.

  • How it works: A* uses a heuristic (a smart guess) to estimate the distance remaining from a node to the goal. The algorithm evaluates nodes based on the formula: F = G + H
    • G: The exact cost from the start to the current node (like Dijkstra).
    • H (Heuristic): The estimated cost from the current node to the end target.
    • F: The total score. A* always explores the node with the lowest F first.
  • Pros: It is incredibly fast because it actively stretches towards the target, ignoring paths that obviously go in the wrong direction. It guarantees the shortest path (if the heuristic is well-designed).
  • Cons: Can consume a lot of memory on massive maps, requiring optimizations like NavMeshes or Hierarchical Pathfinding.
  • Best for: Almost every modern game requiring intelligent point-A to point-B movement.

Example Code (Grid-based with Heuristic):

// Manhattan distance heuristic for 4-directional grid movement
function heuristic(nodeA, nodeB) {
  return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}

function a_star_grid(grid, start, target) {
  let pq = [{ node: start, fCost: 0 }];
  let gCosts = {}; // Cost from start
  gCosts[`${start.x},${start.y}`] = 0;
  
  while (pq.length > 0) {
    pq.sort((a, b) => a.fCost - b.fCost); // Explore lowest F-cost first
    let current = pq.shift().node;
    
    if (current.x === target.x && current.y === target.y) return true; // Found
    
    let neighbors = getNeighbors(grid, current);
    for (let item of neighbors) {
      let nextNode = item.node;
      let newGCost = gCosts[`${current.x},${current.y}`] + item.weight; 
      let key = `${nextNode.x},${nextNode.y}`;
      
      if (!(key in gCosts) || newGCost < gCosts[key]) {
        gCosts[key] = newGCost;
        // F = G + H
        let fCost = newGCost + heuristic(nextNode, target); 
        pq.push({ node: nextNode, fCost: fCost });
      }
    }
  }
  return false;
}

Summary

  • DFS: Wanders aimlessly until it bumps into the goal. Bad for pathfinding.
  • BFS: Expands equally in all directions. Finds shortest path in unweighted grids.
  • Dijkstra: Expands favoring easier terrain. Finds lowest-cost path in weighted grids.
  • A:* Explores smartly toward the target. The industry standard for efficient pathfinding.

Understanding these concepts will drastically improve how you approach AI movement in your games!