AI AI персонажа PacMan предлагает оптимальное следующее направление - PullRequest
4 голосов
/ 30 июля 2010

Во-первых, это AI для PacMan, а не призраки .

Я пишу живые обои для Android, которые воспроизводят PacMan вокруг ваших иконок.Хотя он поддерживает предложения пользователей с помощью прикосновений к экрану, большую часть игры будет играть ИИ.Я на 99% закончил программирование игры, но ИИ для самого PacMan все еще крайне слаб.Я ищу помощи в разработке хорошего ИИ для определения следующего направления движения PacMan.

Мой первоначальный план был таким:

  1. Инициализировать счетчик оценок для каждого направления со значениемнуля.
  2. Начните с текущей позиции и используйте BFS для перемещения наружу в четырех возможных начальных направлениях, добавляя их в очередь.
  3. Извлечение элемента из очередиубедитесь, что он еще не «виден», убедитесь, что это правильная позиция на доске, и добавьте к соответствующим начальным направлениям значение для текущей ячейки на основе:

    1. Имеет точку:плюс 10
    2. Включено: плюс 50
    3. Есть фрукты: ценность плюс фрукты (зависит от уровня)
    4. Есть призрак, едущий в сторону PacMan: вычесть 200
    5. Имеет призрака, путешествующего вдали от PacMan: ничего не делать
    6. Имеет призрака, путешествующего перпендикулярно: вычтите 50
    7. Умножьте значение ячейки на процент в расчете на количество шагов доячейка, чем больше шагов от начального направления, тем ближе значение ячейки к нулю.

    и поставьте в очередь три возможных направления от текущей ячейки.

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

На бумаге это звучит хорошо, но призраки окружают PacMan очень быстро, и он дергается назад ивперед в тех же двух или трех клетках, пока один не достигнет его.Корректировка значений присутствия призрака тоже не помогает.Моя ближайшая точка BFS может, по крайней мере, добраться до уровня 2 или 3 до окончания игры.

Я ищу код, мысли и / или ссылки на ресурсы для разработки правильного ИИ - предпочтительно первых двух,Я хотел бы выпустить это на Рынке когда-нибудь в эти выходные, так что я немного спешу.Любая помощь будет принята с благодарностью.


К вашему сведению, это было вручную отправлено GameDev.StackExchange

Ответы [ 6 ]

1 голос
/ 31 июля 2010

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

Настройка: Выберите случайный ход и запишите его со счетом 0.

Для каждого шага:

  1. Запустить функцию подсчета доступных ходов.
  2. Если наивысшая оценка на x% больше, чем оценка записи, тогда перезаписать оценку записи и перейти на эту.
  3. Применить ход.

Это приводит к тому, что PacMan больше не будет выбирать «лучший» ход на каждом шаге, но это не похоже на жадный локальный поиск.быть оптимальным в любом случае.Это сделает PacMan более последовательным и остановит подергивания.

0 голосов
/ 11 августа 2010

Вы должны проверить это описание Антиобъектов , которое является техникой, используемой призраками Пакмана для прохождения лабиринта.В частности, обратите внимание:

Каждый из этих антиобъектов или агентов имеет идентичный и простой алгоритм, который он запускает на каждом шагу игры.Вместо того, чтобы делать Призраков достаточно умными, чтобы решать проблемы «кратчайшего пути» вокруг лабиринта, вместо этого создается понятие «запах Pac-Man», и каждая клетка отвечает за то, сколько аромата Pac-Man находится на ее плитке.

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

0 голосов
/ 11 августа 2010

Вам может быть полезно знать, как боты «рассуждают» (как объяснено в этом превосходном досье ).Например, знание паттерна погони / разброса призраков позволит вам получать точки в «опасных» местах и ​​так далее.

Я добавляю этот ответ, зная, что это не лучшее решение, которое вы искали (поскольку вы хотели доставить на следующей неделе ...), но, возможно, будет полезно кому-то, кто читает это в будущем.Сорт капсулы времени:)

0 голосов
/ 31 июля 2010

Я не знаю много об ИИ или конкретных алгоритмах, но вот некоторые вещи, которые вы могли бы попробовать, которые могли бы просто приблизить вас к работе правительства:)

Из-за проблемы с призраками, окружающими его быстро, может быть, ИИ-призрак слишком силен?Я знаю, что для каждого призрака в классическом Пакмане существует, по-видимому, определенное поведение, поэтому, если вы его не включили, вы можете захотеть.он менее склонен возвращаться к прежним путям.Если этого недостаточно, чтобы ударить его в ту или иную сторону, тогда вы можете логарифмически увеличить штраф за привлечение, поэтому один путь станет значительно более привлекательным, чем другой, с очень высокой скоростью.

Для проблемы с нимЕсли вас поймают призраки, вы сможете перейти от общего алгоритма, основанного на целях, к алгоритму уклонения, когда призраки достигнут опасной близости узлов.

0 голосов
/ 30 июля 2010

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

0 голосов
/ 30 июля 2010

Есть способ перевести PacMan в режим следования по пути.План состоит в том, что вы обнаруживаете определенные обстоятельства, рассчитываете заранее заданный путь, которым должен следовать PacMan, а затем вырабатываете условия раннего выхода для этого пути.Вы можете использовать это для нескольких обстоятельств.

Когда PacMan окружен призраками в трех из четырех направлений на определенном расстоянии, тогда создайте выходной путь, который либо уводит PacMan от призраков, либо к включению.Ситуация выхода будет, когда он съест питание или перестанет быть окруженным.

Когда PacMan съест власть, создайте путь, чтобы съесть некоторых близлежащих призраков.Ситуация выхода будет, когда на пути нет призраков, пересчитайте путь.Или, если поблизости нет призраков, выйдите из режима полностью.

Когда осталось менее половины точек или поблизости нет точек, введите путь, чтобы съесть несколько точек, избегая призраков.Пересчитайте путь, когда рядом появляется призрак, или полностью выйдите из него, если поблизости есть несколько призраков.

Если нет ситуаций, которые оправдывают путь, вы можете вернуться к ИИ по умолчанию, который вы запрограммировали ранее.*

...