Unity A*寻路原理与优化思路

2019-03-12 本文已影响0人派大星_5274

A*算法

关键点开启列表【有序列表】关闭列表。开启列表是下一个可以访问的点，关闭列表是不会再被访问的点

路径消耗 : 一张地图类似于一个网（加权图），总路径消耗 F = G + H F:总路径 G:当前位置移动到指定位置的消耗 H: 从指定位置到终点的消耗

算法思路：围绕着 F = G+H 和开启列表关闭列表展开。

1.取F值最小的，加入开启列表，在遍历开启列表中的点，把这个点A的所有周围的点，加入到开启列表。

2.如果这个点A周围的点B已经在开启列表中，计算从开始点经过A 到达B 的G值是不是变小了，变小了就说明从A走，会更近。就把B的父指定为A。并且更新B点的G值和F值。如果没有更近，就不指定。

3.如果这个点A周围的点B不在开启列表中，就把B的父指定为A。

4.经过步骤2和步骤3，最终B会得到一个到起始点最小的G值。因为每次循环，都会替换成最近父给B点。当循环结束，B点的父就是最近的路径。【注意】每次完成一次对B点的循环，就会对开放列表排序一次，下次循环只取第一个，F最小的点

5.循环遍历F值相对低的点，重复2,3步骤，当开启列表中有结束点，就停止循环。从结束点开始往前找父。最终就得到了最短路径。

拓展点： G值得计算策略以及H值得计算策略

H值计算 Abs 绝对值

G的算法 Sqrt 平方根

缺点：启发式的搜索法方法，如果地图格子多，搜索会变慢，成指数级增长。优化策略，用二叉堆优化A*。

耗时的部分主要是每次重新去点之前，要对开启列表做排序。二叉堆优化其实就是对开放列表的数据结构优化，用更优的排序方法，其实就是堆排序，快速排序这些基础算法

二叉堆优化A*算法

二叉堆：完全二叉树+堆（最大堆或者最小堆）二叉堆的特性：根的位置*2 和根的位置*2+1 是这个根的子。子的位置/2 是他的根。

二叉堆并不是完全的顺序排列，但是总是满足根节点是最大或者最小，这就满足了我们的需求

维护二叉堆

为了往堆里添加元素，我们把它放在数组的末尾。然后和它在当前位置/2 处的父节点比较，分数部分被圆整。如果新元素的F值更低，

我们就交换这两个元素。然后我们比较这个元素和它的新父节点，在（当前位置）/2，小数部分圆整，的地方。如果它的F值更低，

我们再次交换。我们重复这个过程直到这个元素不再比它的父节点低，或者这个元素已经到达顶端，处于数组的位置1。

添加元素，新元素放到最后，然后不停的跟新元素位置/2的做比较，小了就交换。

元素删除，删除第一个最小的元素，然后把最后一个元素放到第一个，然后不停的跟*2 和*2+1 做比较。如果大于，就跟较小的交换，直到*2 和*2+1 没有元素位置。表明到底了