コーナーを通過する光線を受け入れるために、この視線アルゴリズムを変更するにはどうすればよいですか？

Question

私は地形/障害物がグリッドパターンに基づいていても、グリッドに制約されていない経路探索に適したシステムを提供するA *の変種であるTheta *に基づいた経路探索アルゴリズムに取り組んでいます。このシステムは、特定の経路が遮られているかどうかを決定する視線アルゴリズムを必要とする。

私はthis非常に有用な視線アルゴリズムを発見し、私は正常に私のコードでそれを実装しました。残念ながら、それは次のように無効なパスであると考える：

しかし、私の目的のために、私は有効と見なされるために、このようなパスをしたいです。私は、基本的なy = mx + b公式を使用して、ポイントがライン自体にあるかどうかを検出することによってアルゴリズムを修正しようとしましたが、アルゴリズムの矛盾が私にこのようなシステムに頼ることを妨げています。

このようなパスを許可するためにこのアルゴリズムを変更する効率的な方法はありますか？よりうまくいく別のアルゴリズムがありますか？パスの開始点と終了点はではなく、が必ずグリッドに限定されるため、すべての点でdoubleの精度が使用されます。

Answer 1

実際に参照するコードは、線がグリッドポイント（4つの四角形が接触する部分）を通過する場合を明示的に処理するために省略します。 error == 0を確認する必要があります。

この場合、グリッドポイントに接触している四角形のうち最大でも1つがブロックされて有効なパスが残っている可能性があります。

よろしく、働くクール エーリッヒ