Back in 2017 I built a pathfinding system for an endless runner. The NPCs were pursuers, and their whole job was to reach the main character - who was constantly running and weaving through a field of obstacles. They could not simply walk in a straight line at the player; they had to navigate around the same walls and hazards the player was dodging, and keep re-targeting a moving destination that never stood still. Getting that chase to feel intelligent, rather than the enemies bumping uselessly into walls, opened the door to one of the most satisfying corners of game programming. The source is still up on Bitbucket. This post is the write-up I wish I had when I started it: how AI actually works in games, the family of pathfinding algorithms you can choose from, why A* was the right call, and how it quietly made the game balanced - which is what makes a game fun.
What "AI" Really Means in a Game
Game AI is rarely the machine learning that the term implies today. It is a set of well-understood techniques for making non-player characters behave believably, and it splits cleanly into two layers: deciding what to do, and figuring out how to move there.
The decision layer is handled by structures like finite state machines (patrol, chase, flee, attack), behavior trees (used in most modern AAA games for their composability), utility systems that score possible actions, and steering behaviors for the small local adjustments - seek, flee, avoid, flock. A guard "sees" the player and its state machine flips from Patrol to Chase.
But once the guard decides to chase, it faces a purely geometric question: what is the actual route from where I stand to where the player is, given the walls, pits, and obstacles between us? That is pathfinding, and it is the movement layer that makes the decision layer look intelligent. A perfect decision system paired with a character that walks straight into a wall looks broken. Pathfinding is what sells the illusion of a thinking opponent.
Turning a Level Into a Graph
No pathfinding algorithm reasons about pixels or 3D geometry directly. The first job is to abstract the walkable world into a graph: a set of nodes (places you can be) connected by edges (moves you can make), each edge carrying a cost.
The most common representations are a uniform grid of square (or hex) tiles, where each walkable tile connects to its neighbors; a navigation mesh, which covers open floor with convex polygons and is standard in 3D games because it needs far fewer nodes; and waypoint graphs, hand-placed points connected by known-clear links. For my endless runner, a grid was the natural fit - the world was already tile-based, so every cell became a node, blocked cells were simply removed from the graph, and each node linked to its open neighbors.
// Each walkable tile is a node; neighbors are the open cells around it.
// On a grid, "cost" to step to an orthogonal neighbor is 1,
// and to a diagonal neighbor is ~1.414 (sqrt of 2).
neighbors(cell):
for each of the 4 (or 8) adjacent cells:
if in-bounds and not blocked:
yield that cellOnce the world is a graph, "find a path" becomes the classic computer-science problem of searching a graph from a start node to a goal node - and now we can talk about algorithms.
The Family of Pathfinding Algorithms
They form a natural progression, each fixing a weakness of the last.
Breadth-First Search (BFS) explores outward from the start in rings, one layer of neighbors at a time. On a graph where every step costs the same, it finds the shortest path (fewest steps) and is dead simple. Its weakness: it treats all edges as equal, so it cannot handle terrain where some moves cost more than others (mud slower than road), and it explores blindly in every direction, including away from the goal - wasteful on large maps.
Dijkstra's Algorithm generalizes BFS to weighted graphs. Instead of counting steps, it tracks the cheapest known cost to reach each node and always expands the cheapest-so-far node next. It guarantees the true shortest path even when edges have different costs, which is why it underpins everything from game maps to GPS routing. Its weakness is the same blindness as BFS: it has no notion of where the goal is, so it fans out in all directions equally and can explore an enormous number of nodes before stumbling onto the target.
Greedy Best-First Search attacks that blindness. It uses a heuristic - a cheap estimate of the remaining distance to the goal - and always expands the node that looks closest to the target. This makes it fast and goal-directed, charging straight toward the destination. But it is greedy in the bad sense: it only considers distance-to-go and ignores the cost already paid, so it happily walks into a dead end or takes a longer route that merely started out pointing the right way. It is fast but not optimal.
A*: The Best of Both Worlds
A* (pronounced "A-star") is the algorithm that combines Dijkstra's guarantee of optimality with Greedy's goal-directed speed, and it is why it became the default for game pathfinding. The insight is a single scoring function evaluated at every node:
f(n) = g(n) + h(n)
g(n) = the actual cost of the path from the start to node n
h(n) = the heuristic estimate of the cost from n to the goal
f(n) = the estimated total cost of a path through nAt each step A* expands the node with the lowest f. The g term is Dijkstra's honesty about the cost already spent; the h term is Greedy's sense of direction toward the goal. Together they mean A* pushes toward the target but never forgets the road it took to get there - so it finds the genuinely shortest path while exploring only a fraction of the nodes Dijkstra would.
The magic is in the heuristic. As long as h never overestimates the true remaining cost - a property called admissibility - A* is guaranteed to return the optimal path. On a grid, the standard admissible heuristics are Manhattan distance (for 4-directional movement) and diagonal/octile distance (for 8-directional). If h is always zero, A* degrades exactly into Dijkstra; the sharper (but still admissible) the heuristic, the fewer nodes A* touches. That tunable trade-off between speed and guaranteed optimality is what makes it so practical.
function aStar(start, goal):
open = priority queue ordered by f // frontier to explore
gScore = { start: 0 }
cameFrom = {}
open.push(start, f = h(start, goal))
while open not empty:
current = open.pop() // lowest f
if current == goal:
return reconstruct(cameFrom, goal)
for neighbor in neighbors(current):
tentative = gScore[current] + cost(current, neighbor)
if tentative < gScore.get(neighbor, INFINITY):
cameFrom[neighbor] = current
gScore[neighbor] = tentative
f = tentative + h(neighbor, goal) // g + h
open.push(neighbor, f)
return no path // goal unreachable
// Manhattan heuristic for 4-directional grid movement
function h(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)Why A* Was Right for the Endless Runner
Choosing A* for that 2017 project came down to the specific constraints of the genre.
Optimality mattered for believability. A pursuer that takes a visibly dumb, roundabout route breaks immersion instantly. A* gave me the shortest route every time, so the chasers always looked like they knew where they were going.
Performance mattered more, because it is a runner. Endless runners live and die on frame rate - the world scrolls constantly and you cannot afford a hitch. A* touches dramatically fewer nodes than Dijkstra thanks to the heuristic, so I got optimal paths at a cost the frame budget could absorb. On the tile grid, the Manhattan heuristic was essentially free to compute and kept the search tightly focused toward the player.
The grid made it a perfect fit. The game was already built on tiles, so I did not need a navigation mesh or hand-placed waypoints - the level geometry was the graph. A* on a grid with a Manhattan heuristic is close to the canonical textbook case, which also made it far easier to debug and reason about than a fancier alternative would have been.
It was the industry-proven default. When you are learning, choosing the algorithm that has powered game pathfinding for decades means the largest possible pool of references, optimizations, and battle-tested wisdom to draw on. There was no reason to reinvent when the standard tool fit the problem exactly.
How Pathfinding Balanced the Game
Here is the part I did not expect going in: adding A* did not just make the enemies smarter, it made the whole game balanced. And game balancing matters for one reason above all - it is what makes a game fun to play.
A game is fun when it sits in the sweet spot between too easy and too hard. Too easy and the player is bored; too hard and they are frustrated and quit. That narrow, satisfying middle - where the player feels genuinely challenged but always believes they can win - is called flow, and balancing is the craft of keeping the game inside it.
Before A*, my pursuers were broken in a way that made the game unbalanced in both directions at once. When they got stuck on an obstacle, the game was suddenly too easy - the player could just outrun brainless enemies that trapped themselves on walls. But when an enemy happened to spawn on a clear line to the player, it rushed in unfairly fast, and the game spiked to too hard for no reason the player could read. The difficulty was random and unearned, which is the opposite of fun.
A* fixed both ends at once. Because every NPC now took the genuine shortest route around the obstacles, the threat became consistent and legible: the pursuers were always a fair, steady pressure behind the player, never trapping themselves and never teleporting into an unfair lead. That consistency is what let me actually tune the game. Once enemy behavior was predictable, difficulty became a set of dials I could turn:
Levers I could balance once pathfinding was reliable:
- enemy movement speed (relative to the player's speed)
- how often NPCs re-plan (chase responsiveness vs. giving
the player room to juke)
- obstacle density (more walls = more escape routes)
- number of pursuers (raising pressure smoothly over time)The key insight: you cannot balance a system you cannot predict. Random, buggy AI cannot be tuned, because every playthrough behaves differently. By giving the enemies reliable, optimal movement, A* turned enemy difficulty from noise into a controllable variable - and only then could I dial the game into that fun, fair, "just one more run" zone that an endless runner lives on. The obstacles helped too: because both the player and the pursuers had to route around them, the walls became the player's tool for escape, giving skilled players a way to earn distance through clever movement rather than raw speed. That is balance you can feel - the game is hard, but every death feels fair, and every escape feels earned.
What I Would Add Today
The core would stay A*, but with the optimizations real games layer on top. Recomputing a full path every frame is wasteful when the target only drifts a little - so you throttle re-planning, or reuse and repair the previous path. For many units sharing one destination you would use a flow field (compute the direction-to-goal once for the whole map, and every unit just reads its cell) instead of running A* per agent. And you would smooth the raw grid path, which zig-zags along tile edges, into natural-looking movement with steering. But every one of those is a refinement around the same idea: represent the world as a graph, and let f = g + h find the way through.
The Takeaway
Pathfinding is where game AI stops being abstract and starts looking alive. The decision layer chooses the goal; A* is what makes the character reach it convincingly. Understanding the progression from BFS to Dijkstra to Greedy to A* is really understanding one question asked four ways - how do you search a graph efficiently when you have information about where you are trying to go? A* is the answer that has held up for over fifty years, and building it into that endless runner in 2017 taught me more about elegant algorithm design than any lecture ever did.