Поиск путей с ограниченным зрением

Question

Я делаю 2D-игру на лабиринте на основе плитки, и я пытаюсь запрограммировать AI-плеер, который может найти свой путь через лабиринт. В отличие от обычного поиска путей, я хотел бы ограничить видение каждого игрока (включая игрока AI) на 2x2 вокруг них. То есть, ИИ должен знать только окружающую 5x5 сетку вокруг него и точные координаты в лабиринте, как:

Tile mapRecord[MAP_SIZE][MAP_SIZE]; 
Direction FindPathAI(int row, int column, Tile surroundings[5][5]) { 
    int i, j; 
    int r = row - 3, c = column - 3; 
    for (i = 0; i < 5; i++) { 
     for (j = 0; j < 5; j++) { 
      r = (r + MAP_SIZE + 1) % MAP_SIZE; //wrap around 
      c = (c + MAP_SIZE + 1) % MAP_SIZE; //wrap around 
      mapRecord[r][c] = surroundings[i][j]; 
     } 
    } 

    //FindPath 

    //return the direction to go 
} 

Что может быть возможный способ решить эту проблему? Я думаю, что могу объявить массив размера всей карты и записать видение игрока AI на карту. Но потом я застрял на том, что мне делать дальше ... любая идея? Спасибо.

Answer 1

Если вход и выход (начало/конец) лабиринта соединены с внешней стенкой другими стенами (то есть один не находится на «острове» посередине), у вас есть односвязный лабиринт ,

+----S----+ 
|   | 
| +-F-+ | <-- OK: "Finish" is connected 
| +---+-|  Simply-connected maze 
|   | 
+---------+ 

+----S----+ 
|   | 
| +-F-+ | <-- Bad: "Finish" is not connected 
| +---+ |  Maze with Start or Finish on an island 
|   | 
+---------+ 

Односвязных лабиринты

Если у вас нет «островок» ситуации, как выше, вы можете использовать простой метод «стена повторителя», который вы можете сделать с завязанными глазами (то есть, нет видение вообще!). Просто держите левую руку (или правую руку) на стене и ходите. Если вы достигнете препятствия, поверните в зависимости от того, какое из направлений позволит вам держать руку на стене. Вы, в конце концов, достигнете выхода, если он есть.

комплекс «Остров» лабиринты

Если приходится иметь дело с островами, вы можете использовать что-то вроде алгоритма Trémaux в. Если вы думаете о каждой пустой плите в вашем 2D-плиточном лабиринте, каждая плитка будет либо пустой, либо отмеченной один, либо два раза. (. 0, 1 или 2 балла)

Очевидно при посещении плитки, вы увеличиваем метки, поэтому предположим, что здесь:

• На старте, двигаться в случайном уважительной направлении (N/S/E/W).
• Когда вы приедете на плиту с 0 посещениями, пройдите в случайном направлении , что не отмечено.
• Когда вы придете на плиту с 1-го места, развернитесь и пройдите назад, как вы пришли.
• В противном случае перейдите к плитке с наименьшими отметками.

Когда вы достигнете своего выхода, плитки, отмеченные ровно один раз, вернут вас к началу.

Для получения дополнительной информации см. Wikipedia page on maze solving.

Answer 2

Это может быть выполнено с запуском двух разных поисков путей, встроенных друг в друга. Один алгоритм анализирует патч лабиринта, который виден игроку (без движения игрока). Другой алгоритм перемещает сам ИИ и ищет путь. Алгоритм, который анализирует видимую часть лабиринта, используется для поиска возможных дальнейших путей для ИИ. Таким образом, ИИ может анализировать весь лабиринт, не зная об этом.

Поиск путей сам по себе является специфичным для реализации, и существует большой список используемых алгоритмов (https://en.wikipedia.org/wiki/Maze_solving_algorithm) - в дополнение к BFS, DFS и другим алгоритмам поиска путей для графиков.

Используемый алгоритм зависит от того, как должен себя вести ИИ. Например, алгоритм настенного следящего элемента прост для реализации, но выглядел бы довольно глупым, если ИИ представляет, например. персонаж в игре. Наиболее эффективный алгоритм, вероятно, будет A * с надлежащей эвристикой (через которую также можно изменить поведение AI).