Unity使用JobSystem实现AStar算法

前言

最近研究了一下Unity推出的Ecs中的JobSystem，发现这东西不怎么好用，本来想通过他的多线程效果去实现一些异步处理的，但是发现不太行，看了官方文档发现这个东西主要还是用于耗时的数据处理，这时我就想到了AStar算法本身也是一个比较耗时的操作，加上改算法本身也只是对数据做处理，没有需要引用类型和外部库的需要，感觉还是挺符合Job的需求的，所以就尝试实现了一些。

实现

数据定义

首先先定义一个结构体，用来记录点的信息。

public struct Point
    {
        public int x;
        public int y;
        internal int g;
        internal int h;
        internal int f => g + h;

        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
            g = int.MaxValue;
            h = int.MaxValue;
        }

        public static bool operator == (Point a, Point b)
        {
            return a.x == b.x && a.y == b.y;
        }

        public static bool operator !=(Point a, Point b)
        {
            return !(a.x == b.x && a.y == b.y);
        }

        public override bool Equals(object obj)
        {
            if (obj is Point)
            {
                return (Point)obj == this;
            }
            return false;
        }

        public override int GetHashCode()
        {
            return x + y + f;
        }

        public override string ToString()
        {
            return $"Point{{x={x}, y={y}, g={g}, h={h}}}";
        }
    }

x，y表示点的位置。g表示该点距离起点的代价。h表示该点距离终点的代价。f表示总代价，等于g+h。

同时为了方便后面运算，所以重写一下相等判断。为了方便调试重写一下ToString方法。

注意：该脚本必须是结构体不能是类，因为Job中不允许使用引用类型。该类应该还需要记录其上一个点的信息，但是由于是结构体，不能去持有上一个点的引用，所以在后续需要一些特殊方法去解决这个问题。

算法实现

源码如下

private struct AStarJob : IJob
        {
            public NativeArray<int> map;
            public NativeList<Point> path;
            public NativeList<Point> openPoints;
            public NativeHashSet<(int x, int y)> closePoints;
            public NativeHashMap<(int, int), (int, int)> pointRelation;
            public Point origin;
            public Point dest;
            public int mapWidth;
            public int mapHeight;
            public Point cur;

            private struct PointComparer : IComparer<Point>
            {
                public int Compare(Point p1, Point p2)
                {
                    return p1.f.CompareTo(p2.f);
                }
            }
            private PointComparer comparer;

            public void Execute()
            {
                cur.g = 0;
                cur.h = GetDistance(cur, dest);

                while (cur != dest)
                {
                    GetNearPoints(cur);
                    if (openPoints.Length == 0)
                        break;
                    cur = openPoints[0];
                }

                if (cur == dest)
                {
                    path.Add(cur);
                    while (pointRelation.ContainsKey((cur.x, cur.y)))
                    {
                        (int x, int y) p = pointRelation[(cur.x, cur.y)];
                        Point point = new Point(p.x, p.y);
                        cur = point;
                        path.Add(cur);
                    }
                }
            }

            private int Get(int x, int y)
            {
                if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight)
                    return -1;
                return map[x * mapHeight + y];
            }

            private void GetNearPoints(Point point)
            {
                (int x, int y)[] dir = new (int x, int y)[4]
                {
                    (-1, 0),
                    (0, 1),
                    (1, 0),
                    (0, -1),
                };

                for (int i = 0; i < 4; i++)
                {
                    int x = point.x + dir[i].x;
                    int y = point.y + dir[i].y;
                    if (Get(x, y) > 0 && !closePoints.Contains((x, y)))
                    {
                        Point newPoint = new Point(x, y);
                        newPoint.g = point.g + GetDistance(point, newPoint);
                        newPoint.h = GetDistance(newPoint, dest);

                        int index = IndexOf(newPoint);
                        if (index == -1)
                        {
                            openPoints.Add(newPoint);
                            pointRelation.Add((x, y), (point.x, point.y));
                        }
                        else
                        {
                            Point oldPoint = openPoints[index];
                            if (newPoint.f < oldPoint.f)
                            {
                                openPoints[index] = newPoint;
                                pointRelation[(x, y)] = (point.x, point.y);
                            }
                        }
                    }
                }

                for (int i = 0; i < openPoints.Length; i++)
                {
                    if (openPoints[i] == point)
                    {
                        openPoints.RemoveAt(i);
                        break;
                    }
                }
                closePoints.Add((point.x, point.y));

                openPoints.Sort(comparer);
            }

            private int GetDistance(Point p1, Point p2)
            {
                return math.abs(p1.x - p2.x) + math.abs(p1.y - p2.y);
            }

            private int IndexOf(Point point)
            {
                for (int i = 0; i < openPoints.Length; i++)
                    if (openPoints[i] == point)
                        return i;
                return -1;
            }
        }

字段解析

map用来表示地图，数据大于0表示可达，其它情况都视为障碍。原本应该为二维数组，但是由于Job中无法定义二维数组（主要是我不知道怎么定义），所以使用一维数组去模拟二维数组。对应公式就是

        map[i * m + j] = array[i][j]

其中m表示的是二维数组的二维长度，array = new int[n, m]。

path用来表示最后计算处理返回的路径。就是一个记录了路径点的列表。

openPoints用来表示astar中当前可选择的路径点。这是一个List类型，主要是因为这个列表需要排序以及更改内部节点的信息，所以选择List类型。

closePoints用来表示astar中不可选择的路径点。这是一个HashSet类型，因为不需要排序和更改值，只需要判断点是否在其中，所以选用HashSet类型，可以快速的插入和查找。

pointRelation是记录点间的关系。前面Point结构时说过，因为point无法记录它上一个点的情况，所以这里使用一个HashMap去维护所有点间的联系，这样在找到路径后就能成功回溯出移动路径。

origin表示起点。

dest表示终点。

mapWidth表示地图的一维长度。

mapHeight表示地图的二维长度。

cur表示当前所在的点，用于astar运算。

comparer是排序使用的比较器。

方法解析

获取x,y处的地图信息。

private int Get(int x, int y)
            {
                if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight)
                    return -1;
                return map[x * mapHeight + y];
            }

获取目标附近的点。

首先定义上下左右为它附近的的方向，然后变量上下左右四个点，当点满足可达且不在closePoints中时该点为可加入点。然后判断该点是否已经在openPoints中，如果不在将该点加入openPoints中，并且将该点和目标点关联起来。如果在openPoints中，则判断该点的代价是否更小，如果更新则更新openPoints中的点，并且更新该点的联系。将当前点移除出openPoints，并且将当前点加入closePoints，被选择过的点不会在被选中。最后将openPoints排序。

private void GetNearPoints(Point point)
            {
                (int x, int y)[] dir = new (int x, int y)[4]
                {
                    (-1, 0),
                    (0, 1),
                    (1, 0),
                    (0, -1),
                };

                for (int i = 0; i < 4; i++)
                {
                    int x = point.x + dir[i].x;
                    int y = point.y + dir[i].y;
                    if (Get(x, y) > 0 && !closePoints.Contains((x, y)))
                    {
                        Point newPoint = new Point(x, y);
                        newPoint.g = point.g + GetDistance(point, newPoint);
                        newPoint.h = GetDistance(newPoint, dest);

                        int index = IndexOf(newPoint);
                        if (index == -1)
                        {
                            openPoints.Add(newPoint);
                            pointRelation.Add((x, y), (point.x, point.y));
                        }
                        else
                        {
                            Point oldPoint = openPoints[index];
                            if (newPoint.f < oldPoint.f)
                            {
                                openPoints[index] = newPoint;
                                pointRelation[(x, y)] = (point.x, point.y);
                            }
                        }
                    }
                }

                for (int i = 0; i < openPoints.Length; i++)
                {
                    if (openPoints[i] == point)
                    {
                        openPoints.RemoveAt(i);
                        break;
                    }
                }
                closePoints.Add((point.x, point.y));

                openPoints.Sort(comparer);
            }

计算两点间的距离，用来作为预估代价。

private int GetDistance(Point p1, Point p2)
            {
                return math.abs(p1.x - p2.x) + math.abs(p1.y - p2.y);
            }

查找一个点在openPoints中所在的位置。

private int IndexOf(Point point)
            {
                for (int i = 0; i < openPoints.Length; i++)
                    if (openPoints[i] == point)
                        return i;
                return -1;
            }

具体实现

public void Execute()
            {
                cur.g = 0;
                cur.h = GetDistance(cur, dest);

                while (cur != dest)
                {
                    GetNearPoints(cur);
                    if (openPoints.Length == 0)
                        break;
                    cur = openPoints[0];
                }

                if (cur == dest)
                {
                    path.Add(cur);
                    while (pointRelation.ContainsKey((cur.x, cur.y)))
                    {
                        (int x, int y) p = pointRelation[(cur.x, cur.y)];
                        Point point = new Point(p.x, p.y);
                        cur = point;
                        path.Add(cur);
                    }
                }
            }

首先先将当前点的g和h都初始化一下。（当前点在初始化时已经定义为起点）

判断当前点是否是终点，不是则获取当前点附近的点，如果openPoints长度为0，说明已经没有可选择的点，目标点是无法到达的，就退出循环。否则将当前的更新为总代价最小的点，重复以上步骤。

在退出循环后，判断当前点是否是终点，如果不是，说明没有到终点的路径。如果是就回溯路径，将回溯过程的点加入path中。

使用

public static List<Point> GetPath(int[,] map, Point origin, Point dest)
        {
            List<Point> path = new List<Point>();

            int mapWidth = map.GetLength(0);
            int mapHeight = map.GetLength(1);
            NativeArray<int> nativeMap = new NativeArray<int>(mapWidth * mapHeight, Allocator.TempJob);
            NativeList<Point> nativePath = new NativeList<Point>(Allocator.TempJob);
            NativeList<Point> nativeOpenPoints = new NativeList<Point>(Allocator.TempJob);
            NativeHashSet<(int x, int y)> nativeClosePoints = new NativeHashSet<(int x, int y)>(mapWidth * mapHeight, Allocator.TempJob);
            NativeHashMap<(int, int), (int, int)> pointRelation = new NativeHashMap<(int, int), (int, int)>(mapWidth * mapHeight - 1, Allocator.TempJob);
            for (int i = 0; i < mapWidth; i++)
            {
                for (int j = 0; j < mapHeight; j++)
                {
                    nativeMap[i * mapHeight + j] = map[i, j];
                }
            }

            AStarJob job = new AStarJob()
            {
                map = nativeMap,
                path = nativePath,
                origin = origin,
                dest = dest,
                mapWidth = mapWidth,
                mapHeight = mapHeight,
                openPoints = nativeOpenPoints,
                closePoints = nativeClosePoints,
                pointRelation = pointRelation,
                cur = origin
            };
            JobHandle handle = job.Schedule();
            handle.Complete();

            for (int i = nativePath.Length - 1; i >= 0; i--)
                path.Add(nativePath[i]);

            nativeMap.Dispose();
            nativePath.Dispose();
            nativeOpenPoints.Dispose();
            nativeClosePoints.Dispose();
            pointRelation.Dispose();

            return path;
        }

初始化所有AStar需要的参数，将算出来的路径返回即可。

演示