Maze solving with A* visualized

I've been interested in getting into AI a little bit more, since I rarely get a chance to do it in my day job. One of the most fundamental algorithms in AI is the A* algorithm. It's very similar to other shortest distance algorithms. It uses a directed graph and traverses it, then decides where to go next based on the estimate cost of the entire path.

A* adds something small but it has a huge effect. It adds the ability to add a heuristic when evaluating paths. It is essentially a "best guess" for any given state.

In the context of solving mazes, this can take several forms. The maze in the example of above always starts at the top left and ends and the bottom right. The black squares are randomly generated obstacles. Since the goal is known, a good guess is if the next move brings you closer to the bottom right. The edge case being that obstacles could corner you and then you'd have to backtrace.

The algorithm always ends up in the same place, regardless of the heuristic you use. However, it can change the path you take to get their. It is primarily helpful for arriving at a correct situation faster. By programmatically guessing which paths are likely to be more correct, you save a lot of execution time.