連續搜索空間的路徑算法？

Question

我目前正在製作一個RTS遊戲，我需要一種方法來計算連續2d飛機上的兩個點之間的最短路徑，其中存在某些障礙物。

我有一個開始位置，一個結束位置和一個可以測試位置是否有效的函數。我需要一種算法，返回一系列要移動的點以便到達目的地。

我所知道的大多數路徑算法（如A *和IDA *）都需要離散化的搜索空間。我會自己將飛機劃分成一個網格，但我擔心這會導致沿對角線移動時看起來非常不自然的之字形圖案。有沒有辦法來緩解這個問題，或者我可以使用不同的路徑算法？它甚至不需要找到絕對的最短路徑，只是一條有意義的路徑。

Answer 1

一種方法可能是通過僅考慮刨削有趣的點（例如障礙邊界上的點）來離散搜索空間，例如僅限於邊界框的角點，然後使用您已知的任何算法。

另一種選擇是在網格上計算並平滑網格上找到的最佳路徑。