Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Если вы говорите об ИА-призраке, посмотрите страницу, на которую Чад упомянул: Досье Pac-Man - призраки на самом деле просто используют евклидовое расстояние при определении того, как сделать это на своих целевых плитах, что делает их очень плохими при поиске Pac Man в некоторых случаях.

Ответ 2

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

Здесь описано, как работает преследование AI призраков (каждый из них работает по-разному). Не забудьте также прочитать вышеприведенную главу о том, как они на самом деле пытаются добраться до

Ответ 3

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

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

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

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

Ответ 4

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

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

Удачи!

Ответ 5

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