How To Implement A* Pathfinding with Cocos2D Tutorial

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