一篇写的比较简单的A*寻路算法(转)

2024-08-24 01:58

本文主要是介绍一篇写的比较简单的A*寻路算法(转),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://www.raywenderlich.com/zh-hans/21503/a%E6%98%9F%E5%AF%BB%E8%B7%AF%E7%AE%97%E6%B3%95%E4%BB%8B%E7%BB%8D

这篇文章还可以在这里找到 英语

If you're new here, you may want to subscribe to my RSS feed or follow me on Twitter. Thanks for visiting!

这篇blog是由iOS Tutorial Team的成员  Johann Fradj发表的,他目前是一位全职的资深iOS开发工程师。他是Hot Apps Factory的创始人,该公司开发了App Cooker。

 

Learn how the A* Pathfinding Algorithm Works!

学习A星寻路算法是如何工作的!

你是否在做一款游戏的时候想创造一些怪兽或者游戏主角,让它们移动到特定的位置,避开墙壁和障碍物呢?

如果是的话,请看这篇教程,我们会展示如何使用A星寻路算法来实现它!

在网上已经有很多篇关于A星寻路算法的文章,但是大部分都是提供给已经了解基本原理的高级开发者的。

本篇教程将从最基本的原理讲起。我们会一步步讲解A星寻路算法,幷配有很多图解和例子。

不管你使用的是什么编程语言或者操作平台,你会发现本篇教程很有帮助,因为它在非编程语言的层面上解释了算法的原理。稍后,会有一篇教程,展示如何在Cocos2D iPhone 游戏中实现A星算法。

现在找下到达一杯咖啡因饮料和美味的零食的最短路径,开始吧!:]

一只探路猫

 

让我们想象一下,有一款游戏,游戏中一只猫想要找到获取骨头的路线。

“为什么会有一只猫想要骨头?!”你可能会这么想。在本游戏中, 这是一只狡猾的猫,他想捡起骨头给狗,以防止被咬死!:]

现在想像一下下图中的猫想找到到达骨头的最短路径:

This cat just wants someone to throw him a bone!

不幸的是,猫不能直接从它当前的位置走到骨头的位置,因为有面墙挡住了去路,而且它在游戏中不是一只幽灵猫!

游戏中的猫同样懒惰,它总是想找到最短路径,这样当他回家看望它的女朋友时不会太累:-)

但是我们如何编写一个算法计算出猫要选择的那条路径呢?A星算法拯救了我们!

 

简化搜索区域

 

寻路的第一步是简化成容易控制的搜索区域。

怎么处理要根据游戏来决定了。例如,我们可以将搜索区域划分成像素点,但是这样的划分粒度对于我们这款基于方块的游戏来说太高了(没必要)。

作为代替,我们使用方块(一个正方形)作为寻路算法的单元。其他的形状类型也是可能的(比如三角形或者六边形),但是正方形是最简单并且最适合我们需求的。

像那样去划分,我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图,我们的搜索区域将会是一个有625个正方形的数组。如果我们把地图划分成像素点,搜索区域就是一个有640,000个正方形的数组了(一个方块是32*32像素)!

现在让我们基于目前的区域,把区域划分成多个方块来代表搜索空间(在这个简单的例子中,7*6个方块 = 42 个方块):

Dividing the maze into a tile-based search area

 

Open和Closed列表

 

既然我们创建了一个简单的搜索区域,我们来讨论下A星算法的工作原理吧。

除了懒惰之外,我们的猫没有好的记忆力,所以它需要两个列表:

  1. 一个记录下所有被考虑来寻找最短路径的方块(称为open 列表)
  2. 一个记录下不会再被考虑的方块(成为closed列表)

猫首先在closed列表中添加当前位置(我们把这个开始点称为点 “A”)。然后,把所有与它当前位置相邻的可通行小方块添加到open列表中。

下图是猫在某一位置时的情景(绿色代表open列表):
Adding adjacent tiles from the start position to the open list

现在猫需要判断在这些选项中,哪项才是最短路径,但是它要如何去选择呢?

在A星寻路算法中,通过给每一个方块一个和值,该值被称为路径增量。让我们看下它的工作原理!

路径增量

 

我们将会给每个方块一个G+H 和值:

  • G是从开始点A到当前方块的移动量。所以从开始点A到相邻小方块的移动量为1,该值会随着离开始点越来越远而增大。
  • H是从当前方块到目标点(我们把它称为点B,代表骨头!)的移动量估算值。这个常被称为探视,因为我们不确定移动量是多少 – 仅仅是一个估算值。

你也许会对“移动量”感兴趣。在游戏中,这个概念很简单 – 仅仅是方块的数量。

然而,在游戏中你可以对这个值做调整。例如:

  • 如果你允许对角线移动,你可以针对对角线移动把移动量调得大一点。
  • 如果你有不同的地形,你可以将相应的移动量调整得大一点 – 例如针对一块沼泽,水,或者猫女海报:-)

这就是大概的意思 – 现在让我们详细分析下如何计算出G和H值。

关于G值

 

G是从开始点A到达当前方块的移动量(在本游戏中是指方块的数目)。

为了计算出G的值,我们需要从它的前继(上一个方块)获取,然后加1。所以,每个方块的G值代表了从点A到该方块所形成路径的总移动量。

例如,下图展示了两条到达不同骨头的路径,每个方块都标有它的G值:
An illustration of the G variable in the A* Pathfinding Algorithm

关于H值

H值是从当前方块到终点的移动量估算值(在本游戏中是指方块的数目)。

移动量估算值离真实值越接近,最终的路径会更加精确。如果估算值停止作用,很可能生成出来的路径不会是最短的(但是它可能是接近的)。这个题目相对复杂,所以我们不会再本教程中讲解,但是我在教程的末尾提供了一个网络链接,对它做了很好的解释。

为了让它更简单,我们将使用“曼哈顿距离方法”(也叫“曼哈顿长”或者“城市街区距离”),它只是计算出距离点B,剩下的水平和垂直的方块数量,略去了障碍物或者不同陆地类型的数量。

例如,下图展示了使用“城市街区距离”,从不同的开始点到终点,去估算H的值(黑色字):
An illustration of the H variable in the A* pathfinding algorithm with the Manhattan algorithm

A星算法

 

既然你知道如何计算每个方块的和值(我们将它称为F,等于G+H),  我们来看下A星算法的原理。

猫会重复以下步骤来找到最短路径:

  1. 将方块添加到open列表中,该列表有最小的和值。且将这个方块称为S吧。
  2. 将S从open列表移除,然后添加S到closed列表中。
  3. 对于与S相邻的每一块可通行的方块T:
    1. 如果T在closed列表中:不管它。
    2. 如果T不在open列表中:添加它然后计算出它的和值。
    3. 如果T已经在open列表中:当我们使用当前生成的路径到达那里时,检查F 和值是否更小。如果是,更新它的和值和它的前继。

如果你对它的工作原理还有点疑惑,不用担心 – 我们会用例子一步步介绍它的原理!:]

猫的路径

让我们看下我们的懒猫到达骨头的行程例子。

在下图中,我根据以下内容,列出了公式F = G + H 中的每项值:

  • F(方块的和值):左上角
  • G(从A点到方块的移动量):左下角
  • H(从方块到B点的估算移动量): 右下角

同时,箭头指示了到达相应方块的移动方向。

最后,在每一步中,红色方块表示closed列表,绿色方块表示open列表。

好的,我们开始吧!

第一步

第一步,猫会确定相对于开始位置(点A)的相邻方块,计算出他们的F和值,然后把他们添加到open列表中:
A* Example Part 1

你会看到每个方块都列出了H值(有两个是6,一个是4)。我建议根据“城市街区距离”去计算方块的相关值,确保你理解了它的原理。

同时注意F值(在左上角)是G(左下角)值和H(右下脚)值的和。
第二步

在第二步中,猫选择了F和值最小的方块,把它添加到closed列表中,然后检索它的相邻方块的相关数值。
A* Example Part 2

现在你将看到拥有最小增量的是F值为4的方块。猫尝试添加所有相邻的方块到open列表中(然后计算他们的和值),除了猫自身的方块不能添加以外(因为它已经被添加到了closed列表中)或者它是墙壁方块(因为它不能通行)。

注意被添加到open列表的两个新方块,他们的G值都增加了1,因为他们现在离开始点有2个方块远了。你也许需要再计算下“城市街区距离”以确保你理解了每个新方块的H值。
第三步

再次,我们选择了有最小F和值(5)的方块,继续重复之前的步骤:
A* Example Part 3

现在,只有一个可能的方块被添加到open列表中了,因为已经有一个相邻的方块在close列表中,其他两个是墙壁方块。

第四步

现在我们遇到了一个有趣的情况。正如你之前看到的,有4个方块的F和值都为7 – 我们要怎么做呢?!

有几种解决方法可以使用,但是最简单(快速)的方法是一直跟着最近被添加到open列表中的方块。现在继续沿着最近被添加的方块前进。
A* Example Part 4

这次有两个可通过的相邻方块了,我们还是像之前那样计算他们的和值。
第五步

接着我们选择了最小和值(7)的方块,继续重复之前的步骤:
A* Example Part 5

我们越来越接近终点了!

第六步

你现在训练有素了!我打赌你能够猜出下一步是下面这样子了:
A* Example Part 6

我们差不多到终点了,但是这次你看到有两条到达骨头的最短路径提供给我们选择:
Two shortest paths to the bone

在我们的例子中,有两条最短路径:

  • 1-2-3-4-5-6
  • 1-2-3-4-5-7

It doesn’t really matter which of these we choose, it comes down to the actual implementation in code.

选择哪一条其实没关系,现在到了真正用代码实现的时候了。

第七步

让我们从其中一块方块,再重复一遍步骤吧:
A* Example Part 7

啊哈,骨头在open列表中了!
第八步

现在目标方块在open列表中了,算法会把它添加到closed列表中:
A* Example Part 8

然后,算法要做的所有事情就是返回,计算出最终的路径!
A* Example Part 9

一只有远见的猫

在上面的例子中,我们看到当猫在寻找最短路径时,它经常选择更好的方块(那个在它的未来最短路径上的方块)- 好像它是一只有远见的猫!

但是如果猫是盲目的,并且总是选择第一个添加到它的列表上的方块,会发生什么事情?

下图展示了所有在寻找过程中会被使用到的方块。你会看到猫在尝试更多的方块,但是它仍然找到了最短路径(不是之前的那条,而是另一条等价的):
What would happen if the cat wasn't so smart...

图中的红色方块不代表最短路径,它们只是代表在某个时候被选择为“S”的方块。

我建议你看着上面的图,并且尝试过一遍步骤。这次无论你看到哪个相邻的方块,都选择“最坏”的方式去走。你会发现最后还是找到了最短路径!

所以你可以看到跟随一个“错误的”方块是没有问题的,你仍然会在多次重复尝试后找到最短路径。

所以在我们的实现中,我们会按照以下的算法添加方块到open列表中:

  • 相邻的方块会返回这些顺序: 上面/左边/下面/右边。
  • 当所有的方块都有相同的和值后,方块会被添加到open列表中(所以第一个被添加的方块是第一个被猫挑选的)。

下面是从原路返回的示意图:
The cat finding the shortest path, even after some wrong turns

最短的路径是从终点开始,一步步返回到起点构成的(例子:在终点我们可以看到箭头指向右边,所以该方块的前继在它的左边)。

总的来说,我们可以用下面的伪代码,合成猫的寻找过程。这是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 listif ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path// PATH FOUNDbreak; // break the loop}adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squaresforeach (aSquare in adjacentSquares) {if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore itcontinue; // 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星寻路算法!

同时,如果你对于A星算法有任何的疑问,请加入下面的论坛!

作者:

 

 

 

 

这篇blog是由iOS Tutorial Team的成员  Johann Fradj发表的,他目前是一位全职的资深iOS开发工程师。他是Hot Apps Factory的创始人,该公司开发了App Cooker。

翻译者:

Picture of Oliver Ou

欧泽林目前在ZAKER,一款中国最流行的新闻阅读类app,负责iOS端的开发工作,在中国广州。他是位苹果的超级粉丝,曾经以学生身份参加过2011年6月份的苹果全球开发者大会(WWDC)。刚毕业不久,喜欢与苹果有关的一切东西,希望可以跟更多人分享交流。你可以在Twitter, Facebook, 或者Weibo上找到他。


这篇关于一篇写的比较简单的A*寻路算法(转)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101126

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

最大公因数:欧几里得算法

简述         求两个数字 m和n 的最大公因数,假设r是m%n的余数,只要n不等于0,就一直执行 m=n,n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为:6 代码实现 #include<iostream>using namespace std;/