A*寻路生成错误路径

Question

我正在构建一个迷宫游戏，如果玩家进入他的范围，敌人准备追捕玩家，我正在使用 A*Pathfinding 算法来这样做，我以程序方式构建迷宫，其中每个块在迷宫中有一个带有 x 和 z 位置的 MapLocation，所以起始位置是敌人的位置，目标是玩家的位置，但有时，当玩家进入敌人的范围时，pathfing 会忽略迷宫的某些块以找到播放器，我正在上传视频来说明问题：

https://www.youtube.com/watch?v=_amIf75wruw

IEnumerator Search(Vector3 start, Vector3 goal)
        {
            pathSuccess = false;
            waypoints = new Vector3[0];
            Heap<Path> open = new Heap<Path>(maze.MaxSize);
            HashSet<Path> closed = new HashSet<Path>();

            Path startNode = new Path(maze.GetMapLocation(start), 0, 0, 0, null);
            Path goalNode = new Path(maze.GetMapLocation(goal), 0, 0, 0, null);

            open.Add(startNode);
            lastPos = startNode;

            while (open.Count > 0)
            {
                if (lastPos.Equals(goalNode))
                {
                    pathSuccess = true;
                    break;
                }
                foreach (MapLocation dir in maze.directions)
                {
                    MapLocation neighbour = dir + lastPos.location;
                    if (maze.map[neighbour.x, neighbour.z] == 1) continue;
                    if (neighbour.x < 1 || neighbour.z >= maze.width || neighbour.z < 1 || neighbour.z >= maze.depth) continue;
                    if (IsClosed(neighbour, closed)) continue;

                    float G = Vector2.Distance(lastPos.location.ToVector(), neighbour.ToVector()) + lastPos.G;
                    float H = Vector2.Distance(neighbour.ToVector(), goalNode.location.ToVector());
                    float F = G + H;

                    if (!UpdateMarker(neighbour, G, H, F, lastPos, open))
                        open.Add(new Path(neighbour, G, H, F, lastPos));
                }
                Path pm = open.RemoveFirst();
                closed.Add(pm);

                lastPos = pm;
            }
            yield return null;
            if (pathSuccess)
            {
                waypoints = RetracePath(startNode);
            }
            PathRequestManager.Instance.FinishedProcessingPath(waypoints, pathSuccess);
        }

        bool UpdateMarker(MapLocation pos, float g, float h, float f, Path prt, Heap<Path> open)
        {
            foreach (Path p in open)
            {
                if (p.location.Equals(pos))
                {
                    p.G = g;
                    p.H = h;
                    p.F = f;
                    p.parent = prt;
                    return true;
                }
            }
            return false;
        }

        bool IsClosed(MapLocation marker, HashSet<Path> closed)
        {
            foreach (Path p in closed)
            {
                if (p.location.Equals(marker)) return true;
            }
            return false;
        }

        Vector3[] RetracePath(Path startNode)
        {
            Path begin = lastPos;
            List<Vector3> path = new List<Vector3>();
            while (!startNode.Equals(begin) && begin != null)
            {
                path.Add(begin.Position(maze));
                begin = begin.parent;
            }
            path.Reverse();
            return path.ToArray();
        }

public MapLocation GetMapLocation(Vector3 position)
        {
            MapLocation mapLocation = new MapLocation((int)position.x / scale, (int)position.z / scale);
            return mapLocation;
        }
public List<MapLocation> directions = new List<MapLocation>() {
                                            new MapLocation(1,0),
                                            new MapLocation(0,1),
                                            new MapLocation(-1,0),
                                            new MapLocation(0,-1) };

迷宫是这样生成的：

public byte[,] map;
 public virtual void Generate()
        {
            for (int z = 0; z < depth; z++)
                for (int x = 0; x < width; x++)
                {
                   if(Random.Range(0,100) < 50)
                     map[x, z] = 0;     //1 = wall  0 = corridor
                }
        }

Answer 1

调试在 GetMapLocation() 中除以比例时获得的值，它可能会因为缩放/舍入而跳过单元格？

我会有一个 map[x,y] 数组，然后按比例乘以它以使其在屏幕上以像素为单位正确显示，但是在原始未缩放的 Map[x,y] 数组上进行寻路。 IE 将逻辑与渲染分开。