Route Finding

This week, I will be discussing the algorithms that go into route finding. As someone that has always been very interested in maps in general, the application of route finding to a problem such as finding the fastest way to get from point A to point B is very appealing. In fact, one of the things that bothers me more than it should is that throughout the Richmond campus, there are many routes that seem to be equally fast, so you can never be sure that you're going the best way.

In a programming world, route finding becomes simpler when the routes are reduced to a more regimented, grid-related structure. Take this example from Khan academy, for instance:


In this picture, a maze has a goal (the red square) and the yellow circle, which began the maze at the square labeled 8 on the bottom of the maze (it is a simulation and I couldn't take the picture in time). When a user inputs the goal square, the program then maps backwards from that square. The square directly to the right of the red square is one unit away, then above and below that square are two units away, and so on. It has to take this incremental approach because a direct calculation of the distance between the circle and the goal would ignore the gray walls of the maze. The end result is that the program reaches the yellow circle from the red square more quickly by going "down" than it would have by going "up," so that is the path the circle takes.

In the context of maps, route finding just becomes more complex and difficult to calculate, but follows the same principles. Using this screenshot of the Richmond campus, we can trace out a route from Sarah Brunet Hall to the target similarly.



From the target, the gray circle at the bottom, a program could trace .01 mile increments. It would likely reach the fork in the road in one or two increments, then continue to add the same increment around the loop. It would also explore options such as Ryland Circle, but this would obviously be irrelevant to the end goal. Letting Google Maps do the calculations, we find that the fastest route is:





https://www.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/route-finding
https://www.google.com/maps/@37.5774941,-77.5373498,16.76z