How to become an author
Search
Write a publication
Pull to refresh

Comments 72

UFO just landed and posted this here
Я так понимаю, что проблема в понимании принципа составления этой «магической таблицы», а не алгоритма. Т.е. реверснуть код — не проблема. Проблема понять как он составил таблицу, которая тупо зашита в код.
Total votes 25: ↑25 and ↓0 +25
Вполне возможно, что он просто действовал перебором, пока не получил стабильные результаты. В этом случае, никакой магии там нет, простое везение и случайность.
Total votes 11: ↑10 and ↓1 +9
Отчего же никто больше не может тем же перебором составить такую же таблицу? Уж современные компьютеры побыстрее обкуренных программистов. Хотя…
Total votes 9: ↑7 and ↓2 +5
Не может или нафиг никому не нужно?

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

Насколько я понимаю в 90-х вам было 10 и выше? Что-то не встречал вашего ника среди разработчиков…
Total votes 6: ↑4 and ↓2 +2
Мне уж далеко за 40, не учите. Да, и переходить на личности — признак того, что Вам нечего сказать по существу.

Вы, похоже, меня не поняли.
Алгоритмы, имхо, что тогда, что сейчас примерно одинаковой сложности.
Вот только сейчас принято алгоритмы «подбирать» с помощью ИИ, а не выводить с помощью математики.
Total votes 3: ↑1 and ↓2 -1

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

Total votes 1: ↑1 and ↓0 +1
Эм, так Вы же сказали ровно то же, что и я :)
This comment wasn’t rated yet 0
А ничего что современный ПК ушел от МК чуть далее, чем дофига?
В современных системах прикладную программу к реальному железу никто не пустит. На пути будет как минимум несколько железных слоев абстракций, и еще не меньше — программных.

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

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

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

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

На МК с такими оптимизациями на грани можно поиграться и сегодня. Например на многих микро МК стек находится в области ОЗУ, но растет сверху вниз, и т.к. ОЗУ небольшая, достаточно легко пересечься со стеком.
Total votes 1: ↑0 and ↓1 -1

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

Total votes 1: ↑1 and ↓0 +1
Вполне возможно, что он просто действовал перебором

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

Да, но это если предполагать, что решение может быть только одно. На самом деле, может каждая сотая комбинация дает достаточно хорошое построение лабиринта. В статье же указано, что лабиринт вовсе не всегда оказывается связанным. Возможно, можно дебажить таблицу кусками, постепенно находя оптимум. Возможно, можно оптимизировать процесс даже на тех ресурсах и написать тесты, которые проверят лабиринт автоматически.
Total votes 1: ↑1 and ↓0 +1
Левая часть таблицы 4х4 построена по принципу «не повторения комбинаций трёх символов ни по строкам, ни по столбцам, ни по диагонали».
Total votes 1: ↑1 and ↓0 +1
Непонятна Ваша претензия и про 1000 у.е. за код на C. В статье есть переписанный вариант на JS. То есть самим переложением алгоритма на другой язык проблемы нет.
Total votes 7: ↑7 and ↓0 +7
UFO just landed and posted this here

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


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

Total votes 6: ↑6 and ↓0 +6
Вы, видимо, статью дальше ката читать не стали?
В ней есть подробное описание алгоритма, за которое вы просите $1000.
Total votes 14: ↑14 and ↓0 +14
Ахаха, сейчас создаются сложнейшие математические модели, настолько сложные, что используют мощнейшие суперкомпьютеры, а вы пишете что число Пи до сих пор полностью не записано?
Total votes 1: ↑1 and ↓0 +1
Что-то вроде наивной реализации плиток Вана?
Total votes 2: ↑2 and ↓0 +2

Я делал генератор лабиринтов для (старой версии, в новой не работает) игры 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
  • Позиция старта захардкожена, позиция выхода находится там где на каждом шаге алгоритма выбиралась левая секция
Total votes 11: ↑11 and ↓0 +11
Залогинился сюда просто чтобы пожать вам руку, это очень круто, достойно уважения! Скинул своим друзьям в Дискорд чатик на ознакомление.
This comment wasn’t rated yet 0
Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.
Вполне верю, один раз не мог разобраться, почему не работает написаный мной алгоритм, начал смотреть код — так и не смог понять, что я имел ввиду, когда его писал, при этом вспомнил, что писал в полусонном/полупьяном состоянии, и этот код тогда мне казался вполне логичным и правильным.
Total votes 6: ↑6 and ↓0 +6
Не, это не считается. Вот написать код, который работает но при этом на трезвую голову не понятен — вот это интересно.
Total votes 4: ↑4 and ↓0 +4
Разве в комментарии не это и описано?
Total votes 13: ↑12 and ↓1 +11
Нет.
один раз не мог разобраться, почему не работает написаный мной алгоритм
Total votes 4: ↑4 and ↓0 +4
Хм, интересно, что как минимум 12 человек тоже не заметили разницы в одно «не».
Total votes 1: ↑1 and ↓0 +1
Код должен работать хуй пойми почему, а у вас не работает
This comment wasn’t rated yet 0

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

Total votes 1: ↑1 and ↓0 +1
Больше похоже на генетический алгоритм.
Total votes 4: ↑4 and ↓0 +4

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

Total votes 1: ↑1 and ↓0 +1
Нейросети в 40-х годах придумали.
Total votes 4: ↑4 and ↓0 +4
Мы все нейросети так то…
Total votes 1: ↑1 and ↓0 +1
Скорее всего, только частично. Наверняка есть и другие механизмы, которые пока ещё нам неизвестны.
This comment wasn’t rated yet 0
И были успешные программы реализованные такие образом?)
This comment wasn’t rated yet 0
Я один раз так не мог разобраться с чем-то в игре которую сам-же пилил, ушел проветриться и по итогу с друзьями напился. Как вернулся домой не помню. Ближе к вечеру следующего дня решил вернуться к проблеме и оказалось что она уже решена… Расследование показало что я вернулся домой и не лег спать а включил компьютер и все починил. Правда сложностей с пониманием не возникло, довольно быстро разобрался в том коде который был написан.
This comment wasn’t rated yet 0
как отметил khim, там «набор команд столь ограничен и крив, что при написании программ возникает в основном вопрос «а как на этом чуде вообще хоть что-то написать»?»

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

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

То есть у вас оказывалось 128 индексных регистров для работы с памятью. Работать с памятью было одно удовольствие.
Total votes 2: ↑2 and ↓0 +2
То есть у вас оказывалось 128 индексных регистров для работы с памятью

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

This comment wasn’t rated yet 0
Мы в школе на ассемблере 6502 писали. В 1990 году. У нас Агаты стояли.
Там помнится был бэйсик с ассемблерными вставками, но проще было перейти на чистый ассемблер. Мой одноклассник компилятор С пытался написать, но до выпускного не успел.
This comment wasn’t rated yet 0

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

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

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

Total votes 1: ↑1 and ↓0 +1
Не вижу как на картинке попасть с линии 2 на линию 3 и не попасть дальше в тупик, если движение по диагонали запрещено.
Total votes 4: ↑4 and ↓0 +4
Герой может иногда разрушать стены. Об этом и в статье написано и на видео есть.
Total votes 1: ↑1 and ↓0 +1
видео ролики говорят о том, что можно сделать прострел вбок
Total votes 1: ↑1 and ↓0 +1
у игрока есть ограниченная возможность «пробивать стены»
This comment wasn’t rated yet 0
В статье есть упоминание, что у игрока есть ограниченная возможность пробивать стены, поэтому редкие несвязности допустимы.
This comment wasn’t rated yet 0
Таблица может быть всего лишь набором случайных чисел, табличным RND-генератором. При этом действительно, между байтами не будет никакой связи, так как её и не должно быть.Табличными RND-генераторами любили пользоваться многие, например Кармак в Doom и Wolfenstein использует табличку из 256 байт.

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

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

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

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

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

PS:
Total votes 4: ↑4 and ↓0 +4

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

Основную часть написал какой-то уволившийся торчок. Я связался с ним, чтобы выяснить, как его алгоритм работал. Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.
This comment wasn’t rated yet 0
На самом деле эта цитата не показывает ничего кроме низкой квалификации рассказчика (и его пренебрежения к его бывшему коллеге).
Во первых ассемблер такой же язык как и все другие и по тексту совершенно понятно что программа делает, это же не какой-то зашифрованный нечитаемый шум, тем более у него явно были исходники с худо-бедно проименованными функциями и переменными (а при желании разбирают и дизассемблированные программы, с автоматически сгенерированными именами функций и переменных вида XD04AF. Собственно говоря все кряки и пиратские генераторы серийников именно так и появляются, дизассемблированием кода и выяснением алгоритма)
Total votes 2: ↑1 and ↓1 0
Между «понять, что код делает» и «понять, как это приводит к результату» может быть довольно широкая пропасть.
Характерный пример — быстрый обратный квадратный корень: функция занимает всего с десяток ассемблерных команд, но объяснению того, как она работает, посвящены многие десятки статей.
Total votes 1: ↑1 and ↓0 +1

И чтобы понять надо все эти десятки статей прочесть? Или одной все же хватит?

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

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

This comment wasn’t rated yet 0
В 1983 Atari вывалила на свалку 47 тонн картриджей для Atari 2600 — не меньше десятка полных грузовиков! Раздавленные асфальтовым катком и залитые сверху бетоном, эти картриджи лежали тридцать лет
Нормально ребята перестраховываются
Total votes 1: ↑1 and ↓0 +1
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr