Introduction to A* Pathfinding

A Non-Visionary Cat

In the example above, we saw that while the cat was finding the shortest path, he often chose the better square (the one along his future shortest path) – kind of like he was a visionary cat!

But what would happen if the cat was not extralucid and always chose the first square added to his list?

Here’s an illustration that shows what would all the squares that would have been used in this process. You’ll see that the cat tries more squares, but he still finds a shortest path (not the same as previous, but another equivalent):

The red squares in the diagram don’t represent the shortest path, they just represent the squares that have been chosen as an “S” square at some point.

I recommend looking at the above diagram and trying to go through it. This time, whenever you see a tie always choose the “worst” way to go. You’ll see that you still end up with the shortest path!

So you can see that it’s no problem to follow the “wrong” square, you’ll still end up with the shortest path even if it takes more iterations.

So in our implementation, we’ll add squares to the open list with the following algorithm:

• Adjacent squares will be returned in that order: top / left / bottom / right.
• A square will be added in the open list after all the squares that have the same score (so the first added square will be the first picked by the cat).

Here’s a diagram of the backtracking:

The shortest path is construct by starting by the final destination and go backward from parent to parent (example: at the final destination we can see that the arrow heading right, so the parent of that square is at its left).

To conclude, we can synthesize the cat process with the following pseudo code. This is Objective-C, but you could implement this in any language:

[openList add:originalSquare]; // start by adding the original position to the open list
do {
	currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score
	
	[closedList add:currentSquare]; // add the current square to the closed list
	[openList remove:currentSquare]; // remove it to the open list
	
	if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
		// PATH FOUND
		break; // break the loop
	}
	
	adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares
	
	foreach (aSquare in adjacentSquares) {
		
		if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
			continue; // Go to the next adjacent square
		}
		
		if (![openList contains:aSquare]) { // if its not in the open list
			
			// compute its score, set the parent
			[openList add:aSquare]; // and add it to the open list
			
		} else { // if its already in the open list
			
			// test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path
			
		}
	}
	
} while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)

Are you getting excited to implement this yet?! In the next tutorial, we’ll do exactly that!

Where To Go From Here?

Congrats, you now know the basics of A* pathfinding! If you want ot learn more from here, I recommend reading Amit’s A* Pages.

In the next tutorial in the series, we’ll implement the A* algorithm in a simple Cocos2D tile mapped game!

In the meantime, if you have any questions about the A* algorithm in general, please join the forum discussion below!

This is a blog post by iOS Tutorial Team member Johann Fradj, a software developer currently full-time dedicated to iOS. He is the co-founder of Hot Apps Factory which is the creator of App Cooker.