很久以前，我尝试使用修改后的客户端和简单的广度优先搜索算法来实现具有寻路功能的 Minecraft 机器人，该算法有效，但性能极差。尽管如此，我实际上已经能够决定打破某些障碍或放置它们以达到目标是否会更明智。
所以我开始实现我自己的 Minecraft 客户端，我猜它工作得“不错”:D 另外我想使用 A* 寻路来获得更好的性能。不幸的是，在实现它之后，我开始发现它在大多数情况下都工作得很好，但是一旦路径变得更加复杂，它就会直接计算几分钟而无法找到到达目标的路径。看起来它要么搜索了错误的方向，要么以某种方式完全跳过了目标。不管怎样，它找不到它。除此之外，在实现跳跃以能够跳过间隙之后，无论他是否必须，它都会继续跳跃。看起来就像一个快乐的《我的世界》玩家在跳来跳去，但没有任何意义。即使将跳跃成本设置为非常大的数字，它仍然会到处跳跃，而不是正常行走。
我开始认为这种方法一定存在根本性错误，但无法找出它可能是什么。
这是我的寻路逻辑
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();
}
}
这是我的 Node 类
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 次移动的路径。
机器人试图从右侧的橙色方 block 移动到梯子末端的蓝色方 block ，该物体位于空中，这使得寻路变得更加困难:
这是可视化:
绿色:采取的路径，蓝色:封闭列表，浅蓝色:开放列表
从我看来，寻路似乎有效，但我未经教育的假设是，它非常无效，因为在最终找到目标之前，它在封闭列表中有很多 block 。
随着路径越长，这个时间似乎呈指数级增长，因为有时需要长达半小时左右才能找到目标，我认为这是行不通的。
最佳答案
我还没有看到所有的代码，但 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);
关于c# - A* 寻路在 3D Minecraft 环境中不起作用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/65655920/