c++ - 1 つのユニットの兵士がグリッド マップ上で接続されているかどうかを判断する方法

Question

私はゲームを作成しており、マップはグリッドのようなもので、いくつかのユニットがあります (すべてのユニットにはカップルの兵士がいます)。1 つのユニットの兵士が接続されているかどうかを判断する方法 (接続されているとは、すべての兵士が少なくとも 1 つの方向で同じユニットの兵士を隣人に持っていることを意味します)。マップはグリッドであり、隣接セルは 2 つであり、x および/または y で 1 だけ異なる場合があります (境界線を除くすべてのセルには、マトリックスのように 8 つの隣接セルがあります)。

Answer 1

ここで塗りつぶしを使用できます。グラフはグリッドのG=(V,E)場所であり、VE = { (u,v) | there is a soldier in both u and v from the same unit }

基本的に、問題をこのグラフに縮小すると、任意のグラフ検出アルゴリズムで問題が解決されます。目的のユニットの兵士のいずれかからアルゴリズムを呼び出すと、発見アルゴリズムが正確に kノードを発見した場合、ユニットが「接続」されているかどうかがわかりますk。

Answer 2

ユニオン検索データ構造を使用します。兵士の各ペアをテストします。2 人の兵士が隣接している場合は常に、同等のクラスが統合されます。そのようなすべてのペアをテストした後、単一の同等クラスになった場合、ユニットは接続されています。