Pathfinding Algorithms Explained

Most explanations of AI start with something abstract: a neural network diagram, a loss function, a wall of matrix notation. That's not where AI started, and it's not the easiest place to build intuition either. Long before anyone trained a model, computer science already had a working definition of "intelligent behaviour": search a space of possible actions, and pick the one that gets you to a goal. Pathfinding is that idea in its purest, most watchable form.

I wanted a demo that made this concrete rather than theoretical, so below is a small stealth puzzle. A grid, an entrance, an exit, and one or more guards patrolling a fixed route with a cone of vision. An algorithm plans a route, walks it tick by tick, and if a guard spots it, the level resets and it tries again, remembering exactly what went wrong. Watch a level run through a few attempts before reading on. It'll make the rest of this post a lot more concrete.

Pick a level, pick an algorithm from the dropdown, and watch it go. Every failed attempt leaves a faint trail on the grid, the current attempt draws a bold one, and switching algorithms wipes the level's memory and starts over. The rest of this post is about what's actually happening inside that loop.

The problem isn't the maze, it's the clock

A static maze is a solved problem. Breadth-first search finds the shortest route through a fixed grid in the time it takes to read this sentence. What makes this demo harder, and more representative of real pathfinding problems, is that the obstacles move on a schedule.

A guard walking back and forth means a tile that's safe right now might not be safe two seconds from now, and a tile that's dangerous right now might be perfectly safe in five. The question isn't just "which tiles are open?" any more. It's "which tiles are open, and when?"

The standard trick for this, used in everything from warehouse robot fleets to multiplayer game AI, is to stop thinking of the grid as two-dimensional. Add time as a third axis. Instead of a state being just (x, y), it becomes (x, y, tick). Moving from one cell to an adjacent one costs one tick. Standing still costs one tick too, because waiting is a valid move, and often the only safe one. Suddenly "avoid a moving guard" is just an ordinary graph search over a bigger graph, with time baked into the definition of what "reachable" means. This is sometimes called a space-time A-star or cooperative pathfinding approach in the literature, and it's exactly what the algorithms below are running underneath the hood.

Because the guards in this demo patrol on a fixed, repeating loop, the whole system has a period: the number of ticks before every guard is back exactly where it started. The search only ever needs to reason about time modulo that period, which keeps the state space small enough to explore instantly, even inside a browser tab.

Four algorithms, one search

The demo's dropdown lets you swap the algorithm without changing the level. All four are solving the exact same space-time graph. What differs is the order they explore it in, and that difference is the entire point of learning more than one.

Breadth-First Search (BFS)

BFS is the simplest correct answer to "find the shortest path." It explores every state one tick away from the start, then every state two ticks away, and so on, using a plain first-in-first-out queue. It never needs to know which direction the exit is in, and it never weighs one route as "better" than another beyond tick count.

function bfs({ start, isGoal, neighboursOf }) {  const queue = [start];  const visited = new Set([stateKey(start)]);  const cameFrom = new Map();
  while (queue.length > 0) {    const current = queue.shift();    if (isGoal(current)) return reconstructPath(cameFrom, current);
    for (const next of neighboursOf(current)) {      const key = stateKey(next);      if (visited.has(key)) continue;      visited.add(key);      cameFrom.set(key, current);      queue.push(next);    }  }
  return null;}

Strengths: Dead simple, and guaranteed to find the fewest-ticks route. Weakness: it has no concept of risk. If the fastest route happens to idle one tile away from a guard's patrol lane, BFS won't care, because "fewest ticks" is the only thing it's optimising for.

Dijkstra's Algorithm

Dijkstra generalises BFS to graphs where edges can cost different amounts, exploring states in order of total accumulated cost using a priority queue instead of a plain queue. In this demo, every move still costs one tick, but I added a small extra cost for stepping into a tile within a guard's maximum patrol range, even if that guard can't currently see it. That's not part of the hard safety rule, just a soft preference for keeping distance.

On a grid where every edge costs exactly the same, Dijkstra and BFS would find identical routes. The moment you introduce any kind of weighting (patrol proximity here, but it could just as easily be "difficult terrain" or "fuel cost" in another domain) Dijkstra starts finding routes that trade a few extra ticks for a wider berth around danger. That's the whole reason it's worth learning even though it looks like "BFS with extra steps": it's the general-purpose version, and A* is built directly on top of it.

Greedy Best-First Search

Greedy throws away accumulated cost entirely and expands whichever state is closest, in a straight line, to the exit. It's often fast to find a path, because it beelines toward the goal rather than exploring outward evenly like BFS does. The catch is in the name: it's greedy. It never reconsiders a choice based on what it cost to get there, which means it can walk straight past a cheaper, safer option because a slightly closer tile looked more tempting in the moment.

In this demo, Greedy is usually the fastest algorithm to plan a route, and also the one most likely to hug a patrol lane, because "closer to the exit" and "closer to a guard" are often the same direction.

A-Star Search

A-star, almost always written A*, is Dijkstra and Greedy fused together: it expands the state that minimises cost-so-far + estimated-cost-to-go. The first half keeps it honest about what a route has actually cost so far (patrol proximity included); the second half keeps it aimed at the exit instead of wandering. That combination is why A* is the default choice for pathfinding in shipped games, GPS routing, and robot motion planning: it's provably optimal (given a heuristic that never overestimates, which straight-line distance is), and in practice it explores dramatically fewer states than Dijkstra to get there.

function aStar({ start, isGoal, neighboursOf, cost, heuristic }) {  const open = new MinHeap();  const gScore = new Map([[stateKey(start), 0]]);  open.push(heuristic(start), start);
  while (open.size > 0) {    const current = open.pop();    if (isGoal(current)) return reconstructPath(current);
    for (const next of neighboursOf(current)) {      const tentativeG = gScore.get(stateKey(current)) + cost(current, next);      if (tentativeG < (gScore.get(stateKey(next)) ?? Infinity)) {        gScore.set(stateKey(next), tentativeG);        open.push(tentativeG + heuristic(next), next);      }    }  }
  return null;}

That's the default selected in the demo above, and it's a reasonable default for you too: reach for A* first, and only drop to something simpler if you have a specific reason to (a uniform-cost graph where BFS is just as good and easier to explain, for instance).

How it learns without a reward function

Here's the part that ties this back to AI more broadly rather than just "graph search with extra steps." None of the four algorithms above ever gets to look at a guard's vision cone directly. They only ever avoid a specific (x, y, tick-in-cycle) combination if a previous attempt actually got caught there.

The first attempt on a fresh level assumes the whole grid is safe, because nothing has been learned yet. It plans the fastest route, walks it, and if it steps into a cone, the level resets. But it doesn't just remember "I got caught at that one tile." When a guard spots the player, the demo reconstructs that guard's entire vision cone at that exact moment in its patrol cycle, and marks every tile inside it as unsafe at that phase. The next attempt replans with that knowledge subtracted from the graph, and it either finds a different route or waits a beat longer before crossing.

That loop, try, get caught, learn precisely what caught you, try again with that lesson folded in, is the same shape as the trial-and-error loop that sits underneath reinforcement learning, just without a neural network doing the remembering. It's why the attempt counter in the demo climbs for a few tries before a level solves: each failure is buying real information, not being wasted.

This is also a fair place to be honest about where the analogy ends. What's running in your browser is deterministic search over a graph with known rules: the grid, the guards' patrol routes, and the vision-cone geometry are all fully specified up front. Reinforcement learning earns its keep when you don't have that luxury: when the rules of the environment aren't fully known, when there are too many possible states to search exhaustively, or when "correct behaviour" has to be discovered from reward signals rather than read off a rulebook. A goal-conditioned DQN training against a stealth level over hundreds of epochs (a good search term if you want to go down that path) is solving a harder, blurrier version of the same problem this demo solves by search in milliseconds. Search first, learn when search stops being tractable, is a genuinely useful rule of thumb.

What the vision cones are actually checking

The cones aren't just decoration. Each one is built by casting a fan of rays out from the guard, at the angle it's currently facing, and stopping each ray the instant it hits an obstacle. That gives every guard a vision cone that's correctly cut off by cover, which is also exactly why the obstacle blocks in these levels matter for more than just blocking movement. Stand behind one and a guard looking straight at you simply can't see you.

The player is "spotted" when its position falls inside that same cone shape, using an ordinary point-in-polygon test. That means the visual cone you see on screen and the thing that actually catches the player are the same computation. Nothing is faked for the animation; if it looks like the cone reaches you, it did.

Why the tick rate matters more than it looks

One detail that's easy to undersell: the whole simulation runs on a shared clock. The player moves one cell per tick, and every guard moves exactly one cell per tick too, on the same schedule. That's a deliberate constraint, not a performance shortcut. It's what turns "avoid the guards" into a clean, deterministic search problem in the first place. If guards moved at their own pace, or continuously rather than in discrete steps, you'd need to model the world with real-valued time and interpolate collisions, which is a substantially harder problem (and a much more expensive one to search).

The tick speed in the demo is tuned to be fast enough that you can watch several attempts play out in the time it takes to read a paragraph, but slow enough to actually see the guard's cone sweep past a near miss. That balance is worth paying attention to if you're ever building something similar: a simulation that's technically correct but too fast to observe teaches you nothing, and one that's accurate but glacial won't hold anyone's attention long enough to learn from it.

Where this shows up outside of games

It's tempting to file "grid, guards, cones" under game mechanics and move on, but the space-time search underneath is doing real work in places that have nothing to do with games. Warehouse robots plan routes through a shared floor full of other moving robots the same way: expand the grid with a time axis, and forbid two robots (or a robot and a hazard) from claiming the same space-time cell. Multiplayer game AI uses it to route non-player characters around each other without collisions. Airport ground traffic control and elevator scheduling are, structurally, the same problem with different obstacles.

The reason to actually learn BFS, Dijkstra, Greedy, and A* isn't to hand-roll pathfinding into your next side project, most engines and libraries already give you a good implementation. It's so that when you hit a search problem in the wild (and "find the best sequence of actions given constraints" shows up far more often than it looks), you recognise the shape of it, and you know which of the four trade-offs you actually need.

Play with the demo above a bit more if you haven't already. Try the same level with Greedy and then A*, and watch how differently they treat the same guard. That difference in behaviour, not the definitions, is what actually sticks.