Здравствуйте, меня зовут Дмитрий Карловский. Недавно я оказался при смерти и понял как сильно я люблю Жизнь. Это идеальная игра для социопатов, где вы выступаете в роли бога, своею дланью единоправно решающего кому жить, кому умереть, а кому фаллоформировать. Новая клетка появляется как результат соития трёх других однополых соседей и умирает будучи затоптанной толпой из более чем трёх, оставшись наедине с собой или в компании всего одного. Кто бы мог подумать, что столь простые законы породят настолько огромное разнообразие игрового опыта, что играть в Жизнь будут и спустя 50 лет после их формулировки.
Если вы ещё не работали со $mol, то перед чтением рекомендуется прочитать более дружелюбное к новичкам руководство "$mol_app_calc: вечеринка электронных таблиц". А если его уже осилили, то далее вы узнаете:
Как работать с бесконечным жизненным полем.
Как рисовать быструю векторную графику.
Как в $mol легко и просто соединить управление пальцем и рисование графики.
Векторная графика
$mol разрабатывался в расчёте на компактность, эффективность кода и простоту его использования. Это значит, что прикладному программисту достаточно лишь указать что куда рендерить не задумываясь об оптимизациях, а графические модули уже сами разберутся как это лучше сделать. Коллекция модулей $mol_plot именно такая реализация. В простейшем случае, вы скармливаете ей вектор чисел и тип графика, а она сама располагает их как следует:
Сейчас поддерживаются следующие типы: линейный, столбчатый, точечный и заливочный. Плюс вертикальная и горизонтальная линейки. Кроме того, если специальный тип графика позволяющий объединять несколько других типов в один, что позволяет конструировать новые типы графиков, комбинируя существующие. Например, мы можем сконструировать "Верёвочный тип графика с заполнением":
$my_plot_rope $mol_plot_group
graphs /
<= Line $mol_plot_line
<= Dot $mol_plot_dot
<= Fill $mol_plot_fill
Разумеется, мы можем нарисовать и несколько графиков по разным векторам, при этом $mol_plot_pane умеет сам давать каждому графику уникальный цвет начиная с базового оттенка:
<= Plot $mol_plot_pane
hue_base 206
graphs /
<= Fact $mol_plot_bar
series <= fact /
1000
2000
4000
9000
<= Plan $mol_plot_line
series <= plan /
1000
3000
5000
7000
type \dashed
Но и это ещё не всё, типы графиков могут возвращать семплы для легенды. При этом семплы, как и собственно графики, умеют комбинироваться. Так что у вас никогда не возникнет жуков, когда на графике отображается один тип линии, а в легенде - другой. Вы только взгляните на автоматически генерируемую из графиков легенду:
Скорость графики
Реализация графиков мало того, что очень компактная, так ещё и весьма эффективная:
Бенчмарк верёвочных диаграмм
Бенчмарк столбчатых диаграмм
Достигается такая эффективность за счёт многих факторов:
Реализация банально проще и требует меньше накладных расходов.
Используется Реактивное Программирование для эффективного обновления состояний. Это настолько эффективно, что вы можете легко менять любой аспект рендеринга в реальном времени почти не нагружая систему. Например: графическая дискотека.
Точки, располагающиеся визуально неотличимо близко друг ко другу схлопываются в одну. Как бы много данных вы ни закинули в рендеринг - он не не положит систему многократным ререндерингом одного и того же пикселя.
Точки, выпавшие за пределы области просмотра исключаются из рендеринга. Актуально при панорамировании огромных объёмов данных. Чем меньше мы рендерим, тем быстрее мы рендерим.
Графики рисуются минимумом SVG элементов.
По последнему пункту есть даже отдельный бенчмарк, показывающий, что правильно реализованный SVG график, с рендерингом через один path элемент вместо кучи line элементов, по скорости не сильно уступает ручному рендерингу по холсту:
Графика Жизни
Рисовать нам надо будет точки, расположенные не по порядку слева направо, а в произвольных местах. Для этого мы зададим не series, а points_raw, который возвращает не вектор чисел, а вектор из координат:
Обратите внимание, что мы убрали отступы графика от края области рендеринга (gap) и схлопывание близко расположенных точек (threshold) так как они нам не нужны.
У $mol_plot_pane есть свойства shift и scale позволяющие централизованно изменять размер и положение графиков. Давайте введём свойство zoom, которое будет задавать коэффициент масштабирования, и pan которое будет алиасом для shift. И то и другое у нас будет изменяемым.
Обратите внимание, что мы указали диаметр точек равный степени приближения. А по умолчанию степень приближения равна 16. Значит всё поле изначально у нас будет представлять 16-пиксельную сетку в ячейках которых будут находиться 16-пиксельные кружки.
Зум и панорамирование
В $mol есть специальные компоненты, которые предназначены не для самостоятельного рендеринга, а для добавления функциональности к другим. Один из таких плагинов - $mol_touch, перехватывающий события пальцевого и мышиного ввода и реализующего различные жесты. Нам нужно лишь менять размер клеток и перемещать поле, поэтому мы добавляем плагин и провязываем объявленные ранее свойства:
Вот и всё. Правда. Двустороннее связывание - просто чудесная вещь. Вы пишите минимум кода, но при этом всё под вашим полным контролем. Когда любой вложенный компонент запрашивает значение свойства или пытается в него что-то записать - вызывается ваша функция. Например, давайте зададим минимальный уровень приближения равный единице:
@ $mol_mem
zoom( next = super.zoom() ) {
return Math.max( 1 , next )
}
А в качестве смещения по умолчанию зададим половину размера области рендеринга, чтобы клетка с координатами [0,0] изначально располагалась в центре:
@ $mol_mem
pan( next? : number[] ) {
return next || this.size_real().map( v => v / 2 )
}
Правила игры
Можно было бы ограничиться небольшим полем в размер экрана, но мы не ищем лёгких путей, поэтому поле наше будет бесконечным. Ну как бесконечным.. тороидальным, но очень большим: 64K * 64K = 4Г клеток.
Рассчитывать состояние каждой клетки такого огромного поля - слишком долгая операция. Заметим, что число живых клеток несопоставимо меньше, чем мёртвых. А это значит, что на каждом шаге имеет смысл обновлять состояние лишь живых клеток и их ближайших окрестностей.
Для этого нам понадобится структура под названием множество (Set) для хранения координат живых клеток. Да вот беда: координаты клетки - это два числа, а ключом множества может быть лишь одно примитивное значение (или ссылка на объект, но это фактически тоже примитив).
Мы могли бы сериализовать числа в строки и сконкатенировать их, получив ключ. Но работа со строками относительно не быстрая операция. Самое эффективное - соединить 2 числа в одно, используя битовые операции. Битовые операции в JS всегда приводят числа к 32-битному представлению. А значит на каждую координату у нас будет целых 16 бит - отсюда и ограничение на размер поля в 4 гигаклетки.
Соединить числа весьма просто - обрезаем до 16 бит и объединяем с разными смещениями:
function key( a : number , b : number ) {
return a << 16 | b & 0xFFFF
}
Также нам потребуется их и разъединять, чтобы итерируясь по множеству получать координаты. Старшее число получить не сложно, просто сдвинув его с заполнением старшим битом:
function x_of( key : number ) {
return key >> 16
}
А вот чтобы получить младшее число недостаточно просто обрезать старшие биты, ведь тогда сломаются отрицательные значения, старшие биты которых должны быть единицами, а не нулями. Нужно сдвинуть младшие биты на место старших, а затем задача сводится к предыдущей:
function y_of( key : number ) {
return key << 16 >> 16
}
Теперь мы можем создавать множества и добавлять/удалять из них координаты:
const state = new Set<[ number , number ]>()
state.add( key( 1, 2 ) )
state.add( key( 3, 4 ) )
state.delete( key( 1, 4 ) )
for( let key of state ) {
console.log( x_of( key ) , y_of( key ) )
}
Заведём реактивное свойство state, которое будет хранить у нас состояние вселенной на текущий момент и пусть оно формирует множество живых клеток на основе сериализованного представления snapshot, через которое можно будет устанавливать начальное состояние извне:
@ $mol_mem
state( next? : Set<number> ) {
const snapshot = this.snapshot()
if( next ) return next
return new Set( snapshot.split( '~' ).map( v => parseInt( v , 16 ) ) )
}
Обратите внимание, что мы сначала читаем текущий снепшот, а только потом позволяем его переопределить. Это надо, чтобы даже если мы изменили состояние, оно всё равно синхронизировалось бы со снепшотом.
Кроме того, предоставим возможность реактивно же получить из компонента снепшот текущего изменённого состояния:
Не забудем объявить коммуникационные свойства во view.tree:
snapshot \
snapshot_current \
-
speed 0
population 0
Заодно мы объявили свойство speed задающее частоту обновления мира и population позволяющее получить число живых клеток на данный момент. Последний реализовать несложно:
Наконец, самое интересное - обновление состояния с заданной скоростью. Для этого мы заведём свойство future, которое будет читать состояние, на его основе вычислять новое и записывать обратно:
@ $mol_mem
future( next? : Set<number> ) {
let prev = this.state()
const state = new Set<number>()
// заполнили state на основе prev
return this.state( state )
}
Такое свойство вычислится один раз и всё, а нам надо периодически, поэтому добавляем ему зависимость от текущего времени с нужной частотой:
@ $mol_mem
future( next? : Set<number> ) {
let prev = this.state()
if( !this.speed() ) return prev
this.$.$mol_state_time.now( 1000 / this.speed() )
const state = new Set<number>()
// заполнили state на основе prev
return this.state( state )
}
Теперь оно будет инвалидироваться каждые N миллисекунд (от 16 до 1000), что приведёт к исполнению метода и обновлению состояния мира. Кстати, вот и код этого обновления:
const state = new Set<number>()
const skip = new Set<number>()
for( let alive of prev ) {
const ax = x_of( alive )
const ay = y_of( alive )
for( let ny = ay - 1 ; ny <= ay + 1 ; ++ny ) for( let nx = ax - 1 ; nx <= ax + 1 ; ++nx ) {
const nkey = key( nx , ny )
if( skip.has( nkey ) ) continue
skip.add( nkey )
let sum = 0
for( let y = -1 ; y <= 1 ; ++y ) for( let x = -1 ; x <= 1 ; ++x ) {
if( !x && !y ) continue
if( prev.has( key( nx + x , ny + y ) ) ) ++sum
}
if( sum != 3 && ( !prev.has( nkey ) || sum !== 2 ) ) continue
state.add( nkey )
}
}
Тут уже применены основные оптимизации. Возможно именно вы сможете оптимизировать его ещё сильнее. Дерзайте!
Наконец, сформируем список точек для рендеринга:
points() {
const points = [] as number[][]
for( let key of this.future().keys() ) {
points.push([ x_of( key ) , y_of( key ) ])
}
return points
}
Божественная длань
Чтобы игрок был не просто немым свидетелем, а властителем судеб, подпишемся на несколько событий указателя:
Не смотря на название, работают они как с мышь, так и с пальцем. К сожалению событие click тут не подойдёт, ибо оно срабатывает даже при панорамировании, что нам совершенно не надо. Поэтому при активации указателя мы будем запоминать текущее его положение:
Игровое поле $mol_app_life_map готово, можно приступать к созданию приложения по его управлению. Представлять из себя оно у нас будет обычную страницу $mol_page, состоящую из шапки и игрового поля:
$mol_app_life $mol_page
title @ \Life of {population} cells
sub /
<= Head -
<= Map $mol_app_life_map
speed <= speed -
snapshot <= snapshot \
snapshot_current => snapshot_current
population => population
Тут мы устанавливаем полю скорость и базовый снепшот, а вытягиваем число живых клеток и снепшот текущего состояния.
В заголовке заменяем плейсхолдер на конкретное число живых клеток:
https://page.hyoo.ru/#!=va88oc_2tpaa4
Здравствуйте, меня зовут Дмитрий Карловский. Недавно я оказался при смерти и понял как сильно я люблю Жизнь. Это идеальная игра для социопатов, где вы выступаете в роли бога, своею дланью единоправно решающего кому жить, кому умереть, а кому фаллоформировать. Новая клетка появляется как результат соития трёх других однополых соседей и умирает будучи затоптанной толпой из более чем трёх, оставшись наедине с собой или в компании всего одного. Кто бы мог подумать, что столь простые законы породят настолько огромное разнообразие игрового опыта, что играть в Жизнь будут и спустя 50 лет после их формулировки.
Если вы ещё не работали со $mol, то перед чтением рекомендуется прочитать более дружелюбное к новичкам руководство "$mol_app_calc: вечеринка электронных таблиц". А если его уже осилили, то далее вы узнаете:
Векторная графика
$mol разрабатывался в расчёте на компактность, эффективность кода и простоту его использования. Это значит, что прикладному программисту достаточно лишь указать что куда рендерить не задумываясь об оптимизациях, а графические модули уже сами разберутся как это лучше сделать. Коллекция модулей $mol_plot именно такая реализация. В простейшем случае, вы скармливаете ей вектор чисел и тип графика, а она сама располагает их как следует:
Сейчас поддерживаются следующие типы: линейный, столбчатый, точечный и заливочный. Плюс вертикальная и горизонтальная линейки. Кроме того, если специальный тип графика позволяющий объединять несколько других типов в один, что позволяет конструировать новые типы графиков, комбинируя существующие. Например, мы можем сконструировать "Верёвочный тип графика с заполнением":
Разумеется, мы можем нарисовать и несколько графиков по разным векторам, при этом $mol_plot_pane умеет сам давать каждому графику уникальный цвет начиная с базового оттенка:
Но и это ещё не всё, типы графиков могут возвращать семплы для легенды. При этом семплы, как и собственно графики, умеют комбинироваться. Так что у вас никогда не возникнет жуков, когда на графике отображается один тип линии, а в легенде - другой. Вы только взгляните на автоматически генерируемую из графиков легенду:
Скорость графики
Реализация графиков мало того, что очень компактная, так ещё и весьма эффективная:
Бенчмарк верёвочных диаграмм![Результаты бенчмарка верёвочных диаграмм](https://habrastorage.org/webt/ws/q0/xk/wsq0xkpt0rhuypvw3k8c9nqd8p8.png)
Бенчмарк столбчатых диаграмм![Результаты бенчмарка столбчатых диаграмм](https://habrastorage.org/webt/k0/-k/y8/k0-ky8qthu2sr7q3gydodoboc-m.png)
Достигается такая эффективность за счёт многих факторов:
По последнему пункту есть даже отдельный бенчмарк, показывающий, что правильно реализованный SVG график, с рендерингом через один path элемент вместо кучи line элементов, по скорости не сильно уступает ручному рендерингу по холсту:
Графика Жизни
Рисовать нам надо будет точки, расположенные не по порядку слева направо, а в произвольных местах. Для этого мы зададим не
series
, аpoints_raw
, который возвращает не вектор чисел, а вектор из координат:Обратите внимание, что мы убрали отступы графика от края области рендеринга (
gap
) и схлопывание близко расположенных точек (threshold
) так как они нам не нужны.У
$mol_plot_pane
есть свойстваshift
иscale
позволяющие централизованно изменять размер и положение графиков. Давайте введём свойствоzoom
, которое будет задавать коэффициент масштабирования, иpan
которое будет алиасом дляshift
. И то и другое у нас будет изменяемым.Обратите внимание, что мы указали диаметр точек равный степени приближения. А по умолчанию степень приближения равна 16. Значит всё поле изначально у нас будет представлять 16-пиксельную сетку в ячейках которых будут находиться 16-пиксельные кружки.
Зум и панорамирование
В $mol есть специальные компоненты, которые предназначены не для самостоятельного рендеринга, а для добавления функциональности к другим. Один из таких плагинов - $mol_touch, перехватывающий события пальцевого и мышиного ввода и реализующего различные жесты. Нам нужно лишь менять размер клеток и перемещать поле, поэтому мы добавляем плагин и провязываем объявленные ранее свойства:
Вот и всё. Правда. Двустороннее связывание - просто чудесная вещь. Вы пишите минимум кода, но при этом всё под вашим полным контролем. Когда любой вложенный компонент запрашивает значение свойства или пытается в него что-то записать - вызывается ваша функция. Например, давайте зададим минимальный уровень приближения равный единице:
А в качестве смещения по умолчанию зададим половину размера области рендеринга, чтобы клетка с координатами
[0,0]
изначально располагалась в центре:Правила игры
Можно было бы ограничиться небольшим полем в размер экрана, но мы не ищем лёгких путей, поэтому поле наше будет бесконечным. Ну как бесконечным.. тороидальным, но очень большим: 64K * 64K = 4Г клеток.
Рассчитывать состояние каждой клетки такого огромного поля - слишком долгая операция. Заметим, что число живых клеток несопоставимо меньше, чем мёртвых. А это значит, что на каждом шаге имеет смысл обновлять состояние лишь живых клеток и их ближайших окрестностей.
Для этого нам понадобится структура под названием множество (
Set
) для хранения координат живых клеток. Да вот беда: координаты клетки - это два числа, а ключом множества может быть лишь одно примитивное значение (или ссылка на объект, но это фактически тоже примитив).Мы могли бы сериализовать числа в строки и сконкатенировать их, получив ключ. Но работа со строками относительно не быстрая операция. Самое эффективное - соединить 2 числа в одно, используя битовые операции. Битовые операции в JS всегда приводят числа к 32-битному представлению. А значит на каждую координату у нас будет целых 16 бит - отсюда и ограничение на размер поля в 4 гигаклетки.
Соединить числа весьма просто - обрезаем до 16 бит и объединяем с разными смещениями:
Также нам потребуется их и разъединять, чтобы итерируясь по множеству получать координаты. Старшее число получить не сложно, просто сдвинув его с заполнением старшим битом:
А вот чтобы получить младшее число недостаточно просто обрезать старшие биты, ведь тогда сломаются отрицательные значения, старшие биты которых должны быть единицами, а не нулями. Нужно сдвинуть младшие биты на место старших, а затем задача сводится к предыдущей:
Теперь мы можем создавать множества и добавлять/удалять из них координаты:
Заведём реактивное свойство
state
, которое будет хранить у нас состояние вселенной на текущий момент и пусть оно формирует множество живых клеток на основе сериализованного представленияsnapshot
, через которое можно будет устанавливать начальное состояние извне:Обратите внимание, что мы сначала читаем текущий снепшот, а только потом позволяем его переопределить. Это надо, чтобы даже если мы изменили состояние, оно всё равно синхронизировалось бы со снепшотом.
Кроме того, предоставим возможность реактивно же получить из компонента снепшот текущего изменённого состояния:
Не забудем объявить коммуникационные свойства во view.tree:
Заодно мы объявили свойство
speed
задающее частоту обновления мира иpopulation
позволяющее получить число живых клеток на данный момент. Последний реализовать несложно:Наконец, самое интересное - обновление состояния с заданной скоростью. Для этого мы заведём свойство
future
, которое будет читать состояние, на его основе вычислять новое и записывать обратно:Такое свойство вычислится один раз и всё, а нам надо периодически, поэтому добавляем ему зависимость от текущего времени с нужной частотой:
Теперь оно будет инвалидироваться каждые N миллисекунд (от 16 до 1000), что приведёт к исполнению метода и обновлению состояния мира. Кстати, вот и код этого обновления:
Тут уже применены основные оптимизации. Возможно именно вы сможете оптимизировать его ещё сильнее. Дерзайте!
Наконец, сформируем список точек для рендеринга:
Божественная длань
Чтобы игрок был не просто немым свидетелем, а властителем судеб, подпишемся на несколько событий указателя:
Не смотря на название, работают они как с мышь, так и с пальцем. К сожалению событие
click
тут не подойдёт, ибо оно срабатывает даже при панорамировании, что нам совершенно не надо. Поэтому при активации указателя мы будем запоминать текущее его положение:А по деактивации, проверять смещение и, если оно не сильно изменилось, инициировать переключение жизни и смерти клетки, что попала под руку:
Интерфейс управления
Игровое поле
$mol_app_life_map
готово, можно приступать к созданию приложения по его управлению. Представлять из себя оно у нас будет обычную страницу $mol_page, состоящую из шапки и игрового поля:Тут мы устанавливаем полю скорость и базовый снепшот, а вытягиваем число живых клеток и снепшот текущего состояния.
В заголовке заменяем плейсхолдер на конкретное число живых клеток:
Базовый снепшот берём из ссылки:
Заодно формируем ссылку на текущее состояние мира, переход по которой будет добавлять текущий снепшот в историю браузера:
Выведем эту ссылку мы на тулбар в шапке вместе с переключателем скоростей:
Если ссылка ведёт на текущий снепшот, то засеряем её:
И последний штрих - добавляем локализацию:
Ещё немного мелких правок и приложение готово:
Интересные комбинации
Фабрика планеров![Фабрика планеров](https://habrastorage.org/webt/sk/rx/uw/skrxuwcvieumpssl0dqziypd5ak.png)
Асфальтоукладчик![Асфальтоукладчик на старте](https://habrastorage.org/webt/-g/5-/5n/-g5-5n1xjac-xvqtxzzqz-qc0i4.png)