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

[ Версия для печати ]
Добавить в Facebook Добавить в Twitter Добавить в Вконтакте Добавить в Одноклассники
  [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]
Ubix
9.07.2020 - 16:39
Статус: Offline


Ярила

Регистрация: 24.04.14
Сообщений: 5861
20
via

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

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

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


Это сообщение отредактировал Ubix - 9.07.2020 - 16:39

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать
 
[^]
kistanov
9.07.2020 - 16:42
7
Статус: Offline


оптихуист

Регистрация: 11.09.08
Сообщений: 4851
я так деньги несколько раз прятал
 
[^]
scrudge
9.07.2020 - 16:43
58
Статус: Offline


Живая шляпа

Регистрация: 6.03.13
Сообщений: 4261
Раньше даже конченные нарики умели писать на ассемблере gigi.gif
 
[^]
HellMagic
9.07.2020 - 16:44
13
Статус: Offline


Хохмач

Регистрация: 13.09.15
Сообщений: 650
канеш! 128 байт, дизасемблер, сложно неебически )
 
[^]
rus2205
9.07.2020 - 16:48
4
Статус: Offline


Ярила

Регистрация: 1.02.14
Сообщений: 4994
вот здесь можно пощупать это
https://www.retrogames.cz/play_1044-Atari2600.php
 
[^]
kei2012
9.07.2020 - 16:50
13
Статус: Offline


Мирный атом

Регистрация: 28.06.16
Сообщений: 951
Это байка, на хабре есть разбор этого алгоритма и рассказ создателя. https://habr.com/ru/company/ruvds/blog/510266/
 
[^]
rus2205
9.07.2020 - 16:50
-2
Статус: Offline


Ярила

Регистрация: 1.02.14
Сообщений: 4994
Цитата (HellMagic @ 9.07.2020 - 16:44)
канеш! 128 байт, дизасемблер, сложно неебически )

что там дизасемблить, если он сразу на ассемблере хуярил?
Да и 128 байт - это используемое ОЗУ, сам код мог быть во много раз больше
 
[^]
scrudge
9.07.2020 - 16:59
1
Статус: Offline


Живая шляпа

Регистрация: 6.03.13
Сообщений: 4261
const canvas = document.getElementsByTagName('canvas')[0];
const context = canvas.getContext('2d');
context.fillStyle = 'black';
context.fillRect(0, 0, 320, 178);

const width = 18;

function prrow(seed, frame, nextgen) {
if (frame)
setTimeout(prrow, 40, seed, frame-1, nextgen);
else
setTimeout(nextgen, 40);
context.drawImage(canvas, 0, -1);
context.fillStyle = 'rgb(190,173,81)';
context.fillRect(0, 177, 320, 1);
context.fillStyle = 'black';
for (let i=1; i<=width; i++) {
if (seed & 1)
context.fillRect(16*i, 177, 16, 1);
seed >>= 1;
}
}

// initialize

let sets = [];
let cells = [];
for (let col=0; col < width; col++) {
sets[col+1] = 1 << col;
cells[col] = col + 1;
}

let verticals = 1 << (Math.random() * width);
prrow(verticals, 16, rowgen1);

function rowgen1() {
function merge(a, b) {
let id_a = cells[a];
let id_b = cells[b];
if (id_a == id_b)
return;

sets[id_a] |= sets[id_b];
for (let col=0; col < width; col++) {
if (sets[id_b] & 1)
cells[col] = id_a;
sets[id_b] >>= 1;
}
}

for (let col = 0; col < width-2; col++) {
if ((cells[col] != cells[col+2]) && (Math.random() < 0.5) && !(verticals & (1<<(col+3)))) {
merge(col, col+1);
merge(col+1, col+2);
} else if ([(verticals & (1<<col)) && (verticals & (1<<(col+2))), !(verticals & (1<<(col+1)))][+(cells[col] != cells[col+2])]) {
col++;
let id = cells[col];
cells[col] = 0;
sets[id] ^= 1 << col;
}
}
for (let col = 0; col < width-1; col++)
if (cells[col] && cells[col+1] && (cells[col] != cells[col+1]))
merge(col, col+1);

let seed = 0;
for (let id = 1; id <= width; id++)
seed |= sets[id];

prrow(seed, 16, rowgen2);
}

function rowgen2() {
verticals = 0;
for (let id in sets) {
let set = sets[id];
if (!set)
continue;

let mask;
do { mask = Math.random() * (1 << width); }
while (!(set & mask));
set &= mask;
verticals |= set;
sets[id] = set;
}
for (let col = 0; col < width; col++) {
if (!(verticals & (1<<col))) {
let id = sets.indexOf(0);
sets[id] = 1 << col;
cells[col] = id;
}
}
prrow(verticals, 16, rowgen1);
}
 
[^]
Strangerr
9.07.2020 - 17:08
0
Статус: Offline


Tanstaafl

Регистрация: 26.09.13
Сообщений: 2244
Цитата (rus2205 @ 9.07.2020 - 16:50)
Цитата (HellMagic @ 9.07.2020 - 16:44)
канеш! 128 байт, дизасемблер, сложно неебически )

что там дизасемблить, если он сразу на ассемблере хуярил?
Да и 128 байт - это используемое ОЗУ, сам код мог быть во много раз больше

ПЗУ - до 4к единовременно. Используя страницы - максимум 32к. Это совсем немного для дизассемблирования кода 6502 процессора.
 
[^]
Батарейкин
9.07.2020 - 17:21
1
Статус: Offline


Ярила

Регистрация: 26.06.12
Сообщений: 3593
Цитата (scrudge @ 9.07.2020 - 19:59)
const canvas = document.getElementsByTagName('canvas')[0];
const context = canvas.getContext('2d');
context.fillStyle = 'black';
context.fillRect(0, 0, 320, 178);

const width = 18;

function prrow(seed, frame, nextgen) {
if (frame)
setTimeout(prrow, 40, seed, frame-1, nextgen);
else
setTimeout(nextgen, 40);
context.drawImage(canvas, 0, -1);
context.fillStyle = 'rgb(190,173,81)';
context.fillRect(0, 177, 320, 1);
context.fillStyle = 'black';
for (let i=1; i<=width; i++) {
if (seed & 1)
context.fillRect(16*i, 177, 16, 1);
seed >>= 1;
}
}

// initialize

let sets = [];
let cells = [];
for (let col=0; col < width; col++) {
sets[col+1] = 1 << col;
cells[col] = col + 1;
}

let verticals = 1 << (Math.random() * width);
prrow(verticals, 16, rowgen1);

function rowgen1() {
function merge(a, b) {
let id_a = cells[a];
let id_b = cells[b];
if (id_a == id_b)
return;

sets[id_a] |= sets[id_b];
for (let col=0; col < width; col++) {
if (sets[id_b] & 1)
cells[col] = id_a;
sets[id_b] >>= 1;
}
}

for (let col = 0; col < width-2; col++) {
if ((cells[col] != cells[col+2]) && (Math.random() < 0.5) && !(verticals & (1<<(col+3)))) {
merge(col, col+1);
merge(col+1, col+2);
} else if ([(verticals & (1<<col)) && (verticals & (1<<(col+2))), !(verticals & (1<<(col+1)))][+(cells[col] != cells[col+2])]) {
col++;
let id = cells[col];
cells[col] = 0;
sets[id] ^= 1 << col;
}
}
for (let col = 0; col < width-1; col++)
if (cells[col] && cells[col+1] && (cells[col] != cells[col+1]))
merge(col, col+1);

let seed = 0;
for (let id = 1; id <= width; id++)
seed |= sets[id];

prrow(seed, 16, rowgen2);
}

function rowgen2() {
verticals = 0;
for (let id in sets) {
let set = sets[id];
if (!set)
continue;

let mask;
do { mask = Math.random() * (1 << width); }
while (!(set & mask));
set &= mask;
verticals |= set;
sets[id] = set;
}
for (let col = 0; col < width; col++) {
if (!(verticals & (1<<col))) {
let id = sets.indexOf(0);
sets[id] = 1 << col;
cells[col] = id;
}
}
prrow(verticals, 16, rowgen1);
}

По моему это какие то СИ но никак не ассемблер biggrin.gif
 
[^]
ekimosss
9.07.2020 - 17:31
1
Статус: Offline


электроанархист

Регистрация: 26.05.11
Сообщений: 4240
Цитата
По моему это какие то СИ но никак не ассемблер

скорее какая то ява)
 
[^]
sslevelss
9.07.2020 - 17:46
0
Статус: Offline


Шутник

Регистрация: 5.07.20
Сообщений: 43
Цитата (kistanov @ 09.07.2020 - 16:42)
я так деньги несколько раз прятал

А я так находила, чуйка возрожалась.....

Размещено через приложение ЯПлакалъ
 
[^]
pruginkad
9.07.2020 - 17:51
0
Статус: Offline


Хохмач

Регистрация: 5.09.18
Сообщений: 719
угу. байки о программистах.
 
[^]
NetFix
9.07.2020 - 17:57
4
Статус: Offline


Ярила

Регистрация: 14.08.13
Сообщений: 1094
Цитата (Батарейкин @ 9.07.2020 - 17:21)
Цитата (scrudge @ 9.07.2020 - 19:59)
const canvas = document.getElementsByTagName('canvas')[0];
const context = canvas.getContext('2d');
context.fillStyle = 'black';
context.fillRect(0, 0, 320, 178);

const width = 18;

function prrow(seed, frame, nextgen) {
    if (frame)
        setTimeout(prrow, 40, seed, frame-1, nextgen);
    else
        setTimeout(nextgen, 40);
    context.drawImage(canvas, 0, -1);
    context.fillStyle = 'rgb(190,173,81)';
    context.fillRect(0, 177, 320, 1);
    context.fillStyle = 'black';
    for (let i=1; i<=width; i++) {
      if (seed & 1)
        context.fillRect(16*i, 177, 16, 1);
      seed >>= 1;
    }
}

// initialize

let sets = [];
let cells = [];
for (let col=0; col < width; col++) {
    sets[col+1] = 1 << col;
    cells[col] = col + 1;
}

let verticals = 1 << (Math.random() * width);
prrow(verticals, 16, rowgen1);

function rowgen1() {
    function merge(a, b) {
        let id_a = cells[a];
        let id_b = cells[b];
        if (id_a == id_b)
            return;

        sets[id_a] |= sets[id_b];
        for (let col=0; col < width; col++) {
            if (sets[id_b] & 1)
                cells[col] = id_a;
            sets[id_b] >>= 1;
        }
    }

    for (let col = 0; col < width-2; col++) {
        if ((cells[col] != cells[col+2]) && (Math.random() < 0.5) && !(verticals & (1<<(col+3)))) {
            merge(col, col+1);
            merge(col+1, col+2);
        } else if ([(verticals & (1<<col)) && (verticals & (1<<(col+2))), !(verticals & (1<<(col+1)))][+(cells[col] != cells[col+2])]) {
            col++;
            let id = cells[col];
            cells[col] = 0;
            sets[id] ^= 1 << col;
        }
    }
    for (let col = 0; col < width-1; col++)
        if (cells[col] && cells[col+1] && (cells[col] != cells[col+1]))
            merge(col, col+1);

    let seed = 0;
    for (let id = 1; id <= width; id++)
        seed |= sets[id];

    prrow(seed, 16, rowgen2);
}

function rowgen2() {
    verticals = 0;
    for (let id in sets) {
        let set = sets[id];
        if (!set)
            continue;

        let mask;
        do { mask = Math.random() * (1 << width); }
        while (!(set & mask));
        set &= mask;
        verticals |= set;
        sets[id] = set;
    }
    for (let col = 0; col < width; col++) {
        if (!(verticals & (1<<col))) {
            let id = sets.indexOf(0);
            sets[id] = 1 << col;
            cells[col] = id;
        }
    }
    prrow(verticals, 16, rowgen1);
}

По моему это какие то СИ но никак не ассемблер biggrin.gif

Это JS.
 
[^]
wanu
9.07.2020 - 19:15
0
Статус: Offline


Балагур

Регистрация: 22.02.10
Сообщений: 884
бля, чуваки теорию клеточных автоматов не вкуривают?!!!
Life, машина Бэнкса.....
 
[^]
уставший
9.07.2020 - 19:19
0
Статус: Offline


Хохмач

Регистрация: 1.01.15
Сообщений: 679
Пацаны, я не понимаю нихера в этом, но можно я тут посижу. Дико интересно.
По сабжу. Ихмо такая же хрень типа римского бетона и прочей ебани. Которая людям в теме ясна как 2х2. А непосвященные, начинают надрачивать на тайны и мистик.
 
[^]
НечтоИзСети
9.07.2020 - 20:54
0
Статус: Offline


Хохмач

Регистрация: 29.11.14
Сообщений: 628
Цитата (Strangerr @ 9.07.2020 - 17:08)
Цитата (rus2205 @ 9.07.2020 - 16:50)
Цитата (HellMagic @ 9.07.2020 - 16:44)
канеш! 128 байт, дизасемблер, сложно неебически )

что там дизасемблить, если он сразу на ассемблере хуярил?
Да и 128 байт - это используемое ОЗУ, сам код мог быть во много раз больше

ПЗУ - до 4к единовременно. Используя страницы - максимум 32к. Это совсем немного для дизассемблирования кода 6502 процессора.

У Atari 2600 ЦП MOS 6507 - это урезанная версия 6502.
 
[^]
SSgood
9.07.2020 - 21:16
0
Статус: Offline


Приколист

Регистрация: 11.02.11
Сообщений: 362
Цитата (NetFix @ 9.07.2020 - 20:57)
Цитата (Батарейкин @ 9.07.2020 - 17:21)
Цитата (scrudge @ 9.07.2020 - 19:59)
const canvas = document.getElementsByTagName('canvas')[0];
const context = canvas.getContext('2d');
context.fillStyle = 'black';
context.fillRect(0, 0, 320, 178);

const width = 18;

function prrow(seed, frame, nextgen) {
    if (frame)
        setTimeout(prrow, 40, seed, frame-1, nextgen);
    else
        setTimeout(nextgen, 40);
    context.drawImage(canvas, 0, -1);
    context.fillStyle = 'rgb(190,173,81)';
    context.fillRect(0, 177, 320, 1);
    context.fillStyle = 'black';
    for (let i=1; i<=width; i++) {
      if (seed & 1)
        context.fillRect(16*i, 177, 16, 1);
      seed >>= 1;
    }
}

// initialize

let sets = [];
let cells = [];
for (let col=0; col < width; col++) {
    sets[col+1] = 1 << col;
    cells[col] = col + 1;
}

let verticals = 1 << (Math.random() * width);
prrow(verticals, 16, rowgen1);

function rowgen1() {
    function merge(a, b) {
        let id_a = cells[a];
        let id_b = cells[b];
        if (id_a == id_b)
            return;

        sets[id_a] |= sets[id_b];
        for (let col=0; col < width; col++) {
            if (sets[id_b] & 1)
                cells[col] = id_a;
            sets[id_b] >>= 1;
        }
    }

    for (let col = 0; col < width-2; col++) {
        if ((cells[col] != cells[col+2]) && (Math.random() < 0.5) && !(verticals & (1<<(col+3)))) {
            merge(col, col+1);
            merge(col+1, col+2);
        } else if ([(verticals & (1<<col)) && (verticals & (1<<(col+2))), !(verticals & (1<<(col+1)))][+(cells[col] != cells[col+2])]) {
            col++;
            let id = cells[col];
            cells[col] = 0;
            sets[id] ^= 1 << col;
        }
    }
    for (let col = 0; col < width-1; col++)
        if (cells[col] && cells[col+1] && (cells[col] != cells[col+1]))
            merge(col, col+1);

    let seed = 0;
    for (let id = 1; id <= width; id++)
        seed |= sets[id];

    prrow(seed, 16, rowgen2);
}

function rowgen2() {
    verticals = 0;
    for (let id in sets) {
        let set = sets[id];
        if (!set)
            continue;

        let mask;
        do { mask = Math.random() * (1 << width); }
        while (!(set & mask));
        set &= mask;
        verticals |= set;
        sets[id] = set;
    }
    for (let col = 0; col < width; col++) {
        if (!(verticals & (1<<col))) {
            let id = sets.indexOf(0);
            sets[id] = 1 << col;
            cells[col] = id;
        }
    }
    prrow(verticals, 16, rowgen1);
}

По моему это какие то СИ но никак не ассемблер biggrin.gif

Это JS.

бля, я вижу бабу в красном платье!!! gigi.gif
 
[^]
Strangerr
9.07.2020 - 21:20
0
Статус: Offline


Tanstaafl

Регистрация: 26.09.13
Сообщений: 2244
НечтоИзСети
Цитата
У Atari 2600 ЦП MOS 6507 - это урезанная версия 6502.

Урезанная аппаратно - меньше адресных линий. С программной точки зрения - а тут именно код обсуждали - они идентичны. как i8086 и i8088.
 
[^]
Cпец
9.07.2020 - 23:19
0
Статус: Offline


Ярила

Регистрация: 2.02.12
Сообщений: 2763
Цитата (ekimosss @ 09.07.2020 - 17:31)
скорее какая то ява)

Скорее ява скрипт )

Размещено через приложение ЯПлакалъ
 
[^]
gskm
10.07.2020 - 04:02
0
Статус: Online


Ярила

Регистрация: 3.01.15
Сообщений: 2972
Цитата (scrudge @ 9.07.2020 - 01:59)
const canvas = document.getElementsByTagName('canvas')[0];
const context = canvas.getContext('2d');
context.fillStyle = 'black';
context.fillRect(0, 0, 320, 178);

...

prrow(verticals, 16, rowgen1);
}

И как читать эту портянку, ни отступов, ни-хе-ра, и правда торчок писал, еще и ассемблер с явойскрипт перепутал
 
[^]
и7ветер
10.07.2020 - 09:18
0
Статус: Offline


Ярила

Регистрация: 22.11.13
Сообщений: 3545
Да, очень сложные вещи можно делать очень просто, с минимальной затратой ресурсов. Но тогда, во первых, все должны писать талантливые люди, а с ними сложно иметь дело. А во вторых - как тогда втюхивать лохам вычислительные мощности, которые нахуй никому не сдались?
 
[^]
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста, или зарегистрируйтесь, если не зарегистрированы.
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) Просмотры темы: 3147
0 Пользователей:
[ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]


 
 



Активные темы








Наверх