3

現在、2D グリッド ベースのサンドボックス タイプのゲームに取り組んでいます。技術的には、マップとしての 3D は、グリッド タイルを互いの背後に配置できる 3 次元配列です。ただし、2D でレンダリングされます。Android 向けのリリースを検討しているため、ゲーム内のすべてのスクリプトは非常に効率的である必要があります。

ゲームには、プレーヤーがワイヤーを使用してマシンを電源に接続できるようにする主要な配線メカニズムがあります。すべての回路のワイヤで接続されたすべてのエンティティを効率的に計算する方法が必要です。

私が考えることができる唯一のフェイルセーフな方法は、フラッド フィル アルゴリズムを使用して 1 点から広がり、接続されているすべてのオブジェクトを記録することですが、これは Android アプリには非効率的すぎると感じています。

ゲームの構造とワイヤーに関する情報を次に示します。

  • ゲームはJavaで書かれています。
  • 現在、すべてのオブジェクトは静的です。
  • すべてのオブジェクトは、オブジェクトの位置を反映する配列に保持されます。隣接するオブジェクトとその変数には、配列内の x/y 値を参照するだけでアクセスできます。これは、隣接するブロックを必要に応じて更新できることを意味します。
  • ワイヤーはプレイヤーが自由に配置および削除でき、任意のパターンに従うことができます。
  • ワイヤは、すべての x/y/z 軸で他のワイヤや機械に接続できます。
  • 特定のオブジェクトは電力を出力し、他のオブジェクトは電力を使用します。

私は現在、ワイヤー自体を含むワイヤーのグループに接続されたすべてのオブジェクトを含むwireGroupオブジェクトを持つという方針に沿って考えています。各ワイヤ オブジェクトには、新しいワイヤ (およびマシン) を簡単にワイヤ グループに追加できるようにするワイヤ グループ ID が含まれます。

私が本当に必要としているのは、ワイヤが取り外されたときに接続されたオブジェクトを検出する方法だけです。接続されたオブジェクトが配置されているときにそれを検出するのは簡単です。新しいワイヤの隣にある機械を、隣接するワイヤの wireGroup のリストに追加するだけです。

ワイヤーを外す時に問題が発生します。2 つのオブジェクトを接続する 7 つまたは 8 つの固有のワイヤ パスである可能性があるため、1 つのワイヤを削除した場合の効果を見つけるのは困難です。

例えば：

EG1

ここでは、接続されたオブジェクトに変更が加えられていないことがわかります。

EG2

ここで、wireGroup は 2 つの wireGroups に分割されます。1 つは青と下の白を含み、もう 1 つは 2 つの白を含みます。

誰かが 2D のみのアルゴリズムを思いついたとしても、それは素晴らしいことです。

申し訳ありませんが、何か重要なことを見逃している場合は、教えてください。修正できるようにします。

4

2 に答える 2

3

すべての「接続可能な」ポイント (空、電源、またはマシン) を (切断された) グラフのノードと考えてください。ワイヤは 2 つのノードを接続できます。各ノードが接続されているワイヤを追跡し、各ワイヤを「給電」と「非給電」の 2 つのタイプのいずれかであると考えているとします。「給電」ワイヤは、このノードに電力を送信しているワイヤです。各ノードは、これらをペアのセットで追跡します。「給電」セットにワイヤがある場合、またはそれ自体が電源である場合、ノードは「給電」されています。

興味深い質問は、ワイヤの追加または削除を処理する方法です。

ワイヤが 2 つのノード間に配置される場合、2 つのノードのそれぞれについて、他のノードの「電源」ステータスに応じて、電源が入っているセットまたは電源が入っていないセットのいずれかに配置します。その結果、このノードが非給電状態から給電状態になった場合は、ワイヤを「非給電状態」から「給電状態」に移動して、ノードとワイヤの状態を適切に変更しながらグラフをたどります。

ワイヤーが削除された場合は、それが存在する接続されたワイヤーのセットからそれを削除します。いずれかのエンドポイント ノードに空の「電力供給された」接続のセットがある場合は、そのノードからグラフを移動して全員をオフにします。

これにより、複数の電源入力が非常に効率的に処理され、状態が変化した場合にのみ複数のノードにアクセスする必要があります。また、サブグラフ内のいずれかのノードの状態が変化すると、サブグラフ内のすべてのノードの状態が変化します。

于 2013-03-29T04:05:05.993 に答える
0

各ノードが電力を供給または受け取ると想像してください。各ワイヤには、電力が移動する 1 つまたは複数の方向 (電源から要素へ) が含まれています。2 つの接続された電源は、2 つの内部接続によって表される 1 つのワイヤを持ちます。

したがって、力の有向グラフがあります。ワイヤを削除すると、関連するすべての内部接続が削除されます。ワイヤの除去が影響したすべてのノードをチェックして、着信接続があるかどうかを確認します。何もなく、ノードが以前に電源投入されていた場合は、その時点からグラフをたどって、すべてのノードの電源を切る必要があります。

ワイヤの追加も簡単です。両方のノードの電源状態を確認します。電力が供給されている各ノードは、他のノードの方向に内部接続を構築します。次に、すべてのノードで外向きの接続を構築する他のノードからグラフをウォークする必要があります。どちらにも電力が供給されていない場合は、電力が供給された場合に変更される可能性のある方向のない接続を構築します。これにより、複数の電源を非常に効率的に使用できます。

于 2013-03-29T03:13:49.983 に答える