Pathfinding has been with us for a very long time. From Marco Polo to Christopher Columbus, the adventures and misadventures of getting from one place to another have been turning points in history. As it turns out, being able to navigate from one point to another is a really useful thing to be able to do – and so, computer programmers have figured out a way (in fact, many ways) to do it using computers. You probably use these algorithms all the time. Every time you get directions from Waze or Google Maps, you’re using a pathfinding algorithm that probably works very similarly to this simple example.
Consider a grid, like a chessboard. Imagine yourself put on one of these squares, and told to find a path to some destination square. You know what direction it’s in, so you start walking towards it. If you hit an obstacle, you try to walk around it, and eventually you reach your goal. Computer scientists call what you just did a Greedy Best-first search – at every step of your process, you tried to get as close to your goal as you could, based on some guess of which steps would take you closer. This got you to the destination eventually, but you probably spent a lot of time finding your way around obstacles.
Let’s try this example again, but this time, you want to avoid knocking into any walls. Instead of immediately finding your goal and moving towards it, you instead start searching the tiles around you. Because you want to walk as little as possible, you explore the squares closest to your starting point, and explore outwards in this fashion until you find your destination. This gets you a shortest path (for there may be many equally short paths) towards your goal. We in the computer business call what you just did Dijkstra’s Algorithm (no, I can’t help you pronounce that, but Wikipedia can). It got you the best path, but you spent a lot of time exploring.
On your third attempt at this maze, you decide to combine the approaches of your first two attempts. You want to explore tiles before traversing them to avoid obstacles, but you also don’t want to waste time looking at tiles that aren’t going to help you get closer to your destination. This time, you consider both how far you are from your destination and from your goal when you decide on your final path. This is the secret to the algorithm known as A* (pronounced “A Star”). By looking at both your starting point and destination, you can be both fast and find an optimal path.
A* works using what computer scientists call a Heuristic. This algorithm’s heuristic is the same one that you were using in the first example – how far do I think I am from my destination. For every tile you looked at in example one, you estimated how far it would be to your destination. For every tile you looked at in example two, you could easily see how far it was from your starting point. In example 3, you can say that you added the two numbers together. For every tile you looked at, you combine how far you are from your starting point with how far you think you are from your goal. You can see then that if that number is small, you’ve found a short path (i.e. if you are close to both the start and end). The beauty of A* is that it lets you customize the parameters of your search. If you always take the distance to the destination to be 0, then you’re only looking at the distance to the start (this is Dijkstra’s Algorithm). If you take the distance to the origin to always be 0, then you’re only looking at the distance to the goal (Greedy Best-first). The smaller you estimate the distance to the destination to be, the more time you spend searching but the better your final path. The larger your estimate of the distance to the destination is, the less time you spend searching, but your search takes less time. This ability to customize the algorithm makes its utility clear.
My implementation of A* was done on a 2D grid, on which we generated a maze using Recursive Backtracking and then knocking out some random walls. The maze itself was a class, which stored the maze as a 2D array of GridCell objects, which each had a location on the grid, a randomly generated inherent cost, amd an array storing booleans representing walls on each side. After generating, the Maze object would then make a new instance of the AStar class, which ran on the Maze. The implementation used Java’s built-in Priority Queue, which organized gridCells yet to be looked at by their heuristic cost.
The process of conversion was, to put it mildly, quite a challenge. This was my first time working in JavaScript, and dealing with the differences between it and Java were quite difficult. JavaScript, unlike Java, is an interpreted functional language with weak typing. What does that mean? Java is a compiled language. Whenever I want to run it, I have to translate (compile) it into a form that can run on my JVM. JavaScript, however, is interpreted – browsers load the source code, then look at it and execute it line by line. Java is what we call an object-oriented language. Everything in Java is an object, which we can assign properties to and make instances of. For an example, if you were to describe your house in Java, you might have a “chair” class, and every chair in your house would be an instance of that class. JavaScript is functional – everything in it is a function under the hood. This makes it difficult to use the same ideas as real life – where things are “objects” that share certain properties, it makes many other tasks much easier, and lets you modify your program when it runs in ways that you can’t with Java. Another difference between Java and JavaScript is that JavaScript has many fewer built in functions and data types. This meant that I needed to implement the Priority Queue and the Stack data types myself, but fortunately that wasn’t too hard, as JavaScript has a lot of useful functions of its own that can be run on an array.
For the sake of time and my sanity, my conversion was fairly simple. Rather than completely rewrite the algorithm from scratch, I instead altered my syntax and changed some structures until it ran without throwing errors. Though unoptimized, it let me get the job done in a timely manner.
Thanks for reading, and fly safe!
You can try out my A* implementation in glorious fullscreen by going to https://theocoulson.com/stuff/code/AStarJS/ and pressing Space to start. Use the arrow keys to change the dimensions of the maze. Enjoy!
