Алгоритм поиска пути для Pacman [закрыт]

15

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

    
задан Karan 09.04.2010 в 00:59
источник

6 ответов

13

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

  • BFS будет искать гораздо больше узлов, чем A *, что делает его намного медленнее
  • A * выйдет с тем же ответом, что и BFS
  • A * очень просто реализовать
    • Используйте Манхэттенское расстояние в качестве эвристики - это безумно легко реализовать и ведет к очень эффективному поиску.
    • Посмотрите Ссылка для получения дополнительной информации (вся серия действительно интересна).

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

    
ответ дан Daniel G 09.04.2010 в 01:35
источник
  • К сожалению, демонтаж Pac-Man был удален. –  Anonym Mus 25.05.2010 в 09:20
  • A * не является оптимальным в общем случае, как вы говорите. Гарантируется только поиск оптимального решения с допустимой и последовательной эвристикой. –  b3bop 03.02.2012 в 07:33
  • @ b3bop Вы правы в общем случае; Я говорил о случае использования Манхэттенского расстояния на сетке (т. Е. Лабиринте Pac-Man). В этом случае эвристика является допустимой и последовательной, а A * будет иметь тот же ответ, что и BFS. –  Daniel G 04.02.2012 в 23:50
20

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

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

    
ответ дан Chad Birch 09.04.2010 в 01:04
источник
  • спасибо за ссылку! –  Karan 09.04.2010 в 01:07
  • Спасибо, Чад. Раньше я не читал эту статью. –  Audie 09.04.2010 в 01:15
  • Ссылка мертва ... –  GingerPlusPlus 04.04.2016 в 08:56
  • web.archive.org/web/20151006023914/http://home.comcast.net/... –  arynaq 21.03.2017 в 22:03
4

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

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

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

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

    
ответ дан mcabral 09.04.2010 в 01:06
источник
3

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

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

Удачи!

    
ответ дан Audie 09.04.2010 в 01:12
источник
1

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

    
ответ дан rlbond 09.04.2010 в 01:04
источник
  • спасибо! У меня была догадка, что это может быть так –  Karan 09.04.2010 в 01:08
  • bfs излишне медленно, хотя –  user151496 09.03.2016 в 09:53
  • Для простой игры pac-man маловероятно. –  rlbond 23.03.2016 в 20:05
0

Связанный с этим вопрос, который, вероятно, отвечает на ваш вопрос: Поиск путей в Java 2d Игра?

    
ответ дан strager 23.05.2017 в 13:53
источник