Unity 中 A*寻路（AStar，A星）的优化，二叉堆，双向队列，哈希表

 概述

前篇：a星寻路的简单实现

a星寻路，在2d地图下使用频率较高

本篇基于上一篇文章实现的a星寻路进一步优化。利用二叉堆代替了原先openlist的数据结构，

改进了path返回时的操作，以及在搜索时的性能开销。

c# sort函数和堆排序比较

c#中的sort函数，在实现方面采用的是快速排序。

在日常的使用上，好像已经很满足需求了，快速排序的时间复杂度为o(nlogn)，堆排序的时间复杂度也为o(nlogn)。两者看起来速度基本一致。

但是当每次选择的主元都是当前子数组的最小或最大值时，快速排序的时间复杂度是最差的。这种情况下，快速排序退化为类似于选择排序或插入排序的时间复杂度，即 o(n^2)。

而堆排序最好，最坏，平均时间复杂度都是o(nlogn)。

在元素定位方面，快速排序需要依次搜索。堆能够更高效的搜索到。

同时，本文不再等openlist累积一段时间后再进行排序，而是在每个结点添加进openlist时自动定位；移出openlist时，自动调整结构。需要频繁的移动和调整结点位置，此时堆更合适这种操作。

二叉堆简介

了解改进之前，需要先了解一下二叉堆的基本概念。本文用到的二叉堆和数据结构里，堆排序中的堆并无出入。但是在使用方面略有不同，而不是直接的调用堆排序代替list中的sort函数。

二叉堆，实际上是一颗完全二叉树，满足两点性质：

1. 可分为大根堆和小根堆
   1. 大根堆：任意结点的值都不小于其子结点的值
   2. 小根堆：任意结点的值都不大于其子结点的值
2. 除了最底层的叶子结点，其它层的结点数都达到最大值。且仅对于叶子结点来说，从开始叶子结点到最后一个叶子结点之间没有空缺。

一般用顺序表存储，也即下标从0开始

数组长度为n，假设结点父结点孩子结点存在

• 下标为i元素，左孩子为 2 * i + 1，右孩子为2 * i + 2
• 父节点为 (i - 1) / 2
• 非叶子结点下标满足 i < (n - 1) / 2

对于小根堆，中的两个核心操作

• 上滤操作：将新结点添加进二叉堆尾部，如果该结点值小于父节点的值，则将该结点与父节点换位，直到不满足小于的情况
• 下滤操作：如果某结点值小于两个孩子结点中的最小值，那么将该结点与比较小的孩子结点换位，直到不满足此情况

二叉堆结构在a*中的应用

将openlist维护成小根堆结构，这样根结点的值一定是最小值。取最小值时间复杂度为o(1)

将结点加入小根堆尾部，并执行上滤操作，时间复杂度为 o(logn)

将根结点从小根堆中删除时，先交换根结点根最后一个元素，然后对新根结点执行下滤操作，时间复杂度为 o(logn)

堆代码中额外写了堆排序的代码，可以用来代替自带的sort排序，在基数大的情况下，堆排序更好一点。本文不再使用排序

using system.collections;
using system.collections.generic;
using unityengine;

public class heapsort : basemanger<heapsort>
{
    /// <summary>
    /// 二叉堆排序
    /// </summary>
    /// <param name="list"></param>
    public void myheapsort(list<astarnode> list = null)
    {
        if (list.count < 2 || list is null) return;
        heapify(list, list.count - 1);
        for (int i = list.count - 1; i > 0; i--)
        {
            //依次将最后一个未排序元素与堆顶元素交换
            swap(list, 0, i);
            //交换完，i位置为已排序位置，i - 1 确定新的未排序界限
            sifedown(list, 0, i - 1);
        }
    }

    /// <summary>
    /// 堆化，建立小根堆
    /// </summary>
    /// <param name="list"></param>
    /// <param name="r">未排序序列最后元素下标</param>
    private void heapify(list<astarnode> list, int r)
    {
        //r - 1 >> 1 为最后一个非叶子结点下标
        for(int hole = (r - 1) >> 1; hole >= 0; hole--)
        {
            sifedown(list, hole, r);
        }
    }

    /// <summary>
    /// 下滤
    /// </summary>
    /// <param name="list"></param>
    /// <param name="hole">需要下滤的结点的下标</param>
    /// <param name="r">未排序序列最后元素下标</param>
    public void sifedown(list<astarnode> list, int hole, int r)
    {        
        //列表可能为空，造成hole下标越界
        if (hole > list.count - 1) return;
        astarnode target = list[hole];
        int child = hole * 2 + 1;
        while(child <= r)
        {
            //确定值较小的孩子的下标
            if(child < r && list[child + 1].f < list[child].f) child++;
            if (list[child].f < target.f)
            {
                list[hole] = list[child];
                //hole继续下滤
                hole = child;
                //更新新的孩子下标
                child = hole * 2 + 1;
            }
            else
            {
                break;
            }
            list[hole] = target;
        }
    }

    /// <summary>
    /// 上滤
    /// </summary>
    /// <param name="list"></param>
    /// <param name="hole"></param>
    public void sifeup(list<astarnode> list, int hole)
    {
        astarnode target = list[hole];
        int parent = (hole - 1) >> 1;
        while(hole > 0 && target.f < list[parent].f)
        {
            list[hole] = list[parent];
            hole = parent;
            parent = (hole - 1) >> 1;
        }
        list[hole] = target;
    }

    /// <summary>
    /// 删除根节点
    /// </summary>
    /// <param name="list"></param>
    public void deleteheaproot(list<astarnode> list)
    {
        if(list.count == 0) return;
        int lastindex = list.count - 1;
        //交换根节点和最后一个结点
        swap(list, 0, lastindex);
        //移除最后一个结点
        list.removeat(lastindex);
        //将新的根节点下滤，维持小根堆性质
        sifedown(list, 0, lastindex - 1);
    }

    void swap(list<astarnode> list, int i, int j)
    {
        if (i == j || i < 0 || j < 0 || i > list.count - 1 || j > list.count - 1) return;
        astarnode tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }
}

 在原先findpath函数中作修改

            //排序
            //openlist.sort(sortruler);
            
            //选择新的父节点
            startnode = openlist[0];       
            
            //添加到closelist
            closelist.add(startnode);
            //openlist.removeat(0);
            heapsort.getinstance().deleteheaproot(openlist);

 在原先addnearlynode2openlist函数中修改

        //将结点加入openlist
        openlist.add(an);
        heapsort.getinstance().sifeup(openlist, openlist.count - 1);

返回列表path优化

原先需要对添加完的path列表再执行反转操作

使用双向队列优化

在双向链表中，插入或删除一个节点的时间复杂度为 o(1)，而在列表中通常是 o(n)。

    if (startnode == endnode)
    {
        linkedlist<astarnode> path = new linkedlist<astarnode>();
        path.addfirst(startnode);

        while (endnode.father != null)
        {
            path.addfirst(endnode.father);
            endnode = endnode.father;
        }

        return new list<astarnode>(path);
    }

contains的优化

c# 中的contains采用的是遍历的方式，在数据结构中搜索。数据基数过大，就太影响性能了

采用dictionary类型 来代替原来list类型的openlist 和 closelist 

原先的contains的时间复杂度取决于元素数量，o(n)

dictionary的类实现为哈希表，一次查找时间复杂度为，o(1)

提升非常可观

对于障碍点统计和寻路消耗f的优化思考

此条优化，针对地图中障碍点不变化，并且进行不同路径寻路的情况下。

对于一次寻路操作，会计算规划路径过程中，周围存在的障碍点。并且路径中搜索过的点都会计算f的值

可以再添加一个记录每个格子相邻障碍点的数组，在地图初始化的时候统计全部结点。这样在判断某个结点周围是否有障碍时，可以在该数组中查看。但是在初始加载的时候，可能会消耗一部分性能

本文仅为学习过程中的一个总结，可能存在纰漏，按需查看