A*寻路算法入门(七)

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.
如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)


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

一只没有远见的猫咪

在上面的例子中,我们看到猫咪在选择最短路径的时候,它总是选择最好的方块(在未来最短路径中的一块) — 就像他它是一只有远见的猫咪一样!

但是如果这只猫咪不总是头脑清楚的去选择第一个添加到列表中的方块时会发生什么呢?

这里有一张示意图显示了这些被用在该处理过程中的方块.你将看到猫咪会尝试更多的方块,但是它仍然能找到一条最短的路径(不一定和前面相同,但是等效的):

上图中红色方块并不表示最短路径,它仅表示在某些点上选择的”S”方块.

我建议你检查上图并且视图跟随遍历它.这次,你将发现无论怎样”最坏的”的路径被选择,在最后你仍然可以得到一条最短的路径!

所以你可以看到跟随”错误”的方块也没有关系,在最终你仍然可以得到最短路径,即使你会经历更多次的迭代.

在我们的实现中,我们将按以下算法将方块添加到开放列表中去:

  • 邻居方块将按以下顺序返回:上/左/下/右.
  • 一个具有相同分值的方块将被添加到开放列表中所有相同分值相同方块的最后面(所以第一个添加的将第一个被猫咪取得).

这里是一张回溯的示意图:

最短路径通过开始从目的地回退到其父方块来建立起来(比如:在目的地我们可以看到箭头指向右侧,所以该方块的父方块在它的左侧).

最终,我们可以通过下面的伪代码来合成猫咪的处理.它被写为Objective-C,但是你可以用任何语言实现:

[openList add:originalSquare]; // start by adding the original position to the open list
do {
    currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score

    [closedList add:currentSquare]; // add the current square to the closed list
    [openList remove:currentSquare]; // remove it to the open list

    if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
        // PATH FOUND
        break; // break the loop
    }

    adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares

    foreach (aSquare in adjacentSquares) {

        if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
            continue; // Go to the next adjacent square
        }

        if (![openList contains:aSquare]) { // if its not in the open list

            // compute its score, set the parent
            [openList add:aSquare]; // and add it to the open list

        } else { // if its already in the open list

            // test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path

        }
    }

} while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)

你有没有小激动想要实现一下?!在下一篇课程中,我们将完全实现它!

接下来呢?

恭喜,你现在了解了基本的A*寻路算法!如果你想要从这里学到更多内容,我推荐你阅读 Amit’s A* Pages.

在本系列的下一篇课程中,我们将在一个简单的Cocos2D地图游戏中实现A*算法!(之前猫猪写过的 Cocos2D将v1.0的tileMap游戏转换到v3.4中一例系列博文即是前奏,大家可以先看一下 ;)

与此同时,如果你有关于A*算法的任何问题,请加入下面的讨论中来!

时间: 2024-11-08 19:40:00

A*寻路算法入门(七)的相关文章

A*寻路算法入门(一)

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途.同时,转载时不要移除本申明.如产生任何纠纷,均与本博客所有人.发表该翻译稿之人无任何关系.谢谢合作! 该篇博客由iOS课程团队的Johann Fradj发布,他现在是一个全职开发iOS的开发者.他是Hot Apps Factory(其是App Cooker的创造者)的共同创建

A*寻路算法入门(二)

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途.同时,转载时不要移除本申明.如产生任何纠纷,均与本博客所有人.发表该翻译稿之人无任何关系.谢谢合作! 一只寻路的猫咪(本猫猪也是路痴,猫猪注.) 让我们想象我们有一个游戏,游戏中一只猫咪想要找到得到骨头的路径. "为毛一只在世界上的猫咪想要一根骨头呢?!"你可能会这

A*寻路算法入门(四)

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途.同时,转载时不要移除本申明.如产生任何纠纷,均与本博客所有人.发表该翻译稿之人无任何关系.谢谢合作! 路径评分 我们将给每一个正方形一个分值 G + H : G是从开始点A到当前方块的移动花费.所以对于一个开始A点的邻居方块来说,值为1,但是离开开始点越远它的值会越大. H是

A*寻路算法入门(五)

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途.同时,转载时不要移除本申明.如产生任何纠纷,均与本博客所有人.发表该翻译稿之人无任何关系.谢谢合作! 关于A*算法 现在你该知道如何计算每一个方块的分值了(我们将称之为F,它等于G+H),让我们看看A*算法是如何工作的. 这只猫咪将用以下重复的步骤来找到最短路径: 从开发列表

A*寻路算法入门(六)

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途.同时,转载时不要移除本申明.如产生任何纠纷,均与本博客所有人.发表该翻译稿之人无任何关系.谢谢合作! 步骤3 我们再一次选择最小F值(5)的瓦块去继续迭代: 这时,只有一个可能的瓦块被添加到开放列表中,因为一个瓦块已经存在于闭合列表,两个瓦块是墙壁. 步骤4 现在我们遇到了一

A*寻路算法的lua实现

前言:又好久没写blog了,感觉有点"颓废"了,最近认识好多好多同龄人,也是大学刚毕业,觉得他们很优秀,认识到自己跟他们的差距,有点自愧不如.没写blog当然也有一部分原因是因为工作,本来经验就有点欠缺,还要承担起一个项目的压力,原本国庆回去就要把这个寻路的功能改进一下,结果第一次去女朋友家了就没碰电脑,回上海来的第一个夜晚满脑子全是心事,早上凌晨四点就在床上辗转睡不着了,这个月随着项目的进行感觉压力也越来越大,上班时期天天六点多就醒了睡不着,希望挺过这段适应期.关于寻路问题,在几个月

ActionScript 3.0(as3)实现的A*寻路算法源代码下载

曾经写过A*寻路算法的教程,但没有贴出任何代码,这次代码全都贴出,大家可以进一步学习我只是按照A*的基本思想,将A*寻路算法用AS3实现了一下,没有做太多的寻路优化等如果你本身已经会用A*寻路算法了,那么下面的代码也不必研究了代码中注释很多,就不贴过多的解释看代码以前,可以先看看下面这两篇文章,或者看代码的时候配合例子和教程来看A*(A星)寻路算法讲解A*寻路算法,DEMO展示在DEMO展示中,有三个版本,由于代码写了很久了,我也不记得下面贴出的代码是哪个版本的了,见谅.. 首先是文档类Inde

Windows 8风格应用开发入门 七 页面视图概览

Windows 8风格应用中包含哪些视图 常用的几种视图包括: 开发入门 七 页面视图概览-页面视图"> 1. FullScreenLandscape(水平方向全屏视图) 2. Filled(填充视图) 3. Snap view(贴靠视图) 4. FullScreenPortrait(竖直方向全屏视图) 最小视图状态分辨率支持1024*768,全屏视图状态分辨率为1366*768以上. 注意:实现贴靠视图的最小分辨率为1366*768. Visual Studio 2012和模拟器中如何开

深入理解游戏中寻路算法

如果你玩过MMOARPG游戏,比如魔兽,你会发现人物行走会很有趣,为了模仿人物行走的真实体验,他们会选择最近路线达到目的地,期间会避开高山或者湖水,绕过箱子或者树林,直到走到你所选定的目的地. 这种看似寻常的寻路在程序实现起来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是寻路算法首先要考虑的问题. 在这篇文章中我们会循序渐进来讲解寻路算法是如何演进的,你会看到一种算法从简单到高效所遇到的问题,以及精进的过程,带着问题来阅读,理解更快. 本篇主要包含以下内容: 1.图 2