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