How To Implement A* Pathfinding with Cocos2D Tutorial

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.