在平铺的二维世界中实现寻路

Question

我有一个由瓷砖组成的二维世界。方块要么可以通过，要么不能通过，或者有某种移动惩罚。

所有实体和图块都有自己的碰撞盒和大小，用于碰撞检测。 每个图块的尺寸为 16x16 像素。

我读过的大多数例子似乎都表明我们正在从一个图块的中心移动到另一个图块的中心。正如我们从下图中看到的，红色部分看起来并不是最佳的，也没有考虑实体大小。此外，路径节点也被放入二维数组中，每个节点只有 8 个可能的方向。

但实际上最短路径不是这样的吗？

我应该如何实现寻路？ 是否应该将图块分割成较小的节点以进行寻路，或者是否有其他方法来获得更准确的路线？即使我将每个图块分割为 10x10 寻路节点，它仍然找不到 2 点之间的最短线。

是否应该有超过8个方向？如果是，应该如何实施？

例如，如果我的世界有 50x50 块大，那么寻路地图应该是什么样子以及如何生成？

Answer 1

这取决于您对“最短路径”的定义以及您打算用它做什么。

在您的示例中，您似乎认为有效的移动是在无障碍视图中从一个图块的中心到任何其他图块的中心。目前尚不清楚如何验证移动到部分受阻的图块。这与几何最短路径不同，几何最短路径显然会紧贴墙壁，而现实的最短路径将使用单位宽度和转弯半径来避免墙壁和方向突然变化。

一种常见的方法是照常使用A*，然后通过多种方式对路径进行后处理以对其进行优化和平滑。这既适用于像您这样的基于网格的世界，也适用于更一般的导航网格。

Gamasutra对此有一个很好的概述，称为“走向更现实的寻路”，其中包含从平滑之字形和添加曲线到优化具有加速度和方向的单位路径的各种想法和技术。 我遇到了几乎同样的问题，我已经为所有图块编写了一个预计算软件，并进行了一些优化

Answer 2

https://github.com/FurkanGozukara/pathfinding-2d-tile-map

开发视频在这里：https://www.youtube.com/watch?v=jRTA0iLjv6M

我确实提出了自己的算法和实现。因此它可能不是最好的也不是最优化的。虽然它已经实现到我的免费浏览器游戏 MonsterMMORPG 中并且效果很好：https://www.monstermmorpg.com/