A星算法详解-通俗易懂初学者必看(5)

(智乐圆入门2)

终于把A*寻路算法看懂了，虽然还有点小问题，但A*寻路算法我已经略知一二，帮助还不知道的朋友进入A*算法入门阶级，应该不成问题，下面就来看看A*算法的原理（以下讲解不带入任何程序语言，因此只要你看懂了下面所有的话，那么你可以随意用在任意程序语言中）

在下也是初学，写这篇文章的目的只是让新手入门，因此高手看到这就飘过吧，当然愿意给予指点的高手请继续往下看

前言：

在文中可能会出现一些专业术语或者是我信口雌黄的话语，未免看官不明白，前面我先加以注解，具体意思可以从文中体会到

方格：一个一个的小方块

障碍物：挡着去路的东西

目标方格：你想到达的方格

操控方格：你控制的寻路对象

标记：临时为某一个方格做的标记

父标记：除了操控方格所创建的临时标记，每个标记都有个父标记，但父标记不是随便乱定的，请看下文 开启标记列表：当该标记还未进行过遍历，会先加入到开启标记列表中

关闭标记列表：当该标记已经进行过遍历，会加入到关闭标记列表中

路径评分：通过某种算法，计算当前所遍历的标记离目标方格的路径耗费估值（后面会讲一种通用的耗费算法）

首先描述一个环境，在一望无际的方格中，我身处某某方格，如今我想去某某方格，接

下来我开始寻路！

在脑海中，先创建开启标记列表、关闭标记列表，然后把我的初始位置设置为开始标记进行遍历，同时因为开始标记已经遍历过了，因此把开始标记加入到关闭列表。通过开始标记我们找出了相邻的八个方格，为它们创建相应的标记，加入到开启标记列表中，并把每个标记的父标记设置为开始标记，是因为开始标记才让我们这些方格创建了属于自己的标记，它就是我们的再生父母。但不符合条件的我们就不加入开启标记列表（下面的条件符合任何

一条都不要加入到开启标记列表中）：

1、它在我们的搜寻地图范围外，比如你地图的寻路范围是 0*0 - 50*50，那么但这个

点在边缘的时候，那它相邻的八个方格，必定有几个是处在外面的！

2、搜寻的这个方格是否有障碍物、或不可到达，比如河流，石头，山川等

3、判断它是否已经加入关闭标记列表，若已经加入表示该方格已经遍历过了，在遍历

一次也无济于事，还会影响效率

4、判断它是否已经加入开启标记列表，若已经加入那么咋们就来判断一下该标记是否

离开始标记更近一些

5、判断当斜着走的时候，它的上下或左右是否有障碍，如果有则表示你无法斜着走，

需要先横走一下，再竖走一下或者是竖走一下，再横走一下

把相邻的八方向都添加到开启标记列表中后，现在从开启标记列表中取出一个路径评分最低标记，对他开始进行遍历相邻的八个方格，并进行创建标记、添加到开启标记列表、设