How does an enemy find its way around a wall? Pathfinding and A* explained

Walk an enemy toward you in a straight line and the first wall ruins it. It presses its face against the brick and stays there. Games solve this with pathfinding: a method for finding a route around obstacles. If you want to make your own game, it is one of the first things you will meet, and the idea behind it fits in your head.

The map is a grid of squares

A computer does not see a room. It sees a list of squares, and each square is either open or blocked. Pathfinding is a question about that list: starting here, which open squares do I step through to reach there?

In the simplest version you can move up, down, left or right, one square at a time. Every step costs the same, so the best route is simply the one with the fewest steps.

Try it: three ways to look for a route

The grid below starts with a wall between the green start square and the coral goal. Tap or drag on the grid to add or remove walls, then press a method and watch which squares it checks. The checked squares are the interesting part: fewer checks means less work for the game on every frame.

What you just saw

Walk straight is how a beginner's enemy often moves: always step to the neighbouring square that is closest to the target. It is cheap, and it works until the first wall. Then every neighbour is farther away, so it stops. It never plans, so it never backs up.

Check everything fixes that by being thorough. It spreads outward from the start in every direction, one ring of squares at a time, like water poured onto the map. The first time the water touches the goal, the route it took is a shortest one. The cost is that it checks squares in directions that obviously lead nowhere, such as behind the start.

A* (said "A star") is the one most games use as a starting point. It spreads out like the thorough method, but it keeps a score for each square it could check next: the steps taken so far, plus a guess of how many are left. It always checks the lowest score first, so it leans toward the goal while still going around walls. Try it on the default map, then draw a long wall that forces a detour, and compare how many squares each method checked.

The guess has to be honest

That guess is called a heuristic. On a grid with up, down, left, right moves, the usual one is the Manhattan distance: how many columns and rows lie between a square and the goal, added together, as if you walked along city blocks and ignored walls. It never claims a square is closer than it really is, and that is what keeps the route a shortest one. A guess that is too low only means more checking. A guess that is too high can make the enemy take a longer way round than needed.

What this means for your game

You rarely write this yourself at first. Engines ship pathfinding tools: Godot, for example, has grid-based pathfinding classes and a navigation system for agents, and Unity has its own navigation system. They mostly use the same ideas as above, with extras such as diagonal moves, different costs for mud or roads, and smoothing the route so characters do not walk in staircase patterns.

Two habits will save you trouble. First, do not recalculate the route every frame; recalculate when the goal moves or something blocks the way. Second, decide what should happen when there is no route at all, because the "no route exists" message above is a real case: an enemy needs something sensible to do when you hide behind a locked door.

What to look for

When you pick a pathfinding tool, check what each choice gives you. A grid is easiest to understand and fits tile-based games. A navigation mesh describes walkable areas as larger shapes, which suits open 3D levels. Either way, ask whether it handles obstacles that move, how it prices different ground, and what it returns when no route exists. Start with whatever your engine already provides, and only write your own when you want to learn how it works.