OTCA Metapixel

[ermouth]

Нашлось внезапно. Клеточный автомат с правилами Жизни Конвея, который эмулирует сам себя в крупном масштабе.

То-есть это вот так:

Называется OTCA Metapixel

Comments

[morfizm.livejournal.com]

Вот получше вариант:

https://www.youtube.com/watch?v=xP5-iIeKXE8

[dennyrolling.livejournal.com]

что то он не сам себя эмулирует, а какую-то левую картинку из жизни. вот если бы сам себя... ;)

[ermouth.livejournal.com]

Это ~1.8e13 бит (2 терабайта) х 1.25e9 шагов всего-то.

Предположим мы это всё делаем на GPU с пропускной способностью памяти, скажем, терабит/с, и, допустим у нас её хватает (ну да, всего 2 Тб видеопамяти) и хватает шейдерных процессоров (примерно 10К), чтобы её нагрузить.

Получается чуть больше 600 лет на кадр. В принципе, это всё эффективно сравнительно паралеллится, так что вложив несколько миллионов бачей, можно довести срок до единиц суток, я думаю )

[morfizm.livejournal.com]

Тяжеловато, да. Поэтому Hashlife :)

[ermouth.livejournal.com]

И брать такую хэш-функцию, которая отображает квадрат 2048х2048 аккурат в 1 бит ) Профит!

[morfizm.livejournal.com]

lol :) Ход твоей мысли мне нравится.

На самом деле, хэшфункция в 1 бит может быть всё равно эффективнее, чем высчитывать педантично всё (но, конечно, надо больше).

С хэшированием тут идея такая: если взять какой-то произвольного размера кусок карты, скажем, 64x64 (ну или даже 2048x2048), и посмотреть, сколько у него может быть разных вариантов, то там обнаружится, что вариантов намного меньше, чем 64^2. Можно создать хэштаблицу по этим вариантам, а значения таблицы - массив 64x64 результатов, по размеру равный длине периода. Соответственно, берёшь кусок 64x64, look-up'ишь его в таблице, берёшь кол-во поколений по модулю размер массива (период) и look-up'ишь конечный переход.

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

[morfizm.livejournal.com]

Сам себя - это мой линк, см. коммент выше.

[dennyrolling.livejournal.com]

побуду децл занудой: там тоже только полоска с четырьмя космическими кораблями. но ход их мыслей мне нравится больше!

[morfizm.livejournal.com]

Ты зануда. Там в конце те же горизонтальные глайдеры, что и вначале ролика. Полоска это малозаметный overhead =)