寻路之 A* 搜寻算法
39

Powered By Jiajian Chan

最近做到一道题,题目如下:

有 A、B 两点,中间有一堆障碍物,求出A点到B的可行的路径,写出一个 DEMO 并可用任何语言实现(要求可以任意设置 A、B 点和障碍物的位置,需要做UI)。

WechatIMG171.jpeg

首先,理解一下题意,需要求出 A、B 两点的可行路线,要注意的是可以任意设置 A、B 两点位置以及障碍物的位置且需要做 UI。题目需一句话带过,但需要做不少的工作。嗯,很明显,这是一道考算法逻辑还有 UI 的题目。

现在我们将主要工作放在如何去求出 A、B 两点的可行的路径呢?

估计看到题目,很多人都会无从下手。但再认真想想,其实这道题目就类似我们日常用的导航,寻找起点和终点可行的最短路线。那么,我们可以使用搜寻算法解决这一道题目。搜寻算法有很多种,如:最佳优先搜索算法 (Best-First Search)、戴克斯特拉算法(Dijkstra)、A 搜寻算法和迭代加深 A 算法(IDA* )等等。

*先来了解一下 A 搜寻算法:**

A* 算法综合了 最佳优先搜索算法 (Best-First Search) 和 戴克斯特拉算法(Dijkstra)的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数) 维基百科

*A 搜寻算法的估算函数:**

f(n) = g(n) + h(n)

g(n) 表示起点到任意点 n 的距离,h(n) 表示任意点 n 到目标点的距离,f(n) 则表示任意点 n 到起点以及目标点的和。f(n) 越小时,那么起点到目标点的可行路径越小。

接下来我们使用图文来说明一下我们该如何计算:

我们可以将所有格子看作一个二维数组,里面分为可行以及不可行(即障碍物)。我们将起始点标记为 A 以及目标点(终点)标记为 B,此处我们忽略可斜走的情况(因为需要做各种限制,略麻烦),本文 Open List 存放所有 A 附近可行的方格,Close List 存放已行的不需要再关注的方格。

WechatIMG171.jpeg

(图一)

可见图一,起点 A 上下左右有四个方格,右边格子为障碍物,再次我们则忽略它,那么起点 A 相邻可行的格子有上左下这三个。我们设置一个 Open List 用于存放可行的方格,以及一个 Close List 用于记录已行方格。首先将起点 A 放进 Open List 中,然后搜寻起点 A 附近可行方格放到 Open List 中作记录。

从上面 A 搜寻算法的简单了解,我们可知 A 搜寻算法的估算函数是:f(n) = g(n) + h(n)

A 相邻的长方形 f(n) 越小,则 A 到达 B 的可行路径最短,因此我们需要选择最小 f(n) 的长方形行走。接下来看看我们如何去计算 f(n) 的值。

为了方便计算,我们将方格的长宽设置为 1 ,如果可斜走那么每一个的斜线为 gh2.png 。当然为了方便计算可使用长宽为 10,斜线为 14 的比例来计算。

a* 1.jpeg

(图二)

如图二,起点 A 有三块可行的方格,我们标记为粉红色,那么首先我们计算这三个方格的 g 值。起点 A 的上左下的方格分别离 A 点距离 g(n) 为 1 ,所以标记粉红色的上左下的方格 g(n) 值为 1。

那么接下来计算 h(n) 值,计算 h(n) 值时忽略障碍物,即所有方格可行的情况下计算(如果可行斜线情况下,那么在计算 h(n) 值的时候不计算斜走的情况,只计算任意点直行到终点距离)。那么可计算出起点 A 下方的方格 h(n) 等于 7,左方 h(n) 等于 9,上方 h(n) 等于 9。那么得出上左下三个方格的 f(n) 值:

起点 A 上方:f(n) = g(n) + h(n) = 1 + 9 = 10

起点 A 左方:f(n) = g(n) + h(n) = 1 + 9 = 10

起点 A 下方:f(n) = g(n) + h(n) = 1 + 7 = 8

由上面的计算可得出起点 A 下方的 f(n) 值为最小,那么我们第一步走到起点 A 下方的方格。那么将起点 A 下方的方格存到 Close List,且同时从 Open List 中移除。

a*2.jpeg

(图三)

如图三,我们走了第一步后 A 点去到了起点的下方一个,那个继续去计算,由于上面起点已经存在于 Close List 以及已存在于 Open List 的格子我们不需要再关注,那么图上可看到 A 点接着可行点只有左右两点,那么计算 A 点到左边格子 g(n) 为 2,h(n) 为 8,右边格子 g(n) 为 2,h(n) 为 6。那么 A 点左边格子 f(n) 等于 10,右边格子 f(n) 等于 8,因此我们第二步走 A 点右边格子,将格子从 Open List 移除,存进 Close List(如图四)。

a*3.jpeg

(图四)

以此类推,我们最终可得出的路径(如图五)。

a*4.jpeg

(图五)

如图五,绿色路径为可行的最短路径,红色标志的则是已存在于 Open List 的方格。

基本原理就是如此,代码我就不一一列出来,我会放到 Github 或者看看 Jsfiddle 上面,有兴趣的可以看一下,对应方法也有对应的注释。可以看一下最终实现的 效果

动画演示各种算法地址:http://www.webhek.com/post/pathfinding.html

新手一枚,如果有什么写错的或者不好的地方,请各位大大指点探讨一下,我会不断优化提升。

哦,最近本人在找工作,期待工作地区广州、深圳、佛山,如有好工作或者内推等可以私聊一下我。

Nothing is impossible. —— @Jiajian Chan

本帖由系统于 1年前 自动加精
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 13

6666666666

1年前

给大佬跪了

file

1年前
Destiny

大佬佳佳

1年前
overtrue

666

1年前

非常赞

1年前
wujunze

:+1:

1年前

66666

1年前

一脸懵逼的进来,再一脸懵逼的出去。
file

1年前
茄子

鹅厂的 offer 搞定了没?

1年前

一脸懵逼的进来,再一脸懵逼的出去。

1年前

@茄子 没呢。各种因素阻碍着。:laughing:

1年前

只了解过迷宫算法

有没有可能没有路径呢 :jack_o_lantern:

1年前

请问是不是没考虑障碍导致要重新寻路的情况?

7个月前

  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,使用方法请见 Emoji 自动补全来咯,可用的 Emoji 请见 :metal: :point_right: Emoji 列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
  请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!