小咸鱼
0%

Astar寻路在Unity项目中的简单应用

发表于 更新于 分类于

概念

  • 寻找计算两点之间的最短路径，基本思想源于BFS，是Dijkstra寻路的进阶版，相比DijkStra引入了目标点到终点的预估消耗值。

算法伪逻辑代码

算法伪码图
其中OpenList可以考虑使用最小二叉堆或者优先级队列，这样每次取最小值时间复杂度为O(1)。

之前在旧博客的实现

Unity逻辑实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
using System;
using System.Collections;
using System.Collections.Generic;
using KeyBoard.Util;
using UnityEngine.Profiling;

namespace KeyBoard.Logic.Map
{
    public abstract class IAstarNode<T> : IComparable
    {
        public float G_Value { get; set; }

        public float H_Value { get; protected set; }

        public abstract bool IsWalkable {get;}

        public float F_Value => G_Value + H_Value;

        public IAstarNode<T> Parent { get; set; }

        public T NodeData { get; private set; }

        public IAstarNode(T data)
        {
            NodeData = data;
        }

        public abstract float GetDistance(IAstarNode<T> target);


        public static bool TryFindPath<Node>(List<Node> nodes, Node start, Node end, int Width, int Length, out List<Node> path) where Node:IAstarNode<T>
        {
#if UNITY_EDITOR
            Profiler.BeginSample("CustomAstar:" + typeof(Node));
            // var watch = System.Diagnostics.Stopwatch.StartNew();
#endif
            path = null;
            if(!nodes.Contains(start) || !nodes.Contains(end))
                return false;
            if(Width < 0 || Length < 0)
                return false;
            var openNodes = new SortedSet<Node>();
            HashSet<Node> closeNodes = new HashSet<Node>();
            path = new List<Node>();
            openNodes.Add(start);
            while(openNodes.Count > 0)
            {
                var curNode = openNodes.Min;
                openNodes.Remove(curNode);
                closeNodes.Add(curNode);

                if(curNode == end) break;

                var idx = nodes.IndexOf(curNode);
                var neighbor = UIUtil.GetNeighbors(idx, (int)Width, (int)Length);
                SearchNeighbor(curNode, nodes.SafeGet(neighbor.left), end, openNodes, closeNodes);
                SearchNeighbor(curNode, nodes.SafeGet(neighbor.right), end, openNodes, closeNodes);
                SearchNeighbor(curNode, nodes.SafeGet(neighbor.up), end, openNodes, closeNodes);
                SearchNeighbor(curNode, nodes.SafeGet(neighbor.down), end, openNodes, closeNodes);
            }

            while(end != null)
            {
                path.Add(end);
                end = end.Parent as Node;
            }
#if UNITY_EDITOR
            // watch.Stop();
            // UnityEngine.Debug.Log($"自定义寻路用时{watch.ElapsedMilliseconds}ms");
            Profiler.EndSample();
#endif
            return path.Count > 0;
        }

        private static void SearchNeighbor<Node>(Node curNode, Node neighborNode, Node end, ISet<Node> openNodes, ISet<Node> closeNodes) where Node:IAstarNode<T>
        {
            if(neighborNode == null || !neighborNode.IsWalkable || closeNodes.Contains(neighborNode))
                return;
            float newCost_G = curNode.G_Value + curNode.GetDistance(neighborNode);
            if(newCost_G < neighborNode.G_Value || !openNodes.Contains(neighborNode))
            {
                neighborNode.G_Value = newCost_G;
                neighborNode.H_Value = neighborNode.GetDistance(end);
                neighborNode.Parent = curNode;
                if(!openNodes.Contains(neighborNode))
                {
                    openNodes.Add(neighborNode);
                }
            }
        }


        public int Compare(IAstarNode<T> x, IAstarNode<T> y)
        {
            if(x.H_Value < y.H_Value)
                return -1;
            if(x.H_Value > y.H_Value)
                return 1;
            return 0;
        }

        public int Compare(object x, object y)
        {
            var a = x as IAstarNode<T>;
            var b = y as IAstarNode<T>;
            if(a != null && b != null)
                return a.CompareTo(b);
            return 0;
        }

        public int CompareTo(object obj)
        {
            if (obj == null) return 1;

            var other = obj as IAstarNode<T>;
            if (other != null)
                return F_Value.CompareTo(other.F_Value);
            else
                throw new ArgumentException("Object is not an IAstarNode");
        }
    }
}