Pathfinding Algorithms Explained

Most explanations of AI start with something abstract: a neural network diagram, a loss function, a wall of matrix notation. That is not where AI started, and it is 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.

Below is a small stealth puzzle. A grid, an entrance, an exit, and guards on fixed patrols with vision cones. An algorithm plans a route, walks it tick by tick, and if a guard spots it, the level resets and it tries again with that death remembered. Watch a few attempts before reading on.

Pick a level, pick an algorithm from the dropdown, and watch it go. Failed attempts leave faint trails. Switching algorithms clears that level's memory. For animations and full write-ups of each algorithm, open the algorithms index.

The problem is the clock, not just the maze

A static maze is easy. What makes this harder is that danger moves on a schedule. A tile that is safe at tick 6 may be lethal at tick 10. States are (x, y, tick), not just (x, y). You cannot stand still: every tick must spend itself on a real step.

Guards loop, so danger repeats every period ticks. Learned deaths are stored as "x,y,phase" where phase = tick % period. The same square can be banned at one phase and free at another. Surviving a square does not store a "safe" fact. Only deaths grow the calendar. A* Search has the clearest worked example of that retiming.

Three categories, and why they exist

Every option in the dropdown solves the same space-time problem. The category answers one question: what information shapes the next decision? Browse them all as a grid of animations on /algorithms.

Naive

No graph search. Each tick follows a local rule.

• Random Walk picks a safe neighbour at random.
• Wall Follower keeps a hand on the wall.
• Potential Fields rides attract/repel forces.

They can still respect learned death phases (those cells are simply not legal picks). They never plan a full route.

Uninformed search

Real search over space-time states, but blind to where the exit is. Order comes only from the frontier structure.

• Breadth-First Search uses a queue and finds the fewest-ticks legal path.
• Depth-First Search uses a stack, finds a route if one exists, and rarely finds a short one.
• Iterative Deepening Depth-First Search repeats depth-limited Depth-First Search with rising limits.
• Bidirectional Search searches from both ends and meets in the middle.

Informed search

Search that orders expansion using extra knowledge: path cost, distance to the exit, or both.

• Dijkstra's Algorithm expands lowest accumulated cost (including soft patrol risk), still without aiming at the exit.
• Greedy Best-First Search expands whatever looks closest to the exit and ignores sunk cost.
• A* Search combines cost-so-far with distance-to-go. That is the default for a reason.
• Jump Point Search skips boring straight runs on grids.
• Theta* allows any-angle shortcuts when line of sight is clear.
• D* Lite is built for replanning when the map of danger grows.

Sampling / stochastic

• RRT / RRT* grows a random tree through free space.
• Monte Carlo Tree Search scores moves by random rollouts.

Learning

• Learning Real-Time A* updates heuristics from what went wrong.
• Q-Learning learns action values across attempts.

Constraint search

• Conflict-Based Search adds bans when a plan conflicts with the death calendar, then replans.

Browse animations for all of them on /algorithms.

How learning feeds the next attempt

None of the planners get to read vision cones during planning. Attempt 1 assumes the walkable grid is safe. It plans, walks, and often dies. The engine then stores the catching cone at that patrol phase and runs the same algorithm again. Same rules, bigger blacklist.

That is why the attempt counter climbs: each fail buys calendar facts, not a different algorithm. Soft risk (Dijkstra's Algorithm / A* Search) is separate. It only nudges preferences. Hard bans from deaths remove edges entirely.

Build your own level

The pathfinding level editor lets you paint a grid, place entrance and exit, add guards with patrol or loop routes, pick an algorithm, and share the result as a link. The Learn more link next to each algorithm opens its page under /algorithms.