Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 52
Изначально долго раскочегаривается под Chrome — 1 fps
Страница не найдена
О-о-о, у-у-у. а-а-а! Давно пора. Я более года назад делал реализацию, получалось 4-5 мс на ход в Fx 3.6 (200 в секунду), если без графики (при поле 180х150), с графикой меньше. Но с тех пор так и не брался за доработки и оптимизации, тема исчерпала себя.
(Javascript и canvas в игре «Жизнь» Джона Конвея)
(Javascript и canvas в игре «Жизнь» Джона Конвея)
Да, глядя на те результаты, прогресс производительности JS в Firefox-е впечатляет :-)
Тут ещё от процессора зависит (у меня был e2180), а графика — от видеокарты.
Вот страница, готовая для тестов (с графикой): spmbt.kodingen.com/lifeConway.htm.
Сейчас проверил на Хроме18 то же поле, на тексте — 4.5 секунды на 100 ходов (тогда в Хроме 8 было столько же. Firefox 12 — 10 секунд (а было 15). Зато канвас-режим (с 4 пикселями квадратики) у него сильно улучшился — было 12, стало 5.5 с. Проверялось на АМД-ноутбуке 1.8ГГц с дискретной штатной видеокартой. Это — тесты с отрисовкой графики, а графика отъедала раза в 2-3 большее время после всех оптимизаций, чем цикл на массивах без графики.
В общем, согласен, что массивы по определению должны считаться неэффективно, и есть лучшие методы, но оптимизировать энтузиазма не было. Ядро цикла вычислений можно с удобством увидеть на codepaste.ru/5091/, там прокомментировано.
Вот страница, готовая для тестов (с графикой): spmbt.kodingen.com/lifeConway.htm.
Сейчас проверил на Хроме18 то же поле, на тексте — 4.5 секунды на 100 ходов (тогда в Хроме 8 было столько же. Firefox 12 — 10 секунд (а было 15). Зато канвас-режим (с 4 пикселями квадратики) у него сильно улучшился — было 12, стало 5.5 с. Проверялось на АМД-ноутбуке 1.8ГГц с дискретной штатной видеокартой. Это — тесты с отрисовкой графики, а графика отъедала раза в 2-3 большее время после всех оптимизаций, чем цикл на массивах без графики.
В общем, согласен, что массивы по определению должны считаться неэффективно, и есть лучшие методы, но оптимизировать энтузиазма не было. Ядро цикла вычислений можно с удобством увидеть на codepaste.ru/5091/, там прокомментировано.
Отличная идея! Может кто-нибудь даст ссылок на подобные(анимация, околоайтишная тематика) 404-странички?
Есть это например, habrahabr.ru/post/142038/
Но там без анимации в основном.
Но там без анимации в основном.
Сначала было 404, но потом началася война какая-то клеточная!
Такое впечатление, что вначале программа дико тормозит, поэтому вызывает желание посмотреть загрузку процессора. Может стоит быстрее увеличивать скорость?
А вообще, очень красивая реализация.
Такое впечатление, что вначале программа дико тормозит, поэтому вызывает желание посмотреть загрузку процессора. Может стоит быстрее увеличивать скорость?
А вообще, очень красивая реализация.
Автор: есть такая, довольно отличная идея. Посмотрел на законченный вариант «404» — там быстро всё рассыпается. Зато, известно, что вариант игры по правилам «DayNight» склонен держать границы гораздо лучше. Чтобы убедиться в этом, поиграйтесь с моим демо: spmbt.kodingen.com/lifeConway.htm. Для просмотра режима «DayNight» выполните такую инструкцию:
1) открыть или перезагрузить страницу;
2) выбрать радиокнопку «DayNight»;
3) поставить «размер» 4;
4) чекбокс «на canvas»;
4.1) чекбокс «rect» (будет быстрее);
5) нажать «Init Random»;
6) нажать кнопку с крестиком (запустится 100 ходов получившегося рандомного поля)
При таких настройках у меня 100 ходов пролетают за 7 секунд в Хроме (время отражается на странице), алгоритм выбора правил по матрице, несколько медленнее, чем чистый. В результате получается нечто подобное на 100-м ходу, каждый раз, естественно, разное:
Видно, что границы стабилизируются и далее плавают интересно и медленно (можно наблюдать, нажимая дальше на кнопку «Х»). Можно сделать клетки 2 на 2, написать цифры «404» с не очень ровными краями как инит-поле — будет, думаю, интересно.
Ещё для этой версии игры зашит интересный сценарий по нажатию «Init r» вместо «Init Random».
1) открыть или перезагрузить страницу;
2) выбрать радиокнопку «DayNight»;
3) поставить «размер» 4;
4) чекбокс «на canvas»;
4.1) чекбокс «rect» (будет быстрее);
5) нажать «Init Random»;
6) нажать кнопку с крестиком (запустится 100 ходов получившегося рандомного поля)
При таких настройках у меня 100 ходов пролетают за 7 секунд в Хроме (время отражается на странице), алгоритм выбора правил по матрице, несколько медленнее, чем чистый. В результате получается нечто подобное на 100-м ходу, каждый раз, естественно, разное:
Видно, что границы стабилизируются и далее плавают интересно и медленно (можно наблюдать, нажимая дальше на кнопку «Х»). Можно сделать клетки 2 на 2, написать цифры «404» с не очень ровными краями как инит-поле — будет, думаю, интересно.
Ещё для этой версии игры зашит интересный сценарий по нажатию «Init r» вместо «Init Random».
Когдато от нечего делать писал «супермегаоптимальную™ жизнь» на 286 компе, для медитативного наблюдения приходилось вставлять задержки. Позже когда я увидел «супермегаоптимальную™ жизнь» под линух, и сравнил со своей, моя оказалась быстрее, но мой интерес к этому давно угас а исходники канули в лету :)
«Жизнь» в свое время по моему почти каждый кто увлекался программированием делал.
Я вон тоже, когда еще только начинал интересоваться программированием, делал реализацию «жизни» на паскале, тоже под 286 компом :)
А недавно вообще сделал извращенную реализацию «жизни» на Java в L2, на неписях, служащих клетками мира игры :)
видео того как это выглядит
исходники этого безобразия на pastebin
Я вон тоже, когда еще только начинал интересоваться программированием, делал реализацию «жизни» на паскале, тоже под 286 компом :)
А недавно вообще сделал извращенную реализацию «жизни» на Java в L2, на неписях, служащих клетками мира игры :)
видео того как это выглядит
исходники этого безобразия на pastebin
Результаты опроса: Писали ли Вы реализацию игры «Жизнь»Конвея?
Вы не поняли :) тут именно была идея в оптимальности :) К примеру, я там такие алгоритмические улучшения придумал, что обращение к одной клетке, если мне не изменяет память, происходило раз в три хода. Вобщем это была не та «жизнь» которую «каждый пишет», ту «жизнь» я написал еще в школе на спеке :)
Uint16Array для хранения (быстрая структура) +
Web Worker для вычислений (другой поток и у воркера более низкое разрешение таймера) +
Рисовать на скрытом канвасе. Можно еще попробовать putImageData.
Web Worker для вычислений (другой поток и у воркера более низкое разрешение таймера) +
Рисовать на скрытом канвасе. Можно еще попробовать putImageData.
Рисовать на скрытом канвасе. Можно еще попробовать putImageData.
Оба пункта — антиоптимизации. Остальное имеет смысл, но не везде есть.
Что можешь сказать про оптимизацию очистки канваса? jsperf.com/canvasclear
Считаю, что надо стараться отказаться от идеи функции clearAll и очищать только участки, которые реально поменялись)
На практике изменение dom-параметра привязано к ситуации и вызывает reflow, что на тестовой вёрстке незаметно, а в боевом интерфейсе вызовет непонятные тормоза.
clear rect:
change width:
На практике изменение dom-параметра привязано к ситуации и вызывает reflow, что на тестовой вёрстке незаметно, а в боевом интерфейсе вызовет непонятные тормоза.
clear rect:
change width:
Держитесь за стулья, с Uint32Array — в хроме просадка по скорости в 4 раза.
В высшей мере странно, должно быть проблема JIT-компилятора.
jsperf.com/typed-array-comparison/5 показывает ожидаемые +20-+30% и в хроме и в FF у Uint32Array против Array.
jsperf.com/typed-array-comparison/5 показывает ожидаемые +20-+30% и в хроме и в FF у Uint32Array против Array.
если у вас в uint32 массиве хранятся числа вылазящие по значению за max_int, то V8 это не нравится на настоящий момент — деоптимизирует (http://code.google.com/p/v8/source/browse/trunk/src/ia32/lithium-codegen-ia32.cc#2524 ) и потом отключает оптимизацию тех функций, в которых вы так массив используете.
related issue: code.google.com/p/v8/issues/detail?id=2097
related issue: code.google.com/p/v8/issues/detail?id=2097
Круто! Перед сном заменил 404-ю страницу на новую с этим скриптом и пока разбирал, да пытался подогнать возникла мысль об острой нехватке этого в виде расширения для вордпресса)
А все заметили наверху глайдерную пушку, которое через какое-то количество ходов рушит в клочья один из обломков? И еще несколько глайдеров случайно образуются в процессе, если я не ошибаюсь, и улетают в бесконечность.
Потрясно.
Реализовывал игру «жизнь» на Ассемблере в 1998 году.
Реализовывал игру «жизнь» на Ассемблере в 1998 году.
Можете объяснить смысл двух циклов в исходном коде?
и
for(bit=0;bit<16;bit++)
{
sum = ((0164624 >>> (((v1>>>bit)&7)<<1))&3)+
((0164624 >>> (((v2>>>bit)&5)<<1))&3)+//&5 because we skip middle cell when calculating number of surrounding cells;
((0164624 >>> (((v3>>>bit)&7)<<1))&3);
new_state |= ((0340 >>> ((sum<<1) | ((v2>>>(bit+1))&1)))&1)<<bit;
}
и
for(bit=0;bit<16;bit++)
{
sum = ((0164624 >>> (((v1>>>bit)&7)<<1))&3)+
((0164624 >>> (((v2>>>bit)&5)<<1))&3)+//&5 because we skip middle cell when calculating number of surrounding cells;
((0164624 >>> (((v3>>>bit)&7)<<1))&3);
new_state |= ((0340 >>> ((sum<<1) | ((v2>>>(bit+1))&1)))&1)<<(bit+16);
}
Первый считает первые 16 бит результата, второй — вторые. Сделать в один цикл не выйдет, т.к. нужно 34 бита исходных данных (по одной клетке слева и справа), чтобы рассчитать новое состояние первой и последней клетки в текущем int32.
Видно что второй цикл пишет биты по позиции (bit+16). v1,v2 и v3 сдвигаются на 16 таким образом, чтобы в них было загружено по одному лишнему биту в начале и конце текущих 16 бит.
Видно что второй цикл пишет биты по позиции (bit+16). v1,v2 и v3 сдвигаются на 16 таким образом, чтобы в них было загружено по одному лишнему биту в начале и конце текущих 16 бит.
Не вполне понял зачем нужны два «лишних» бита и как состоится без знаковый сдвиг с приведенным вами в топике примером. Если не сложно, можете чуть разъяснить логику?
Нам нужно считать кол-во живых клеток «вокруг» — слева, справа, сверху и снизу.
Т.е. для первого бита из группы из 32-х бит — чтобы посчитать клетки слева — нужно иметь доступ к последнему биту предыдущей группы, а для последнего — к первому биту следующей группы.
Бесзнаковый сдвиг в коде в статье нигде не нужен, он нужен когда мы сдвигаем v1,v2 и v3 на 16 бит вправо для дозагрузки дополнительных данных (добавлю это в статье). Знаковый сдвиг вдвигал бы единицы для отрицательный чисел, и поскольку объединение старых и новых данных делается через or, все биты в v1,v2 и v3 постепенно стали бы 1.
Т.е. для первого бита из группы из 32-х бит — чтобы посчитать клетки слева — нужно иметь доступ к последнему биту предыдущей группы, а для последнего — к первому биту следующей группы.
Бесзнаковый сдвиг в коде в статье нигде не нужен, он нужен когда мы сдвигаем v1,v2 и v3 на 16 бит вправо для дозагрузки дополнительных данных (добавлю это в статье). Знаковый сдвиг вдвигал бы единицы для отрицательный чисел, и поскольку объединение старых и новых данных делается через or, все биты в v1,v2 и v3 постепенно стали бы 1.
Ждем реализацию в minecraft
А потом в minecraft, который в minecraft'e.
Не совсем Minecraft, но от того же вендора: www.0x10cforum.com/forum/m/4932880/viewthread/2723108-game-life
У меня все «рыбки» сдохли :(
Красиво, что планерное ружьё оказалось уничтожено взрывными волнами =)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пишем и оптимизируем Жизнь Конуэя на JS