Path Finding (RBD1510)

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.

Oh, and please, don’t stick compasses in your eyes, ok?