Article Preview
Buy Now
COLUMN
Path-Finding
Issue: 1.5 (April/May 2003)
Author: Joe Strout
Author Bio: Joe Strout once got lost on his way to work at REAL Software, and wished he had a path-finding algorithm handy.
Article Description: No description available.
Article Length (in bytes): 28,587
Starting Page Number: 15
Article Number: 1510
Resource File(s):
1510.zip Updated: 2013-03-11 19:07:56
Related Link(s): None
Excerpt of article text...
Imagine you're in a dense forest, tired and hungry from a long day of hiking. Most of the underbrush is impassable, so you're forced to stick to the trails. All you want is to get back to the lodge as quickly as possible. Fortunately, you have a trail map. So it's no problem: you simply look at the map, identify the shortest route, and off you go.
But that's because you're human. We're very good at problems like this; while you may not identify the absolute shortest route, you'll identify a very short one, without spending hours considering all the possibilities.
Computers, on the other hand, have no such natural ability. Yet it's quite likely that sooner or later you'll have to program a computer to solve this exact problem, or one very much like it. These path-finding problems turn up in nearly every modern type of computer game, whether it's finding a route through a deadly minefield or simply navigating from one room to another. If computer games aren't your thing, keep reading anyway; it turns out that a great variety of other problems, which seem quite dissimilar on the surface, can be addressed with the very same techniques.
General Approach
In general terms, a problem consists of a set of states, with operators that move from one state to another. For path-finding in particular, the state is simply what location you're in. In this article, we'll be searching for a path on a rectangular grid of cells which may be either passable or unpassable; each cell on the grid represents a potential state of the problem. We can represent any state with the row and column numbers of that cell.
...End of Excerpt. Please purchase the magazine to read the full article.