Я нашел много ссылок на ИИ призраков в Пакмане, но ни один из них не упомянул, как глаза возвращаются к центральной дыре призраков после того, как Пакман съел призрака.
В моей реализации я реализовал простое, но ужасное решение. Я просто жестко прописал на каждом углу, в каком направлении следует идти.
Есть ли лучшее / или лучшее решение? Может быть, общий, который работает с различными уровнями дизайна?
artificial-intelligence
path-finding
heuristics
pacman
RoflcoptrException
источник
источник
Ответы:
На самом деле, я бы сказал, что ваш подход - довольно крутое решение с почти нулевыми затратами времени по сравнению с любым поиском пути.
Если вам нужно сделать обобщение на произвольные карты, вы можете использовать любой алгоритм поиска пути - например, поиск в ширину очень просто реализовать - и использовать его для вычисления направлений для кодирования в каждом из углов перед запуском игры.
РЕДАКТИРОВАТЬ (11 августа 2010 г.): Я только что обратился к очень подробной странице о системе Pacman: «Досье Pac-Man» , и, поскольку у меня есть принятый ответ, я решил обновить его. Кажется, что статья не охватывает явное возвращение в дом монстров, но в ней говорится, что прямое нахождение пути в Pac-Man имеет место в следующем случае:
источник
Я решил эту проблему для общих уровней следующим образом: перед началом уровня я делаю какую-то «заливку» из ямы монстра; каждая плитка лабиринта, которая не является стеной, получает число, указывающее, как далеко она находится от отверстия. Поэтому, когда глаза находятся на плитке с расстоянием 68, они смотрят, какая из соседних плиток имеет расстояние 67; это путь тогда.
источник
В качестве альтернативы более традиционным алгоритмам поиска путей вы можете взглянуть на (правильно названный!) Паттерн Pac-Man Scent Antiobject .
При запуске вы можете распространять запах монстр-дыр вокруг лабиринта, и ваши глаза будут следовать за ним домой.
Как только запах настроен, затраты времени выполнения очень низки.
Редактировать: к сожалению, статья в Википедии была удалена, поэтому WayBack Machine на помощь ...
источник
Вы должны взглянуть на алгоритм поиска пути, такой как алгоритм Дийсктра или алгоритм A * . Это то, что ваша проблема: проблема графика / пути.
источник
Любое простое решение, которое можно поддерживать, надежно и достаточно хорошо работает, является хорошим решением. Мне кажется, что вы уже нашли хорошее решение ...
Решение для поиска пути, вероятно, будет более сложным, чем ваше текущее решение, и, следовательно, с большей вероятностью потребует отладки. Это, вероятно, также будет медленнее.
ИМО, если он не сломан, не чини.
РЕДАКТИРОВАТЬ
IMO, если лабиринт исправлен, то ваше текущее решение - хороший / элегантный код. Не делайте ошибку, приравнивая «хорошее» или «элегантное» к «умному». Простой код также может быть «хорошим» и «элегантным».
Если у вас есть настраиваемые уровни лабиринта, то, возможно, вам следует просто найти путь при первоначальной настройке лабиринта. Проще всего было бы заставить дизайнера лабиринта сделать это вручную. Я бы потрудился автоматизировать это, только если у вас есть лабиринт лабиринтов ... или пользователи могут создавать их.
(Помимо: если маршруты настраиваются вручную, конструктор лабиринта может сделать уровень более интересным, используя неоптимальные маршруты ...)
источник
В оригинальном Пакмане Призрак обнаружил желтого пожирателя таблеток по его «запаху», он оставлял след на карте, призрак бродил вокруг случайно, пока не обнаруживал запах, затем они просто следовали по пути запаха, который ведет их прямо к игрок. Каждый раз, когда Пакман двигался, «значения запаха» уменьшались на 1.
Теперь, простой способ обратить вспять весь процесс - это иметь «пирамиду призрачного запаха», которая имеет самую высокую точку в центре карты, тогда призрак просто двигается в направлении этого запаха.
источник
Предполагая, что у вас уже есть логика, необходимая для погони за Pacman, почему бы не использовать это снова? Просто измените цель. Похоже, это будет гораздо меньше работы, чем пытаться создать совершенно новую процедуру, используя ту же логику.
источник
Это проблема поиска пути. Популярный алгоритм см. По адресу http://wiki.gamedev.net/index.php/A* .
источник
Как насчет каждого квадрата со значением расстояния до центра? Таким образом, для каждого данного квадрата вы можете получить значения ближайших соседних квадратов во всех возможных направлениях. Вы выбираете квадрат с наименьшим значением и двигаетесь к нему.
Значения будут предварительно рассчитаны с использованием любого доступного алгоритма.
источник
Это был лучший источник информации о том, как это работает.
http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Когда призраки убиты, их бестелесные глаза возвращаются в исходное положение. Это просто достигается установкой целевой плитки призрака в это место. Навигация использует те же правила.
Это действительно имеет смысл. Возможно, не самый эффективный в мире, но довольно хороший способ не беспокоиться о другом состоянии или чем-то подобном, что вы просто меняете цель.
Примечание: я не осознавал, насколько круты те программисты pac-man, которые в основном создали целую систему сообщений в очень маленьком пространстве с очень ограниченной памятью ... это удивительно.
источник
Я думаю, что ваше решение подходит для проблемы, проще, чем сделать новую версию более "реалистичной", где призрачные глаза могут проходить сквозь стены =)
источник
Вот аналог и псевдокод для идеи заполнения потока ammoQ.
Идея состоит в том, что это поиск в ширину, поэтому каждый раз, когда вы сталкиваетесь с новым смежным квадратом s, лучший путь - через p. Это O (N), я верю.
источник
Я мало знаю о том, как вы реализовали свою игру, но вы могли бы сделать следующее:
Какой-то псевдокод:
источник
Предложение dtb23 просто выбрать случайное направление в каждом углу, и в конце концов вы обнаружите, что звуки монстра-дыры ужасно неэффективны.
Однако вы можете использовать его неэффективный алгоритм возврата домой, чтобы сделать игру более увлекательной, добавив больше вариаций в сложность игры. Вы бы сделали это, применив один из вышеперечисленных подходов, таких как ваши путевые точки или заливка, но сделав это недетерминированным образом. Таким образом, на каждом углу вы можете сгенерировать случайное число, чтобы решить, выбрать ли оптимальный путь или случайное направление.
По мере того, как игрок прогрессирует по уровням, вы уменьшаете вероятность того, что выбрано случайное направление. Это добавило бы еще один рычаг на общий уровень сложности в дополнение к скорости уровня, скорости призрака, паузе приема таблеток (и т. Д.). У вас есть больше времени, чтобы расслабиться, пока призраки - это просто безобидные глаза, но это время становится все короче и короче по мере вашего прогресса.
источник
Короткий ответ, не очень хорошо. :) Если вы измените лабиринт Pac-Man, глаза не обязательно вернутся. Некоторые из хаков, плавающих вокруг, имеют эту проблему. Так что это зависит от наличия кооперативного лабиринта.
источник
Я бы предположил, что призрак хранит путь, который он прошел от дыры до Pacman. Поэтому, как только призрак умирает, он может следовать этому сохраненному пути в обратном направлении.
источник
Зная, что пути pacman неслучайны (т. Е. Каждый конкретный уровень 0-255, inky, blinky, pinky и clyde будут работать точно так же для этого уровня).
Я взял бы это и затем предположил бы, что есть несколько главных путей, которые обертывают вокруг всего лабиринта как «обратный путь», который объект глазного яблока принимает в ожидании, где это находится, когда pac человек съел призрак.
источник
Призраки в pacman следуют более или менее предсказуемым образцам, пытаясь сопоставить сначала X или Y, пока цель не будет достигнута. Я всегда предполагал, что это было точно так же, как глаза возвращаются назад.
источник
Наслаждайтесь!
источник
Мой подход немного требователен к памяти (с точки зрения эпохи Пакмана), но вам нужно вычислить только один раз, и он работает для любого уровня дизайна (включая прыжки).
Узлы меток один раз
Когда вы впервые загружаете уровень, пометьте все узлы логова монстров 0 (представляя расстояние от логова). Выполняйте внешнюю маркировку подключенных узлов 1, подключенных к ним узлов 2 и т. Д., Пока все узлы не будут помечены. (примечание: это работает даже если логово имеет несколько входов)
Я предполагаю, что у вас уже есть объекты, представляющие каждый узел и соединения с их соседями. Псевдокод может выглядеть примерно так:
Глаза двигаются к соседу с самым низким расстоянием
Как только все узлы помечены, маршрутизация глаз становится тривиальной ... просто выберите соседний узел с меткой наименьшего расстояния (примечание: если несколько узлов имеют одинаковое расстояние, не имеет значения, какой из них выбран). Псевдокод:
Полностью маркированный пример
источник
Для моей игры в PacMan я создал несколько «
shortest multiple path home
» алгоритм, который работает для любого лабиринта, который я ему предоставляю (в рамках моего набора правил). Это также работает через их туннели.Когда уровень загружен, все
path home data in every crossroad
пусто (по умолчанию), и как только призраки начинают исследовать лабиринт, ониcrossroad path home information
продолжают обновляться каждый раз, когда сталкиваются с «новым» перекрестком или с другого пути, натыкающегося на их известный перекресток.источник
Оригинальный человек не использовал поиск пути или причудливый ИИ. Это просто заставило геймеров поверить в то, что в нем больше глубины, чем было на самом деле, но на самом деле это было случайно. Как говорится в «Искусственном интеллекте для игр» / Ян Миллингтон, Джон Фанге.
Не уверен, правда это или нет, но для меня это имеет большой смысл. Честно говоря, я не вижу такого поведения, о котором говорят люди. Red / Blinky for ex, как говорится, не всегда следует за игроком. Похоже, что никто не преследует игрока нарочно. Вероятность того, что они последуют за тобой, выглядит случайной для меня. И просто очень заманчиво видеть поведение в случайном порядке, особенно когда вероятность того, что вас преследуют, очень высока, с 4 врагами и очень ограниченными возможностями поворота в небольшом пространстве. По крайней мере, в первоначальной реализации игра была предельно простой. Посмотрите книгу, она в одной из первых глав.
источник