How To Implement A* Pathfinding with Cocos2D Tutorial

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.

In this tutorial, you’ll learn how to add the A* Pathfinding algorithm into a simple Cocos2D game.

Before you go through this tutorial, it’s helpful if you read this Introduction to A* Pathfinding first. It will walk you through the basic concepts of the algorithm we’re implementing here, along with an illustrated example.

To go through this tutorial, it’s helpful if you have prior knowledge of Cocos2D with iOS. It’s OK if you don’t though, since you can always take the examples presented here and adapt them to another language or framework.

So find the shortest path to your keyboard, and let’s begin! :]

Cat Maze

First let’s take a moment to introduce you to the simple game we’re going to be working with in this tutorial.

Go ahead and download the starter project for this tutorial. Compile and run the project, and you should see the following:

In this game, you take the role of a cat thief trying to make your way through a dungeon guarded by dangerous dogs. If you try to walk through a dog they will eat you – unless you can bribe them with a bone!

So the game is all about trying to pick up the bones in the right order so you can make it through the dogs and find your way through the exit.

Note that the cat can only move vertically or horizontally (i.e. not diagonally), and will move from one tile center to another. Each tile can be either walkable or unworkable.

So try out the game, and see if you can make your way through! I also recommend looking through the code to get familiar with how it works. It’s a pretty basic tile-mapped game, and we’ll be modifying it to add A* pathfinding in the rest of the tutorial.

Cat Maze and A* Overview

As you can see, currently when you tap somewhere on the map, the cat will jump to an adjacent tile in the direction of your tap.

We want to modify this so that the cat continues to move to whatever tile you tapped, much like many RPGs or point-and-click adventure games.

Let’s take a look at how the touch handling code currently works. If you open HelloWorldLayer, you’ll see that it implements a touch handler like the following:

- (void)registerWithTouchDispatcher {
    [[CCTouchDispatcher sharedDispatcher] addTargetedDelegate:self priority:0 swallowsTouches:YES];
}

- (BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event {
    
    if (_gameOver) return NO;
    
    CGPoint touchLocation = [_tileMap convertTouchToNodeSpace:touch];
    [_cat moveToward:touchLocation];
    return YES;
}

You can see that it’s just calling a method on the cat sprite to move the cat toward a touch point on the tile map.

So what we are going to do is to modify the following method in CatSprite.m to find the shortest path to that point, and start following it:

- (void)moveToward:(CGPoint)target {
    // Figure out the shortest path to the target, and start following it!
}

Creating the ShortestPathStep Class

Let’s start by creating an inner class which will represent a step on a path. In our case, this is a tile and its F, G, and H scores calculated by the A* algorithm.

So add the following code at the top of CatSprite.m (above the @implementation of CatSprite):

// A class that represents a step of the computed path
@interface ShortestPathStep : NSObject
{
	CGPoint position;
	int gScore;
	int hScore;
	ShortestPathStep *parent;
}

@property (nonatomic, assign) CGPoint position;
@property (nonatomic, assign) int gScore;
@property (nonatomic, assign) int hScore;
@property (nonatomic, assign) ShortestPathStep *parent;
 
- (id)initWithPosition:(CGPoint)pos;
- (int)fScore;

@end

As you can see, this is a very simple class that keeps track of the following:

• The tile’s coordinate
• The G score (remember, this is the number of tiles between the start and current point)
• The H score (remember, this is the estimated number of tiles between the current point and destination)
• The ShortestPathStep from where we came from
• The F score, which is the score for this tile (calculated by adding F + G).

Now we can write its implementation at the end of the CatSprite.m (below the @end).

@implementation ShortestPathStep

@synthesize position;
@synthesize gScore;
@synthesize hScore;
@synthesize parent;

- (id)initWithPosition:(CGPoint)pos
{
	if ((self = [super init])) {
		position = pos;
		gScore = 0;
		hScore = 0;
		parent = nil;
	}
	return self;
}

- (NSString *)description
{
	return [NSString stringWithFormat:@"%@  pos=[%.0f;%.0f]  g=%d  h=%d  f=%d", [super description], self.position.x, self.position.y, self.gScore, self.hScore, [self fScore]];
}

- (BOOL)isEqual:(ShortestPathStep *)other
{
	return CGPointEqualToPoint(self.position, other.position);
}

- (int)fScore
{
	return self.gScore + self.hScore;
}

@end

As you can see this is straightforward. We redefine the description method here for easy debugging, and create an isEquals method because two ShortestPathSteps are equal if and only if they have the same position (i.e. they represent the same tile).

Creating the Open and Closed Lists

Next we’ll use two NSMutableArrays to keep track of our open and closed lists.

You may wonder why we aren’t using NSMutableSet instead. Well, there’s two reasons:

1. NSMutableSet isn’t ordered, but we want the list to be ordered by F score for quick lookups.
2. NSMutableSet won’t call our isEqual method on ShortestPathStep to test if two entries are the same (but we need it to do this).

So let’s add the definition of those arrays in CatSprite.h:

@interface CatSprite : CCSprite {
    //...
	
@private
	NSMutableArray *spOpenSteps;
	NSMutableArray *spClosedSteps;
}

Then make the following modifications to CatSprite.m:

// Add to top of file
// Private properties and methods
@interface CatSprite () 
@property (nonatomic, retain) NSMutableArray *spOpenSteps;
@property (nonatomic, retain) NSMutableArray *spClosedSteps;
@end

// Add after @implementation CatSprite
@synthesize spOpenSteps;
@synthesize spClosedSteps;

// Add inside initWithLayer
self.spOpenSteps = nil;
self.spClosedSteps = nil;

//Add dealloc method to CatSprite
- (void)dealloc
{
	[spOpenSteps release]; spOpenSteps = nil;
	[spClosedSteps release]; spClosedSteps = nil;
	[super dealloc];
}

Checking our Start and End Points

Now the bootstrapping is over, let’s replace the moveToward method with a new fresh implementation.

We’ll start by getting current position (point A) and the target position (point B) in tile coordinates. Then we’ll check if we need to compute a path, and finally test if the target position is walkable (in our case only walls are not walkable).

So replace the moveToward method with the following:

- (void)moveToward:(CGPoint)target
{		
    // Get current tile coordinate and desired tile coord
    CGPoint fromTileCoord = [_layer tileCoordForPosition:self.position];
    CGPoint toTileCoord = [_layer tileCoordForPosition:target];

    // Check that there is a path to compute ;-)
    if (CGPointEqualToPoint(fromTileCoord, toTileCoord)) {
        NSLog(@"You're already there! :P");
        return;
    }

    // Must check that the desired location is walkable
    // In our case it's really easy, because only wall are unwalkable
    if ([_layer isWallAtTileCoord:toTileCoord]) {
        [[SimpleAudioEngine sharedEngine] playEffect:@"hitWall.wav"];
        return;
    }	

    NSLog(@"From: %@", NSStringFromCGPoint(fromTileCoord));
    NSLog(@"To: %@", NSStringFromCGPoint(toTileCoord));
}

Compile, run and tap on the map. If you didn’t tap a wall, in the console you’ll see the “from” is equals to {24, 0} which is the cat position. You’ll also see the “to” coordinates are between [0; 24] for x and y, representing the tile coordinate for where you tap on the map.

Implementing the A* Algorithm

According to our algorithm, the first step is to add the current position to the open list.

We’ll also need three helper methods:

1. One method to insert a ShortestPathStep into the open list at the appropriate position (ordered by F score).
2. One method to compute the movement cost from a tile to an adjacent one.
3. One method to compute the H score for a square, according to the “city block” algorithm.

So open up CatSprite.m and make the following modifications:

// In "private properties and methods" section
- (void)insertInOpenSteps:(ShortestPathStep *)step;
- (int)computeHScoreFromCoord:(CGPoint)fromCoord toCoord:(CGPoint)toCoord;
- (int)costToMoveFromStep:(ShortestPathStep *)fromStep toAdjacentStep:(ShortestPathStep *)toStep;

// Add these new methods after moveToward

// Insert a path step (ShortestPathStep) in the ordered open steps list (spOpenSteps)
- (void)insertInOpenSteps:(ShortestPathStep *)step
{
	int stepFScore = [step fScore]; // Compute the step's F score
	int count = [self.spOpenSteps count];
	int i = 0; // This will be the index at which we will insert the step
	for (; i < count; i++) {
		if (stepFScore <= [[self.spOpenSteps objectAtIndex:i] fScore]) { // If the step's F score is lower or equals to the step at index i
			// Then we found the index at which we have to insert the new step
            // Basically we want the list sorted by F score
			break;
		}
	}
	// Insert the new step at the determined index to preserve the F score ordering
	[self.spOpenSteps insertObject:step atIndex:i];
}

// Compute the H score from a position to another (from the current position to the final desired position
- (int)computeHScoreFromCoord:(CGPoint)fromCoord toCoord:(CGPoint)toCoord
{
	// Here we use the Manhattan method, which calculates the total number of step moved horizontally and vertically to reach the
	// final desired step from the current step, ignoring any obstacles that may be in the way
	return abs(toCoord.x - fromCoord.x) + abs(toCoord.y - fromCoord.y);
}

// Compute the cost of moving from a step to an adjacent one
- (int)costToMoveFromStep:(ShortestPathStep *)fromStep toAdjacentStep:(ShortestPathStep *)toStep
{
	// Because we can't move diagonally and because terrain is just walkable or unwalkable the cost is always the same.
	// But it have to be different if we can move diagonally and/or if there is swamps, hills, etc...
	return 1;
}

The comments in the code above should explain these methods in good detail, so be sure to take the time to read them through.

Next, we need a method to get all the walkable tiles adjacent to a given tile. Because in this game the HelloWorldLayer manages the map, we'll need to add the method there.

So add the method definition in HelloWorldLayer.h, after the @interface:

- (NSArray *)walkableAdjacentTilesCoordForTileCoord:(CGPoint)tileCoord;

Then add the implementation in HelloWorldLayer.m:

- (NSArray *)walkableAdjacentTilesCoordForTileCoord:(CGPoint)tileCoord
{
	NSMutableArray *tmp = [NSMutableArray arrayWithCapacity:4];
	
	// Top
	CGPoint p = CGPointMake(tileCoord.x, tileCoord.y - 1);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	// Left
	p = CGPointMake(tileCoord.x - 1, tileCoord.y);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	// Bottom
	p = CGPointMake(tileCoord.x, tileCoord.y + 1);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	// Right
	p = CGPointMake(tileCoord.x + 1, tileCoord.y);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	return [NSArray arrayWithArray:tmp];
}

Now that we have all of these helper methods in place, we can continue the implementation of our moveToward method in CatSprite.m. Add the following at the end of your moveToward method:

BOOL pathFound = NO;
self.spOpenSteps = [[[NSMutableArray alloc] init] autorelease];
self.spClosedSteps = [[[NSMutableArray alloc] init] autorelease];

// Start by adding the from position to the open list
[self insertInOpenSteps:[[[ShortestPathStep alloc] initWithPosition:fromTileCoord] autorelease]];

do {
    // Get the lowest F cost step
    // Because the list is ordered, the first step is always the one with the lowest F cost
    ShortestPathStep *currentStep = [self.spOpenSteps objectAtIndex:0];
    
    // Add the current step to the closed set
    [self.spClosedSteps addObject:currentStep];
    
    // Remove it from the open list
    // Note that if we wanted to first removing from the open list, care should be taken to the memory
    [self.spOpenSteps removeObjectAtIndex:0];
    
    // If the currentStep is the desired tile coordinate, we are done!
    if (CGPointEqualToPoint(currentStep.position, toTileCoord)) {
        
        pathFound = YES;
        ShortestPathStep *tmpStep = currentStep;
        NSLog(@"PATH FOUND :");
        do {
            NSLog(@"%@", tmpStep);
            tmpStep = tmpStep.parent; // Go backward
        } while (tmpStep != nil); // Until there is not more parent
        
        self.spOpenSteps = nil; // Set to nil to release unused memory
        self.spClosedSteps = nil; // Set to nil to release unused memory
        break;
    }
    
    // Get the adjacent tiles coord of the current step
    NSArray *adjSteps = [_layer walkableAdjacentTilesCoordForTileCoord:currentStep.position];
    for (NSValue *v in adjSteps) {
        ShortestPathStep *step = [[ShortestPathStep alloc] initWithPosition:[v CGPointValue]];
        
        // Check if the step isn't already in the closed set 
        if ([self.spClosedSteps containsObject:step]) {
            [step release]; // Must releasing it to not leaking memory ;-)
            continue; // Ignore it
        }		
        
        // Compute the cost from the current step to that step
        int moveCost = [self costToMoveFromStep:currentStep toAdjacentStep:step];
        
        // Check if the step is already in the open list
        NSUInteger index = [self.spOpenSteps indexOfObject:step];
        
        if (index == NSNotFound) { // Not on the open list, so add it
            
            // Set the current step as the parent
            step.parent = currentStep;
            
            // The G score is equal to the parent G score + the cost to move from the parent to it
            step.gScore = currentStep.gScore + moveCost;
            
            // Compute the H score which is the estimated movement cost to move from that step to the desired tile coordinate
            step.hScore = [self computeHScoreFromCoord:step.position toCoord:toTileCoord];
            
            // Adding it with the function which is preserving the list ordered by F score
            [self insertInOpenSteps:step];
            
            // Done, now release the step
            [step release];
        }
        else { // Already in the open list
            
            [step release]; // Release the freshly created one
            step = [self.spOpenSteps objectAtIndex:index]; // To retrieve the old one (which has its scores already computed ;-)
            
            // Check to see if the G score for that step is lower if we use the current step to get there
            if ((currentStep.gScore + moveCost) < step.gScore) {
                
                // The G score is equal to the parent G score + the cost to move from the parent to it
                step.gScore = currentStep.gScore + moveCost;
                
                // Because the G Score has changed, the F score may have changed too
                // So to keep the open list ordered we have to remove the step, and re-insert it with
                // the insert function which is preserving the list ordered by F score
                
                // We have to retain it before removing it from the list
                [step retain];
                
                // Now we can removing it from the list without be afraid that it can be released
                [self.spOpenSteps removeObjectAtIndex:index];
                
                // Re-insert it with the function which is preserving the list ordered by F score
                [self insertInOpenSteps:step];
                
                // Now we can release it because the oredered list retain it
                [step release];
            }
        }
    }
    
} while ([self.spOpenSteps count] > 0);

if (!pathFound) { // No path found
    [[SimpleAudioEngine sharedEngine] playEffect:@"hitWall.wav"];
}

Again, the comments in the code above should do a good job explaining how each bit works. So once you've added it and read over the comments, compile and run to try it out!

If you touch the tile shown below:

You should see something like this in the console:

<ShortestPathStep: 0x6a336b0>  pos=[22;3]  g=9  h=0  f=9
<ShortestPathStep: 0x6a33570>  pos=[21;3]  g=8  h=1  f=9
<ShortestPathStep: 0x6a33400>  pos=[20;3]  g=7  h=2  f=9
<ShortestPathStep: 0x6a328c0>  pos=[20;2]  g=6  h=3  f=9
<ShortestPathStep: 0x6a32750>  pos=[20;1]  g=5  h=4  f=9
<ShortestPathStep: 0x6a7b940>  pos=[21;1]  g=4  h=3  f=7
<ShortestPathStep: 0x6a7b810>  pos=[22;1]  g=3  h=2  f=5
<ShortestPathStep: 0x6a7b700>  pos=[23;1]  g=2  h=3  f=5
<ShortestPathStep: 0x6a86150>  pos=[24;1]  g=1  h=4  f=5
<ShortestPathStep: 0x6a321c0>  pos=[24;0]  g=0  h=0  f=0

Remember the path is built backwards, so you have to read from bottom to top to see what path the cat has chosen. I recommend trying to match these up to the tiles so you can see that the shortest path actually works!

Following the Yellow Brick Path

Now that we have found our path, we just have to make the cat follow it.

What we are going to do is to remember the whole path, and make the cat move across it step by step.

So create an array to store the path in CatSprite.h, inside the CatSprite @interface's private section:

NSMutableArray *shortestPath;

Then make the following modifications to CatSprite.m:

// Add inside the CatSprite private properties and methods section
@property (nonatomic, retain) NSMutableArray *shortestPath;

// After the CatSprite @implementation
@synthesize shortestPath;

// Inside initWithLayer
self.shortestPath = nil;

// Inside dealloc	
[shortestPath release]; shortestPath = nil;

Now we'll create a method which will store the whole path and be in charge of starting the animation. Make these changes to CatSprite.m:

// Add inside the CatSprite private properties and methods section
- (void)constructPathAndStartAnimationFromStep:(ShortestPathStep *)step;

// Inside moveToward, comment out the pathFound BOOL
//BOOL pathFound = NO;

// Inside moveToward, replace pathFound = YES with this:
[self constructPathAndStartAnimationFromStep:currentStep];

// Also comment all of the debugging statements below that.

// Inside moveToward, replace if (!pathFound) with this:
if (self.shortestPath == nil) { // No path found

// Add this new method:

// Go backward from a step (the final one) to reconstruct the shortest computed path
- (void)constructPathAndStartAnimationFromStep:(ShortestPathStep *)step
{
	self.shortestPath = [NSMutableArray array];
	
	do {
		if (step.parent != nil) { // Don't add the last step which is the start position (remember we go backward, so the last one is the origin position ;-)
			[self.shortestPath insertObject:step atIndex:0]; // Always insert at index 0 to reverse the path
		}
		step = step.parent; // Go backward
	} while (step != nil); // Until there is no more parents
	
    for (ShortestPathStep *s in self.shortestPath) {
        NSLog(@"%@", s);
    }
}

Note that in the moveToward method, we are calling the new method instead of printing the result to the console and we have removed the pathFound boolean. As usual, the comments in the constructPathAndStartAnimationFromStep method explains what's going on in detail.

Now build and run. If you touch the same position as we done before, you should see on the console:

<ShortestPathStep: 0x6b37160>  pos=[24;1]  g=1  h=4  f=5
<ShortestPathStep: 0x6b37340>  pos=[23;1]  g=2  h=3  f=5
<ShortestPathStep: 0x6b37590>  pos=[22;1]  g=3  h=2  f=5
<ShortestPathStep: 0x6b395c0>  pos=[21;1]  g=4  h=3  f=7
<ShortestPathStep: 0x6b37ae0>  pos=[20;1]  g=5  h=4  f=9
<ShortestPathStep: 0x6b38c60>  pos=[20;2]  g=6  h=3  f=9
<ShortestPathStep: 0x6b36510>  pos=[20;3]  g=7  h=2  f=9
<ShortestPathStep: 0x6b3b850>  pos=[21;3]  g=8  h=1  f=9
<ShortestPathStep: 0x6b3cf30>  pos=[22;3]  g=9  h=0  f=9

Note that this is similar to before, except now it's from start to finish (instead of reversed) and the steps are nicely stored in an array for us to use.

The last thing to do is to go though the shortestPath array and animate the cat to follow the path. In order to achieve this we will create a method which will pop a step from the array, make the cat move to that position, and add a callback to repeat calling this method until the path is complete.

So make the following changes to CatSprite.m:

// Add inside the CatSprite private properties and methods section
- (void)popStepAndAnimate;

// Add to bottom of constructPathAndStartAnimationFromStep
[self popStepAndAnimate];

// Add new method
- (void)popStepAndAnimate
{	
	// Check if there remains path steps to go through
	if ([self.shortestPath count] == 0) {
		self.shortestPath = nil;
		return;
	}

	// Get the next step to move to
	ShortestPathStep *s = [self.shortestPath objectAtIndex:0];
	
	// Prepare the action and the callback
	id moveAction = [CCMoveTo actionWithDuration:0.4 position:[_layer positionForTileCoord:s.position]];
	id moveCallback = [CCCallFunc actionWithTarget:self selector:@selector(popStepAndAnimate)]; // set the method itself as the callback
	
	// Remove the step
	[self.shortestPath removeObjectAtIndex:0];
	
	// Play actions
	[self runAction:[CCSequence actions:moveAction, moveCallback, nil]];
}

Compile and run, and. . .

Our cat automatically moves to the final destination that you touch! :-)

However, as you play with it you'll see a bunch of problems:

• The cat looks a little bit frozen,
• The cat does not take the bones
• The can go through the dog (with no bones) without being chomped to death
• The cat has a strange behavior if you touch a new location before it has finish to go to the previous one.

So to take care of its frozen aspect, and the game logic (win/lose, dogs, bones, etc...) we have to put back the old game logic that was present in the first implementation. Let's fix this up next.

Re-Adding the Game Logic

To fix these problems, replace the popStepAndAnimate method with the following:

- (void)popStepAndAnimate
{	
    // Check if there is still shortestPath 
	if (self.shortestPath == nil) {
		return;
	}
	
	// Game Logic (Win / Lose, dogs, bones, etc...)
	CGPoint currentPosition = [_layer tileCoordForPosition:self.position];
	
	if ([_layer isBoneAtTilecoord:currentPosition]) {
		[[SimpleAudioEngine sharedEngine] playEffect:@"pickup.wav"];
		_numBones++;
		[_layer showNumBones:_numBones];
		[_layer removeObjectAtTileCoord:currentPosition];
	}
	else if ([_layer isDogAtTilecoord:currentPosition]) { 
		if (_numBones == 0) {
			[_layer loseGame];     
			self.shortestPath = nil;
			return;
		}
		else {                
			_numBones--;
			[_layer showNumBones:_numBones];
			[_layer removeObjectAtTileCoord:currentPosition];
			[[SimpleAudioEngine sharedEngine] playEffect:@"catAttack.wav"];
		}
	}
	else if ([_layer isExitAtTilecoord:currentPosition]) {
		[_layer winGame];
		self.shortestPath = nil;
		return;
	}
	else {
		[[SimpleAudioEngine sharedEngine] playEffect:@"step.wav"];
	}
	
	// Check if there remains path steps to go trough
	if ([self.shortestPath count] == 0) {
		self.shortestPath = nil;
		return;
	}
	
	// Get the next step to move to
	ShortestPathStep *s = [self.shortestPath objectAtIndex:0];
	
	CGPoint futurePosition = s.position;
	CGPoint diff = ccpSub(futurePosition, currentPosition);
	if (abs(diff.x) > abs(diff.y)) {
		if (diff.x > 0) {
			[self runAnimation:_facingRightAnimation];
		}
		else {
			[self runAnimation:_facingLeftAnimation];
		}    
	}
	else {
		if (diff.y > 0) {
			[self runAnimation:_facingForwardAnimation];
		}
		else {
			[self runAnimation:_facingBackAnimation];
		}
	}
	
	// Prepare the action and the callback
	id moveAction = [CCMoveTo actionWithDuration:0.4 position:[_layer positionForTileCoord:s.position]];
	id moveCallback = [CCCallFunc actionWithTarget:self selector:@selector(popStepAndAnimate)]; // set the method itself as the callback
	
	// Remove the step
	[self.shortestPath removeObjectAtIndex:0];
	
	// Play actions
	[self runAction:[CCSequence actions:moveAction, moveCallback, nil]];
}

No magic, just a little refactoring of the original source code.

Build and run, and you'll see that everything is OK, except the cat’s strange behavior when he has to go to a new location before finishing the previous.

Because it's not really relevant to the topic, I'll not detail the (really simple) implementation. But if you're curious, you can download the final Cat Maze project and check it out.

Congrats, you have now implemented A* pathfinding in a simple Cocos2D game from scratch! :-)

What About Diagonal Movement?

It is really easy to allow diagonal movement into the A* algorithm if you want.

You just have to update two functions:

• walkableAdjacentTilesCoordForTileCoord: Update this to include the diagonal tiles as well.
• costToMoveFromStep:toAdjacentStep: Update this to give diagonal movement a different cost than horizontal/vertical movement.

You might wonder how you should compute the cost for movement in the diagonal direction. Well this is quite easy with some simple math!

The cat is moving from the center of a tile to another, and because the tiles are squares, A, B and C forms a triangle rectangle as you can see in the diagram below:

According to the Pythagorean Theorem, C² = A² + B², so:

C = √(A² + B²)
with A = B = 1 (The movement cost to move from a square to another = G cost)
C = √(2)
C ≈ 1.41

So the cost to move diagonal is equal to 1.41, which is lower than going left then up which is equals to 2 (1 + 1).

As you may know, computing with integers is far more efficient than floats, so instead of using floats to represent the cost of a diagonal move, we can simply multiply the costs by 10 and round them, so moving horizontally or vertically will cost 10 and diagonally will cost 14.

So let's try this out! First replace the costToMoveFromSTep:toAdjacentStep in CatSprite.m:

// Compute the cost of moving from a step to an adjecent one
- (int)costToMoveFromStep:(ShortestPathStep *)fromStep toAdjacentStep:(ShortestPathStep *)toStep
{
	return ((fromStep.position.x != toStep.position.x) && (fromStep.position.y != toStep.position.y)) ? 14 : 10;
}

Then modify walkableAdjacentTilesCoordForTileCoord (in HelloWordLayer.m) to return the diagonal adjacent squares:

- (NSArray *)walkableAdjacentTilesCoordForTileCoord:(CGPoint)tileCoord
{
	NSMutableArray *tmp = [NSMutableArray arrayWithCapacity:8];
    
    BOOL t = NO;
    BOOL l = NO;
    BOOL b = NO;
    BOOL r = NO;
	
	// Top
	CGPoint p = CGPointMake(tileCoord.x, tileCoord.y - 1);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
        t = YES;
	}
	
	// Left
	p = CGPointMake(tileCoord.x - 1, tileCoord.y);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
        l = YES;
	}
	
	// Bottom
	p = CGPointMake(tileCoord.x, tileCoord.y + 1);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
        b = YES;
	}
	
	// Right
	p = CGPointMake(tileCoord.x + 1, tileCoord.y);
	if ([self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
        r = YES;
	}
    
    
	// Top Left
	p = CGPointMake(tileCoord.x - 1, tileCoord.y - 1);
	if (t && l && [self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	// Bottom Left
	p = CGPointMake(tileCoord.x - 1, tileCoord.y + 1);
	if (b && l && [self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	// Top Right
	p = CGPointMake(tileCoord.x + 1, tileCoord.y - 1);
	if (t && r && [self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
	
	// Bottom Right
	p = CGPointMake(tileCoord.x + 1, tileCoord.y + 1);
	if (b && r && [self isValidTileCoord:p] && ![self isWallAtTileCoord:p]) {
		[tmp addObject:[NSValue valueWithCGPoint:p]];
	}
    
    
	return [NSArray arrayWithArray:tmp];
}

Important note: You can spot the code to add diagonal squares is a bit different than adding the horizontal/vertical squares.

Indeed, for example, the left is added only when both top and left entries are added. This was made to prevent the cat from walking through corners of walls. Here are all the exhaustive cases to deal with:

• O = Origin
• T = Top
• B = Bottom
• L = Left
• R = Right
• TL = Top - Left
• ...

Take for example the case shown in the top left of the above image.

The cat wants to go from the origin (O) to the bottom left diagonal square. If there is a wall in the left or the bottom (or both) and test it to go diagonal it will cut the corner of a wall (or two). So the bottom-left diagonal square is open only if there is a wall on the left or on the bottom.

Tips: You can simulate different type of terrain by updating the costToMoveFromStep method to take the terrain type into consideration. Indeed if you lower the G cost that means the cat will be faster on those squares and vice-versa.

Where to go from here?

Here is the Cat Maze project with all of the code from the above tutorial (including diagonal movements).

Congratulations, now you know the basics of the A* algorithm and have experience implementing it! Now you should be prepared to:

• Implement the A* algorithm in you're own game
• Refine it as necessary (by allowing different kind of terrain, better heuristics, etc...) and optimizing it
• Read other topics out there like this awesome guide : Amit’s A* Pages

If you have any questions or comments about this tutorial, 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.