- So first, we designate the starting node and the ending node. In the example picture we use A & F.
- To begin we start with the starting node. That node is then placed on the open list.
- Put simply there are two lists we use in A* Pathing to keep track of what we've stepped over and what we are considering.
- The Open List is the list that all of our currently examined node sit in.
- The Closed List is a list of all of the nodes we've stepped over or 'completed'.
- Then we calculate the connections to our starting node. For our example A only has one connection, B. but if it had more than one connection we'd calculate all of those as well. By calculating I mean that it finds the Heuristic and Cost to move to B, as well as the Estimated Total Cost it will get to the ending node.
- The Heuristic is a value for how far away the current node is from the ending node. There can be many different ways of calculating this value, but the simplest is to use a bird's path or straight line from the current node to the ending node.
- The Cost So Far is how far the node has moved from the starting node along the path. Each path has a 'distance' and as we move through the path we keep track of the cumulative amount of that 'distance' for this variable. In the example, A has a Cost So Far of Zero because it hasn't moved at all yet.
- The Estimated Total Cost is, simply put, the sum of the Heuristic and the Cost So Far.
- Once we have calculated all of the connections to A, it is put on the closed list.
- Then we figure out which of the nodes on the open list has the least Estimated Total Cost. Once we find that we continue with the steps for the node A.
- For the sake of my fingers and your eyes, we'll skip over the process for the B node since its exactly the same as A's.
- Moving onto C, we can notice that there are now two nodes it connects to. So we calculate both of those just like before and then more C onto the closed list.
- Because D has a lower Estimated Total Cost than E, our program should continue on with D and put E to the side on the open list for now.
- Then once D is done calculating and is moved onto the closed list, F is chosen next because of its still lower Estimated Total Cost than E.
- Then there's some simple logic for figuring out the end condition. The simplest way to do so would be to just have the program consider when the end node is selected but there are other end conditions where coders choose to have it so "when every node is on the closed list", that way every possibility is checked.
Now some of you might ask "But Daniel, what if E's connection to F is shorter than D's?" and the answer is simple. The way A* Pathing should work with its calculations means that if D's connection was larger, for example 7 instead of 3.5, then that would make F's Estimated Total Cost larger than E's on the open list and then we'd check E. This of course would make us reevaluate F's values and since there's no other open nodes to check we simply take F, which is the ending node and causes the ending condition.
