我有一个由瓷砖制成的2d世界 . 瓷砖要么是可以通行的，要么是不可通过的，要么有某种运动损失 .
所有实体和图块都有自己的命中框和大小以进行碰撞检测 . 每个瓷砖的尺寸为16x16px .
我读过的大多数例子似乎表明我们正在从一个瓷砖的中心移动到另一个瓷砖的中心 . 正如我们从下面的图片中看到的那样，红色部分看起来不是最佳的，也不考虑实体大小 . 路径节点也被放置在2d阵列中，每个节点只有8个可能的方向 .
但实际上最短路径不是这样的吗？
我该如何实现寻路？是否应将切片拆分为较小的节点以进行寻路，或者是否有其他方法可以获得更准确的路径？即使我将每个图块分割为10x10个寻路节点，它仍然找不到2个点之间的最短线 .
是否应该有超过8个方向，如果有，应该如何实施？
例如，如果我的世界是50x50瓷砖大，那么寻路贴图应该如何以及应该如何生成？
1 回答
这取决于你对“最短路径”的定义以及你打算用它做什么 .
在您的示例中，您似乎认为有效移动是从一个磁贴的中心到无障碍视图中任何其他磁贴的中心 . 如何验证移动到部分阻塞的瓷砖尚不清楚 . 这与几何上最短的路径不同，后者显然会拥抱墙壁，而现实的最短路径将使用单位宽度和转弯半径来避免墙壁和方向的突然变化 .
一种常见的方法是像往常一样使用A *，然后以多种方式对路径进行后处理以优化和平滑它 . 这适用于像您这样的基于网格的世界，以及更一般的导航 .
Gamasutra对此进行了很好的概述，称为Toward More Realistic Pathfinding，具有平滑曲折和添加曲线的各种想法和技术，以优化具有加速度和方向的单位的路径 .