共计 1421 个字符，预计需要花费 4 分钟才能阅读完成。
在贪吃蛇游戏较量里，计算蛇吃食物门路时要用到寻路算法，以下是我的算法演化过程。
1、简略寻路 – 按图索骥
我一开始想到的办法就是最简略的：指标在哪个方位就往哪个方位走，就和平时看地图寻路一样。这时候算法的根本思维为：
即以终点起点连线方向为正方向，与正方向越靠近的办法给予更小的权值，当搜寻门路时总以总权值和最小为目标进行搜寻，直到搜寻到起点。
但在地图上有障碍物时会产生：
所以要对地图上的点做一些解决，即把障碍物从能够搜寻的地图点汇合中去除。
以下是此算法的搜寻后果，蓝色点为搜寻过的地图点，彩色为障碍物：
能够看见在简略状况下此算法能够很好的工作并找到一条最短门路，消耗的资源也不多。
但在简单状况下可能会产生：
为了解决这种简单状况下可能呈现的找不到最短门路的问题，我又想了一种解决办法。
2、简略寻路 – 投石问路
这种算法的根本思维和蝙蝠的超声波导航相似：
即一圈一圈向外查找，直到找到起点。
这种办法能很好地解决简单状况下找到最短门路的问题：
但也正如图中显示的，蓝色的格点（查找点）太多，对于资源的耗费太大，尤其在地图很大很简单或对实时性要求较高的状况下用此算法根本不可能。
于是为了补救以上两者的毛病并取其长处就产生了 A * 寻路算法。
3、A* 寻路 – 融汇贯通
以上两种算法中，第一种算法以起点为导向，谋求终点到起点的最近，但可能舍本逐末；第二种算法以终点为导向，最求起点到终点的地位最近，但因为无奈确定起点地位导致了资源耗费过大。于是 A * 算法同时思考终点和起点，它的根本思维如下：
其中蓝色为终点，黄色为中继点，彩色为阻碍，X 为起点。
即选取要查看的地图点，以此地图点为中继点，别离计算间隔终点和起点的地位，并把二者加和作为这一点的权值，寻路的门路就是总权值和最小的点的汇合。
因为贪吃蛇游戏中只有程度和垂直两个方向，于是上图也能够演变成下图：
能够的出间隔 F = G’+H’。
上面分步骤阐明 A * 寻路的具体流程：
1、将以后节点（蓝色节点）的四周节点退出待检测汇合 openList（黄色节点）中，并计算 F 值；将阻碍节点退出 abandonList。
2、选取一个在 openList 中 F 值最小的节点，放入检测结束汇合 closeList（绿色节点）中。若此节点为起点，算法完结。
3、计算以后节点（绿色节点）四周节点，并进行解决：
1 如果节点在 closeList 中则抛弃节点（退出 abandonList）。2 如果节点在 openList 中则从新计算这一点的 F 值。3 如果节点不在 openList 中，反复步骤 2。n、反复步骤 2、3
下图是简单状况下 A * 寻路的后果：
既找到了最短门路，也没有搜寻很多格子，是一种比拟优良的算法。
当然其实 A star 寻路在泛滥寻路算法中也算比拟根底的寻路算法。现在比拟罕用的算法有 D star 算法（次要用于动静未知环境下的寻路，用于机器人寻路）和 JPS（Jump Point Search）算法（用于格子地图的寻路，速度快且资源耗费少）等 A * 算法的优化算法以及 Dijkstra 算法（上述简略寻路的优化，次要用于动态地图下的寻路，最优可达线性工夫复杂度）。
还有更进一步的寻路就是通过神经网络训练 AI，但这种办法的毛病就在于算法不受控，开发人员不晓得寻路的实现规定。一般而言很少会用这种形式做寻路。
在寻路算法背地也有地图的优化算法，罕用的是划分 navigation mesh（导航网格），其中的 mesh 为一个个凸多边形，划分实现后能大大减少地图点的数目。当然这就是另外一个故事了。
