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. -
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.