Алгоритм Pathfinding для Pacman

Question

Я хотел реализовать игру Pacman. Для ИИ я думал об использовании алгоритма A *, увидев его на многочисленных форумах. Тем не менее, я реализовал Breadth First Search для некоторого простого поиска пути (от точки a до точки b с определенными препятствиями между ними) и нашел, что он дал оптимальный путь всегда. Я думаю, это может быть потому, что в игре, такой как pacman, которая использует простое отслеживание пути, нет понятия затрат на графике. Итак, будет ли ОК, если я использую BFS вместо A * для поиска пути в Pacman?

Answer 1

Для пути по установлению фактов, обратите внимание на следующее

• BFS будет выглядеть на много больше узлов, чем A * Будет, что делает его гораздо медленнее
• A * придумает тот же ответ, как BFS
• A * действительно легко осуществить
  • Используйте Manhattan Distance как ваш эвристики - это безумно легко реализовать, и приводит к очень эффективные поиски
  • Посмотрите на http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html для получения дополнительной информации (вся серия действительно интересно)

Если вы говорите о призраке AI, проверьте страницу Чад отметил: The Pac-Man Dossier - призраки на самом деле просто использовать евклидовой когда вы определяете, как сделать это с их целевыми плитами, что делает их очень плохими в поиске Pac Man в некоторых случаях.

Answer 2

BFS всегда укажет кратчайший путь, если не используются никакие веса. Если вам не нужны весовые коэффициенты, я бы это использовал. Вы всегда можете переключиться позже.

Answer 3

Ну, это зависит от того, действительно ли вы хотите, чтобы призраки работали так же, как в Pac-Man?

Here's a description of how the ghosts' chase AI works (каждый из них работает по-разному). Обязательно прочитайте вышеприведенную главу о том, как они на самом деле пытаются добраться до своего target tile. Эта страница представляет собой удивительно подробный анализ Pac-Man, интересного чтения.

Answer 4

Связанные вопрос, который, вероятно, ответ на ваш вопрос: Path finding in a Java 2d Game?

Answer 5

Это зависит от многого. BFS является полным и оптимальным (в том смысле, что он находит оптимальное решение)

Недостатком? Это может занять много времени, долгое время, чтобы найти его! Кроме того, в зависимости от коэффициента ветвления вашей проблемы вы можете быстро разрядиться.

Если у вас нет проблем с производительностью, тогда держите BFS, но если вы хотите попробовать его в огромном лабиринте, то для получения решения может потребоваться некоторое время.

Предлагаю вам попробовать A *, лучшую стратегию поиска IMHO. Даже если у вас нет проблем с BFS, A * - хороший алгоритм для реализации, и вы узнаете много классных вещей.

Answer 6

Возможно, вы захотите рассмотреть подход, основанный на использовании антиобъектива, который использовали оригинальные дизайнеры Pacman, вы можете прочитать об этом here и here.

Однако, чтобы ответить на ваш вопрос, используйте то, что работает! Если вы получаете хорошие результаты от BFS, используйте его. Не забудьте полностью отследить путь, который вы можете заменить позже, если найдете что-то лучше.

Удачи вам!