Пакман: ​​как глаза возвращаются к дыре монстров?

321

Я нашел много ссылок на ИИ призраков в Пакмане, но ни один из них не упомянул, как глаза возвращаются к центральной дыре призраков после того, как Пакман съел призрака.

В моей реализации я реализовал простое, но ужасное решение. Я просто жестко прописал на каждом углу, в каком направлении следует идти.

Есть ли лучшее / или лучшее решение? Может быть, общий, который работает с различными уровнями дизайна?

RoflcoptrException
источник
11
Вы уверены, что жесткое кодирование на углу достаточно хорошо? Это не гарантирует лучший маршрут. Представьте, что призрак стоит перед длинным узким проходом. По вашему алгоритму ему придется пройти весь этот проход, дойти до угла, а затем выбрать самый быстрый маршрут. Если вы жестко запрограммированы на каждом квадрате, в каком направлении идти, он может знать, что нужно просто повернуться.
Марк Питерс
3
@ Марк, зависит от вашего определения на углу. Если это Т-соединение, даже если вы просто идете прямо в верхней строке, это нормально.
Турбьерн Равн Андерсен
1
@ Thorbjørn: я даже не говорю о перекрестках. Взгляните на эту доску: en.wikipedia.org/wiki/File:Pac-man.png . Если призрак двигался вправо и располагался на второй точке слева-внизу, какое-то время он не встречал никакого пересечения. Это заставит его пройти на 10 квадратов дальше, чем если бы он повернул назад (влево) и пошел по кратчайшему пути.
Марк Питерс
6
Ваше решение использует путевые точки (или хлебные крошки), и я думаю, что это распространенная техника для ускорения алгоритмов поиска путей.
Ник Дандулакис
1
Спасибо за ответы на все вопросы! Я просто придерживался своего предыдущего решения и жестко прописывал указания на каждом углу. Чтобы сделать это общим, требуется, чтобы файл leveldesigner / a level также определял эту информацию в определении уровня.
RoflcoptrException

Ответы:

152

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

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

РЕДАКТИРОВАТЬ (11 августа 2010 г.): Я только что обратился к очень подробной странице о системе Pacman: «Досье Pac-Man» , и, поскольку у меня есть принятый ответ, я решил обновить его. Кажется, что статья не охватывает явное возвращение в дом монстров, но в ней говорится, что прямое нахождение пути в Pac-Man имеет место в следующем случае:

  • продолжайте движение к следующему перекрестку (хотя это, по сути, частный случай «когда предоставляется выбор, выберите направление, которое не подразумевает изменение вашего направления, как показано на следующем шаге);
  • на перекрестке посмотрите на соседние квадраты выхода, кроме той, с которой вы только что пришли;
  • выбирая тот, который ближе всего к цели. Если рядом с целью находится более одного, выберите первое правильное направление в следующем порядке: вверх, влево, вниз, вправо.
Kylotan
источник
16
Я думаю, он имеет в виду, что вы можете вычислить его во время выполнения (когда уровень загружен, но до того, как вы начнете играть), но только один раз. Это не сложно поддерживать.
Марк Питерс
3
Да, или если есть инструмент для создания карт, как часть этого.
Kylotan
6
В предварительных вычислениях путей возврата нет ничего плохого. Вы торгуете хранилищами (путями) для производительности во время выполнения.
Стив Куо
6
Спасибо. Я думаю, что я буду придерживаться этого решения. Кто-нибудь знает, как это было сделано в оригинальном пакмане?
RoflcoptrException
4
Нет не знаю В первоначальном вопросе использовался этот термин, но он не является юридически обязательным.
Kylotan
85

Я решил эту проблему для общих уровней следующим образом: перед началом уровня я делаю какую-то «заливку» из ямы монстра; каждая плитка лабиринта, которая не является стеной, получает число, указывающее, как далеко она находится от отверстия. Поэтому, когда глаза находятся на плитке с расстоянием 68, они смотрят, какая из соседних плиток имеет расстояние 67; это путь тогда.

Эрих Кицмюллер
источник
15
Да. Floodfill очень хорош для поиска путей в любой ситуации, когда мир не слишком велик, чтобы сделать его жизнеспособным. Я бы подумал, что его можно использовать даже в больших мирах, наложив более грубую сетку, связность которой была предварительно рассчитана. Это могло бы немного изменить ситуацию, но это было бы лучше, чем пробки, которые я видел в таких играх.
Лорен Печтел
1
Чтобы сэкономить место (для больших миров или систем с ограничениями), вы можете сохранить направление движения на каждом перекрестке, а не сохранять значение для каждой плитки. По сути, это то, что предлагал ОП.
BlueRaja - Дэнни Пфлюгофт
BlueRaja: Конечно, но это сделать сложнее, и результат не столь оптимален - призрак съедается между двумя пересечениями, поэтому он может в течение некоторого времени бежать в неправильном направлении. Мое решение хорошо работало на en.wikipedia.org/wiki/HP_200LX, так насколько оно может быть более ограниченным?
Эрих Кицмюллер
5
(Я опоздал ...) Да, заливка хороша, но на самом деле вам не нужно полное число, просто направление (два бита) в каждом квадрате, чтобы указывать на следующий квадрат для использования.
Матье М.
Матье: Да, это была бы возможная оптимизация.
Эрих Кицмюллер
42

В качестве альтернативы более традиционным алгоритмам поиска путей вы можете взглянуть на (правильно названный!) Паттерн Pac-Man Scent Antiobject .

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

Как только запах настроен, затраты времени выполнения очень низки.


Редактировать: к сожалению, статья в Википедии была удалена, поэтому WayBack Machine на помощь ...

Дэн Винтон
источник
2
это будет мой ответ. По сути, это то же самое, что и ammoQ, но я всегда помню о запахе pacman :)
Люк Шафер
Похоже, статья в Википедии мертва / удалена. Лучший результат Google - эта тема, но я думаю, что это близко.
Дэвид
2
Я запутался на секунду, но потом сразу понял, что означает «запах». Это отличный способ описать эти скалярные поля!
Стивен Лу
18

Вы должны взглянуть на алгоритм поиска пути, такой как алгоритм Дийсктра или алгоритм A * . Это то, что ваша проблема: проблема графика / пути.

Клемент Херреман
источник
18

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

Решение для поиска пути, вероятно, будет более сложным, чем ваше текущее решение, и, следовательно, с большей вероятностью потребует отладки. Это, вероятно, также будет медленнее.

ИМО, если он не сломан, не чини.

РЕДАКТИРОВАТЬ

IMO, если лабиринт исправлен, то ваше текущее решение - хороший / элегантный код. Не делайте ошибку, приравнивая «хорошее» или «элегантное» к «умному». Простой код также может быть «хорошим» и «элегантным».

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

(Помимо: если маршруты настраиваются вручную, конструктор лабиринта может сделать уровень более интересным, используя неоптимальные маршруты ...)

Стивен С
источник
Да, это работает. Однако я хотел бы написать хороший код, а не только код. Кроме того, я добавил последнее предложение в свой вопрос, поэтому, если возможно, алгоритм должен быть не только для одного лабиринта, но и для нескольких.
RoflcoptrException
лабиринты также могут быть сгенерированы (у меня есть алгоритм, который генерирует симпатичные pacman лабиринты), так что немного автоматизации - путь вперед
Эрих Китцмюллер
«... или пользователи могут создавать их». В этом случае у вас действительно есть лабиринт.
phuzion
@phuzion - я знаю об этом. Однако между этими двумя случаями есть различие. Если это OP, создающий лабиринт bazzilion, то создавать маршрут вручную неудобно. Если это конечный пользователь ... это означает, что ОП должен писать документацию, заниматься бесконечными поисками неисправностей в лабиринтах конечных пользователей, выдвигать бесконечные жалобы на то, насколько это недружелюбно, и так далее. Другими словами, причины реализации автоматической генерации маршрута разные .
Стивен С.
14

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

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

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

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

Джон Гарденье
источник
да, у меня есть логика преследования pacman, уже реализованная, но я тоже не доволен ею;)
RoflcoptrException
По моему опыту (я люблю писать версии pacman просто для удовольствия), это может привести к тому, что глаза надолго застрянут вне отверстия. Это потому, что алгоритм погони обычно идет по принципу «если Пакман находится на севере, идите на север», но лабиринт может содержать «ловушки», в которых глаза должны идти в первую очередь на юг. Так как pacman движется, призрак рано или поздно сбежит, но дыра - фиксированная цель. (Примечание: я говорю о сгенерированных лабиринтах)
Эрих Кицмюллер
3

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

Значения будут предварительно рассчитаны с использованием любого доступного алгоритма.

MVBL FST
источник
Я собирался предложить это. Наружное заполнение, начинающееся с «дыры монстра». Я думаю, что ваш ответ выиграл бы от картинки.
AjahnCharles
3

Это был лучший источник информации о том, как это работает.

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Когда призраки убиты, их бестелесные глаза возвращаются в исходное положение. Это просто достигается установкой целевой плитки призрака в это место. Навигация использует те же правила.

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

Примечание: я не осознавал, насколько круты те программисты pac-man, которые в основном создали целую систему сообщений в очень маленьком пространстве с очень ограниченной памятью ... это удивительно.

Midpipps
источник
2

Я думаю, что ваше решение подходит для проблемы, проще, чем сделать новую версию более "реалистичной", где призрачные глаза могут проходить сквозь стены =)

Эрнан Эш
источник
2
Чтобы добавить еще больше реализма, позвольте самим призракам проходить сквозь стены: D
Томас Эдинг
3
Это непрозрачные стены призрака, но призраки второго порядка (призрак призрака) более прозрачны. (Вы можете найти много руководств пользователя с ошибками, преобразованными в функции)
Hernán Eche
1
+1 для «призраков второго порядка» - о да, производная от призрака должна обязательно превосходить простые объекты первого порядка, такие как стены ... :)
Асад Эбрахим
2

Вот аналог и псевдокод для идеи заполнения потока ammoQ.

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

Идея состоит в том, что это поиск в ширину, поэтому каждый раз, когда вы сталкиваетесь с новым смежным квадратом s, лучший путь - через p. Это O (N), я верю.

Марк Питерс
источник
2

Я мало знаю о том, как вы реализовали свою игру, но вы могли бы сделать следующее:

  1. Определите расположение глаз относительно положения ворот. т.е. это осталось выше? Прямо внизу?
  2. Затем переместите глаза в одно из двух направлений (например, сделайте так, чтобы они двигались влево, если они находятся справа от ворот, и ниже ворот) и проверьте, есть ли стены и препятствующие этому.
  3. Если есть стены, мешающие вам сделать это, то заставьте его двигаться в противоположном направлении (например, если координаты глаз относительно булавки находятся прямо на севере, и в настоящее время она движется влево, но на пути есть стена, сделайте ее двигаться на юг
  4. Не забывайте проверять каждый раз, чтобы двигаться, чтобы проверять, где глаза относительно ворот, и проверять, нет ли широтной координаты. то есть только над воротами.
  5. В случае, если он находится только над воротами, двигайтесь вниз, если есть стена, двигайтесь влево или вправо и продолжайте делать это 1 - 4, пока глаза не окажутся в логове.
  6. Я никогда не видел тупиков в Pacman, этот код не будет учитывать тупики.
  7. Кроме того, я включил решение проблемы, когда глаза будут «колебаться» между стеной, проходящей через начало координат в моем псевдокоде.

Какой-то псевдокод:

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile

источник
2

Предложение dtb23 просто выбрать случайное направление в каждом углу, и в конце концов вы обнаружите, что звуки монстра-дыры ужасно неэффективны.

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

По мере того, как игрок прогрессирует по уровням, вы уменьшаете вероятность того, что выбрано случайное направление. Это добавило бы еще один рычаг на общий уровень сложности в дополнение к скорости уровня, скорости призрака, паузе приема таблеток (и т. Д.). У вас есть больше времени, чтобы расслабиться, пока призраки - это просто безобидные глаза, но это время становится все короче и короче по мере вашего прогресса.

imoatama
источник
2

Короткий ответ, не очень хорошо. :) Если вы измените лабиринт Pac-Man, глаза не обязательно вернутся. Некоторые из хаков, плавающих вокруг, имеют эту проблему. Так что это зависит от наличия кооперативного лабиринта.

dwidel
источник
2

Я бы предположил, что призрак хранит путь, который он прошел от дыры до Pacman. Поэтому, как только призрак умирает, он может следовать этому сохраненному пути в обратном направлении.

Фишер Людриан
источник
2
этот путь, скорее всего, будет слишком длинным
Ахмад Ю. Салех
Всякий раз, когда вы посещаете узел, вы можете исключить цикл из истории. Это сделало бы это немного более прямым. Может быть интереснее, чем всегда следовать по одному и тому же прямому пути, но довольно часто он будет включать несколько довольно глупых почти петель (например, 3 стороны квадрата).
AjahnCharles
1

Зная, что пути pacman неслучайны (т. Е. Каждый конкретный уровень 0-255, inky, blinky, pinky и clyde будут работать точно так же для этого уровня).

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

Инкогнито
источник
1

Призраки в pacman следуют более или менее предсказуемым образцам, пытаясь сопоставить сначала X или Y, пока цель не будет достигнута. Я всегда предполагал, что это было точно так же, как глаза возвращаются назад.

плинтус
источник
1
  1. Перед началом игры сохраните узлы (пересечения) на карте.
  2. Когда монстр умрет, возьмите точку (координаты) и найдите ближайший узел в вашем списке узлов
  3. Рассчитайте все пути, начиная с этого узла до отверстия
  4. Возьмите кратчайший путь по длине
  5. Добавьте длину пространства между точкой и ближайшим узлом
  6. Рисовать и двигаться по пути

Наслаждайтесь!

GingerHead
источник
1

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

Узлы меток один раз

Когда вы впервые загружаете уровень, пометьте все узлы логова монстров 0 (представляя расстояние от логова). Выполняйте внешнюю маркировку подключенных узлов 1, подключенных к ним узлов 2 и т. Д., Пока все узлы не будут помечены. (примечание: это работает даже если логово имеет несколько входов)

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

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

Наводнение из логова

Глаза двигаются к соседу с самым низким расстоянием

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

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

Полностью маркированный пример

Полная карта

AjahnCharles
источник
0

Для моей игры в PacMan я создал несколько « shortest multiple path home» алгоритм, который работает для любого лабиринта, который я ему предоставляю (в рамках моего набора правил). Это также работает через их туннели.

Когда уровень загружен, все path home data in every crossroadпусто (по умолчанию), и как только призраки начинают исследовать лабиринт, они crossroad path home informationпродолжают обновляться каждый раз, когда сталкиваются с «новым» перекрестком или с другого пути, натыкающегося на их известный перекресток.

iNyuu
источник
-2

Оригинальный человек не использовал поиск пути или причудливый ИИ. Это просто заставило геймеров поверить в то, что в нем больше глубины, чем было на самом деле, но на самом деле это было случайно. Как говорится в «Искусственном интеллекте для игр» / Ян Миллингтон, Джон Фанге.

Не уверен, правда это или нет, но для меня это имеет большой смысл. Честно говоря, я не вижу такого поведения, о котором говорят люди. Red / Blinky for ex, как говорится, не всегда следует за игроком. Похоже, что никто не преследует игрока нарочно. Вероятность того, что они последуют за тобой, выглядит случайной для меня. И просто очень заманчиво видеть поведение в случайном порядке, особенно когда вероятность того, что вас преследуют, очень высока, с 4 врагами и очень ограниченными возможностями поворота в небольшом пространстве. По крайней мере, в первоначальной реализации игра была предельно простой. Посмотрите книгу, она в одной из первых глав.

user4664601
источник
да, он использовал немного ИИ. И да, Блинки следует за Пакманом, когда он находится в режиме погони (переключается на него время от времени), так что с ИИ все в порядке
Жан-Франсуа Фабр