Некоторые вопросы с поиском пути pacman

Question

Я узнал об A *, BFS, DFS и могу реализовать их довольно хорошо.Однако, некоторые проблемы возникают, когда я пытаюсь сделать это при решении проблемы поиска пути pacman.Давайте предположим, что существует только два типа лабиринтов: один имеет полные элементы, как в пустом квадрате, все это либо pacman, либо элемент для сбора, либо стена;и у одного есть только несколько предметов (4 или меньше).

1. Как именно реализованы BFS и DFS, если нужно собрать более одного предмета?В таком случае, они все еще дают оптимальный результат?

2. Каков наилучший алгоритм / эвристика для карты полного элемента?До сих пор я придумал что-то вроде жадной эвристики, но это довольно случайно, потому что на карте слишком много предметов для сбора и, следовательно, не очень хорошая идея для решения такого лабиринта.

3. Используя A * на карте из нескольких предметов, есть ли хороший способ определить, какой предмет следует взять первым?Я думал о том, чтобы попытаться использовать расстояние Махаттана в качестве приблизительной оценки, но это не очень правильно, особенно в некоторых сложных ситуациях.

Answer 1

1) Проблема, с которой я столкнулся бы при использовании BFS или DFS в этой ситуации, заключается в том, насколько неэффективным это окажется, особенно в примере с полной картой. Чтобы заставить любой алгоритм работать с несколькими целями, вы можете либо построить поиск, чтобы он не заканчивался после того, как найден первый путь, но это все равно не дало бы вам «оптимальный» путь для каждого куска еды на карте. Или вы могли бы пройти путь от пакмана до ближайшей еды, от этой еды до ближайшей ближайшей и т. д., найти эти пути, а затем сравнить их, чтобы найти действительно оптимальный путь, но я не хочу думать о том, как долго это будет продолжаться. брать.

2) Я бы, вероятно, придерживался жадного A *, который смотрит только на ближайшую еду (в большинстве случаев я не вижу проблем с расстоянием до Манхэттена, так как карта для pacman уже является сеткой; неоптимальный для крайних случаев, когда стены мешают Pacman получить доступ к ближайшему, но это трудная проблема для решения. Манхэттен будет приличным, возможно, измененным плотностью еды, а не просто расстоянием, что-то вроде: (Манхэттенское расстояние) / (общее количество еды в 3х3 квадрата еды)

3) Если не использовать поиск пути к каждому элементу, а затем выбирать самый короткий, я думаю, что Манхэттен хорошо подойдет для сценария с несколькими пунктами. Он не всегда выбирает лучшего, но 100% оптимальный ИИ обычно не лучшая цель для игр.

В этом случае я бы хотел попробовать жадный А * с кластерами предметов, способствующих весу, в качестве простого и прилично быстрого решения.

Более сложное решение, которое должно возвращаться к оптимальным путям, которым должен следовать Пакман, - использовать алгоритм для поиска Минимального связующего дерева http://en.wikipedia.org/wiki/Minimum_spanning_tree но я не знаю, насколько это легко осуществить. Вот вопрос, обсуждающий достоинства двух алгоритмов минимального остовного дерева: Крускал против Прима

Answer 2

Алгоритмы не меняются, если вы добавляете больше еды.Единственное, что меняется - это пространство состояний.Вы должны думать о новом способе представления вашей проблемы.Если у вас есть только 1 еда, вам нужна только позиция x, y pacman.Например, если у вас есть 3 точки, вы должны добавить эту информацию в вашу модель.Вы можете добавить 3 логические переменные, чтобы указать, что pacman прошел через точку.Теперь в вашем пространстве состояний находится граф, состоящий из узлов следующих типов:

 ((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food
 ((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food
 ((x,y),TRUE,TRUE,TRUE) -> this is the goal state

Чтобы решить проблему, вы просто запускаете тот же алгоритм в своей новой модели.BFS и A * всегда дадут вам оптимальное решение.Проблема в том, что чем больше еды вы кладете, тем медленнее становится решение.Таким образом, эти алгоритмы не дадут ответа в разумные сроки.Вы должны подумать о новом способе сделать это.