- PVSM.RU - https://www.pvsm.ru -

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать - 1

В 2017 двое ученых, канадец John Aycock и британка Tara Copplestone, опубликовали [1] анализ классической игры Entombed [2] для игровой приставки Atari 2600 [3]. Механика этой игры, выпущенной в 1982, крайне проста: археолог, управляемый игроком, должен пробраться по прокручивающимся снизу вверх катакомбам, уворачиваясь от зомби.

У Atari 2600 было всего 128 байт ОЗУ; тем не менее, кажущийся бесконечным лабиринт при каждом запуске был новым, т.е. генерировался в памяти. Как же программистам это удалось? Вот комментарий Стивена Сидли — программиста, 38 лет назад создавшего эту игру:

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

Генераторы лабиринтов

В Википедии перечислены [4] дюжина разных алгоритмов для генерации лабиринтов. Наибольший интерес для игровых приставок представляет «алгоритм Эллера [5]», созданный в том же 1982 Мартином Эллером [6] из Microsoft. Алгоритм Эллера позволяет построчно создавать связные лабиринты без циклов, причем для генерации лабиринта неограниченной высоты достаточно хранить в памяти только пару последних строк. Казалось бы, это как раз то, что нужно для Entombed! Но увы, с игровой механикой вертикального скроллера алгоритм Эллера несовместим, потому что в получившемся лабиринте регулярно приходится обходить препятствия сверху. Для демонстрации этого я слегка модифицировал алгоритм Эллера, чтобы лабиринт создавался в матрице из «стен» и «проходов», как и в Entombed:

Более изощренные алгоритмы, использующие рекурсию и т.п., не уложились бы в 128 байт ОЗУ. Итак, требования к алгоритму для Entombed такие: Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать - 2

  1. Построчная генерация лабиринтов неограниченной высоты;
  2. В создаваемых лабиринтах должно быть как можно меньше несвязных участков; (у игрока есть ограниченная возможность «пробивать стены», так что редкие несвязности не представляет проблемы)
  3. Создаваемые лабиринты должны состоять в основном из ветвящихся и соединяющихся вертикальных проходов — так, чтобы для прохождения лабиринта не требовалось движение вверх;
  4. Для генерации новых строк лабиринта должны использоваться только несколько последних сгенерированных строк. (Поскольку у Atari 2600 нет видеобуфера, то все видимые на экране строки лабиринта должны в каком-то виде храниться в 128 байтах основной памяти).

Кто и как создал этот алгоритм?

Двое ученых, называющих себя «археологами видеоигр», решили начать свои изыскания именно с Entombed — игры про археолога в лабиринте. В ходе своего исследования они разыскали Стивена Сидли, и спросили его, какой алгоритм он использовал для генерации лабиринта. Как уже было упомянуто, Сидли им ответил, что даже автор алгоритма не мог вспомнить, в чем его алгоритм состоял, а сам Сидли — тем более. Затем исследователи попытались найти «торчка», создавшего этот алгоритм; вторая половина истории нашлась в интервью [7], опубликованном в 2008:

Генератор лабиринтов для Entombed создали Дункан [Duncan Muirhead] и я [Paul Allen Newell]. Как-то вечером после работы мы с Дунканом пошли выпить, и у нас завязалось обсуждение того, возможно ли генерировать бесконечный алгоритм, в котором всегда есть проход. Тогда мы не думали о создании игры, нас интересовала сама задача генерации лабиринта. Алгоритм мы придумали вместе, и поскольку я умел программировать для VCS [Atari 2600], то за выходные я создал работоспособный прототип. Нас обоих впечатлило, насколько реализация получилась элегантной. Потом мы показали этот прототип начальству, и они решили, что из него получится отличная игра. Мне это уже не было интересно, так что я доделал Towering Inferno [8], задействовав там часть нашего алгоритма, и уволился. После моего ухода фирма наняла Стивена Сидли, и передала генератор лабиринтов ему. Существенную часть моего кода ему пришлось удалить, чтобы освободить место для игровой механики. [У Atari 2600, кроме жестких ограничений по объемам ОЗУ и ПЗУ, было еще и требование, чтобы генерация каждой строки пикселей занимала ровно 76 тактов примечание автора].

Сидли упомянул, что код генератора лабиринтов был написан на ассемблере 6502 безо всяких комментариев. Это само по себе похоже на подвиг: как отметил [9] khim [10], там «набор команд столь ограничен и крив, что при написании программ возникает в основном вопрос «а как на этом чуде вообще хоть что-то написать»?» Тем не менее, исследователи расковыряли код игры, и выяснили, что лабиринт генерируется следующим образом: для каждой из восьми ячеек генерируемой строки рассматриваются пять уже сгенерированных ячеек (три сверху и две слева), и в соответствии с «магической таблицей» выбирается состояние новой ячейки (проход, стена, либо случайный выбор). Две самые левые ячейки всегда заполнены, и в памяти не хранятся. Правая половина лабиринта — просто зеркальное отражение левой.

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать - 3

Таинственная таблица в сердце неразгаданного алгоритма

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать - 4 Свойства генерируемого лабиринта зависят от того, какое состояние новой ячейки задается для каждой пятерки сгенерированных ранее. Таблица, вшитая в Entombed, немало озадачила исследователей: «Мы не заметили в ней никаких закономерностей, даже когда мы несколькими способами представили ее в виде карты Карно [11] Сидли высказался в том же духе: «Для меня она остается загадкой: я так и не смог ее распутать, и использовал ее как черный ящик.» Впрочем, отсутствие закономерностей в таблице — некоторое преувеличение: например, на карте Карно видно, что при c=1 (стена слева сверху от текущей ячейки) не будет генерироваться X=1 (стена в текущей ячейке).

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать - 5

BBC в своем репортаже [12] про «цифровую археологию» прибегла к еще более драматичным преувеличениям: «Таблица составлена поистине гениально: при каждом запуске игры создается новый лабиринт, по которому можно пройти из начала в конец. Если бы значения в этой таблице были хоть немного другими, то скорее всего, лабиринт получался бы непроходимым. Это просто необъяснимо.» Перепост [13] на hackaday.com сформулирован еще увереннее: «Загадочная таблица всегда создает проходимые лабиринты, но стоит в ней поменять любые биты, и головоломка станет неразрешимой.» На самом же деле, и лабиринт не всегда получался связным, как видно на видеозаписи игры [14]; и небольшие изменения в таблице не оказывают заметного влияния на получающиеся лабиринты: я сделал версию на JavaScript [15], в которой вы можете сами поиграть с «загадочной таблицей» — менять ее прямо «на ходу» и следить, как в результате меняется лабиринт. Вероятно, гарантия связности лабиринта, о которой упоминал и Paul Newell в своем интервью, была потеряна вместе с удаленной частью кода.

Археология видеоигр

John Aycock прокомментировал, как Entombed стала объектом его исследования: он готовил для своих студентов задание на реверс-инжиниринг, и выбрал относительно малоизвестную игру, потому что для популярных игр студенты могли бы найти в сети уже разобранный код. Если в игре, выбранной наугад, встретилась такая выдающаяся находка — не значит ли это, что практически в любой игре того времени найдутся блестящие программистские решения, стоит лишь копнуть поглубже? Стивен Сидли сравнил разработку для Atari 2600, с ее убогим набором команд, 128 байтами ОЗУ, и 76 тактами на каждую строку пикселей, — с «восхождением на Эверест без кислородных баллонов»: сами ограничения платформы вынуждали программистов изобретать гениальные алгоритмы.

«Копнуть поглубже» — это не только метафора. Исследование классических видеоигр осложняется как недолговечностью носителей, на которых они были записаны, так и отношением к старым играм как к неинтересному мусору. В 1983 Atari вывалила на свалку [16] 47 тонн картриджей для Atari 2600 — не меньше десятка полных грузовиков! Раздавленные асфальтовым катком и залитые сверху бетоном, эти картриджи лежали тридцать лет, пока в 2014 «цифровые археологи» не получили разрешение на раскопки и извлечение уцелевших картриджей. Ни один из выкопанных картриджей не работал, но как минимум один из них удалось восстановить [17], перепаяв компоненты.

Поведение Atari, залившей картриджи бетоном, чтобы защитить их от «расхитителей» — весьма типично для правообладателей, которые легче предадут свои наработки вечному забвению, чем потерпят «упущенную выгоду» от того, что их интеллектуальная собственность кому-то достанется бесплатно. Но возможно, еще не поздно защитить «виртуальный культурный слой» 20-го века, разрешив свободное копирование программ, давно утративших коммерческую ценность?

Автор: ruvds

Источник [18]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/algoritmy/354812

Ссылки в тексте:

[1] опубликовали: https://arxiv.org/ftp/arxiv/papers/1811/1811.02035.pdf

[2] Entombed: https://en.wikipedia.org/wiki/Entombed_(Atari_2600)

[3] Atari 2600: https://ru.wikipedia.org/wiki/Atari_2600

[4] перечислены: https://en.wikipedia.org/wiki/Maze_generation_algorithm

[5] алгоритм Эллера: https://habr.com/ru/post/176671/

[6] Мартином Эллером: https://en.wikipedia.org/wiki/Marlin_Eller

[7] интервью: http://www.digitpress.com/library/interviews/interview_paul_allen_newell.html

[8] Towering Inferno: https://www.youtube.com/watch?v=YFAlJFJFcdc

[9] отметил: https://habr.com/ru/post/506832/#comment_21750436

[10] khim: https://habr.com/ru/users/khim/

[11] карты Карно: https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE

[12] репортаже: https://www.bbc.com/future/article/20190919-the-maze-puzzle-hidden-within-an-early-video-game

[13] Перепост: https://hackaday.com/2019/09/30/emtombed-secrets-partially-unearthed-as-researchers-dissect-clever-maze-generating-algorithm/

[14] видеозаписи игры: https://www.youtube.com/watch?v=oIR8IT493_Y&t=143

[15] версию на JavaScript: http://atari.ruvds.com/

[16] вывалила на свалку: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D1%85%D0%BE%D1%80%D0%BE%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE%D0%B8%D0%B3%D1%80_Atari

[17] удалось восстановить: https://www.benheck.com/atari-landfill-cartridge-resurrection/

[18] Источник: https://habr.com/ru/post/510266/?utm_source=habrahabr&utm_medium=rss&utm_campaign=510266