Pathfinding concepts
Understand why straight-line movement fails in complex maps, how BFS explores a tile grid level by level, and how A* uses a heuristic to explore far fewer nodes.
- Explain why direct movement fails when walls exist
- Describe BFS on a tile grid — expansion order, visited set, parent pointers
- Explain what a heuristic is and why it dramatically reduces nodes explored
- Contrast BFS with A* at a conceptual level
An enemy that moves directly toward the player — pos += direction * speed —
works on an open field. Put a wall in the way and the enemy presses against it
indefinitely. Players find this laughably easy to exploit: stand just behind a
corner and the enemy is helpless.
Pathfinding solves this by computing a route through the map's free tiles before moving.
Representing the world as a graph
A tile map is naturally a graph. Each passable tile is a node. Two horizontally or vertically adjacent passable tiles share an edge (or eight neighbours if you allow diagonal movement). Finding a path is then a graph traversal problem.
Breadth-first search
BFS expands nodes in order of their distance from the start — layer by layer, like ripples spreading outward. The algorithm:
- Put the start node in a queue.
- For each node dequeued, add its unvisited passable neighbours to the queue and record each one's parent (the node you came from).
- Stop when the goal is dequeued.
- Reconstruct the path by following parent pointers backward from the goal to the start, then reversing.
BFS is guaranteed to find the shortest path on an unweighted graph. Its cost is O(V + E) — it visits every reachable node in the worst case. On a 40×30 tile map that is 1,200 nodes, which is fast. On a 200×200 map with many open tiles it can become noticeable, especially if many enemies recalculate every frame.
The heuristic idea
BFS wastes time expanding nodes that are moving away from the goal. A smarter approach would expand toward the goal preferentially. This requires an estimate of how far each node is from the goal — a heuristic.
The Manhattan distance is the standard heuristic for axis-aligned tile grids:
h(node) = |node.col - goal.col| + |node.row - goal.row|It is admissible: it never overestimates the true remaining cost (it ignores walls). This is the key property that makes A* optimal.
A* — BFS + heuristic
A* replaces BFS's plain queue with a priority queue ordered by:
f(n) = g(n) + h(n)where g(n) is the known cost to reach node n from the start and h(n) is
the heuristic estimate to the goal.
The node with the lowest f is expanded next. Because h pulls the frontier
toward the goal, A* typically explores a fraction of the nodes that BFS would.
On a clear corridor, A* expands only the nodes along the corridor. On a maze,
it still finds the optimal path but may explore somewhat more of the maze.
On a grid with uniform movement costs, A* with the Manhattan heuristic is essentially "BFS that prefers the direction of the goal." The priority queue does the heavy lifting.
Practical notes for games
Don't recalculate every frame. A* on a 100×100 grid takes a few milliseconds. Running it for every enemy every frame will tank performance. Instead, recalculate when the enemy enters CHASE state, when the player moves more than N tiles, or on a timer (every 0.5 s).
Cache the path. Store the list of waypoints returned by A* and follow them one tile at a time, recalculating only when the path becomes invalid (a door closed, a platform moved).
Tile size vs. entity size. If the player is 2×2 tiles wide, naively pathfinding to a 1-tile gap produces a path the entity cannot physically follow. Either widen the graph or mark tiles as blocked when they are too narrow for the entity.
Where to go next
Next: A on a grid* — a complete Python implementation using heapq, tested
against a grid with obstacles.