简介
A星算法也称作A*算法，是目前比较流行的启发式搜索算法之一，应用于路径优化领域，在使用时，会将
-
游戏内的寻路
-
计算
这里要对每个最短路径的结点做预估值的计算，即F = G + H，这里的F就是计算出来的代价，G值计算是当前结点到起始结点的代价，H值计算的是当前结点到最终结点的代码 -
具体步骤
- 将起始结点放到open_list内
- 重复以下步骤
- 1.将open_list中F值最小的结点取出，作为当前要处理的结点。
- 2.将当前结点放入到close_list中
- 3.计算当前结点的所有最小相邻结点的移动单位(所有最小，就是如果有附近8个结点就判断8个，如果是判断上下左右的话，就判断4个而已)，如果这些结点是不可到达的，或者在close_list中，则忽略，否则继续以下判断:
- 1.判断不在open_list中的话，则加入到open_list，并且将当前结点设置为父结点，记录该结点的F,G和H值。
- 2.在open_list中的话，检查这条路径（经由当前结点到达它那里）是否更好。以G值为参考，更小的G值表示这是更好的路径。如果是更好的路径，把它的父结点设置为当前结点，并重新计算它的G和F值。
- 3.按F值的大小重新对open_list从小到大的排序。
- 寻路结束。当把终点加入到open_list中，此时路径已经找到了；或者open_list中无可用的下一移动结点，此时没有路径。
- 保存路径。从终点开始，沿着父结点移动直到起点，记录每个方向的改变点，就形成了一条完整的路径。
性能和优化
AStar主要的性能瓶颈在于从open_list里面取最小的值，如果进行for的循环去取值也是可以的，但是当数据量大的时候就会存在很大的时间复杂度，所以优化点就是将open_list改成一个二叉堆的数据结构，方便从里面取最大或者最小的数据。
扩展
- 二叉堆
- 二叉堆属于完全二叉树或者近似二叉树，主要有两种，最大堆和最小堆，最大堆：父结点的值总是大于或者等于任一子节点的值，最小堆：父结点的值总是小于或者等于任一节点的值。一般是使用数组表示，而按照根节点在数组开始下标表示的不同，可以分为：
- 如果是在数组中用下标0开始表示，则左节点在数组的下标为2n，右节点在数组中的下标为2n+1;
- 如果在数组中用下标1开始表示，则左节点在数组的下标为2n+1，右节点在数组的下标为2n+2.
- 根据二叉堆的性质，最大堆的堆顶永远是最大值，最小堆的堆顶永远是最小值，而在A星之中，需要的就是拿到移动代价最小的值，所以将open_list改成一个最小堆，在对open_list进行插入值时，每次内部调整一次，这样最后直接取值时，就拿到最小堆的堆顶值作为移动代价最小的结点.
- 二叉堆属于完全二叉树或者近似二叉树，主要有两种，最大堆和最小堆，最大堆：父结点的值总是大于或者等于任一子节点的值，最小堆：父结点的值总是小于或者等于任一节点的值。一般是使用数组表示，而按照根节点在数组开始下标表示的不同，可以分为：
引用
- 部分博客链接
https://blog.csdn.net/m0_37290785/article/details/93203624 (直接搜百度的第一篇文章，基本就懂了) - 二叉堆
- A星
- Github Demo
AStar-for-Unity
