c# - A* 寻路在 3D Minecraft 环境中不起作用

Question

很久以前，我尝试使用修改后的客户端和简单的广度优先搜索算法来实现带有寻路功能的 Minecraft Bot，该算法有效，但性能极差。尽管如此，我实际上已经能够决定打破某些块或放置它们以达到目标是否更聪明。
所以我开始实现我自己的 Minecraft 客户端，我猜它可以正常工作 :D 另外我想使用 A* Pathfinding 来获得更好的性能。不幸的是，在实现它之后，我开始发现它在大多数情况下都很好用，但是一旦路径变得更加复杂，它就会直接计算几分钟而没有找到通往目标的路径。似乎它要么朝错误的方向搜索，要么以某种方式完全跳过目标。无论哪种方式，它都找不到它。再加上实现跳跃后可以越过间隙，不管他是否必须，他都会继续跳跃。看起来像一个快乐的 Minecraft 玩家跳来跳去，但没有任何意义。即使将跳跃成本设置为极大值，它仍然会到处跳跃，而不是正常行走。
我开始认为这种方法肯定存在根本性错误，但无法找出它可能是什么。
这是我的寻路逻辑

class PathFinder
{
    private const int WalkCost = 10;
    private const int DiagonalWalkCost = 14;
    private const int JumpCost = 5;

    private const int MaxDistance = 100;

    private int GetDistance(Node a, Node b)
    {
        return Math.Abs(b.X - a.X) + Math.Abs(b.Y - a.Y) + Math.Abs(b.Z - a.Z);
    }

    public Path FindPath(Node start, Node goal)
    {
        start.H = GetDistance(start, goal) * WalkCost;
        var open = new List<Node>();
        open.Add(start);
        var closed = new List<Node>();
        var cameFrom = new Dictionary<Node, Node>();
        var action = new Dictionary<Node, Movement>();
        var done = false;
        var considered = 0;
        var world = Client.Instance.World;

        Node current;
        while (open.Count > 0)
        {
            current = open.OrderBy(n => n.F).First();

            open.Remove(current);
            closed.Add(current);

            if (current == goal)
            {
                done = true;
                break;
            }

            foreach (var neighbour in GetNeighbours(current))
            {
                if (GetDistance(neighbour, start) > MaxDistance)
                    continue;

                if (closed.Contains(neighbour))
                    continue;

                if (neighbour.Y > current.Y) //Jump up
                {
                    if (!IsWalkable(neighbour)
                        || world.IsSolid(current.Up().Up()))
                        continue;

                    neighbour.G = current.G + WalkCost + JumpCost;
                    action[neighbour] = Movement.JumpUp;
                }
                else if(neighbour.Y < current.Y) //Jump Down
                {
                    if (!IsWalkable(neighbour)
                        || world.IsSolid(neighbour.Up().Up()))
                        continue;

                    neighbour.G = current.G + WalkCost + JumpCost;
                    action[neighbour] = Movement.Fall;
                }
                else //Walk
                {
                    if (!IsWalkable(neighbour))
                        continue;

                    if (neighbour.X != current.X && neighbour.Z != current.Z) //Diagonal
                    {
                        if (world.IsSolid(new Node(neighbour.X, current.Y, current.Z))
                            || world.IsSolid(new Node(neighbour.X, current.Y, current.Z).Up())
                            || world.IsSolid(new Node(current.X, current.Y, neighbour.Z))
                            || world.IsSolid(new Node(current.X, current.Y, neighbour.Z).Up()))
                            continue;

                        neighbour.G = current.G + DiagonalWalkCost;
                        action[neighbour] = Movement.Walk;
                    }
                    else //Straight
                    {
                        if(GetDistance(current, neighbour) >= 2) //Straight Jump
                        {
                            var nodeBetween = new Node(current.X + (neighbour.X - current.X) / 2, current.Y, current.Z + (neighbour.Z - current.Z) / 2);
                            if (world.IsSolid(current.Up().Up())
                                || world.IsSolid(neighbour.Up().Up())
                                || world.IsSolid(nodeBetween)
                                || world.IsSolid(nodeBetween.Up())
                                || world.IsSolid(nodeBetween.Up().Up()))
                                continue;

                            neighbour.G = current.G + 2 * WalkCost + JumpCost;
                            action[neighbour] = Movement.JumpGap;
                        }
                        else //Straight Walk
                        {
                            neighbour.G = current.G + WalkCost;
                            action[neighbour] = Movement.Walk;
                        }
                    }
                }

                considered++;

                var previousEntry = open.FirstOrDefault(n => n == neighbour);
                if (previousEntry == null || neighbour.G < previousEntry.G)
                {
                    neighbour.H = GetDistance(neighbour, goal) * WalkCost;
                    cameFrom[neighbour] = current;
                    open.Add(neighbour);
                }
            }
        }

        Client.Instance.SendChatMessage(String.Format("{0} possible moves considered", considered));

        if (!done)
            return null;

        var currentNode = goal;
        var path = new List<Node>();
        var moves = new List<Movement>();
        while (currentNode != start)
        {
            path.Add(currentNode);
            moves.Add(action[action.Keys.First(k => k == currentNode)]);
            currentNode = cameFrom[cameFrom.Keys.First(k => k == currentNode)];
        }
        path.Add(start);
        path.Reverse();
        moves.Add(Movement.Walk);
        moves.Reverse();
        return new Path(path, moves);
    }

    private bool IsWalkable(Node node)
    {
        var world = Client.Instance.World;
        var block = world.GetBlock(node.X, node.Y, node.Z);
        return world.IsSolid(node.Down())
            && !world.IsSolid(node)
            && !world.IsSolid(node.Up())
            && !block.BlockName.Contains("water")
            && !block.BlockName.Contains("lava");
    }

    private Node[] GetNeighbours(Node node)
    {
        var neighbours = new List<Node>();

        //neighbours.Add(node.Up()); //pillar up
        //neighbours.Add(node.Down()); //dig down

        neighbours.Add(node.North()); //simple walk
        neighbours.Add(node.East());
        neighbours.Add(node.South());
        neighbours.Add(node.West());

        neighbours.Add(node.North().East()); //diagonal walk
        neighbours.Add(node.North().West());
        neighbours.Add(node.South().East());
        neighbours.Add(node.South().West());

        neighbours.Add(node.North().Up()); //jump up
        neighbours.Add(node.East().Up());
        neighbours.Add(node.South().Up());
        neighbours.Add(node.West().Up());

        neighbours.Add(node.North().Down()); //fall down
        neighbours.Add(node.East().Down());
        neighbours.Add(node.South().Down());
        neighbours.Add(node.West().Down());

        neighbours.Add(node.North().North()); //jump 1 wide gap
        neighbours.Add(node.East().East());
        neighbours.Add(node.South().South());
        neighbours.Add(node.West().West());

        return neighbours.ToArray();
    }
}

这是我的节点类

public class Node/* : IEquatable<Node>*/
{
    public int X { get; set; }
    public int Y { get; set; }
    public int Z { get; set; }

    public int G { get; set; }
    public int H { get; set; }

    public int F { get => G + H; }

    public Node CameFrom { get; set; }

    public Node(int x, int y, int z)
    {
        X = x;
        Y = y;
        Z = z;
    }

    public Node()
    {

    }

    public Node Down()
    {
        return new Node(X, Y - 1, Z);
    }

    public Node Up()
    {
        return new Node(X, Y + 1, Z);
    }

    public Node East()
    {
        return new Node(X + 1, Y, Z);
    }

    public Node West()
    {
        return new Node(X - 1, Y, Z);
    }

    public Node South()
    {
        return new Node(X, Y, Z + 1);
    }
    public Node North()
    {
        return new Node(X, Y, Z - 1);
    }

    //public bool Equals(Node other)
    //{
    //    return other.X == X && other.Y == Y && other.Z == Z;
    //}

    public override bool Equals(object obj)
    {
        if (!(obj is Node))
            return false;

        return this == (Node)obj;
    }

    public static bool operator ==(Node a, Node b)
    {
        if (a is null && b is object || b is null && a is object)
            return false;
        if (a is null && b is null)
            return true;
        return a.X == b.X && a.Y == b.Y && a.Z == b.Z;
    }

    public static bool operator !=(Node a, Node b)
    {
        if (a is null && b is object || b is null && a is object)
            return true;
        if (a is null && b is null)
            return false;

        return a.X != b.X || a.Y != b.Y || a.Z != b.Z;
    }

    //public static bool operator ==(Node a, Node b)
    //{
    //    return a.GetHashCode() == b.GetHashCode();
    //}

    //public static bool operator !=(Node a, Node b)
    //{
    //    return a.GetHashCode() != b.GetHashCode();
    //}

    public override int GetHashCode()
    {
        int hash = 17;
        hash = hash * 23 + X.GetHashCode();
        hash = hash * 23 + Y.GetHashCode();
        hash = hash * 23 + Z.GetHashCode();
        return hash;
    }
}

忽略困惑的平等检查。我在想这可能与我在节点中检查相等性的方式有关，但也没有成功，除了我的代码比 xD 之前更困惑
有人对这里可能出现的问题有什么建议吗？任何关于类似事物的文章，这意味着在 3D 环境中寻找路径并跳过间隙，也将不胜感激。
添加
这是一个运行过程的可视化，它花费了 16.5 秒，查看了 62.700 个可能的邻居，最终总共有 48 个移动的路径。
机器人试图从右边的橙色块移动到梯子末端的蓝色块，它在空中，这使得寻路更难公平:

这是可视化:

绿色:采用的路径，蓝色:封闭列表，浅蓝色:开放列表
从我所看到的，寻路似乎是有效的，但我没有受过教育的假设是，它是非常无效的，因为它在最终找到目标之前在封闭列表中有很多块。
随着路径越长，这个时间似乎呈指数增长，因为有时需要长达半小时左右才能找到目标，我认为这是行不通的。

Answer 1

我还没有看到所有的代码，但 GetDistance 似乎是错误的。
假设我们忘记了 Y。
(1,1) 和 (2,2) 与您的方法的距离为 2，因此与 (1,1) 和 (1,3) 的距离相同，这是错误的，您可以绘制以查看。
对于 3D 距离，计算是

float deltaX = b.x - a.x;
float deltaY = b.y - a.y;
float deltaZ = b.z - a.z;

float distance = (float) Math.Sqrt(deltaX * deltaX + deltaY * deltaY + deltaZ * deltaZ);