A星算法原理

（x，x）

xx

(x，x)

（3，5）

根号2+11

(2，6)

移动

开启列表

（3，6）

1+10

关闭列表

（2，7）

（0，0）

首先定义如下的一个数据结构用于表示每个block的数据

（2，6）

null

（3，7）

根号2+9

坐标（2，7）作为key

寻路消耗

block的父对象

（1，5）

根号2+13

终点

这里消耗如何计算？分两段，父block到当前block的距离+当前block的距离到终点block的距离，父block到当前block的距离是可以直接计算的，对角的四个block的距离都是根号2，纵向和横向的四个block的距离都是1。当前block到终点block的距离采用哈夫曼距离，因为这个距离是预估的，为什么说是预估值？因为不确定当前的block存在与最终的路径中，有可能要进行回溯的这里根据开启列表得出（3，7）block是消耗最小的，把（3，7）动到关闭列表中，这个时候就把（3，7）作为下一轮的起点，继续以上的操作

A星寻路基本概念

（1，7）

Unity现在已经有了寻路工具了，但是使用Unity工具的寻路工具在需要动态生成地图的时候寻路变得很难处理，所以自定义寻路还是非常必要的，自定义寻路还可以做一些特殊的功能，加深游戏的定制化

起点

首先是需要将起点的block加入到关闭列表中，并遍历起点周围的8个block，把这8个block的数据加入到开启列表中，之后通过寻路消耗对比找出开启列表中寻路消耗最小的block作为下一个起点，之后反复以上的操作。具体来说，首先将（2，6）：f = -1，parent = null加入到关闭列表中，将（1，5）、（1，6）、（1，7）、（2，7）、（2，5）、（3，7）、（3，6）、（3，5）的block存放到开启列表中（已经存在关闭列表和开启列表的block不会再次计算，直接取出来使用）

（1，6）

1+12

1、寻路消耗公式：f(寻路消耗) = g（离起点的距离）+ h（离终点的距离）2、开启列表（一个k-v容器）：用于回溯和下一个最优点的选择3、关闭列表（一个k-v容器）：用于最终路径的生成

障碍物

怎样找出最终的路径？正向是没有办法的，找出最终的路径需要逆向寻找，最终的时候终点block的数据是已知的，终点数据中从关闭列表中找出终点block的parent，再找parent的parent... 这个时候你就会发现路径的链表其实已经生成了，直到找到parent为null的起点block为止

之后就是按照以上规则向开启列表和关闭列表中添加数据知道找到终点什么时候会有回溯？当新加入到开启列表的数据中的block的路径消耗不是开启列表中最小的时候会有回溯，这个时候就会回溯到之前当前开启列表中路径消耗最小的block去

（2，5）

将地图分为一个个的方格子这里把方格子叫做block，现在需要从起点（黄色方格子）移动到重点（绿色方格子），红色方格子为障碍物，首先就是需要确定所有方格子的坐标（自定义），这里设置左下角的方块为坐标原点，起点就是（2，6），终点为（9，9），障碍物有【（4，3-8）】，这里在游戏运行时起点为角色所在的block，而终点为用户输入的坐标（比如像LOL一样的鼠标点击），那么障碍物信息如何获取呢？直接hardcode是非常不现实的，这时候就需要编写地图编辑器记录下地图的信息，在运行时加载地图信息获取障碍物的block坐标，比如地图编辑器编辑完之后保存了一个json，这个json里面保存了障碍物的信息，在运行时加载这个json获取即可。