大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.

如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)

免责申明：本博客提供的所有翻译文章原稿均来自互联网，仅供学习交流之用，请勿进行商业用途。同时，转载时不要移除本申明。如产生任何纠纷，均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作！

那么关于对角线移动呢?

如果你想要在A*算法中允许对角线移动真是太容易了.

你只要更新如下2个函数:

• walkableAdjacentTilesCoordForTileCoord:更新该函数去包括对角线上的瓦块.
• constToMoveFromStep:toAdjacentStep:更新该函数给与对角线移动一个不同于水平/垂直移动的移动花费.

你可能会奇怪如何计算对角线方向的移动花费,用一些简单数学知识来解释的话那是相当的容易!

这只猫咪从瓦块中心移动到其他瓦块,并且因为瓦块是正方形,A,B和C组成了一个三角形,正如你在下图中看到的那样:

根据勾股定理,C² = A² + B²,有:

C = √(A² + B²)with A = B = 1 (The movement cost to move from a square to another = G cost)C = √(2)C ≈ 1.41

所以对角线移动花费大致等于1.41,它比向左然后向上移动的花费(1+1)要低.

正如你所知道的那样,用整数比用浮点数计算更有效率,所以我们不用浮点数表示对角线的移动花费,而是简单的将结果乘以10,并且圆整结果,所以横向和纵向将花费10,而对角线将花费14.

让我们试一下!首先在CatSprite.m中将costToMoveFromStep:toAdjacentStep方法内容替换如下:

// 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;}

然后修改walkableAdjacentTilesCoordForTileCoord(在HelloWorldLayer.m中),让其返回对角线上的邻居方块:

- (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];}

重要提示:你可以看到代码在添加对角线方块时和增加横向/纵向方块时有一点不同.

确实,举个栗子,左侧仅当上侧和左侧都被添加时才能被添加.这是用来防止猫咪可以从墙壁的拐角穿越出去.以下是所有详尽的需要处理的情况:

• O = Origin
• T = Top
• B = Bottom
• L = Left
• R = Right
• TL = Top-Left
• …