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

问题描述

很久以前，我尝试使用经过修改的客户端和简单的广度优先搜索算法来实现具有寻路功能的 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 个移动路径。

机器人试图从右边的橙色方块到梯子末端的蓝色方块，这种东西在空中，这使得寻路更难公平：

这是可视化：

绿色：采用的路径，蓝色：关闭列表，浅蓝色：打开列表

从我所见，寻路似乎是有效的，但我未受过教育的假设是，它非常无效，因为它在最终找到目标之前在封闭列表中有很多块。

这个时间似乎随着路径的延长而呈指数增长，因为有时需要半个小时左右才能找到目标，我认为这是行不通的。

标签： c#3dminecraftpath-findinga-star

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

问题描述

解决方案

推荐阅读