If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Route-finding

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

Maze games are fun, so let's delve deeper into one. In our game, the main character can navigate to destinations in a maze. As the human player, you control the main character by clicking on the next destination in the maze, and the computer figures out how to move the character there. The destination is marked with a red rectangle labeled "GOAL", and the character starts off on their first destination, the start square. Try playing it below:
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 move from one square to an adjacent square. This character, like a chess rook, cannot move diagonally.
Here's the idea behind the algorithm that this program uses: move 1 square closer to the goal—the place the user clicked on—in each step. But what does "closer to the goal" mean? Traveling in a straight line toward the goal will often cause the character to smack into a wall. The algorithm needs to determine which of the surrounding squares are indeed "closer to the goal", and we can do that by assigning a "cost" to each square that represents the minimum number of steps the character would have to take to get from that vertex to the goal. Here's an algorithm for assigning a cost to each square:
  1. Start on the goal square. How far is the goal from the goal? Zero steps, mark the goal with the number 0.
  2. Find all squares in the maze that are exactly one step away from the goal. Mark them with the number 1. In this maze, if the goal is the exit square, then there is only one square that is exactly one step away.
  3. Now find all squares in the maze that are exactly two steps away from the goal. These squares are one step away from those marked 1 and have not yet been marked. Mark these squares with the number 2.
  4. Mark all squares in the maze that are exactly three steps away from the goal. These squares are one step away from those marked 2 and have not yet been marked. Mark these squares with the number 3.
  5. Keep marking squares in the maze in order of increasing distance from the goal. After marking squares with the number k, mark with the number k, plus, 1 all squares that are one step away from those marked k and have not yet been marked.
Eventually, the algorithm marks the square where the character starts. The program can then find a path to the goal by choosing a sequence of squares from the start such that the numbers on the squares always decrease along the path. If you view the number as the height of the square, it would be like going downhill.
You can play through the cost-marking algorithm below. Click "Restart algorithm" to start the steps over.
What if the user were trying to get from the start square to the goal? Using the square-marking algorithm, the start square is 13 steps away from the goal. Here's a picture showing the connections between possible locations for the character, the start, the goal, and the shortest distance of each location from the goal:
There's a square immediately to the south of the start that is only 12 steps from the goal. So the first move is "south". South of that square is an 11. South again. South again to a 10. Then east twice to an 8. North to a 7, east to a 6, then north five times to a 2. Finish up by going west once, to a 1, and finally north once, to the goal.
We won't discuss exactly how to implement this maze search algorithm right now, but you might find it fun to think about how you might represent the maze and the character using JavaScript and how you might implement the algorithm.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Want to join the conversation?

  • ohnoes default style avatar for user Sankaran Rajendra, Kabir Krishna R
    what do you think the best language is
    (0 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Rob Griffin
      No such thing. It varies by what you want to do with programming.

      If you're some kind of funky systems developer, C or Assembly
      And if you want some kind of insane swiss-army chainsaw, then Perl or Common Lisp.
      That being said, Clojure's access to Java libraries is pretty nice. Too bad those three look like a cat walked on your keyboard until you become a powerful lisp wizard.
      (13 votes)
  • leaf green style avatar for user Zihad Tarafdar
    what if I reverse the counting process, i.e setting the origin as 0 and keep adding marks until I find the goal, thus climbing uphill ? Is there any downside of this?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      You can start from the origin and work towards the goal, but reconstructing the path becomes more difficult. If we started from the origin and worked out we would have:
      ************* G  *****
      **10 11 12 11 **
      ** 9 *********** 10 **
      ** 8 ** S ** 10 9 **
      ** 7 ** 1 ***** 8 **
      ** 6 ** 2 ** 6 7 **
      ** 5 4 3 4 5 6 **
      **********************

      If we move the circle towards the next higher number we come to a problem when we reach 3, because we don't know which 4 to take.

      One way to resolve this is to also record in every square which path it took to get to that square. When the numbers reach the goal, we send a copy of the path we recorded in the goal square to the circle. The circle now knows which path to take.

      Hope this makes sense
      (15 votes)
  • blobby green style avatar for user christian  walker
    a meme algorithm would be so cool, wouldn't it?
    (10 votes)
    Default Khan Academy avatar avatar for user
  • primosaur seed style avatar for user Jack C
    Under "route finding", is there a more efficient way of marking the squares if the maze is very large? Effectively testing every possible route sounds like it would be quite slow.
    (8 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Michael Rueben Rivers
    Can this example also explain how a "Ghost" from Pac-Man can track him? Using the cost-marking algorithm with Pac-Man as the Final Cost/Destination?
    (6 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Hao Li
    If the general direction is given , in what way can we better this algorithm?Because it'll be faster with a (x,y)coordinate of each point .
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leafers seedling style avatar for user Peter
    The example is given for a "known" maze. How would one implement an algorithm for a maze that is not known at the start? (always follow the left or always follow the right are the usual rues, but they can fail if there are "blocks" you can go right round while still inside the maze)
    (5 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Daniel Eppley
      What do you mean 'known'? Even if you randomly generate a maze, you can still make it so that the computer recognizes all blocks and points. Also, with this algorithm, the code decides the most efficient way to the finish, so it is required that the maze is 'known' to execute the algorithm. Otherwise, to make the strategy that you said (holding on to one side of a wall), you could generate/make a maze and have the code move a player throughout a maze, turning left or turning right whenever possible.
      (1 vote)
  • blobby green style avatar for user 2T48004U
    Should a person learn J.S before taking computer science? That just seems strange? So far Ive been told through seminars and such that I should learn HTML/CSS then j.s, thought refreshing my computer science would be beneficial, but this is telling me that I should already know j.s by the way its constantly speaking about it like I should already know it. What's the deal?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      I would suggest learning to program before taking computer science. Most computer science analyzes programs. It is hard to analyze something if you haven't done it before, or don't really understand it.

      Java Script is just one of many programming languages. Most programming languages are similar to Java Script. So, if you learn how to program in it, you will have a general understanding of how programming works. After you are comfortable with it, you should be ready for computer science.

      HTML/CSS are not programming languages. They are what are called mark up languages. They are really only useful if you want to make web pages. HTML tells a browser what content a web page contains, and CSS tells the browser what style (color,size,italics,bold) certain elements in the HTML should use when it sees them.

      Learning HTML/CSS probably won't help you learn how to program, but if you want to make web pages it is good to know. The normal way to put programs in web pages is to use Java Script. So, if want to make web pages that do interesting things using programs, then learning Java Script + HTML/CSS would be a good way to do that.

      A course on Javascript programming is here:
      https://www.khanacademy.org/computing/computer-programming/programming#intro-to-programming
      (5 votes)
  • duskpin ultimate style avatar for user Amani Mckenzie
    wow,thats very intresting
    (5 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user shghorsi
    what are the basic steps that we need to write an algorithm
    (7 votes)
    Default Khan Academy avatar avatar for user