Pacman: как глаза находят свой путь назад к дыре монстра?

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

Это проблема поиска пути. Популярный алгоритм см. в http://wiki.gamedev.net/index.php/A*.

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

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

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

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

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

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

ИЗМЕНИТЬ

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

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

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

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

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

При запуске лабиринта можно распространить вокруг него запах монстров и заставить глаза следовать за ним до дома.

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

Edit: к сожалению, статья из википедии была удалена, так что WayBack Machine в помощь...

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

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

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

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

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

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

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

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

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

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