Реализация первого поиска в PacMan

Question

В настоящее время я работаю над проектом C++, чтобы сделать клон PacMan. В основном я сделал почти все, что делает игра. Но я еще не понял, как реализовать широкий поиск, чтобы призраки преследовали pacman. В последние несколько дней я много читал о BFS. Я знаю, что это такое и что он делает. Я также знаю, что для этой цели я должен использовать очередь. Но все же я не могу реализовать этот алгоритм в своей игре. У меня есть 2d сетка из 36 * 28 плиток. Но я действительно не уверен, как реализовать его в моей xy-системе координат, что нужно нажать в очередь и как манипулировать соседними плитками. Я застрял в этом вопросе. Я не прошу о действительном коде. Мне просто нужно четкое и простое объяснение фактической реализации BFS и о том, что нужно учитывать при работе над BFS в этой 2-й игровой сетке. Ваше объяснение будет действительно полезно. Благодарю.

Answer 1

Я предполагаю, что вы хотите делать BFS каждый раз, когда призрак будет делать ход. Что вы можете сделать, так это запустить BFS из PacMan, пока он не найдет всех призраков. Обратите внимание, что вам действительно не нужен полный маршрут, который примет призрак, вам нужно только следующее движение. При выполнении BFS вы можете хранить для каждой ячейки расстояние от PacMan до этой ячейки. Когда вы делаете BFS, все призраки могут смотреть в соседних клетках, чтобы выбрать ячейку с самым низким номером. Обратите внимание, что вы должны инициализировать все ячейки с большим количеством.

Для выполнения вашей BFS вы можете сделать некоторые трюки, например, сопоставить координату (x, y) с одним числом. Этот номер можно разместить в очереди. Обратите внимание, что перед тем, как положить что-то в очередь, вы должны проверить стену. Когда вы вытаскиваете что-то из очереди, запускайте цикл for длиной 4 (количество соседних ячеек).

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 
} 

В качестве упражнения для читателя я старался как можно скорее оставить его открытым.