PacManでの幅広い最初の検索の実装

Question

現在PacManクローンを作成するためのC++プロジェクトに取り組んでいます。基本的には、ゲームが行うことのほとんどすべてを行っています。しかし、私はまだ幽霊がパックマンを追いかけるために幅広い最初の検索をどのように実装するかを考えていない。ここ数日、私はBFSについて多くのことを読んだ。私はそれが何であり、何をしているかを知っています。私はまた、この目的のためにキューを使用しなければならないことも知っています。しかし、私は自分のゲームでこのアルゴリズムを実際に実装することはできません。私は36 * 28タイルの2次元グリッドを持っています。しかし、私は実際にそれを私のxy座標系でどのように実装するのか、キューに何を押し込むべきか、そして隣接するタイルを操作する方法については確信しています。私はこの時点で立ち往生しています。私は実際のコードを求めていません。 BFSの実際の実装と、この第2dゲームグリッドのBFSで作業する際に留意すべき事項について、明確かつ簡単な説明が必要です。 あなたの説明は本当に役に立ちます。ありがとう。

Answer 1

幽霊が移動を行うたびにBFSを実行するとします。あなたがすることができることは、彼がすべての幽霊を見つけ出すまでPacManからBFSを始めることです。幽霊が取る完全なルートは実際には必要ではないことに注意してください。次の移動だけが必要です。 BFSを実行している間、PacManからそのセルまでの距離を各セルごとに保存することができます。あなたがBFSを終えると、すべての幽霊は隣の細胞を見て、最も低い数の細胞を選ぶことができます。すべてのセルを大きな数で初期化する必要があることに注意してください。

あなたのBFSを行うには、（x、y）座標を1つの数字にマッピングするなど、いくつかのトリックがあります。この番号をキューに入れることができます。あなたの待ち行列に何かを入れる前に壁をチェックするべきであることに注意してください。キューから何かを引っ張ると、長さ4のfor-loop（隣接するセルの数）が実行されます。

int dx[] = {0, 1, 0, -1}; 
int dy[] = {1, 0, -1, 0}; 

void do_bfs() { 
    std::queue<int> queue; 
    // initialize grid 
    // add starting position of pacman to queue 

    while(!queue.empty()) { 
     // remove and access first element 
     cur_place = queue.front(); queue.pop(); 
     map_to_coordinate(cur_x, cur_y, cur_place); 
     cur_distance = grid[cur_x][cur_y]; 
     for (int i = 0; i < 4; i++) { 
      if (cur_x + dx[i] >= 0 && /* more checks */) { 
       queue.push_back(map_to_number(cur_x + dx[i], cur_y + dy[i])); 
       grid[cur_x + dx[i]][cur_y + dy[i]] = cur_distance + 1; 
      } 
     } 
    } 
    // now grid is filled, so now you should find out for each ghost how to move 
} 

読者のための練習として、私はポイントを作っている間に多くを開いたままにしました。