Comments 72
Это такой неуловимый Джо, вероятно можно придумать и реализовать куда более стабильный и математически доказанный алгоритм для любых лабиринтов, но зачем? Сейчас ресурсов в миллионы раз больше и можно спокойно генерить бесконечные миры с любыми условиями.
Насколько я понимаю в 90-х вам было 10 и выше? Что-то не встречал вашего ника среди разработчиков…
Вы, похоже, меня не поняли.
Алгоритмы, имхо, что тогда, что сейчас примерно одинаковой сложности.
Вот только сейчас принято алгоритмы «подбирать» с помощью ИИ, а не выводить с помощью математики.
Вы в корне не правы. Ограниченные ресурсы вызывают приступы находчивости. Взять хотя бы clr screen в ZX. Почему очистка делали прямой записью в стек, а стек располагали в экранной области? Сейчас такого программирования уже не встретишь, разве только в МК.
В современных системах прикладную программу к реальному железу никто не пустит. На пути будет как минимум несколько железных слоев абстракций, и еще не меньше — программных.
Да и при современной мощности железа такая оптимизация на грани уже не имеет никакого смысла, и скорее вредна, чем полезна.
Оптимизация:
Плюсы:
-быстрее работает
Минусы:
-значительно дороже разработка (ручные оптимизации занимают много времени)
-значительно дольше разработка (дополнительный бюджет времени на оптимизации)
-не работает или плохо работает на совместимых платформах (использовали в оптимизациях особенности какого-то одного вендора или старый набор инструкций)
-значительно дороже перенос на другие платформы (требуется ручное вмешательство в код)
-значительно дороже поддержка(все ручные оптимизации придется всегда учитывать и актуализировать)
Неоптимизированный софт:
Плюсы:
-дешевле
-быстрее выпускается
-быстрее обновляется
-работает на совместимых платформах (нет привязки к вендору/набору инструкций)
-дешево переносить на новые платформы (обычно достаточно компиляции)
-получает все преимущества от новых платформ (компилятор автоматически использует наиболее производительные наборы инструкций, доступные на конкретной платформе)
Минусы:
-работает медленнее оптимизированного
В большинстве случаев достаточно того, что делает оптимизатор компилятора, остальное решается на уровне архитектуры, ручными микрооптимизациями в нескольких ключевых точках, и ассемблерными вставками.
Для ответственных задач есть вообще отдельное железо.
На МК с такими оптимизациями на грани можно поиграться и сегодня. Например на многих микро МК стек находится в области ОЗУ, но растет сверху вниз, и т.к. ОЗУ небольшая, достаточно легко пересечься со стеком.
Вполне возможно, что он просто действовал перебором
Состояние ячейки определяется состоянием пяти ячеек. Существует 32 комбинации состояний пяти ячеек:
00000
00001
…
11110
11111
Новая ячейка может принимать одно из трех состояний: стена, проход, рандом. Можно составить 3^32 таблицы. 3^32=1853020188851841 — это не очень много, но вручную такое количество не перебрать. Если, скажем, на просмотр каждой таблицы тратить одну секунду — понадобится (((1853020188851841/60)/60)/24)/365.25=58718666.4655 — чуть больше 58-ми миллионов лет.
это не очень много, но вручную такое количество не перебрать. Если, скажем, на просмотр каждой таблицы тратить одну секунду — понадобится
Да, но это если предполагать, что решение может быть только одно. На самом деле, может каждая сотая комбинация дает достаточно хорошое построение лабиринта. В статье же указано, что лабиринт вовсе не всегда оказывается связанным. Возможно, можно дебажить таблицу кусками, постепенно находя оптимум. Возможно, можно оптимизировать процесс даже на тех ресурсах и написать тесты, которые проверят лабиринт автоматически.
В ней есть подробное описание алгоритма, за которое вы просите $1000.
Я делал генератор лабиринтов для (старой версии, в новой не работает) игры 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
- Позиция старта захардкожена, позиция выхода находится там где на каждом шаге алгоритма выбиралась левая секция
Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.Вполне верю, один раз не мог разобраться, почему не работает написаный мной алгоритм, начал смотреть код — так и не смог понять, что я имел ввиду, когда его писал, при этом вспомнил, что писал в полусонном/полупьяном состоянии, и этот код тогда мне казался вполне логичным и правильным.
Был у меня один знакомый в своё время, который писал программу по принципу "добавил пару случайных операторов — запустил — посмотрел, приблизились ли к желаемому поведению — goto шаг 1."
как отметил khim, там «набор команд столь ограничен и крив, что при написании программ возникает в основном вопрос «а как на этом чуде вообще хоть что-то написать»?»
Ассемблер 6502 крайне прост, понятен и логичен, писать на нём очень приятно. Более простой и лёгкий в освоении процессор надо ещё поискать. Другое дело, что код получается довольно многословным, т.к. надо постоянно обращаться к памяти, и также, если придти к этому процессору после чего-то из области 8080/Z80/x86 или PDP/68K, будет непросто переключиться на совершенно иную парадигму программирования.
На 6502 просто нужно думать по-другому.
Один маленький факт об этом процессоре и его системе команд. У него были чудесные режимы индексации памяти, косвенно-индексный и индексно-косвенный. Суть в том, что базовый адрес, куда надо обратиться, сидел по любому адресу из нулевой страницы, а дальше к этому ИЛИ добавлялось значение в регистре Y, или, если для регистра Х, наоборот, сначала брался адрес из этого регистра в нулевой странице, затем оттуда выбирался адрес памяти.
То есть у вас оказывалось 128 индексных регистров для работы с памятью. Работать с памятью было одно удовольствие.
То есть у вас оказывалось 128 индексных регистров для работы с памятью
только при условии, что вы имеете право трогать эти ячейки.
На практике же большинство из них было занято под свои роли всеми окружающими участниками, и документировано это было чуть лучше чем никак — и использовав чуть не ту ячейку можно было получить непредсказуемые сбои в других местах.
Честная 16-битность конкурентов была в этом смысле значительно сопровождаемее.
Я тоже с ним много возился, но сейчас это воспринимаю как в основном потерянное время на постоянные перегонки байтов между памятью и регистрами.
Там помнится был бэйсик с ассемблерными вставками, но проще было перейти на чистый ассемблер. Мой одноклассник компилятор С пытался написать, но до выпускного не успел.
Сдаётся мне, что чувак просто в пик Балмера попал :)
Но возможно, еще не поздно защитить «виртуальный культурный слой» 20-го века, разрешив свободное копирование программ, давно утративших коммерческую ценность?Вот вам лайфхак: свободно копируйте и сохраняйте, но не распространяйте (то есть не передавайте третьему лицу и не выкладывайте в публичный доступ), до тех пор, пока у продукта не истечет срок годности. В таком случае юридически вы будете чисты.
проходы — черные, если что
у игрока есть ограниченная возможность «пробивать стены»
То что это подозрение верно, говорит и сама логика, давайте вдумаемся в алгоритм:
… и в соответствии с «магической таблицей» выбирается состояние новой ячейки (проход, стена, либо случайный выбор)...Всё сходится, в соответствии с RND-генератором выбирается тип прохода.
Здесь немного непонятно что имелось в виду «либо случайный выбор». Но я думаю это опять небольшое недопонимание что там происходит. Смотреть код в эмуляторе Atari 2600 (самый известный — Stella) мне сейчас в 5 утра не очень охота, поэтому я выдвину гипотезу что это означало двойную случайность. Типа, случайный выбор из трёх, где 1,2й предопределены, а 3й отдается на откуп (снова из двух первых) уже другому генератору случайных чисел, с другой природой.
Также в пользу говорит то, что минимальные правки не вносят заметных проблем в генерацию. Тоесть это не единственное найденное уникальное решение, накуренного гения, а всего лишь «одно из многих». Что не умаляет достижения подобного алгоритма, но, надеюсь, сильно снижает «мистическую» составляющую.
Лабиринт абсолютно случайный. Стены разрушать нельзя. Но есть нюанс — стены со временем сдвигаются, образуя проходы или закрывая существующие.
Таким образом, в такой игре главное — сгенерировать персонажа не в одном тупике с монстром.
Пользуйтесь. Хотя кому сейчас нужен такой геймплей? Разве что в рогаликах )
PS:
Цитата легко превращается в шаблон — просто вместо подставляется имя любой банковской системы :)
Основную часть написал какой-то уволившийся торчок. Я связался с ним, чтобы выяснить, как его алгоритм работал. Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.
Во первых ассемблер такой же язык как и все другие и по тексту совершенно понятно что программа делает, это же не какой-то зашифрованный нечитаемый шум, тем более у него явно были исходники с худо-бедно проименованными функциями и переменными (а при желании разбирают и дизассемблированные программы, с автоматически сгенерированными именами функций и переменных вида XD04AF. Собственно говоря все кряки и пиратские генераторы серийников именно так и появляются, дизассемблированием кода и выяснением алгоритма)
Характерный пример — быстрый обратный квадратный корень: функция занимает всего с десяток ассемблерных команд, но объяснению того, как она работает, посвящены многие десятки статей.
Вселенная Elite состоит из восьми галактик по 256 планет в каждой. На ранних этапах разработки игры её создатели намеревались ограничиться несколькими звёздными системами с продуманным расположением планет, однако в скором времени стало ясно, что подобные планы потребуют огромного по тем временам количества данных, создавая непосильную нагрузку на память компьютера. Вместо этого игра интенсивно использует математические алгоритмы процедурной генерации: их применение позволяло закодировать большую галактику в коротком наборе цифр, а затем каждый раз восстанавливать ее в неизменном виде, используя этот код в качестве начального значения (англ. seed) для генератора псевдослучайных чисел — при создании галактик и планет генератор проходит те же самые этапы по порядку, начиная с того же начального значения, и таким образом получает точно такие же значения. Текстовые описания планет собираются случайным образом из таблицы подстановок.
Так что хоть решение хоть и имеет долю оригинальности, но получить повторяемый псевдослучайный массив данных особой сложности не было, это скорее эксплуатация несовершенства генератора случайных чисел.
Впрочем в Майнкрафте при генерации мира тоже можно задавать seed и получать повторяемый мир, так что идея вполне себе жива и ныне.
Когда начал читать описание алгоритма, по спине побежали мурашки: решением точно такой же задачи я занимался 25 лет назад, когда учился в школе. Все свои алгоритмические изыскания я делал в большой тетради на 96 листов, и не один лист в ней был исписан попытками вручную нарисовать лабиринт по простейшим правилам. И эти правила были основаны на трёх клетках предыдущего ряда и двух клетках текущего. Уверяю, что я не тот торчок, да и не получился в то время у меня рабочий код в силу неопытности, но алгоритм крайне похож.
В 1983 Atari вывалила на свалку 47 тонн картриджей для Atari 2600 — не меньше десятка полных грузовиков! Раздавленные асфальтовым катком и залитые сверху бетоном, эти картриджи лежали тридцать летНормально ребята перестраховываются
Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать