摘要：但再认真想想，其实这道题目就类似我们日常用的导航，寻找起点和终点可行的最短路线。越小时，那么起点到目标点的可行路径越小。首先将起点放进中，然后搜寻起点附近可行方格放到中作记录。
最近做到一道题，题目如下：
有 A、B 两点，中间有一堆障碍物，求出A点到B的可行的路径，写出一个 DEMO 并可用任何语言实现（要求可以任意设置 A、B 点和障碍物的位置，需要做UI）。
首先，理解一下题意，需要求出 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 存放已行的不需要再关注的方格。
（图一）
可见图一，起点 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 ，如果可斜走那么每一个的斜线为 。当然为了方便计算可使用长宽为 10，斜线为 14 的比例来计算。
（图二）
如图二，起点 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 点去到了起点的下方一个，那个继续去计算，由于上面起点已经存在于 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（如图四）。
（图四）
以此类推，我们最终可得出的路径（如图五）。
（图五）
如图五，绿色路径为可行的最短路径，红色标志的则是已存在于 Open List 的方格。
基本原理就是如此，代码我就不一一列出来，我会放到 Github 或者看看 Jsfiddle 上面，有兴趣的可以看一下，对应方法也有对应的注释。可以看一下最终实现的 效果
动画演示各种算法地址：http://www.webhek.com/post/pathfinding.html
新手一枚，如果有什么写错的或者不好的地方，请各位大大指点探讨一下，我会不断优化提升。
哦，最近本人在找工作，期待工作地区广州、深圳、佛山，如有好工作或者内推等可以私聊一下我。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/83662.html
摘要：星算法介绍实现星寻路算法在游戏中常有需要主角敌人去移动到某个物品或者追寻敌人的时候，这个时候，可以使用寻路算法为了实现游戏，需要寻路算法，于是便自己用实现了一下原理思路简化搜索区域为了减少资源消耗，首先需要我们将地图分割为区块，如下图建立起 A星算法 介绍 javascript实现A星寻路算法 在游戏中常有需要主角/敌人去移动到某个物品或者追寻敌人的时候，这个时候，可以使用寻路算法 ...
摘要：前言偶尔看到两年前写的贪吃蛇，当时没把自动寻路的算法写好，蛇容易挂，周末找了个时间把当年的坑填上，写了个不会挂的贪吃蛇。 前言 偶尔看到两年前写的贪吃蛇，当时没把自动寻路的算法写好，蛇容易挂，周末找了个时间把当年的坑填上，写了个不会挂的贪吃蛇。 两年前的版本_点击查看 这次更新的版本_点击查看 代码比较简单,使用 canvas 完成游戏的画图，抛开 A* 算法的实现，整个 html 代...
摘要：话说我的地图就是栅格形式用点坐标来表示格子模板模型法很容易理解，就是有几种走法，按情况调用。 寻路模块 (1) 终于要挑战寻路模块，虽然我是在重复造轮子，但看一下别人的轮子怎么造也是很重要的，所以在这之前首先搜索下，看看有什么现成的思路和代码，收获如下: 两种寻路逻辑 有两种寻路逻辑, 随机碰撞和路径规划，考虑到： a. 随机碰撞似乎需要不少经验/实验数据才能达到不错的效果，我缺经验/...
摘要：寻路模块通过一番寻找，发现这系列文章，其不仅包含算法，连寻路算法中的一些基础知识也一并介绍了，不愧是斯坦福出品，也很感谢译者要实现点到点最短路径，还需要做一些微小的工作，下面逐个说明计算曼哈顿距离的函数目的是寻路，肯定需要一个方法来估算两点 寻路模块 (2) 通过一番寻找，发现这系列文章，其不仅包含A*算法，连寻路算法中的一些基础知识也一并介绍了，不愧是斯坦福出品，也很感谢译者要实现点...
阅读 3486·2021-11-24 10:19
阅读 3670·2021-09-30 09:47
阅读 1252·2019-08-30 15:56
阅读 719·2019-08-29 15:11
阅读 869·2019-08-29 13:43
阅读 3528·2019-08-28 18:25
阅读 2122·2019-08-26 13:27
阅读 1361·2019-08-26 11:44
