Introduction

This Summer I attended the Wolfram Summer High School Camp where I worked on implementing the A* algorithm in the Wolfram Language. I worked with Christian Pasquel as my mentor for this project.

The A* Algorithm

The A* Algorithm (pronounced "A-Star") is most often used to traverse a 2D plane of nodes in a quick and efficient manner. In this case, a node is a point on a graph. The basic pseudocode of the algorithm is shown below (Courtesy of this tutorial by Rajiv Eranki) initialize the open list initialize the closed list put the starting node on the open list (you can leave its f at zero) while the open list is not empty find the node with the least f on the open list, call it "q" pop q off the open list generate q's 8 successors and set their parents to q for each successor if successor is the goal, stop the search successor.g = q.g + distance between successor and q successor.h = distance from goal to successor successor.f = successor.g + successor.h if a node with the same position as successor is in the OPEN list \ which has a lower f than successor, skip this successor if a node with the same position as successor is in the CLOSED list \ which has a lower f than successor, skip this successor otherwise, add the node to the open list end push q on the closed list end The algorithm works by generating the nearby nodes of the node with the least cost in the open list. The cost is generated by a formula which is normally made up of two parts. The first is the distance from the start node to the current node, and the second is a heuristic as chosen by the program writer. These two values are summed and the cost is the resulting number. The implementation of the cost function in my code is shown below.

runningCost[cn_, pn_] := 
 Floor[N[(Total[goalNodeCoords - cn] + EuclideanDistance[cn, pn])] + 
   1]

The heuristic I chose, while extremely fast, is also non-admissible. This means that it does not guarantee that an optimal path is generated, only that if a path exists it will find it. I chose this heuristic over others because it made my manipulate run much smoother.

Manipulate Code

I chose to represent the algorithm on a graph generated by GridGraph[]. The closed nodes are represented by red dots and the open nodes are represented by green dots. The graph does not show the path but rather how the algorithm runs over the nodes. The larger red dots are the starting node (in the upper-left corner) and the goal node (in the lower-right corner). It is important to note that my implementation allows for diagonal movement despite an edge not being shown between two nodes diagonally. Keep this in mind when playing with the manipulate!

And here is the code:

Manipulate[
 manipExecuteAStar[ graph = genGraphV4[input, 10, 10]], 
{{input, Table[RandomInteger[{0, 1}, 10], {x, 10}]}, ControlType -> None}, 
 Dynamic[Panel[Grid[Outer[Checkbox[Dynamic[input[[#1, #2]]], {1, 0}] &, Range[10],Range[10]]]]]]

I have attached my notebook with all of my work so far on this project to the post so feel free to look at the underlying functions and play with the manipulate.

Reflection and Looking Forward

Overall, I like the way my project has shaped up. I have only just begun learning how to write in the Wolfram Language so I look forward to improving this implementation in the future. The thing that I dislike the most is the method by which you can create obstacles. The checkboxes were the only solution I could think of, but by looking over some demonstrations I have ideas of how the nodes could be directly clicked on to enable/disable them. Along with this I would like to add further functionality to my project to the point where I could submit it as a demonstration. Adding options for 3D traversals with A*, different heuristics/cost functions, allowing diagonal movement and more will all hopefully be implemented in the future.

This camp has taught me a lot about not only programming, but math and other sciences as well. I had a great time and will continue to work on this project in the months to come. If you are interested, I will be keeping the code updated here on Github. Thanks for reading!

Attachments: