Pathfinding

I covered the subject of pathfinding in games in an recent article for PC Extreme some time ago. For anyone that is interested, here are the two demo programs I wrote to go with it: pathfinder1.zip and pathfinder2.zip.

Pathfinding is a technique used to find a path from one point to another. You have all seen games where you can direct characters on a map, like those RTS games where you control army units, or you have to build a city. You send workers out to get resources, explore the map, battle with enemy units and so on. You click a game character, then right click on the map and it goes there. It walks around mountains, lakes, forests and buildings, until it gets there. This is pathfinding. Bots in games like Quake and Half Life use pathfinding too, so they can find their way from one place to another.

I don't want to repeat the article here, but basically, you divide the map up into squares. For each square you work out:

F = G + H

G is the number of steps you have taken from the start (number in bottom left corner in the diagram), and H is the number of steps to the destination ignoring any obstructions (bottom right corner in the diagram). F is the sum and the path is the squares with the lowest F value. Try the programs and see for yourself. It's a fascinating subject.