大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.
如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)
免责申明：本博客提供的所有翻译文章原稿均来自互联网，仅供学习交流之用，请勿进行商业用途。同时，转载时不要移除本申明。如产生任何纠纷，均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作！
检查我们的起点和终点
现在前奏已经结束了,让我们用新的实现替换moveToward方法.
我们将从瓦片坐标系中取得现有开始位置(点A)和目标位置(点B)开始.然后我们将检查是否需要计算路径,并且最终测试目标位置是否为可达的(在我们的例子中只有墙是不可达的).
将moveToard方法替换为如下代码:
- (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));
}编译运行并且点击地图.如果你没有在墙上点击的话,在控制台中你将看到”from”等于{24,0},这时猫咪的位置.你将同样注意到”to”的坐标系的x和y值在[0;24]之间,这是用来在地图坐标系中表示你在什么位置点击.
实现A*算法
根据我们的算法,第一步是将当前位置添加到开放列表中.
我们同样需要3个帮助方法:
- 一个方法将ShortestPathStep插入到开放列表中合适的位置上(根据F值排序).
- 一个方法计算一个瓦块到其邻居瓦块的移动花费.
- 一个方法去计算瓦块的H值,依据”城区”算法.
打开CatSprite.m做出如下修改:
// 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;
}上面代码中的注释应该解释的足够详细了,请花时间把它们读一遍.
接下来,我们需要一个方法去取得指定瓦块的所有可到达的邻居瓦块.因为在这个游戏中HelloWorldLayer管理着地图,我们需要将方法添加都其中去.
打开HelloWorldLayer.h,在@interface之后增加方法的定义:
- (NSArray *)walkableAdjacentTilesCoordForTileCoord:(CGPoint)tileCoord;然后添加实现代码到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];
}现在我们已经有了这些帮助方法,我们可以继续在CatSprite.m中实现我们的moveToward方法.添加如下的代码到moveToward方法的最后:
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"];
}再一次,上面代码中的注释应该对于每一点工作起了很好的解释作用.所以当你添加代码和阅读过注释之后,尝试去编译运行app!
如果你点击如下图所示的瓦片:
你应该在控制台中看到如下显示:
<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别忘了路径是反向建立起来的,所以你必须从后向前读.我建议你尝试去在地图上实际匹配这些瓦块,这样你就可以明白最短路径实际是如何工作的!