2

私はゲームに取り組んでいます (そして、すでにいくつかの質問をしています) が、皆さんに尋ねたい別の質問があります。

このゲームのレベル形式は、TilemapData 構造体の配列へのインデックスである Uint16 (私は SDL を使用しています) のタイルマップとして設定されます。tilemapData 構造体のビットの 1 つは isConductive ビット/ブール値です。

このビットの使用は基本的に、さまざまなオブジェクトを 1 つの「powerNet」に接続するパスを作成することです。以下に、現在の方法に関するコードをいくつか示します (これは機能しますが、後で本当に嫌いな理由について説明します)。

void findSetPoweredObjects(unsigned long x, unsigned long y, powerNetInfo * powerNet) {
  //Look for poweredObjs on this tile and set their powerNet to the given powernet
  for (int i = 0; i < level->numChunks[CHUNKTYPE_POWEREDDEF]; i++)
    if (level->poweredObjects[i]->position[0] == x && level->poweredObjects[i]->position[1] == y)
      level->poweredObjects[i]->powerNet = powerNet, powerNet->objectsInNet++;
}

void recursiveCheckTile(bool * isWalked, powerNetInfo * powerNet, unsigned long x, unsigned long y, tilemapData * levelMap) {
  //If out of bounds, return
  if (x < 0 || y < 0 || x >= level->mapDimensions[0] || y >= level->mapDimensions[1]) return;
  //If tile already walked, return
  if (isWalked[x + (y * level->mapDimensions[0])]) return;
  //If tile is nonconductive, return
  if (!(level->tiles[levelMap->map[x + (y * level->mapDimensions[0])]]->flags & TILETYPE_CONDUCTIVE)) return;

  //Valid tile to check, see if there's a poweredobj on the tile (link it to the net if it is) and check the adjacent tiles.
  isWalked[x + (y * level->mapDimensions[0])] = true;

  findSetPoweredObjects(x,y,powerNet);

  recursiveCheckTile(isWalked, powerNet, x - 1, y, levelMap);
  recursiveCheckTile(isWalked, powerNet, x + 1, y, levelMap);
  recursiveCheckTile(isWalked, powerNet, x, y - 1, levelMap);
  recursiveCheckTile(isWalked, powerNet, x, y + 1, levelMap);
}

bool buildPowerNets(void) {
  //Build the powernets used by the powered objects
  //TODO: Rewrite buildPowerNets() & recursiveCheckTile() to avoid stack overflows and make it easier to backtrace powernets in-game
  bool * isWalked;
  isWalked = new bool[(level->mapDimensions[0] * level->mapDimensions[1])];
  unsigned long x, y;
  tilemapData * levelMap = level->layers[level->activeMap];
  for (y = 0; y < level->mapDimensions[1]; y++) {
    for (x = 0; x < level->mapDimensions[0]; x++) {
      if (isWalked[x + (y * level->mapDimensions[0])]) continue;
      isWalked[x + (y * level->mapDimensions[0])] = true;
      if (level->tiles[levelMap->map[x + (y * level->mapDimensions[0])]]->flags & TILETYPE_CONDUCTIVE) {
        //it's conductive, find out what it's connected to.

        //But first, create a new powernet
        powerNetInfo * powerNet = new powerNetInfo;
        powerNet->objectsInNet = 0;
        powerNet->producerId = -1;
        powerNet->supplyType = POWER_OFF;
        powerNet->prevSupplyType = POWER_OFF;
        powerNet->powerFor = 0;

        //Find adjacent tiles to this one, add them to it's powernet, and then mark them walked.  Then repeat until the net is done.
        recursiveCheckTile(isWalked, powerNet, x, y, levelMap);
      }
    }
  }
  delete isWalked;
  for (int i = 0; i < level->numChunks[CHUNKTYPE_POWEREDDEF]; i++)
      if (level->poweredObjects[i]->powerNet == NULL) return false;
  return true;
}

false を返すことは、関数が失敗したことを意味することに注意してください (この場合、すべてのオブジェクトが適切にリンクされていません)。

私の心配は、導電性タイルを歩く関数が、スタック オーバーフローのために、より複雑なマップで完全に失敗することです。これらの機能を使用してこのリスクを軽減する方法について、いくつかのアイデアはありますか? 必要に応じて、使用される構造体に関する詳細情報を提供できます。

コードを変更してrecursiveCheckTile、ジャンクションに到達したときにのみ再帰呼び出しを行い、それ以外の場合はそれが存在する導電パスを対話的にたどるようにすることを考えましたが、事前に知ることができないため、それはまだ部分的な解決策にすぎないようですパスがどのようにねじれているか、分岐しているか。

それが違いを生む場合、ここでは速度はまったく重要ではありません。この関数は、マップが使用される前に処理されているときに 1 回しか実行されないため、少し余分な時間を使用しても問題はありません。

4

2 に答える 2

5

フラッドフィル

基本的にグリッドの塗りつぶしを行っているようです。チェックする必要があるキューまたは正方形のスタックを使用することで、再帰を排除できます。疑似コードについては、ウィキペディアの記事の「代替実装」セクションを参照してください。

自分でキュー/スタックを維持する利点は、それらを訪問したときに正方形をリストから削除できることです。一方、再帰的なソリューションでは、それらを訪問した後でも正方形がスタックに残ります。

問題に適応したウィキペディアの記事からの「単純な」代替実装を次に示します。

1. Set Q to the empty queue.
2. Add node to the end of Q.
3. While Q is not empty: 
4.     Set n equal to the first element of Q
5.     Remove first element from Q
6.     If n has already been visited:
7.         Go back to step 3.
8.     Mark n as visited.
9.     Add the node to the west to the end of Q.
10.    Add the node to the east to the end of Q.
11.    Add the node to the north to the end of Q.
12.    Add the node to the south to the end of Q.
13. Return.

これにはスタックまたはキューを使用できますが、どちらも機能することに注意してください。以下は、違いを視覚的に示すクールで魅力的なアニメーションです。

キューベースのフラッド フィル

フラッド キューでいっぱい

スタックベースのフラッド フィル

スタックによるフラッド フィル

連結成分のラベリング

同じグリッド上に複数の電力網を持つことになった場合は、接続されたコンポーネントのラベル付けページも興味深いかもしれません。基本的に、切断された電力ネットが複数あるかどうかを把握するのに役立ちます。そうすると、各正方形がどれに属しているかがわかります。

連結成分のラベル付けの例

于 2009-07-24T03:44:51.937 に答える
1

この関数は繰り返し書き直すことができます。

このように考えてください。検索アルゴリズムのパススタックとして、コールスタックを暗黙的に使用しています。呼び出すたびrecursiveCheckTileに、ノードをそのスタックにプッシュします。ただし、コールスタックは比較的小さいため、すぐに吹き飛ばされます。

パススタックを明示的に管理する必要があります。隣接する4つのノードの再帰関数を呼び出す代わりに、ノードをこの明示的なスタックにプッシュします。アルゴリズムは次のようになります（疑似）：

add starting node to stack

while( nodes on stack )
{
    pop node
    if( node is conductive )
    {
        add node to powerSet
        push 4 adjoining nodes onto stack
    }
}

これにより、同じトラバーサル（深さ優先）が生成されますが、スタックは明示的になるため、メモリのゴブマックを割り当てることができます。

于 2009-07-24T03:38:29.767 に答える