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

这篇具有很好参考价值的文章主要介绍了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. 大根堆：任意结点的值都不小于其子结点的值
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);
    }