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

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

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

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

编辑: 正如 Rudy Velthuis 所指出的，我还没有完全解释我所说的“自然”是什么意思。自然地，我的意思是一条不太长的路径，只需要用户改变几次方向。

最佳答案

A* 是要走的路，但您应该考虑到它需要一些技巧才能产生“自然”路径。

由于您的 map 允许对角线移动，因此启发式可能类似于:

/* "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 (包含大量信息和 wonderful introduction to A* )中进行了描述。

关于c - 在网格上的两点之间找到最自然的路线，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38315676/