A Thinking World
Pathfinding foundations — from simple flood-fill search through to A*.
Demo: A guard/intruder stealth game where each algorithm visibly changes guard behaviour.
Posts
- BFS — Breadth-First Search
- Dijkstra’s — Terrain Costs
- Greedy Best-First
- A*
- Bringing it Together
- Going Further
-
BFS — Breadth-First Search
Time to give your characters some serious brains! So far, your hero has been pretty… let’s say “directionally challenged.” Tell them to go left, they go left - even straight into a wall! But what if they could think for themselves and find clever paths around obstacles?
Welcome to the world of pathfinding - the AI magic behind every smart enemy in RTS games, every helpful companion in RPGs, and every tower defense unit that knows exactly how to reach their target. You’re about to implement the same algorithms that power characters in Starcraft, Age of Empires, and countless other games!
-
Dijkstra's — Terrain Costs
What if your hero doesn’t just want the shortest path — they want the cheapest one? A battlefield isn’t all flat floors. There’s mud that slows you down, roads that speed you up, rivers you’d rather not wade through. Breadth-First Search treats every tile the same. Dijkstra’s algorithm knows better.
Edsger Dijkstra published this algorithm in 1959 — originally to find the shortest driving route between two Dutch cities. Six decades later, it’s still powering pathfinding in games from Civilization to Dwarf Fortress to your next project.
-
Greedy Best-First
Ready to supercharge your AI? While breadth-first search guarantees the shortest path, it can be painfully slow on large maps - exploring EVERYWHERE before finding the target. What if your AI could be smarter and guess which direction to search first?
Enter Best-First Search - the algorithm that adds intuition to pathfinding! Instead of blindly searching in all directions, your AI will make educated guesses about where the target might be, dramatically speeding up path discovery.
-
A*
This is the one. Every pathfinding tutorial builds toward this moment. A* (pronounced “A-star”) is the algorithm used in more shipped games than any other — from Age of Empires to Stardew Valley to AAA blockbusters. It’s optimal like Dijkstra’s and fast like Greedy Best-First, because it’s actually both of them fused together.
The insight is elegant: Dijkstra’s tracks the real cost from start to each tile (
g). Greedy Best-First estimates the remaining cost to the goal (h). A* simply adds them together:f = g + h. Prioritise byf, and you’re guaranteed to find the shortest (or cheapest) path while exploring far fewer tiles than either algorithm alone. -
Finite State Machines
A* tells your guard how to reach the player. It doesn’t tell the guard whether to bother. An entity that only knows how to move isn’t thinking — it’s executing. A Finite State Machine is the decision layer: a formal description of what an entity is doing right now, what it might do instead, and exactly what must be true for it to switch.
Every guard in every stealth game runs on something like this. So does every enemy AI in a platformer, every shop NPC that goes idle when you walk away, every boss that enters its second phase at half health. FSMs are ubiquitous in games because they map directly to how designers describe behaviour: if the player is near, chase; if the player escapes, give up and return home.
-
Behaviour Trees
A Finite State Machine with four states is manageable. One with ten states, where any state might transition to any other, is a maintenance problem. Behaviour Trees solve this by replacing the transition table with a tree of composable nodes — small, reusable pieces that combine into arbitrarily complex behaviour without the O(n²) transition explosion.
A Behaviour Tree is evaluated top-down every frame. Each node returns one of three values:
SUCCESS,FAILURE, orRUNNING. Parent nodes use these return values to decide which child to run next. The result is that you describe AI behaviour as a hierarchy of priorities rather than a flat list of states. -
Influence Maps
Pathfinding tells an entity how to reach a destination. It doesn’t tell the entity which destination is worth reaching. An influence map fills that gap: a second grid, the same dimensions as your tile map, where each cell holds a numeric value representing some property of that location — how dangerous it is, how much of the area a faction controls, how recently the player passed through.
The guard doesn’t need to pathfind to every tile to know that standing in the open near the player is a bad idea. It reads the influence map, finds the cell with the highest “danger” value, and moves away from it. Spatial reasoning without exhaustive search.
-
Steering Behaviours
Grid movement is discrete: an entity occupies a tile, moves to an adjacent tile. That works for turn-based games and many real-time ones. But the moment you want an enemy that smoothly curves toward a target, a projectile that arcs, or a group of guards that spread out without running into each other, you need movement that operates in continuous space.
Steering behaviours — introduced by Craig Reynolds in 1999 — describe motion as the difference between where an entity is heading and where it wants to head. That difference, the steering force, is applied to the entity’s velocity each frame. The result is motion that looks purposeful and organic rather than grid-snapped.
-
Bringing it Together
Four algorithms. One demo. Time to put everything together into something that actually feels like a game.
You’re the intruder. You have a 5-second head start before the guard wakes up. The guard uses A* to track your last known position — not your current position, because fair is fair and omniscient guards aren’t fun. Break line of sight, hide in the shadows, and get to the exit before you get caught.
-
Going Further
A* will take you a long way. Most shipped tile-based games use it and never need anything else. But pathfinding is a rich field, and knowing what’s beyond the horizon helps you recognise when you’ve outgrown your tools.
This chapter is a map of that territory — less code, more concepts, with enough implementation detail to get you started if you want to explore.