## 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

- If the neighbor is traversable and
- 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

Cancel reply to comment