java - 我怎样才能修改这个视线算法来接受穿过角落的光线？

Question

我正在研究一种基于 Theta* 的寻路算法，它是 A* 的一种变体，它提供了一个很好的寻路系统，它不受网格的限制，即使地形/障碍物是基于网格模式的。该系统需要一种视线算法来确定特定路径是否被阻挡。

我找到了 this非常有用的视线算法，我已经在我的代码中成功地实现了它。不幸的是，它认为以下是无效路径:

但是，出于我的目的，我希望这样的路径被认为是有效的。我试图通过使用基本 y = mx + b 公式检测点是否在线上来修改算法，但算法的不一致使我无法依赖这样的系统。

是否有任何有效的方法来修改此算法以允许这样的路径？还有另一种算法会更好吗？请记住，路径的起点和终点不一定必须限制在网格中，因此所有点都使用 double 精度。

Answer 1

您引用的代码实际上省略了明确处理线穿过网格点(四个正方形接触的地方)的情况。您需要检查 error == 0。

在这种情况下，与网格点接触的四个方 block 中至多有一个可能被阻挡以仍然具有有效路径。

问候，埃里希