Новаторский алгоритм для [закрытого] Pacman
6 ответов
Обратите внимание на то, что для поиска пути
- BFS будет проверять гораздо больше узлов, чем A *, что делает его намного медленнее
- A * даст тот же ответ, что и BFS
- A * действительно легко реализовать
- Используйте Manhattan Distance в качестве эвристики - это безумно проста в реализации и ведет к очень эффективному поиску
- Для получения дополнительной информации см. http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html (вся серия действительно интересна)
Если вы говорите об ИИ-призраке, загляните на страницу, упомянутую Чадом: Досье Пакмана - на самом деле призраки просто используют евклидово расстояние, когда определяют, как добраться до своих целевых плиток. , из-за чего в некоторых случаях они не могут найти Pac Man.
Вы можете рассмотреть антиобъектный подход, который использовали оригинальные разработчики Pacman, вы можете прочитать об этом здесь и здесь .
Однако, чтобы ответить на ваш вопрос, используйте то, что работает! Если вы получаете хорошие результаты от BFS, используйте его. Просто не забудьте абстрагироваться от поиска пути, чтобы вы могли заменить его позже, если найдете что-то получше.
Удачи!
Ну, это зависит от того, действительно ли вы хотите, чтобы призраки работали, как в Pac-Man?
Вот описание того, как призраки ' chase AI работает (каждый работает по-своему). Обязательно прочтите также вышеприведенную главу о том, как они на самом деле пытаются добраться до своего целевого тайла . Эта страница представляет собой чудесно подробный анализ Pac-Man, интересно читать.
BFS всегда будет указывать кратчайший путь, если веса ребер не используются. Если вам не нужны утяжелители по краям, я бы использовал это. Вы всегда можете переключиться позже.
Связанный вопрос, который, вероятно, отвечает на ваш вопрос: Поиск пути в игре Java 2d?
Это зависит от ситуации. BFS является одновременно полным и оптимальным (в том смысле, что он находит оптимальное решение)
Обратная сторона? На то, чтобы найти его, может потребоваться много времени! Кроме того, в зависимости от фактора разветвления вашей проблемы, у вас может быстро закончиться нехватка памяти.
Если у вас нет проблем с производительностью, оставьте BFS, но если вы хотите попробовать его в огромном лабиринте, то решение может занять некоторое время.
Я предлагаю вам попробовать A *, лучшую стратегию поиска ИМХО. Даже если у вас нет проблем с BFS, A * - хороший алгоритм для реализации, и вы узнаете много интересных вещей.