Finding A Way Back To Your Heart (With A*)

In my last article I discussed path finding using genetic algorithms.  In that article I explained that we were using a path finding problem to have fun learning GA, but that in real life we'd want to use something far better suited to the problem, such as A*.  Since most of the code was already written for the last article, I thought I'd owe it to you to give you an example of A* in action; and since any love story is really a path finding problem between two kindred spirits, why not do it on Valentine's Day?

Many of you may have learned about A* in school, as I did (back when dinosaurs roamed the Earth); it's a pretty simple algorithm used for finding the optimal path between two points, given an admissible heuristic.  It is similar to a breadth-first search algorithm in that it will end up searching all of the nodes, so if a solution exists it will find it.  To speed up the search, it uses heuristics so that only the most promising nodes are explored first.  

The key components of A* are the following:

  • HScore: Heuristic Cost - What is the estimated cost from the current node to the target?
  • GScore: Movement Cost - What was the cost of getting to the current node?
  • FScore: G + H

In our example, the heuristic cost will be the Manhattan Distance  between the current node and the target node, which makes a lot of sense for us because our maze-walker from the last article is not capable of moving in diagonals.  The movement cost will always be 1.

In English, the algorithm does the following:

  • We select the node from the open list with the smallest F score.  The open list is a set of candidate nodes (nodes that are traversable [e.g. not an obstacle] and that have not been walked yet).  The first selected node is the starting node.
  • We remove the current node from the open list and add it to the closed list. The closed list is a set of nodes that have already been walked.
  • If the current node is the target node, we can return since the problem is now solved (yay!)
  • Since we have not yet reached the target, we need to move from the current node.  We'll look at the list of the current node's neighbors and
    • If the neighbor is traversable and not in the closed list
      • Calculate the G Score and recalculate the F score 
      • If the neighbor is not in the open list, we set it's parent to the current node add it to the open list
      • If the neighbor is in the open list and has a smaller new F Score than what is stored currently, update the G and F scores in the node and set the parent to current
  • Loop to the beginning.  If the open list is empty then there is no path between start and target.

If you're interested in code, you can check out a c# implementation on GitHub.

So how much better is A* than our implementation using Genetic Algorithms?  Here's a solution path using the same maze as the last article (now with a geeky Valentine's Day theme).  It found the solution in milliseconds, whereas the GA took minutes! 

If you're interested in learning more about A*, with optimizations and tricks, check out this video series.

Happy coding and Happy Valentines Day!




Add comment