Pull to refresh

$mol_app_life: симулятор бога своими руками

Reading time 9 min
Views 11K

Здравствуйте, меня зовут Дмитрий Карловский. Недавно я оказался при смерти и понял как сильно я люблю Жизнь. Это идеальная игра для социопатов, где вы выступаете в роли бога, своею дланью единоправно решающего кому жить, кому умереть, а кому фаллоформировать. Новая клетка появляется как результат соития трёх других однополых соседей и умирает будучи затоптанной толпой из более чем трёх, оставшись наедине с собой или в компании всего одного. Кто бы мог подумать, что столь простые законы породят настолько огромное разнообразие игрового опыта, что играть в Жизнь будут и спустя 50 лет после их формулировки.


Планер


Если вы ещё не работали со $mol, то перед чтением рекомендуется прочитать более дружелюбное к новичкам руководство "$mol_app_calc: вечеринка электронных таблиц". А если его уже осилили, то далее вы узнаете:


  1. Как работать с бесконечным жизненным полем.
  2. Как рисовать быструю векторную графику.
  3. Как в $mol легко и просто соединить управление пальцем и рисование графики.

Векторная графика


$mol разрабатывался в расчёте на компактность, эффективность кода и простоту его использования. Это значит, что прикладному программисту достаточно лишь указать что куда рендерить не задумываясь об оптимизациях, а графические модули уже сами разберутся как это лучше сделать. Коллекция модулей $mol_plot именно такая реализация. В простейшем случае, вы скармливаете ей вектор чисел и тип графика, а она сама располагает их как следует:


<= Plot $mol_plot_pane
    graphs /
        <= Trend $mol_plot_line
            series <= trend /
                1
                2
                5
                4

Линейный график


Сейчас поддерживаются следующие типы: линейный, столбчатый, точечный и заливочный. Плюс вертикальная и горизонтальная линейки. Кроме того, если специальный тип графика позволяющий объединять несколько других типов в один, что позволяет конструировать новые типы графиков, комбинируя существующие. Например, мы можем сконструировать "Верёвочный тип графика с заполнением":


$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

План-факт


Но и это ещё не всё, типы графиков могут возвращать семплы для легенды. При этом семплы, как и собственно графики, умеют комбинироваться. Так что у вас никогда не возникнет жуков, когда на графике отображается один тип линии, а в легенде — другой. Вы только взгляните на автоматически генерируемую из графиков легенду:


Диаграмма с графиками разных стилей


Скорость графики


Реализация графиков мало того, что очень компактная, так ещё и весьма эффективная:


Бенчмарк верёвочных диаграмм
Результаты бенчмарка верёвочных диаграмм


Бенчмарк столбчатых диаграмм
Результаты бенчмарка столбчатых диаграмм


Достигается такая эффективность за счёт многих факторов:


  1. Реализация банально проще и требует меньше накладных расходов.
  2. Используется Реактивное Программирование для эффективного обновления состояний. Это настолько эффективно, что вы можете легко менять любой аспект рендеринга в реальном времени почти не нагружая систему. Например: графическая дискотека.
  3. Точки, располагающиеся визуально неотличимо близко друг ко другу схлопываются в одну. Как бы много данных вы ни закинули в рендеринг — он не не положит систему многократным ререндерингом одного и того же пикселя.
  4. Точки, выпавшие за пределы области просмотра исключаются из рендеринга. Актуально при панорамировании огромных объёмов данных. Чем меньше мы рендерим, тем быстрее мы рендерим.
  5. Графики рисуются минимумом SVG элементов.

По последнему пункту есть даже отдельный бенчмарк, показывающий, что правильно реализованный SVG график, с рендерингом через один path элемент вместо кучи line элементов, по скорости не сильно уступает ручному рендерингу по холсту:


SVG vs Canvas
Результаты сравнения разных способов рендеринга


Графика Жизни


Рисовать нам надо будет точки, расположенные не по порядку слева направо, а в произвольных местах. Для этого мы зададим не series, а points_raw, который возвращает не вектор чисел, а вектор из координат:


$mol_app_life_map $mol_plot_pane
    gap 0
    graphs /
        <= Points $mol_plot_dot
            threshold 0
            points_raw <= points /

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


У $mol_plot_pane есть свойства shift и scale позволяющие централизованно изменять размер и положение графиков. Давайте введём свойство zoom, которое будет задавать коэффициент масштабирования, и pan которое будет алиасом для shift. И то и другое у нас будет изменяемым.


$mol_app_life_map $mol_plot_pane
    gap 0
    -
    pan?val /
        0
        0
    zoom?val 16
    scale /
        <= zoom -
        <= zoom -
    shift <= pan -
    -
    graphs /
        <= Points $mol_plot_dot
            threshold 0
            diameter <= zoom -
            points_raw <= points /

Обратите внимание, что мы указали диаметр точек равный степени приближения. А по умолчанию степень приближения равна 16. Значит всё поле изначально у нас будет представлять 16-пиксельную сетку в ячейках которых будут находиться 16-пиксельные кружки.


Зум и панорамирование


В $mol есть специальные компоненты, которые предназначены не для самостоятельного рендеринга, а для добавления функциональности к другим. Один из таких плагинов — $mol_touch, перехватывающий события пальцевого и мышиного ввода и реализующего различные жесты. Нам нужно лишь менять размер клеток и перемещать поле, поэтому мы добавляем плагин и провязываем объявленные ранее свойства:


plugins /
    <= Touch $mol_touch
        zoom?val <=> zoom?val -
        pan?val <=> pan?val -

Вот и всё. Правда. Двустороннее связывание — просто чудесная вещь. Вы пишите минимум кода, но при этом всё под вашим полным контролем. Когда любой вложенный компонент запрашивает значение свойства или пытается в него что-то записать — вызывается ваша функция. Например, давайте зададим минимальный уровень приближения равный единице:


@ $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 ) ) )
}

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


Кроме того, предоставим возможность реактивно же получить из компонента снепшот текущего изменённого состояния:


@ $mol_mem
snapshot_current() {
    return [ ... this.state() ].map( key => key.toString( 16 ) ).join( '~' )
}

Не забудем объявить коммуникационные свойства во view.tree:


snapshot \
snapshot_current \
-
speed 0
population 0

Заодно мы объявили свойство speed задающее частоту обновления мира и population позволяющее получить число живых клеток на данный момент. Последний реализовать несложно:


@ $mol_mem
population() {
    return this.state().size
}

Наконец, самое интересное — обновление состояния с заданной скоростью. Для этого мы заведём свойство 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
}

Божественная длань


Чтобы игрок был не просто немым свидетелем, а властителем судеб, подпишемся на несколько событий указателя:


event *
    ^
    mousedown?event <=> draw_start?event null
    mouseup?event <=> draw_end?event null

Не смотря на название, работают они как с мышь, так и с пальцем. К сожалению событие click тут не подойдёт, ибо оно срабатывает даже при панорамировании, что нам совершенно не надо. Поэтому при активации указателя мы будем запоминать текущее его положение:


@ $mol_mem
draw_start_pos( next? : number[] ) {
    return next
}

draw_start( event? : MouseEvent ) {
    this.draw_start_pos([ event.pageX , event.pageY ])
}

А по деактивации, проверять смещение и, если оно не сильно изменилось, инициировать переключение жизни и смерти клетки, что попала под руку:


draw_end( event? : MouseEvent ) {
    const start_pos = this.draw_start_pos()
    const pos = [ event.pageX , event.pageY ]

    if( Math.abs( start_pos[0] - pos[0] ) > 4 ) return
    if( Math.abs( start_pos[1] - pos[1] ) > 4 ) return

    const zoom = this.zoom()
    const pan = this.pan()

    const cell = key(
        Math.round( ( event.offsetX - pan[0] ) / zoom ) ,
        Math.round( ( event.offsetY - pan[1] ) / zoom ) ,
    )

    const state = new Set( this.state() )
    if( state.has( cell ) ) state.delete( cell )
    else state.add( cell )

    this.state( state )
}

Интерфейс управления


Игровое поле $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

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


В заголовке заменяем плейсхолдер на конкретное число живых клеток:


title() {
    return super.title().replace( '{population}' , `${ this.population() }` )
}

Базовый снепшот берём из ссылки:


snapshot() {
    return this.$.$mol_state_arg.value( 'snapshot' ) || super.snapshot()
}

Заодно формируем ссылку на текущее состояние мира, переход по которой будет добавлять текущий снепшот в историю браузера:


store_link() {
    return this.$.$mol_state_arg.make_link({ snapshot : this.snapshot_current() })
}

Выведем эту ссылку мы на тулбар в шапке вместе с переключателем скоростей:


tools /
    <= Store_link $mol_link
        uri <= store_link?val \
        hint <= store_link_hint @ \Store snapshot
        sub /
            <= Stored $mol_icon_stored
    <= Time $mol_switch
        value?val <=> speed?val 0
        options *
            1 <= time_slowest_label @ \Slowest
            5 <= time_slow_label @ \Slow
            25 <= time_fast_label @ \Fast
            60 <= time_fastest_label @ \Fastest

Если ссылка ведёт на текущий снепшот, то засеряем её:


[mol_app_life_store_link][mol_link_current] {
    opacity: .5;
}

И последний штрих — добавляем локализацию:


{
    "$mol_app_life_title": "Жизнь из {population} клеток",
    "$mol_app_life_store_link_hint": "Запомнить состояние",
    "$mol_app_life_time_slowest_label": "Тягуче",
    "$mol_app_life_time_slow_label": "Лениво",
    "$mol_app_life_time_fast_label": "Живо",
    "$mol_app_life_time_fastest_label": "Рьяно"
}

Ещё немного мелких правок и приложение готово:



Спасибо хабтратестировщикам в комментариях за ценную обратную связь. Все баги уже пофикшены.


Интересные комбинации


Фабрика планеров
Фабрика планеров


Асфальтоукладчик
Асфальтоукладчик на старте

Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+7
Comments 22
Comments Comments 22

Articles