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

В качестве альтернативы более традиционным алгоритмам поиска путей вы можете взглянуть на (соответствующее название!) Пакман запахом выкройка Антиобъект.

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

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

---

Edit: к сожалению, статья Википедии была удалена, поэтомуWayBack Machine to the rescue ...

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

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

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

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

EDIT

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

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

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

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

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

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

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

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

Значения

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

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

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

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

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

Некоторый псевдокод:

   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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Помечайте Узлы Один Раз

При первой загрузке уровня пометьте все узлы логова монстра 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);
}

Полностью Помеченный Пример

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

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

Оригинальный pac-man не использовал поиск путей или причудливый ИИ. Это просто заставило геймеров поверить, что в этом больше глубины, чем было на самом деле, но на самом деле это было случайным. Как сказано в книге искусственный интеллект для игр / Ian Millington, John Funge.

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