Что-то давно я не занимался переводами, вот решил вспомнить как это. По просьбам на хабре решил перевести одну интересную статью: http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior.

Мне кажется правильным начать этот блог с темы, которая вдохновила меня в первую очередь. Не так давно я наткнулся на статью Jamey Pittman «Pac-Man Dossier», в которой приводилось очень детальное описание механики игры Pac-Man. Она показалась мне очень интересной, поэтому этот сайт — попытка собрать такую же детальную информацию об остальных играх. Но в дань уважения я все же начну с Pac-Man, а в частности, с описания алгоритма поведения привидений. Это очень интересная тема и, надеюсь, мое объяснение будет немного более понятным и доступным, чем у Джейми, потому что я сосредоточусь лишь на поведении.

Об игре:

«В то время все доступные игры были очень жестокими — игры о войне и космических захватчиках. Не было ни одной игры для всех сразу, а особенно, которые понравились бы девушкам. Я хотел придумать «комическую» игру, которой могли бы наслаждаться даже девушки» - Toru Iwatani, создатель Pac-Man

Pac-Man — одна из знаковых видеоигр всех времен, большинство людей (даже не геймеров) по крайней мере знакомы с ней. Цель игры очень проста — игрок находится в лабиринте, наполненном «едой» (изображенной в виде точек), и ему нужно съесть их все, чтобы пройти на следующий уровень. Задачу осложняют четыре призрака, преследующих пэкмена. Если пэкмен встретится с одним из привидений, он теряет жизнь и возвращается на начало, так же как съеденные им точки. Кроме простого убегания от привидений, единственная защита пэкмена — это четыре гранулы-энерджайзера, расположенные в углах лабиринта. Если съесть одну — привидения начинают бояться и отступать в течении небольшого времени, а на ранних уровнях пэкмен может съесть кого-нибудь из них, чтобы получить бонусные очки. Съеденное привидение не удаляет его полностью, а возвращает на начальное положение, чтобы заново начать преследование. Кроме поедания точек и призраков, существует еще одна возможность получить бонусные очки — фруктики, которые появляются на каждом уровне ближе к середине лабиринта. Первый фруктик появляется, когда пэкмен съел 70 точек в лабиринте, второй — когда 170.

Каждый уровень Pac-Man использует один и тот же лабиринт с 240 точками (едой) и 4 энерджайзерами. Туннели, ведущие из левого и правого краев экрана могут быть использованы пэкменом и привидениями в качестве переходов на противоположную сторону экрана, хотя скорость призраков при прохождении туннеля значительно уменьшается. Хоть лабиринт все время одинаков, уровни становятся все сложнее из-за изменения скорости самого пэкмена и ускорения привидений. После 21 уровня никаких изменений в игре больше не делается, поэтому все остальные уровни идентичны по сложности.

Общие элементы поведения всех привидений

«Ну, игра про еду — не такое уж большое развлечение, поэтому мы решили вдохнуть немного волнения и напряжения и добавили врагов. Игрок должен был бороться с ними, чтобы получить пищу. Каждый из врагов имеет собственный характер. Враги — это четыре маленьких монстра по форме напоминающих привидений, каждый своего цвета — синего, оранжевого, розового и красного. Я использовал четыре разных цвета в основном для того, чтобы привлечь к игре девочек, я думал им понравятся разные цвета» - Toru Iwatani, создатель Pac-Man

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

Домик привидений

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

Условия, определяющие, когда три оставшихся призрака покидают свой дом, на самом деле достаточно сложны. Поэтому я оставлю их описание за пределами этой статьи, тем более они перестают быть актуальны после первых нескольких уровней. Если вам все же интересно, то «Pac-Man Dossier», упомянутое в начале статьи, охватывает и их.

Целевые клетки

Большая часть механики Pac-Man основана на том, что лабиринт разбит на клетки. «Клетка» в данном контексте — это квадратик 8х8 пикселей на экране. Разрешение экрана оригинальной игры было 224х288, что дает нам общий размер в 28х36 клеток, хотя большинство из них недоступно для привидений и пекмена. В качестве примера: считается, что призрак сожрал пэкмена, когда он занял ту же клетку, что и он. Кроме того, каждая точка в лабиринте находится в центре собственной клетки. Следует заметить, что спрайты призраков и пэкмена больше, чем одна клетка, поэтому они никогда не находятся лишь на одной. Всвязи с этим в игре считается, что персонаж занимает данную клетку, если его спрайт занимает ее центр. Это важно для эффективного убегания от призраков, потому что пэкмен будет пойман только если призраку удастся перенести свою центральную точку в ту же клетку, что и пэкмен.

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

Режимы передвижения призраков

Призраки всегда находятся в одном из трех возможных режимах: преследования (Chase), разбегания (Scatter) или страха (Frightened). «Нормальным» считается режим преследования, именно в этом режиме находятся призраки большую часть игры, пытаясь поймать пэкмена, используя его положения как фактор выбора своей целевой клетки. В режиме разбегания каждый призрак имеет свою фиксированную целевую клетку, расположенную в непосредственной близости к углам лабиринта. Это приводит к тому, что в этом режиме призраки разбегаются по углам. Режим испуга уникален тем, что призраки не имеют целевой клетки во время движения. Вместо этого они псевдослучайно решают куда им двигаться на каждом перекрестке. В режиме испуга призрак становится темно-синим, движется гораздо медленнее и может быть съеден пэкменом. Однако, продолжительность этого режима постепенно уменьшается с увеличением уровня и полностью исчезает на 19 уровне.

«Чтобы внести в игру некоторое напряжение, я хотел, чтобы монстры могли окружить пэкмена на определенном этапе игры. Но я чувствовал, что это создавало бы стресс для игрока, если бы он постоянно был окружен призраками. Поэтому я сделал, чтобы монстры окружали его волнами: сначала атака, потом отступление. Когда они перегруппировывались, атака начиналась снова. Мне показалось это натуральнее, чем постоянное нападение» - Toru Iwatani, создатель Pac-Man

Изменения с режима преследования на режим разбегания происходят по фиксированному таймеру, который и вызывает «волны», описываемые Iwatani. Этот таймер сбрасывается в начале каждого уровня или после смерти пэкмена. Так же он приостанавливается, когда привидения в режиме испуга, что происходит, когда пэкмен съедает энерджайзер. После чего привидения опять возвращаются в свой предыдущий режим и таймер возобновляется. Призраки начинают в режиме разбегания и существует четыре волны смены преследование/ разбегание, после чего призраки будут оставаться в режиме преследования на неопределенное время (пока таймер не сбросится). Для первого уровня продолжительность этих волн:

1. Разбегание в течении 7 секунд, погоня 20 секунд.
2. Разбегание в течении 7 секунд, погоня 20 секунд.
3. Разбегание в течении 5 секунд, погоня 20 секунд.
4. Разбегание в течении 5 секунд, затем постоянная погоня.

Продолжительность этих фаз несколько изменяется, когда игрок переходит на второй уровень, а потом еще раз на пятом. Начиная со второго уровня третья волна преследования значительно увеличивается до 1033 секунд (17 минут 13 секунд), а в следующем режиме разбегание длится всего 1/60 секунды, после чего призраки переходят в постоянный режим преследования. После пятого уровня изменения строятся на дополнительном сокращении первых двух «разбеганий» до 5 секунд и добавление лишних 4 секунд к третьей волне преследования, что удлиняет его до 1037 секунд. Что касается 1/60-секундного режима разбегания на каждом уровне, кроме первого, кажется, что столь небольшое время не может сказаться на игровом процессе, но причина этого будет обоснована дальше.

Основные правила поведения призраков

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

Однако, есть одно исключение из этого правила: когда призраки изменяют режим с преследования или разбегания на любой другой, они обязаны изменить свое направление как только перейдут на следующую клетку. Это обязательство отменяет любое решение о предыдущем направлении движения. Это действует как эффективное уведомление для игрока, что призраки изменили свой режим, так как это единственный раз, когда возможно такое поведение. Заметьте, что когда они покидают режим испуга, они не меняют направление. Итак, 1/60-секундный режим на каждом уровне после первого заставляет всех призраков пересмотреть свое направление движения, даже если их цель осталась там же. Кстати, такое же поведение специально прописано для призраков в «домике», так призрак, который не вышел из домика за время первого переключения режимов, выйдет из него в обратном направлении. Это заставляет их двигаться влево как обычно, а потом сразу изменить направление и пойти вправо.

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

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

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

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

Индивидуальные аспекты поведения

«Это сердце игры. Я хотел, чтобы каждый враг имел свой специфичный характер собственных движений, поэтому они не преследуют пэкмена по одному и тому же пути, это было бы утомительно и не интересно» - Toru Iwatani, создатель Pac-Man

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

Режим разбегания

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

Красное привидение

Красное привидение начинает вне дома привидений и, обычно, его первого надо рассматривать как угрозу, так как он прокладывает кратчайший путь к пэкмэну почти моментально. Его зовут «Блинки» и игра описывает его личность как «тень» (shadow). На Японском она описывается как oikake, что переводится как «преследователь» или «охотник». Описание на обоих языках является точным, так как целевая клетка Блинки в режиме преследования определяется текущей клеткой пэкмэна. Это означает, что Блинки почти всегда непосредственно преследует пэкмэна, до тех пор, пока из-за недальновидного принятия решений он не выберет неэффективный путь.

Хотя метод выбора цели Блинки очень прост, он имеет одну особенность, которой нет у других привидений – в двух определенных координатах на каждом уровне (в зависимости от оставшихся точек) его скорость увеличивается на 5% и поведение в режиме разбегания меняется. Срок изменения скорости варьируется в зависимости от уровня и происходит все раньше и раньше с увеличением прогресса игрока.

Изменения в режиме разбегания, возможно, более значительны, чем изменение скорости, поскольку они являются причиной того, что целевой клеткой Блинки теперь всегда является позиция пэкмена, даже в режиме разбегания, вместо фиксированной клетки в верхнем правом углу. Это фактически держит Блинки в режиме преследования постоянно, хотя он вынужден будет развернуться при смене режима. В этом расширенном состоянии Блинки, как правило, называют «Cruise Elroy», хотя происхождение этого термина, кажется, неизвестно. Даже великий всемогущий гайд «Pac-Man Dossier» не дает нам ответа. Если пэкиен умирает, когда Блинки в режиме Cruise Elroy, он временно возвращается к нормальному поведению, до тех пор, пока другие привидения не вышли из дома привидений.

Розовое привидение

Розовое привидение начинает в доме привидений, но всегда выходит из него незамедлительно, даже на первом уровне. Эго имя «Пинки» и его личность описывается как «быстрый» (speedy). Это значительное отличие от Японского описания личности - machibuse, которое переводится как «сидящий в засаде». Японская версия более соответствует действительности, так как Пинки не двигается быстрее других привидений (даже медленней, чем Блинки в режиме Cruise Elroy), а система поиска цели пытается переместить его туда, куда пэкмэн направляется, а не там, где он сейчас. Целевая клетка Пинки определяется в соответствии с текущей позицией и направлением пэкмэна и выбирает позицию на четыре клетки перед ним. По крайней мере это был замысел и он работал, когда пэкмэн направлялся налево, вниз или вправо. Но когда Пакмэн направлялся вверх, вследствие ошибки переполнения в коде целевая клетка Пинки устанавливалась на четыре клетки перед Пакмэном и четыре слева от него. Я не хочу пугать людей, не знакомых с программированием, но если вы заинтересованы в технических деталях этого бага, Дон Ходжес написал замечательное объяснение (Ссылка на кеш Google, поскольку сервер время от времени лежит от нагрузки), содержащее оригинальный код для поиска цели Пинки и исправленную версию.

Одним из важных последствий метода выбора цели Пинки то, что пэкмэн часто мог выиграть у него в «куриной» игре (на википедии приводится пример из голливуда, когда два водителя идут на таран и один из них в последний момент поворачивает. - прим перев.).
Так как целевая клетка устанавливается на четыре клетки перед пэкмэном, если пэкмэн направляется на него и они менее чем за 4 клетки друг от друга целевая клетка Пинки находится за ним. Это приводит к тому, что Пинки идет в обход, чтобы добраться до своей цели. Поэтому, это была общая стратегия моментального сбивания с толку Пинки, если он подбирался слишком близко. Это часто посылало его в совершенно другую сторону. (на картинке ниже понятно. - прим перев.)

Синее привидение

Привидение по имени Инки остается в домике на короткое время на первом уровне и не бросается в погоню пока пэкмен не съест как минимум 30 точек. На английском его описывают как «застенчивый», «робкий» (bashful), на японском «kimagure» - капризный, причудливый. Поведение Инки сложно предсказать, потому что это единственный призрак, который использует в своей погоне не только положение пэкмена. Инки использует положение и направление как пэкмена, так и Блинки (красного привидения). Метод таргетинга Инки примерно таков: он выбирает клетку на две клетки перед пэкменом (почти как Пинки), затем представьте себе вектор от Блинки до этой точки и удвойте его. Конец вектора и будет целевя клетка Инки.

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

Оранжевое привидение

Оранжевое привидение, «Клайд», последнее привидение, остающееся в доме дольше всех, и не выходящее пока как минимум треть точек не будет съедена. На английском его личность описывается как «тюремщик» (о_О - комментарий перев.) (pokey) , в то время как с японского это otoboke - «притворяться, что игнорируешь». Как обычно японский вариант более точен, метод таргетинга Клайда дает впечатление, что он просто «делает свое дело», не связанное с пэкменом вообще. Уникальная фича таргетинга Клайда — это два режима, которые переключаются в зависимости от его удаленности от пэкмена. Каждый раз когда Клайд должен вычислить свою целевую клетку, он сначала вычисляет расстояние до пэкмена. Если оно больше 8 клеток, то он действует как Блинки, то есть его целью является сам пэкмен. Однако как только его расстояние до пэкмена становится менее восьми клеток, его целевая клетка устанавливается там же, где она была бы в режиме разбегания, неподалеку от левого нижнего угла лабиринта.

Сочетание этих двух методов и дает то, что Клайд постоянно меняет направление то к пэкмену, то в другом направлении. На схеме выше крестиками отмечены места, где происходит переключение режимов. Так что если пэкмену каким-то образом удастся остаться на своем месте, Клайд будет бесконечно крутиться по этой петле. До тех пор пока игрок не находится в левом нижнем углу лабиринта, есть гарантия, что Клайда можно избежать, если вы не блокируете пути его отступления в свой угол. Пока пэкмен находится в восьми клетках от левого нижнего угла, петля Клайда будет иметь ту же форму, какую имела бы в режиме разбегания.

Заключение

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

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

Источники

The Pac-Man Dossier, Jamey Pittman - практически единственный источник, который пригодится вам для собственных исследований. Честно говоря, большая часть это статьи является перефразированием The Pac-Man Dossier. Настоятельно рекомендую к прочтению, если вам понравилась эта статья.

Pac-Man’s Ghost Behaviour Analyzed and Fixed, Don Hodges - объяснение бага в поведении Пинки и Инки.

Pac-Man Museum