How To Implement A* Pathfinding with Cocos2D Tutorial

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!