2D寻路算法

本文关键字：算法 寻路 2D | 更新日期: 2023-09-27 18:23:55

我正试图写一段代码，在二维地图中找到最短路径，但有一些限制：

  1. 地图上没有障碍物
  2. 地图是"环绕"的，这意味着人工智能可以穿过一个边界，出现在对面。（很像旧诺基亚手机上的蛇游戏）
  3. 然而，如果起点和目的地之间有一条链接路径，则该路径的旅行时间将减少，例如10%
  4. 必须走最短的路

普通的A*算法似乎不符合这些要求，因为它不允许从一个边界传送到另一个边界，而且是最佳优先算法。那么，我应该如何解决这个问题？

由于我是在C#中做这件事的，所以C#中的任何相关示例都被告知

2D寻路算法

A*算法将满足您的需求，您只需要以不同的方式思考即可。A*不仅仅是一种网格算法，它还是一种图遍历算法。

因此，为了做到这一点，你必须将地图表示为一系列相互连接的点。然后，这些点可以像一个大圆环一样环绕。然后，每个点都有到其他点的连接，这些边有一个权重，因此遍历不同的边对算法来说更"昂贵"。

维基百科有一个这样的图遍历的例子，沿着页面往下走，带有加权边。

编辑：详细说明环绕问题。假设你有一个简单的点网格，像这个一样环绕

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+

通常情况下，这里的边缘是

1-2, 2-3, 4-5, 5-6, 2-5, 3-6, 4-7, 5-8, 6-9, 7-8, 8-9

为了使这个包裹你会添加边缘

1-7, 2-8, 3-9, 1-3, 4-6, 7-9

到边列表。然后，您将正常应用A*算法，存储您访问过的每个点，并从此点遍历边。请注意，您不能再只处理有问题的点，而是必须跟踪每个点的边。

为了解决某些零件更容易处理的问题，可以在边上存储一个额外的值，以确定遍历它们的难度。假设每条边的值都为1，但边4-5的遍历难度是边4-5的两倍。然后将值2指定给该边，并在计算到目标点的距离的启发式算法时使用该值。

相关文章：