Route-finding
We'll cover the following...
Sometimes, very different-sounding problems turn out to be similar when you think about how to solve them. What do Pac-Man, the royal family of Britain, and driving to Orlando have in common? They all involve route-finding or path-search problems:
How is the current Prince William related to King William III, who endowed the College of William and Mary in 1693?
What path should a ghost follow to get to Pac-Man as quickly as possible?
What's the best way to drive from Dallas, Texas to Orlando, Florida?
We have to be given some information to answer any of these questions.
For example, a family tree of the royal family of Britain would show connections between people who were directly related. Prince William is the son of Charles Philip Arthur Windsor. Charles is the son of Queen Elizabeth II. The problem is to find a short chain on the family tree connecting Prince William and William III, using these direct connections. As you can see from the tree below, it might take quite a few connections.
For Pac-Man, we need a map of the maze. This map shows connections between adjacent open squares in the maze—or lack of connections, if there is a wall in between—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
In order to find a driving route from Dallas to Orlando, we might use a map of the United States, showing connections, roads, between nearby cities. No single road directly connects Dallas to Orlando, but several sequences of roads do.
Exploring a maze
Let's look more deeply at something like Pac-Man, a computer game in which the main character is controlled by clicking on destinations in a maze. The game is below. Try clicking on a few locations to move the character, represented by the yellow circle, to the goal, represented by the green square.
Notice how the character moved to the goal? To make that happen, the program needs to determine the precise set of movements that the character should follow to get to where the user clicked and then animate those movements. There may be multiple paths for the character to follow, and the program needs to choose the best of those paths.
Before deciding on an algorithm, the movement rules first need to be established: walls are made of gray squares and legal locations to travel are empty. In each step, the character can ...