company_banner

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



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

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

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


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



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

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

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


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

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

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



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


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



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

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


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

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

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

    RUVDS.com
    RUVDS – хостинг VDS/VPS серверов

    Comments 59

      0

      слепой хайп, и провокационные заголовки


      сейчас дебажутся и реверс-инженерятся сложнейшие современные игры размером сотни мегабайт(движок), а тут "они не смогли осилить пару кб бинарного кода"… смешно да и только


      если эта задача так интересует автора (или того профессора) пусть ставит денежное вознаграждение за задачу, даже 1000$ достаточно чтоб ему за неделю переписали на чистом Си весь этот бинарный код


      чушь про 128 байтов и такты отрисовки-никак не связан со сложностью, опятьже пустой "лже-хайп" для незнакомых с "программированием"… (типо выступает этот профессор перед аудиторией, и говорит никому непонятные цифры и никто не может ничего понять и спросить, все полча сидят и восхищаются, главное говорить с важным видом и уверенным голосом)


      Такчто да, если задача "реальная"-идешь на любое подобие bountysource, как я сказал за 1000$ ему за неделю весь код на Си перепишут и будет работать на современном ПК.


      А так статья ниочем.
      (и позор таким "профессорам" которые тешат свое чсв и на самом деле ничему и не учат по факту, ему не нужно решение этой задачи ему нужно чтоб студенты ничего не понимали и восхищались, и через 30 лет он будет рассказывать одно и тоже… ужасно)


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

      мистификация и социальные шаблоны для детишек, отвратительно

        +25
        Я так понимаю, что проблема в понимании принципа составления этой «магической таблицы», а не алгоритма. Т.е. реверснуть код — не проблема. Проблема понять как он составил таблицу, которая тупо зашита в код.
          +9
          Вполне возможно, что он просто действовал перебором, пока не получил стабильные результаты. В этом случае, никакой магии там нет, простое везение и случайность.
            +5
            Отчего же никто больше не может тем же перебором составить такую же таблицу? Уж современные компьютеры побыстрее обкуренных программистов. Хотя…
              +23
              Не может или нафиг никому не нужно?

              Это такой неуловимый Джо, вероятно можно придумать и реализовать куда более стабильный и математически доказанный алгоритм для любых лабиринтов, но зачем? Сейчас ресурсов в миллионы раз больше и можно спокойно генерить бесконечные миры с любыми условиями.
                +2
                Современные компьютеры практически не имеют ограничений. Достаточно вспомнить Elite на ZX и реализацию генерации вселенных, миров и названий. Это было революционно. И если вы в то время еще не родились, не вам говорить о простоте или сложности. Сейчас проще всего говорить об этом или хайпить. А вот тогда написать?!?

                Насколько я понимаю в 90-х вам было 10 и выше? Что-то не встречал вашего ника среди разработчиков…
                  –1
                  Мне уж далеко за 40, не учите. Да, и переходить на личности — признак того, что Вам нечего сказать по существу.

                  Вы, похоже, меня не поняли.
                  Алгоритмы, имхо, что тогда, что сейчас примерно одинаковой сложности.
                  Вот только сейчас принято алгоритмы «подбирать» с помощью ИИ, а не выводить с помощью математики.
                    +1

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

                      0
                      Эм, так Вы же сказали ровно то же, что и я :)
                        –1
                        А ничего что современный ПК ушел от МК чуть далее, чем дофига?
                        В современных системах прикладную программу к реальному железу никто не пустит. На пути будет как минимум несколько железных слоев абстракций, и еще не меньше — программных.

                        Да и при современной мощности железа такая оптимизация на грани уже не имеет никакого смысла, и скорее вредна, чем полезна.

                        Оптимизация:
                        Плюсы:
                        -быстрее работает
                        Минусы:
                        -значительно дороже разработка (ручные оптимизации занимают много времени)
                        -значительно дольше разработка (дополнительный бюджет времени на оптимизации)
                        -не работает или плохо работает на совместимых платформах (использовали в оптимизациях особенности какого-то одного вендора или старый набор инструкций)
                        -значительно дороже перенос на другие платформы (требуется ручное вмешательство в код)
                        -значительно дороже поддержка(все ручные оптимизации придется всегда учитывать и актуализировать)

                        Неоптимизированный софт:
                        Плюсы:
                        -дешевле
                        -быстрее выпускается
                        -быстрее обновляется
                        -работает на совместимых платформах (нет привязки к вендору/набору инструкций)
                        -дешево переносить на новые платформы (обычно достаточно компиляции)
                        -получает все преимущества от новых платформ (компилятор автоматически использует наиболее производительные наборы инструкций, доступные на конкретной платформе)
                        Минусы:
                        -работает медленнее оптимизированного

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

                        На МК с такими оптимизациями на грани можно поиграться и сегодня. Например на многих микро МК стек находится в области ОЗУ, но растет сверху вниз, и т.к. ОЗУ небольшая, достаточно легко пересечься со стеком.
                          +1

                          Расскажите это создателям интро и демо.

                  +3
                  Вполне возможно, что он просто действовал перебором

                  Состояние ячейки определяется состоянием пяти ячеек. Существует 32 комбинации состояний пяти ячеек:
                  00000
                  00001

                  11110
                  11111
                  Новая ячейка может принимать одно из трех состояний: стена, проход, рандом. Можно составить 3^32 таблицы. 3^32=1853020188851841 — это не очень много, но вручную такое количество не перебрать. Если, скажем, на просмотр каждой таблицы тратить одну секунду — понадобится (((1853020188851841/60)/60)/24)/365.25=58718666.4655 — чуть больше 58-ми миллионов лет.
                    +1
                    это не очень много, но вручную такое количество не перебрать. Если, скажем, на просмотр каждой таблицы тратить одну секунду — понадобится

                    Да, но это если предполагать, что решение может быть только одно. На самом деле, может каждая сотая комбинация дает достаточно хорошое построение лабиринта. В статье же указано, что лабиринт вовсе не всегда оказывается связанным. Возможно, можно дебажить таблицу кусками, постепенно находя оптимум. Возможно, можно оптимизировать процесс даже на тех ресурсах и написать тесты, которые проверят лабиринт автоматически.
                  +1
                  Левая часть таблицы 4х4 построена по принципу «не повторения комбинаций трёх символов ни по строкам, ни по столбцам, ни по диагонали».
                  +7
                  Непонятна Ваша претензия и про 1000 у.е. за код на C. В статье есть переписанный вариант на JS. То есть самим переложением алгоритма на другой язык проблемы нет.
                    –38

                    извини но не хочется на эту тему говорить, нравиться мистифицировать и верить в чудеса пусть верят

                      +6

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


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

                    +14
                    Вы, видимо, статью дальше ката читать не стали?
                    В ней есть подробное описание алгоритма, за которое вы просите $1000.
                      +1
                      Ахаха, сейчас создаются сложнейшие математические модели, настолько сложные, что используют мощнейшие суперкомпьютеры, а вы пишете что число Пи до сих пор полностью не записано?
                      +2
                      Что-то вроде наивной реализации плиток Вана?
                        +2
                        понял. таблица = список X
                          +11

                          Я делал генератор лабиринтов для (старой версии, в новой не работает) игры Shenzhen I/O
                          https://www.youtube.com/watch?v=geT2uP7MYGc
                          доп. материалы https://imgur.com/a/Vwvit


                          Там памяти еще сильно меньше чем 128 байт (всего где-то около 30 значений от -999 до 999 и без стека и произвольного доступа)


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


                          Алгоритм работет так:


                          • На входе ширина(w) и высота(h) лабиринта и запрашиваемые координаты (x, y)
                          • Псевдослучайно выбираем на какой x0 будет сплошная вертикальная стена.
                          • если x < x0 то поворачиваем прямоугольник на 90 градусов и повторяем алгоритм для левого прямоугольника (для всей части x < x0)
                          • если x > x0 то то же самое для правой части
                          • если x == x0 то выбираем одно или два места (y0 и y1) где в этой вертикальной стене будут проходы. Если y == y0 или y == y1 то проход, иначе стена.
                          • Еще нюанс: стены могут быть только на четных значениях x, а проходы только на нечетных y
                          • Позиция старта захардкожена, позиция выхода находится там где на каждом шаге алгоритма выбиралась левая секция
                            +6
                            Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.
                            Вполне верю, один раз не мог разобраться, почему не работает написаный мной алгоритм, начал смотреть код — так и не смог понять, что я имел ввиду, когда его писал, при этом вспомнил, что писал в полусонном/полупьяном состоянии, и этот код тогда мне казался вполне логичным и правильным.
                              +4
                              Не, это не считается. Вот написать код, который работает но при этом на трезвую голову не понятен — вот это интересно.
                                +11
                                Разве в комментарии не это и описано?
                                  +4
                                  Нет.
                                  один раз не мог разобраться, почему не работает написаный мной алгоритм
                                    +1
                                    Хм, интересно, что как минимум 12 человек тоже не заметили разницы в одно «не».
                                  +1

                                  Был у меня один знакомый в своё время, который писал программу по принципу "добавил пару случайных операторов — запустил — посмотрел, приблизились ли к желаемому поведению — goto шаг 1."

                                    +7

                                    Ваш друг нейросеть.

                                      +4
                                      Больше похоже на генетический алгоритм.
                                        +1

                                        Это был примерно 1997 год. Тогда такого слова ещё не было ;)

                                          +4
                                          Нейросети в 40-х годах придумали.
                                            0
                                            На бирже уже вовсю ими пришпоривали.
                                              +1
                                              труда
                                            +1
                                            Мы все нейросети так то…
                                              0
                                              Фига ты глубоко зашёл)
                                            0
                                            И были успешные программы реализованные такие образом?)
                                            0
                                            Я один раз так не мог разобраться с чем-то в игре которую сам-же пилил, ушел проветриться и по итогу с друзьями напился. Как вернулся домой не помню. Ближе к вечеру следующего дня решил вернуться к проблеме и оказалось что она уже решена… Расследование показало что я вернулся домой и не лег спать а включил компьютер и все починил. Правда сложностей с пониманием не возникло, довольно быстро разобрался в том коде который был написан.
                                          +6
                                          как отметил khim, там «набор команд столь ограничен и крив, что при написании программ возникает в основном вопрос «а как на этом чуде вообще хоть что-то написать»?»

                                          Ассемблер 6502 крайне прост, понятен и логичен, писать на нём очень приятно. Более простой и лёгкий в освоении процессор надо ещё поискать. Другое дело, что код получается довольно многословным, т.к. надо постоянно обращаться к памяти, и также, если придти к этому процессору после чего-то из области 8080/Z80/x86 или PDP/68K, будет непросто переключиться на совершенно иную парадигму программирования.
                                            +5
                                            Вот, тоже резануло.
                                            На 6502 просто нужно думать по-другому.
                                              +3
                                              Ради интереса посмотрел его. Тоже не понял в чём его такой уж трагизм. В восьмибитных процессорах сложно ожидать богатой системы команд, а всё основное на месте. Ну есть особенности адресации конечно, но прямо таки фатальной кривизны не заметил.
                                                +2
                                                Совершенно согласен. Процессор необычен, но его фишки надо было понять и осознать. Я на «этом чуде» написал в своё время компилятор бейсика со своей операционкой, файловой системой с подкаталогами и нестандартными драйверами железа, которые, например, позволяли дисководу двигать головами бесшумно, без этого тр-тр-тр.

                                                Один маленький факт об этом процессоре и его системе команд. У него были чудесные режимы индексации памяти, косвенно-индексный и индексно-косвенный. Суть в том, что базовый адрес, куда надо обратиться, сидел по любому адресу из нулевой страницы, а дальше к этому ИЛИ добавлялось значение в регистре Y, или, если для регистра Х, наоборот, сначала брался адрес из этого регистра в нулевой странице, затем оттуда выбирался адрес памяти.

                                                То есть у вас оказывалось 128 индексных регистров для работы с памятью. Работать с памятью было одно удовольствие.
                                                +10

                                                Сдаётся мне, что чувак просто в пик Балмера попал :)

                                                  +1
                                                  Но возможно, еще не поздно защитить «виртуальный культурный слой» 20-го века, разрешив свободное копирование программ, давно утративших коммерческую ценность?
                                                  Вот вам лайфхак: свободно копируйте и сохраняйте, но не распространяйте (то есть не передавайте третьему лицу и не выкладывайте в публичный доступ), до тех пор, пока у продукта не истечет срок годности. В таком случае юридически вы будете чисты.
                                                    +1
                                                    А когда «истечёт срок годности» у продукта типа «программа»?
                                                    Поправьте, но вроде бы стандартные правила для авторского права (жизнь автора плюс 70 лет)… многовато, мягко говоря, для такой задачи.
                                                    0
                                                    А где здесь бесконечный лабиринт? Судя по ширине проходов ходить по диагонали нельзя.
                                                    image
                                                      +1

                                                      проходы — черные, если что

                                                        +4
                                                        Не вижу как на картинке попасть с линии 2 на линию 3 и не попасть дальше в тупик, если движение по диагонали запрещено.
                                                          +1
                                                          Герой может иногда разрушать стены. Об этом и в статье написано и на видео есть.
                                                      +6
                                                      Таблица может быть всего лишь набором случайных чисел, табличным RND-генератором. При этом действительно, между байтами не будет никакой связи, так как её и не должно быть.Табличными RND-генераторами любили пользоваться многие, например Кармак в Doom и Wolfenstein использует табличку из 256 байт.

                                                      То что это подозрение верно, говорит и сама логика, давайте вдумаемся в алгоритм:
                                                      … и в соответствии с «магической таблицей» выбирается состояние новой ячейки (проход, стена, либо случайный выбор)...
                                                      Всё сходится, в соответствии с RND-генератором выбирается тип прохода.

                                                      Здесь немного непонятно что имелось в виду «либо случайный выбор». Но я думаю это опять небольшое недопонимание что там происходит. Смотреть код в эмуляторе Atari 2600 (самый известный — Stella) мне сейчас в 5 утра не очень охота, поэтому я выдвину гипотезу что это означало двойную случайность. Типа, случайный выбор из трёх, где 1,2й предопределены, а 3й отдается на откуп (снова из двух первых) уже другому генератору случайных чисел, с другой природой.
                                                        +7
                                                        Предположение-разгадка «магической таблицы» — это просто первая сформированная таблица, которая удовлетворяла поставленным условиям. Как отменечно и в статье и в комментариях, истинную связность она не обеспечивает, что решается механикой пробивания стен в игре, а значит она просто должна генерить «нечто». Ну она и генерит, как может.
                                                        Также в пользу говорит то, что минимальные правки не вносят заметных проблем в генерацию. Тоесть это не единственное найденное уникальное решение, накуренного гения, а всего лишь «одно из многих». Что не умаляет достижения подобного алгоритма, но, надеюсь, сильно снижает «мистическую» составляющую.
                                                          +4
                                                          О генерации игровых лабиринтов. На atari 65xe играл в игрушку abracadabra. Геймплей — герой в случайном лабиринте с монстрами и сокровищами.

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

                                                          Таким образом, в такой игре главное — сгенерировать персонажа не в одном тупике с монстром.

                                                          Пользуйтесь. Хотя кому сейчас нужен такой геймплей? Разве что в рогаликах )

                                                          PS:
                                                            0

                                                            Цитата легко превращается в шаблон — просто вместо подставляется имя любой банковской системы :)

                                                            Основную часть написал какой-то уволившийся торчок. Я связался с ним, чтобы выяснить, как его алгоритм работал. Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.
                                                              0
                                                              все относительно… но и как интересное описание реализации алгоритма, так же можно приписать данной статье пропаганду алкоголизма/наркомании для решения задач программистам, хотя достаточно воспользоваться пословицей: утро вечера мудренее (ну или сделать небольшой перерыв).
                                                                +1
                                                                Вспомнилась игра Elite (я с ней познакомился в порте на 48-килобайтном Синклере). Она хоть и из другого поколения, но также впечатляла тем, какой объём данных генерируется при небольшом размере программы. Там же по каждой планете и цены, и типы правления, название и т.д. И вот объяснение из Википедии:
                                                                Вселенная Elite состоит из восьми галактик по 256 планет в каждой. На ранних этапах разработки игры её создатели намеревались ограничиться несколькими звёздными системами с продуманным расположением планет, однако в скором времени стало ясно, что подобные планы потребуют огромного по тем временам количества данных, создавая непосильную нагрузку на память компьютера. Вместо этого игра интенсивно использует математические алгоритмы процедурной генерации: их применение позволяло закодировать большую галактику в коротком наборе цифр, а затем каждый раз восстанавливать ее в неизменном виде, используя этот код в качестве начального значения (англ. seed) для генератора псевдослучайных чисел — при создании галактик и планет генератор проходит те же самые этапы по порядку, начиная с того же начального значения, и таким образом получает точно такие же значения. Текстовые описания планет собираются случайным образом из таблицы подстановок.
                                                                  0
                                                                  На спектруме стандартная функция генератора случайных (на самом деле псевдослучайных) чисел вполне мог выдавать некую повторяемую последовательность, если инициализировать его стартовым числом.
                                                                  Так что хоть решение хоть и имеет долю оригинальности, но получить повторяемый псевдослучайный массив данных особой сложности не было, это скорее эксплуатация несовершенства генератора случайных чисел.
                                                                  Впрочем в Майнкрафте при генерации мира тоже можно задавать seed и получать повторяемый мир, так что идея вполне себе жива и ныне.
                                                                    0
                                                                    Таблица не очень магическая. Простейшая такая таблица была бы повторением значения сверху (этим проверяется что код js генератора не верен). Так из начального сида содержащего хоть один проход сгенерировался абсолютно неинтересный лабиринт, ведь каждый слой повторяет предыдущий. Далее элементарные усложнения, возьмем несколько значений сверху, добавим рандом если справа можно поставить проход, и проход в противном случае. И так далее. Так можно сгененрировать кучу таких таблиц. Веселее было в утерянной части, которая вероятно следила за рандомом. Т.е. если алгоритм создавал две ветки, то только одна могла стать не проходимой. По крайней мере я бы делал так.
                                                                      0

                                                                      Когда начал читать описание алгоритма, по спине побежали мурашки: решением точно такой же задачи я занимался 25 лет назад, когда учился в школе. Все свои алгоритмические изыскания я делал в большой тетради на 96 листов, и не один лист в ней был исписан попытками вручную нарисовать лабиринт по простейшим правилам. И эти правила были основаны на трёх клетках предыдущего ряда и двух клетках текущего. Уверяю, что я не тот торчок, да и не получился в то время у меня рабочий код в силу неопытности, но алгоритм крайне похож.

                                                                      Only users with full accounts can post comments. Log in, please.