这世间纷纷扰扰，哪有那么多捷径可以走
本文将针对游戏中常用的A*算法进行总结。
搜索空间
假设我们在一个地图上希望从A点（绿色）走到B点（红色），且两点之间被墙壁分隔，每次我们可以朝8个方向中的一个进行走动，我们需要绕过蓝色墙从A走到B，并且路径最短。搜索空间就是地图中每一个可以走动的格子。
开始搜索
当我们将地图用一个个节点进行划分后，接下来我们的任务是在节点集合中找到一个子集，可以连通两个点并且路径最短，寻找过程如下：
- 第一步，从起点A开始，将其加入一个openlist中，代表可能的最短路径上的节点
- 第二步，把A节点相邻的可达节点都放入openlist中，将A节点设置为这些节点的父节点
- 第三步，把A从openlist删除，加入closelist中，closelist保存已经确定的最短路径上的节点
当我们获得了保存有可能解的openlist后，下一步就是从中选择最优解，我们定义cost fun如下：
其中
- $g$为从A移动到指定方格的距离
- $h$为从指定方格移动到B的估算距离，为何要估算呢，因为这个方格到B不一定是可达的，路上可能会遇到障碍而停下
之后我们根据$f$对openlist进行排序，下面我们对上面的例子进行一个计算，假设纵横向移动距离为10，斜向移动距离为14，那么得到的结果如下，每个格子上标注了其$g$和$h$的值。
继续搜索
从图中可以看出，A点右侧节点$f$值最小，选择该节点作为下一步节点，将其移动至closelist