私は、パスを見つけるために A* を使用した交差可能な正方形と交差不可能な正方形を備えたグリッドベースのシステムを使用しており、パスを見つけることができるかどうかを確認するために (2 つの領域が接続されているかどうかを確認するために) フラッド フィルを使用しています。
私の問題は、新しい交差不可能な領域が非常に頻繁に (1 秒間に最大 16 回) 導入される可能性があり、グリッドがかなり大きい (約 500 x 500) ため、O(mn) フラッド フィル ソリューションでさえかなり長い時間がかかることです。 . フラッドフィルのさまざまな実装を調べましたが、必要なものに似たものは見つかりませんでした。
だから私の質問は、以前のグリッドに基づいて、新しい交差不可能な領域 (常に長方形になる) のリストに基づいて、繰り返されるフラッド フィル コールを最適化する方法があるということです。