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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

Вот аналог и псевдокод для идеи заполнения потока 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), я верю.

Answer 7

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

Разметка узлов один раз

Когда вы впервые загружаете уровень, пометьте все узлы логова монстров 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);
}

Пример с полной маркировкой

Answer 8

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

Наслаждайся!

Answer 9

Знание того, что пути Пакмана не случайны (т. Е. Каждый конкретный уровень 0-255, чернильный, мигающий, мизинец и Клайд будет работать точно так же для этого уровня).

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

Answer 10

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