A* algorithm

Instructions

Click and drag on everything!

Click on a wall to destroy it (and drag around to destroy multiple walls). Clicking on an empty space allows you to rebuild walls (again dragging builds lots of walls)!

The start and end can be dragged around as well!

What is the A star algorithm?

The A* algorithm is a path finding algorithm that finds the shortest path from some position to some goal. In this case the start is the green square, and the end is the pink square.

In the demonstration above the algorithm only explores the squares that get coloured in. These explored squares come in two different types. Frontier squares (pink) and closed list squares (blue).

In simple terms, the pink squares are ones that the algorithm may explore in the future, while the blue squares are ones that have been fully explored and won’t be returned too.

A* as a metaphor

Every day you take public transport to work, and need to walk the last little bit to work. You do this every day (you work really hard) and want to figure out the shortest path.

One day you’re sick of approximations, and decide to figure out the shortest path once and for all. You open google maps, grab a bunch of sticky notes, and uncap your permanent marker.

You will use google maps to get a distance from your position to the end. (Conveniently, Google maps uses Manhattan distance)

You’ve also come up with a brilliant way of knowing if your path is the shortest.

On your sticky note you’ll write 3 numbers.

• A number representing how far you’ve walked so far, let’s call it g.
• Another number showing how far Google Maps says you are from the end, calling this one h.
• A big number in the middle, which is the addition of the two number… called f.

Starting at the train station, you stick a note on the ground with the following values:

Imagine you stand at starting point holding a magic compass. This compass tells you what direction your goal is as well as how far your goal is from you.

You are also really obsessed about getting the absolute shortest path to that goal. Luckily you’re carrying a bunch of flags and a permanent marker.

You are a genius and have developed a system that will ensure you the shortest path.

Making of A*

Currently I’m enjoying the MIT OpenCourseware Artificial Intelligence course and have found the concepts presented clear. But making it definitely presented challenges. Here are a couple questions I had to answer and work out while creating the A star demo above.

What would you choose?

• How to represent the grid?
  • 2D array
  • linked list
  • tree / graph structure
• How to store the closed nodes (fully explored nodes) vs the fringe nodes (nodes we want to explore soon)?
  • plain old array
  • hash map
  • linked list
  • priority queue
• How to represent walls?
• What’s an admissable enough heuristic?
  • Euclidean distance
  • Manhattan distance

Mistakes

Initially I tried to generate a 2d array of the game board, each node storing the parent node as well as the f, g, and h weights. This was a failure because mutating the game board didn’t allow me to update fringe nodes with potentially better paths.

It ended up being far easier to just create a linked list of nodes that referenced their parent. Once the path was found, I could recursively trace the path back to the root.

This allowed me to store the walls in a dictionary or Map. The algorithm could check the Map to discover if a path was blocked, and simply not offer those nodes.

My heuristic was initially used euclidean distance, which was inadmissable due to a strict 4 directions of movement. Manhattan distance (|delta x| + |delta y|), solved the problem.

I stored the closed list in a Map, allowing me to quickly query for nodes. The open list always needed the most promising node to be at the top. An initial problem was that the min-heap would stop bubbling up if the weight was ==. This lead to a problem where if there were multiple nodes with the same weight, the node just placed would not be chosen. Often it is useful that the most recent node bubbled to the top, thus the min heap was changed to reflect this.

Feedback welcome at my twitters: @spyr1014