Ученые до сих пор не могут понять, как работает эта старинная видеоигра

41
Игра Entombed

Старые программы и, в особенности, видеоигры могут быть ценным источником утраченных знаний. Разработчики времен Atari 2600 постоянно упирались в аппаратные ограничения, поэтому им приходилось применять смекалку, создавая уникальные программные решения. Некоторые настолько парадоксально просты и в тоже время непонятны, что ставят в тупик даже современных специалистов.

Например, история игры под названием «Entombed», выпущенной в 1982-ом. В ней игроку нужно перемещаться по лабиринту и избегать контактов с монстрами, но из-за дефицита памяти хранить карту лабиринта негде. Поэтому он создается динамически, слой за слоем, прокручиваясь вертикально. Игрок может перемещаться в четырех направлениях в пределах экрана, но он не может узнать строение лабиринта даже на шаг вперед. Потому что программа сама этого не знает.

Лабиринт в Entombed предельно простой, уровень состоит из блоков, которые имеют значение «стена» или 1 и «не-стена» или 0. В игре есть модуль, который обрабатывает участок 5х5 блоков и выдает три решения: сделать следующий уровень целиком из стен, пустым или случайной комбинацией стен и пустот. При этом должен сохраняться проход с предыдущего уровня и не возникать тупиков. Принцип работы этого модуля, от которого зависит весь геймплей, современные разработчики не понимают напрочь.

Ученый Джон Эйкок из Университета Калгари в Альберте (Канада) и программист Тара Копплстоун из Йоркского университета (Великобритания) перебрали все возможности, даже провели реверс-инжиниринг, но успеха не добились. В итоге они обратились к Стиву Сидли, разработчику оригинальной игры, и тот поведал историю. Проектирование модуля поручили талантливому «ронину», программисту-наемнику, не из штата компании. Тот просидел над задачей несколько дней и после ее решения на радостях так напился, что только чудом сохранил сам модуль, но вот объяснить его работу уже не мог. Вскоре он сменил работу и след его потерялся, так что есть большая вероятность, что тайна лабиринта «Entombed» останется тайной навсегда.


ЧИТАЙТЕ ТАКЖЕ
Комментарии  41
Добавить комментарий
  • Tsykunov16 июня 2020 в 11:47

    Не пойму, что тут такого сложного. Я для Радио-86РК делал игрушку - лабиринт. На все поле экрана 80х25 символов строился лабиринт. Стена или проход занимали 1 символ. т.е. лабиринт получался весьма сложный. Прошел лабиринт, попал в другой. При этом никогда не повторялся т.к. строился генератором случайных чисел. При этом был гарантированно проходим и не имел замкнутых (слепых) зон. Если интересно могу описать алгоритм.

    Ответить
    • Сергей16 июня 2020 в 23:38

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

      Ответить
      • нормальный программист17 июня 2020 в 23:11

        Да такике как ты полько пиз..ть умеют. Сейчас работают самые лушие програмиты потому, что сейчас индустрия програмирования развата как никогда ранише даже 1/100 сложности програм даже 1/10000000 таких програм по сложности не могли написать.

        Ответить
        • Аноним17 июня 2020 в 23:45

          Вот по тебе и видно типичного современного программиста, который свою мысль даже правильно сформулировать не может и в слове х#й четыре ошибки сделает.

          Ответить
          • Анатолий22 июня 2020 в 13:47

            И нахера так обощать?

            Ответить
          • john doe8 июля 2020 в 00:55

            100%

            Ответить
        • Дмитрий18 июня 2020 в 00:07

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

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

          Ответить
          • Анатолий22 июня 2020 в 13:48

            Ну после онлайн курсов никто в разрабы не берет - не нужно рассказывать сказки. Но в целом щерно истины есть.

            Ответить
          • Logics21 августа 2020 в 01:14

            У тебя(как и у 95% людей) явные проблемы с логикой.
            Огромное кол-во библиотек и решений отнюдь не упрощает жизнь, а усложняет - знать нужно больше, а разрабатывать необходимо всё более сложные вещи.

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

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

            Ответить
      • Whoami18 июня 2020 в 19:40

        ну почему, то что должно быть оптимизировано - оптимизируется. Сервера денег стоят, трудочасы денег стоят. Если алгоритм нагружен и прожорлив - да, есть смысл. А вот отображение алерта да, наоборот "деоптмизируют" анимашками да красивостями. Дабы было на что посмотреть.
        Тема, как по мне, не очень красивая. Программно подбирать задержки методом свободного поиска (ткнул, прокатило? нет?)... не выглядит надежным и масштабируемым решением.

        Ответить
    • Владислав18 июня 2020 в 00:03

      А ты вспомни 90-е, Спектрум, суперигра "Элита". Всего 48 Кб, а какая стратегия, возможности, задачи...

      Ответить
      • Реональд19 июня 2020 в 11:20

        Игра в которой 8 галактик, с сотнями звездных систем и каждая звездная система со своими характеристиками. И все это кодировалось десятком байт и псевдослучайным рандомизатором.
        Так же с радостью я поиграл в Elite 2 Frontier. Летал и искал центр Галактики )))
        Сейчас народ играет в онлайновую Elite Dangerous. За более чем пять лет игры все игроки даже не смогли исследовать одного десятого процента звездных систем.

        Ответить
    • Шаповалов Роман18 июня 2020 в 13:39

      Я подобную вещь делал на программируемом калькуляторе МК-52 со 105 шагами программной памяти и 15 регистрами. Идея простая - функция от значения соседних (пройденных) ячеек (стен) - типа синус от суммы значений (1- стенка, 0 - стенки нет). Если синус больше какой-то величины (настраиваемой), то проход есть. Наличие стенки (двери) - может быть динамическим.
      Единственное, что не сделал - это проверка на проходимость лабиринта, в т.ч. в зависимости от "настройки" порога. Кстати, спасибо, что напомнили - надо будет в экселе на эту тему поиграться.
      Я еще в фотошопе игру "Жизнь" (Life) моделировал. "Месье знает толк в извращениях"

      Ответить
      • Tsykunov19 июня 2020 в 09:30

        У меня сначала строился забор лабиринта. Далее случайно выбирался один их четырех углов. Если это знакоместо занято (стена), то случайно выбирается одно из двух возможных направлений. Если на новом месте стена, снова выбираем случайно направление. Наконец то попалось свободное место. Проверяем на допустимость строительства стены (все соседние 3 направления, кроме того откуда пришли должны быть свободны от стен) строим стену. Запускаем сначала. За доли секунд из углов растут случайные деревья с множеством разветвлений веток и заплетают весь экран. Выбираем две стучайныек точки не занятые стенами - вход и выход лабиринта. Была одна проблема, нет способа определить момент окончания строительства лабиринта. Выделял 3 секунды, хотя достаточно было 1 секунды.

        Ответить
    • Максим20 июня 2020 в 15:36

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

      Для полноты надо понимать какие ограничения были в Атари, чтобы полноценно определить всю сложность.

      Но в те времена (да и позже) творили жуткие вещи:)
      Например могли старшие разряды указателей использовать для хранения данных ,т.к. платформа их не использовала для адресации (допустим у нас 16 битные указатели, а платформа способна работать с адресами в пределах 14 разрядов)

      Ответить
    • Алексей Пажитнов20 июня 2020 в 17:25

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

      Ответить
    • Егор11 августа 2020 в 18:05

      Сложно, очень сложно

      Ответить
  • Аноним17 июня 2020 в 04:17

    похоже на фейк

    Ответить
  • Аноним17 июня 2020 в 19:27

    Или фейк, или современные программисты настолько отошли от 8-битного ассемблера, что не в состоянии понять, как работает программа.
    Впрочем, если так, то могли бы спросить у энтузиастов Atari - это сообщество существует и программы читать/писать они в большинстве своём умеют.

    Ответить
  • Максим Михайлович Хохлов17 июня 2020 в 20:28

    На днях играл в Лост Викингов первая игра от Близард всего 64кб Неделю проходил куча эмоций и удовольствия. А сейчас эти горе бизнесмены на делают игрух на 120гб ни сценария ни графония ни мозгов. P/s Близы еще финалочку умудрились впихать в 64кб (повторюсь) титры так сказать.

    Ответить
    • Вася22 июня 2020 в 12:39

      Иррационально используют сейчас... нет практики "вкус еды постигается черех голод". Сейчас при желании можно на 16 мегабайтах создать гениальную игру при желании, но пробовать мало кто станет... не тот мир для этого... а еще я слышал, что была игра, 3D шутер, что умещался в нескольких мегабайтах... или меньше... в общем все возможно

      Ответить
      • Loki21 августа 2020 в 07:54

        Wolfenstein 3D?

        Ответить
    • Аноним11 августа 2020 в 09:42

      Викинги, конечно же, не 64Кб =) Там порядка 1,5 Мб (DOS версия). и 640 Кб (Sega версия).

      Ответить
  • нестор18 июня 2020 в 13:06

    Чем-то похоже на то, что я когда-то делал (не лабиринт, просто фон, если так можно сказать)
    http://prntscr.com/t1yx05

    Ответить
  • Andrey_77 Andrey_7718 июня 2020 в 20:16

    На ZX спектрум(48 Кбайт ОЗУ) была игра Элита. Симулятор полётов на космолёте в космосе. Реализовано векторное 3d, бои в космосе, торговля. И очень много логики. При этом космос из 8 галактик по 200 планет. У каждой планеты свои характеристики. Примерно в 40000 байт всё это уместили. Скорее всего характеристики планет не хранили, а генерировали.

    Ответить
  • Дмитрий Батаев18 июня 2020 в 23:25

    Интересно, что якобы обрабатываются блоки 5х5, а в "строке" 16 (шестнадцать ) блоков

    Ответить
    • Василий23 сентября 2020 в 08:31

      А тут всё просто - кривой перевод. В оригинальной статье ничего про блоки 5*5 нет.

      Ответить
  • OOO20 июня 2020 в 19:07

    21 07 00 CD 18 F8 40 лет прошло а кусок машинного 8080 кода в голове сидит. В то время программист был на вес золота.
    Вот вам пример особого таланта https://kkrieger.en.softonic.com/
    игра псевдо -3D, шутер от 1 лица. Размеры файла около 100 килобайт. На 1 дискету 3.5" помешалось 1.44Мб. Но особый прикол в том что эта игра разработана для Windows, работает на любой версии, но использует всю мощность компа и софта на полную.Не супер графика, лучше чем DOOM I. II 1993-1994гг, которые "весили" 60-70 Мб.

    Ответить
    • Андрей23 июня 2020 в 09:31

      У меня на Win7 x 64 не запустился этот шутер.

      Ответить
      • rotten cherry8 июля 2020 в 11:58

        пкм свойства совместимость
        и поставь совместимость на win xp sp3 и галочку на запуск от админа + разрешение 640x480

        Ответить
    • Аноним11 августа 2020 в 09:48

      Оригинальный DooM "весит" ~12 Мб, DooM II ~16 Мб. А вот порты и моды с улучшенными текстурами побольше =)

      Ответить
  • Марат Загиров21 июня 2020 в 15:20

    Ну, тупики-то, положим, имеются. Да и симметрия снижает сложность на много.
    Но - да! Программеры выдавали шедевры! На дискете (аж целых 1,2 Мб!) десяток (и более) игрушек помещалось, хе-хе!
    А алгоритм мне видится простым.
    В "работе" 8 клеток (плюс симметрично отражённые) Рандомом ставим 1 и 0, проверяя, чтобы хотя бы два ноля было под предыдущим. Потом (всё чаще) - хотя бы один.
    По сути, перебор 8-битных ASCII от 64 до 255 (Dec). Из которых большая часть не нужна (много ноликов).
    Если ограничить тремя ноликами, то останется эдак четыре десятка циферок. Если для каждой циферки прописать множество возможных последующих за ним, то не придётся побитно сравнивать.
    Ну, это мой экспромт за те десять минут, что читал статью. :) Ногами не бить, если что! :)

    Ответить
  • Евгений22 июня 2020 в 12:01

    Изучите участок с 0:20 по 0:37. Если внимательно посмотреть, то алгоритм игры сгенерировал тупики на всех 4-х ветках. .т.е. без "лотапы" не пройти. В тоже время игра генерирует 2 ветки в которые не попасть без "лопаты". Также обратите внимание на то, что карта зеркальная и одна половина состоит из 8-ми блоков. В общем тут работает генератор случайных чисел. Вывод: Статья - Фейк.

    Ответить
  • Nauro22 июня 2020 в 16:53

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

    Ответить
  • Yuki24 июня 2020 в 15:14

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

    Ответить
  • vlad7 июля 2020 в 17:37

    Почему ученые не могут понять? В чем собственно проблема тупо проследить за значениями регистров процессора и ячеек ОЗУ во время игры и разобраться что где хранится и откуда берется? Для этого даже не нужен исходный код игрушки.

    Ответить
  • енот9 июля 2020 в 08:56

    Насколько вы цените программистов?

    Ответить
  • Тимур12 августа 2020 в 14:35

    Делал похожую игру на бейсике (zx spectrum), как и некоторые из моих знакомых, лет так ...дцать назад. Могу описать алгоритм... Начальная цена 100500 евро и должность ведущего специалиста ХD

    Ответить
    • Василий23 сентября 2020 в 08:32

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

      Ответить
  • Василий23 сентября 2020 в 08:25

    Похоже, тут как-то много гениев разработки, который читать не умеют.
    Открываем оригинал- https://arxiv.org/ftp/arxiv/papers/1811/1811.02035.pdf
    Оказывается, что зареверсить алгоритм они таки смогли и проблема там не понять "как" это сделано (код то есть), а почему всё это именно так, и почему это работает (тоесть код не похож на общеизвестные алгоритмы и хотелось бы узнать, какие решения принимал разработчик Entombed)

    Ответить
  • Аллё-нна*, этоя-нна*22 ноября 2021 в 23:01

    Ни к чему вестись на желтушные заголовки скучающих копипастеров! Ученые мля, не могут понять мля... Чёзана*??? Просто школоло с бодуна решило зарубиться в олд-скул своих предков и легонько покосилось от древней логики! И айда шуметь, мы типа учимся, и какбэ учёные значит, но ничё не вкурили, а значит это парадоксЪ!!! Ну тут уж писаки подоспели и раздули слоняру из наномыши

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

ВойтиРегистрация