如何在Cocos2D游戏中实现A*寻路算法(四)_app

概述大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明：本博客提供的所有翻译文章原稿均来自互联网，仅供学习交流之用，请勿进行商业用途。同时，转载时不要移除本申明。如产生任何纠纷，均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作！检查我们的起点和终点现在前奏已经结束了,让我们用新的实现替换moveTo

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.
如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! 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 cal@R_419_6603@tes 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