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.