找到网格上两点之间最自然的路线

Question

假设我有一个字节数组，每个位代表一个固定大小的正方形并指示它是否可访问，我如何找到两点之间最自然的路线（人类可能采取的路线）？例如，假设数组表示以下网格：

在不能穿过灰色方块的地方，我需要一种算法来找到橙色方块指示的路径，而不是棕色方块表示的路径。

请注意，虽然橙色路径也是最短的，但这只是一个奖励，而不是必需的。我只需要找到方向变化最小的路径（在长度和变化之间取得适当的平衡）。此外，该算法不得需要大量内存，因为它在嵌入式芯片上需要运行。

编辑： 正如 Rudy Velthuis 所指出的，我还没有准确解释 "natural" 的意思。自然地，我的意思是一条不太长的路径，只需要用户改变几次方向。

Answer 1

我认为您正在寻找 A* 寻路。虽然它会产生寻找最短路径的副作用，但它看起来也会很自然。很长一段时间，它都是视频游戏的黄金标准。

这里有一篇关于算法的文章。注意：您必须稍微修改它以允许对角线移动。

https://www.raywenderlich.com/4946/introduction-to-a-pathfinding

Answer 2

构建一个图形，其中每个方向变化都是一条边。

每个单元格表示为 8 个顶点。垂直、水平和对角线边缘是免费的（成本为 0）。其他的具有非零成本（或 45、90 和 135 度转弯的不同成本，如果您想要更急转弯的成本更高）。以自然的方式连接相邻的单元格（N 到 S、W 到 E、SW 到 NE 等）。也为这些边缘分配一些成本（或 vertical/horizontal 和对角线边缘的不同成本，具体取决于您如何定义 "path length"）。

然后在图上使用A*。通过改变成本，您可以调整 "good-looking" 和 "short" 之间的平衡。

Answer 3

A* 是要走的路，但您应该考虑到它需要一些技巧才能生成 "natural" 路径。

由于您的地图允许对角线移动，启发式可以是这样的：

/* "Octile" heuristic */
int h(node n)
{
  int dx = abs(n.x - goal.x);
  int dy = abs(n.y - goal.y);

  if (dx > dy)
    return 14 * dy + 10 * (dx - dy);
  else
    return 14 * dx + 10 * (dy - dx);
}

即使使用这种启发式方法，您还是运行打成平手：SW、SW、SW、W、W、W 的成本与 SW、W、SW、W、SW、W 相同（看起来更好）。

有一些快速的技巧可以解决这个问题（打破平局）。

它们在 Amit's page (which contains a lot of information and a wonderful introduction to A*) 中有描述。

找到网格上两点之间最自然的路线

Finding the most natural route between two points on a grid

c

algorithm

performance

artificial-intelligence