Introduction to A* Pathfinding

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. Have you ever had a game where you wanted to make monsters or players move to a particular point, while […] By Ray Wenderlich.

Leave a rating/review
Save for later
You are currently viewing page 3 of 3 of this article. Click here to view the first page.

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):

What would happen if the cat wasn't so smart...

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 cat finding the shortest path, even after some wrong turns

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


Over 300 content creators. Join our team.