Pathfinding on a Game Map

Keyboard shortcuts

×

?

Open this guide

Alt + B

Show or hide the lesson list

Alt + O

Show or fold the lesson outline

Alt + N

Open or close notes

Alt + H

Toggle semantic colours

Alt + D

Toggle page brightness

Alt + C

Toggle code brightness

← →

Move through a focused code trace

Home End

First or final step in a focused trace

Escape

Close this guide or an open panel

Reader shortcuts pause while you type in a text field.

Cheatsheet for Lesson 4.8Key ideas, reference and questions

A one-page summary of “Pathfinding on a Game Map” you can keep beside your notes. Plain Markdown.

Lesson 4.8 — Pathfinding on a Game Map: cheatsheet

• Remember: BFS finds the route with the fewest steps when every step costs the same. When costs differ, you need A-Star or another cost-aware search.
• Also useful: Think of a hiker with a compass: the cost paid so far is the distance already walked, and the heuristic is a straight-line guess pointing toward the goal.

Key terms

• Vec<T>: A Vec<T> stores its elements in one contiguous row of memory.

Formulas and patterns

• priority = cost already paid + estimated cost remaining

Review

• Q: Why does breadth-first search find a shortest route on a grid where every legal move has equal cost? A: It visits tiles in order of their step count from the start
• Q: A wall lies between the player and a target. Why does moving straight toward the target fail? A: A route must follow legal neighbouring tiles, so a direct line can get stuck on the wall

Download cheatsheet (.md)

Download cheatsheet (.md)

Coordinates can tell a bot where an enemy is, but not how to reach it. If a wall lies between the player and the target, moving directly toward the target gets stuck. A route must follow legal neighboring tiles, which turns the map into a graph-search problem.

Represent walkable tiles as a graph

A strategy game may store terrain as a flat row-major array. Pathfinding becomes easier to understand when you rename the pieces:

• each walkable tile is a node;
• a legal move between neighboring tiles is an edge;
• a route is a sequence of connected nodes;
• a wall simply means no edge crosses that tile.

For a map with width w, tile (x, y) is stored at y * w + x. Always bounds-check before performing that multiplication.

BFS and A-Star use the same search loop. The important difference is how the frontier chooses which tile comes out next:

BFS chooses in first-in-first-out order; A-Star chooses the tile with the best known cost plus its estimate. Both must reject invalid tiles before searching.

Breadth-first search first

Breadth-first search (BFS) explores every tile one step away, then two steps away, and so on. On a grid where every move costs the same, the first route it finds is shortest in number of steps.

The queue is what makes that guarantee work. Because tiles leave the queue in the order they entered it, every tile one step from the start is examined before any tile two steps away, and so on outward. So the first time BFS reaches a tile, it must have arrived by the fewest possible steps: a shorter route would have come out of the queue earlier and got there first.

Notice what that guarantee rests on — every move costing the same. As soon as some tiles cost more to enter, such as deep water, rough ground, or a slope, “fewest steps” and “cheapest route” stop being the same question, and BFS confidently answers the wrong one. Closing that gap is what A-Star is for.

Here is the smallest case where the two questions disagree. S is the start, G is the goal, and entering M costs 9 instead of the ground cost of 1:

ground  ground  ground
S       M       G
ground  ground  ground

BFS finds the direct route in two moves: S → M → G. Its travel cost is 9 + 1 = 10. Going around the top takes four moves but costs 1 + 1 + 1 + 1 = 4. A weighted search should choose the longer route because it answers the cost question. This is a limit of BFS’s guarantee, not a flaw in its queue.

TL;DR: BFS finds the route with the fewest steps when every step costs the same. When costs differ, you need A-Star or another cost-aware search.

use std::collections::{HashMap, VecDeque};

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct Tile {
    x: i32,
    y: i32,
}

fn neighbors(tile: Tile) -> [Tile; 4] {
    [
        Tile { x: tile.x + 1, y: tile.y },
        Tile { x: tile.x - 1, y: tile.y },
        Tile { x: tile.x, y: tile.y + 1 },
        Tile { x: tile.x, y: tile.y - 1 },
    ]
}

fn bfs(
    start: Tile,
    goal: Tile,
    walkable: impl Fn(Tile) -> bool,
) -> Option<Vec<Tile>> {
    let mut frontier = VecDeque::from([start]);
    let mut came_from = HashMap::from([(start, None)]);

    while let Some(current) = frontier.pop_front() {
        if current == goal {
            break;
        }

        for next in neighbors(current) {
            if walkable(next) && !came_from.contains_key(&next) {
                frontier.push_back(next);
                came_from.insert(next, Some(current));
            }
        }
    }

    let mut current = goal;
    let mut route = vec![goal];
    while current != start {
        current = came_from.get(&current).copied().flatten()?;
        route.push(current);
    }
    route.reverse();
    Some(route)
}

came_from does two jobs: it marks visited tiles and remembers how to reconstruct the route. If the goal is absent, ? returns None instead of inventing a path.

Turn coordinates into an array index safely

A Vec<T> stores its elements in one contiguous row of memory. A game can use that row to represent a two-dimensional map by placing row 1 after row 0, row 2 after row 1, and so on. That is why (x, y) becomes y * width + x.

Do not perform that formula until negative and out-of-range coordinates have been rejected. Also use checked arithmetic, because a corrupted width from a bad reverse-engineered layout must not wrap into a believable index:

(0,0)0

(1,0)1

(2,0)2

(0,1)3

(1,1)4

(2,1)5

row y=0

row y=1

For example, a 3-wide grid: (x, y) maps to index y * width + x. Row 1 starts right where row 0 ends, at index width.

#[derive(Clone, Copy, Debug)]
enum Terrain {
    Ground,
    Water,
    Wall,
}

#[derive(Clone, Copy, Debug)]
struct TileInfo {
    terrain: Terrain,
    visible: bool,
    movement_cost: u16,
}

struct Grid {
    width: usize,
    height: usize,
    cells: Vec<TileInfo>,
}

impl Grid {
    fn get(&self, tile: Tile) -> Option<&TileInfo> {
        // 🧭 Conversion fails for negative coordinates.
        let x = usize::try_from(tile.x).ok()?;
        let y = usize::try_from(tile.y).ok()?;

        if x >= self.width || y >= self.height {
            return None;
        }

        // 🧮 Checked math refuses impossible dimensions instead of wrapping.
        let index = y.checked_mul(self.width)?.checked_add(x)?;
        self.cells.get(index)
    }
}

cells.get(index) performs one final length check. That catches an incomplete snapshot whose header claims a 100 × 100 map but whose copied array contains fewer than 10,000 tiles.

Keep facts about one tile in one record such as TileInfo. Three separate vectors named terrain, visible, and movement_cost can drift out of sync so index 42 describes three different tiles. One vector of records makes that mistake harder to express.

A-Star adds a useful guess

A-Star uses the known route cost plus a heuristic, an estimate of the remaining cost. On a four-direction grid where every legal move costs at least 1, Manhattan distance counts the minimum number of horizontal and vertical moves and cannot overestimate that cost:

fn manhattan(a: Tile, b: Tile) -> u32 {
    a.x.abs_diff(b.x) + a.y.abs_diff(b.y)
}

The heuristic must not overestimate if you want the cheapest-path guarantee. For movement costs with a different verified minimum, multiply Manhattan distance by that minimum. If a legal move can cost zero, the safe estimate from this scaling is zero. The search priority is:

priority = cost already paid + estimated cost remaining

For the muddy grid above, the direct route has cost 10 and the top route has cost 4. The estimate guides which tile A-Star explores next; the accumulated cost still decides whether a newly found route improves an old one. If the game permits diagonal moves, Manhattan distance can overestimate: (0,0) to (1,1) might be one diagonal move while Manhattan counts two. Choose an estimate that matches the permitted moves and their minimum costs.

Do not include hidden enemy positions in the heuristic. A legitimate observer should plan from information the local game state actually reveals.

Keep the search’s bookkeeping names precise:

• the frontier contains discovered tiles that still deserve exploration;
• cost_so_far[tile] is the cheapest route to that tile found so far;
• came_from[tile] records the parent of that cheapest known route;
• the heuristic estimates only the cost that remains.

A tile entering the frontier does not mean its best path is final. If a cheaper route reaches it later, update its cost and parent. This distinction is why an implementation that merely marks every discovered tile “done” can return the wrong route on weighted terrain.

Setting the heuristic to zero turns A-Star into Dijkstra’s algorithm. That is a useful debugging switch: if the zero-heuristic version works but the normal one does not, inspect the heuristic and movement-cost assumptions before blaming the recovered map.

Alternative: Think of a hiker with a compass: the cost paid so far is the distance already walked, and the heuristic is a straight-line guess pointing toward the goal.

Keep three layers separate

The search function should never call ReadProcessMemory or press keys. It accepts an ordinary copied grid and returns ordinary coordinates. This makes it testable on any computer.

The input adapter is the only part allowed to translate one confirmed route step into a supported action in your offline lab.

Narration: Because the search never touches the game, a wrong route can be reproduced on any computer from a copied grid. Pressing keys inside it would make that far harder.

Tests that catch real mistakes

For example, here is the exact 3×2 grid this test builds, with the wall forcing a detour through row 1:

The test below gives BFS the start and goal from the diagram and rejects the wall tile (1, 0). A valid result begins at (0, 0), ends at (2, 0), and never includes the wall. The intermediate route follows the open second row.

A breadth-first search finds the route by walking parents backwardEach visited cell remembers the cell it was reached from. Walk those links from the goal, then reverse the list.

1. 1 Follow the parent links backward from the goal

   Backward chain, goal first

   (2,0)goal

   (2,1)

   (1,1)

   (0,1)

   (0,0)start, no parent

   Goal (2,0) was reached from (2,1), which came from (1,1), then (0,1), then the start, which has no parent.

2. 2 Reverse the list to get the forward route

   Backward chain, goal first

   (2,0)goal

   (2,1)

   (1,1)

   (0,1)

   (0,0)start

   ↓ reverse

   Forward route, start first

   (0,0)start

   (0,1)

   (1,1)

   (2,1)

   (2,0)goal

   Reading the same cells in the opposite order gives the way from the start to the goal: four moves, around the wall at (1,0).

Each visited cell remembers the cell it was reached from. Walk those links from the goal, then reverse the list.

#[test]
fn bfs_walks_around_a_wall() {
    let blocked = Tile { x: 1, y: 0 };
    let route = bfs(
        Tile { x: 0, y: 0 },
        Tile { x: 2, y: 0 },
        |tile| (0..=2).contains(&tile.x)
            && (0..=1).contains(&tile.y)
            && tile != blocked,
    ).expect("a route exists through the second row");

    assert_eq!(route.first(), Some(&Tile { x: 0, y: 0 }));
    assert_eq!(route.last(), Some(&Tile { x: 2, y: 0 }));
    assert!(!route.contains(&blocked));
}

Follow that test through the queue. The wall removes the direct move, leaving the route through the open second row:

A queue finds the shortest unweighted route. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

queue = [start]; seen = {start}
take the oldest queued tile
visit unseen, walkable neighbours
record each new tile’s parent
stop when the goal is reached
follow parents to recover the route

Result: 4 moves along 0,0 → 0,1 → 1,1 → 2,1 → 2,0. FIFO discovery gives a shortest route when every edge costs one.

Final values: walls = middle; current = 2,0; visited = 5; queued = 0; found = true; moves = 4; path = 0,0 → 0,1 → 1,1 → 2,1 → 2,0.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs and follow how the next operation changes the state.

   walls = middle.

2. Step 2, line 2. Take 0,0 from the front of the queue.

   walls = middle; current = 0,0; visited = 1; queued = 0.

3. Step 3, line 3. Queue 0,1 once; its parent is 0,0.

   walls = middle; current = 0,0; visited = 1; queued = 1.

4. Step 4, line 2. Take 0,1 from the front of the queue.

   walls = middle; current = 0,1; visited = 2; queued = 0.

5. Step 5, line 3. Queue 1,1 once; its parent is 0,1.

   walls = middle; current = 0,1; visited = 2; queued = 1.

6. Step 6, line 2. Take 1,1 from the front of the queue.

   walls = middle; current = 1,1; visited = 3; queued = 0.

7. Step 7, line 3. Queue 2,1 once; its parent is 1,1.

   walls = middle; current = 1,1; visited = 3; queued = 1.

8. Step 8, line 2. Take 2,1 from the front of the queue.

   walls = middle; current = 2,1; visited = 4; queued = 0.

9. Step 9, line 3. Queue 2,0 once; its parent is 2,1.

   walls = middle; current = 2,1; visited = 4; queued = 1.

10. Step 10, line 2. Take 2,0 from the front of the queue.

    walls = middle; current = 2,0; visited = 5; queued = 0.

11. Step 11, line 5. The goal was reached.

    walls = middle; current = 2,0; visited = 5; queued = 0; found = true.

12. Step 12, line 6. Result: 4 moves along 0,0 → 0,1 → 1,1 → 2,1 → 2,0. FIFO discovery gives a shortest route when every edge costs one.

    walls = middle; current = 2,0; visited = 5; queued = 0; found = true; moves = 4; path = 0,0 → 0,1 → 1,1 → 2,1 → 2,0.

Watch it happenA first-in, first-out queue finds the route around the wall

A grid three tiles wide and two tall with a wall at the top middle. The search takes one tile at a time from the front of a queue, tests its neighbours, queues the new ones, and records each new tile’s parent in a came_from list. When the goal is taken from the queue, the parent links are followed backward to draw the four-move route through the bottom row. A small hero then walks that route to the chest without crossing the wall.

Read the steps

1. The grid is 3 tiles wide and 2 tall. The search starts at (0,0) and wants (2,0), but (1,0) is a wall.
2. Seed the queue with the start, (0,0), and record that it has no parent. A tile that is in the queue counts as seen, so nothing can add it twice.
3. Take (0,0) from the front. Its right neighbour is the wall, and its left and upper neighbours are off the grid. Only (0,1), below, is new, so it joins the back of the queue with (0,0) as its parent.
4. Take (0,1). Up is (0,0), already seen, so skip it. Right is (1,1), which is new: queue it with (0,1) as its parent.
5. Take (1,1). Left is seen and up is the wall. Right is (2,1), which is new: queue it with (1,1) as its parent.
6. Take (2,1). Left is seen. Up is (2,0), the goal, and it is new: queue it with (2,1) as its parent.
7. Take (2,0). It is the goal, so the search stops. Follow came_from backward from the goal, (2,0), (2,1), (1,1), (0,1), (0,0), and reverse the list. Only after that route is known does the hero follow its four moves around the wall.

The queue sets the exploration order. came_from records seen tiles and the way back to the start. Hero movement illustrates the proposed route on this unchanged test grid.

Also test:

• start equals goal;
• goal is completely enclosed;
• coordinates lie outside the map;
• a one-tile corridor;
• terrain cost changes the preferred route;
• the observed grid changes after planning.

That final case matters. A route is based on one snapshot. Before performing the next step, confirm that the current tile and the next tile are still valid. If not, stop and plan again. 🔁

BFS or A-Star?

Use BFS when the grid is small, every step costs the same, or you are still verifying the map. Use A-Star when the map is large and a meaningful heuristic can avoid exploring most irrelevant tiles.

Both algorithms are only as correct as the recovered grid. A brilliant route through a tile you misclassified as walkable is still wrong. Pathfinding does not replace reverse engineering; it consumes the grid that reverse engineering produced.

🧩

Knowledge check

Choose a search rule

Why does breadth-first search find a shortest route on a grid where every legal move has equal cost?

1It visits tiles in order of their step count from the start2It steers toward the goal coordinates at every single step3It inspects every tile in the whole map before it picks a route4It treats wall tiles as walkable until a route has been found

Check answer

Finished Lesson 4.8?

Mark it done and the lesson list shows a ✓ beside it. A chapter whose lessons are all done is marked done too. Progress is saved in this browser only.

Mark lesson doneLesson done. Mark it not done

Chapter 4: 10 lessons

📝 Notes