Как лучше рендерить клеточный автомат?

Question

[Ди Ма]

Здравствуйте!

Имеется довольно большая матрица (чем больше- тем лучше).
Как правильно отрисовать её на странице?
Хотелось бы еще и с нормальной частотой, хотя-бы раз в 50 ms.

// сейчас в таком виде
function renderMatrix(matrix, selector) {
	var wrap = document.querySelector(selector);

	wrap.innerHTML = '';
	for (var y = 0; y < matrix.length; y++) {

		wrap.innerHTML += '<br>';
		for (var x = 0; x < matrix[y].length; x++) {

			var cell = matrix[y][x];
			wrap.innerHTML += '<div class="_'+ cell +'">'+ cell +'</div>';
		}
	}
}

И еще, не будет ли быстрее преобразовывать матрицу в строку через arr.toString(), помещать строку на страницу, а потом регулярным выражением заменить клетки на дивы?

Картинка

Comments

[Даниил Попов]

Не нужно перерисовывать. Нарисуйте 1 раз при загрузке, а дальше манипулируйте содержимым и стилями

Answer 1

[0xD34F]

Имеется довольно большая матрица (чем больше- тем лучше).
Как правильно отрисовать её на странице?
Хотелось бы еще и с нормальной частотой, хотя-бы раз в 50 ms.

Используйте canvas. При правильном подходе сможете добиться результата на порядок лучше, чем 50 миллисекунд.

не будет ли быстрее преобразовывать матрицу в строку через arr.toString()...

Не будет.

Картинка

Указывать состояния не нужно - цветового обозначения вполне достаточно. Кроме того, при небольших размерах клеток вы эти цифры либо не увидите, либо они не будут влезать в свои клетки (вы представьте, что отрисовываете матрицу хотя бы 300x300).

Comments

[Ди Ма]

не будет ли быстрее преобразовывать матрицу в строку через arr.toString()...
Не будет.

Матрицу 15х15 вот такая функция отрисовывает за 2-3 ms, в то время как просто 2 цикла делают это за 150-160 ms

function renderMatrix(matrix, selector) {
	var wrap = document.querySelector(selector);
	var str = '';
	wrap.innerHTML = '';
	for (var y = 0; y < matrix.length; y++) str += matrix[y].toString() + 'n';
	wrap.innerHTML += str
		.replace(/(\d)\,?/g, '<div class="_$1">$1</div>')
		.replace(/n/g, '<br>');
}

Попробую канвас, но пока-что replace быстрее всего

[Владимир Проскурин]

Ди Ма, с dom по определению медленнее, чем с канвой (при условии правильного кода конечно).

[0xD34F]

Ди Ма, извините, не очень удачно выразился - "быстрее" было сказано про сравнение с канвасом, которому все варианты с вёрсткой проигрывают, и сильно.

Попробую канвас, но пока-что replace быстрее всего

2-3 миллисекунды на матрицу 15x15 - это очень медленно. За 2-3 миллисекунды на канвасе можно отрисовывать матрицу 400x400, например (конечно, при решении задачи "в лоб" вы такой производительности не добьётесь, придётся проявить изобретательность).

[Ди Ма]

0xD34F,
Да, канвас быстрее!

придётся проявить изобретательность

Пока что в голову приходит только:
1) Рисовать только "живые" клетки на "мертвом" фоне. А не все подряд.
2) Рисовать только изменившиеся клетки.

Есть еще идеи?)

[0xD34F]

Ди Ма,

Рисовать только "живые" клетки на "мертвом" фоне.

Нет разницы между "живыми" и "мёртвыми" клетками - ведь это просто условные наименования для клеток, находящихся в том или ином состоянии.

По сути, вы хотите не отрисовывать клетки, находящиеся в каком-то определённом состоянии. Как это возможно, не очень понятно - если "живая" клетка стала "мёртвой", это надо как-то отобразить. Не рисовать - не получится, ведь иначе может оказаться так, что реальное и отображаемое состояния клетки будут отличаться.

Рисовать только изменившиеся клетки.

Это хорошая мысль. Правда, тут есть недостаток - скорость рисования получается переменной, в зависимости от количества клеток, изменивших своё состояние. И при большом размере матрицы эта переменность может быть очень хорошо заметна пользователю.

Есть еще идеи?

Покажите получившийся код отрисовки с помощью канваса. Нет, я конечно примерно представляю, каков он, но если покажете, мне будет проще объяснять, что можно сделать.

[Ди Ма]

0xD34F,
Если позволите, покажу весь объект. Может еще что подскажете)

var Machine = {

    matrix: null,  // матрица
    memory: null, // предыдущее состояние
    handler: null, // функция вычисления состояния

    size: { x: 400, y: 400 }, // размер поля


    init: function (matrix, handler) {

        var canvas = document.querySelector('#canvas');
        canvas.setAttribute('width', this.size.x);
        canvas.setAttribute('height', this.size.y);

        this.ctx = canvas.getContext('2d');

        this.matrix = matrix;
        this.handler = handler;

        this.coefX = this.size.x / this.matrix[0].length;
        this.coefY = this.size.y / this.matrix.length;

        this.calc();
    },

    // Вычислить новое состояние
    calc: function () {

        var res = [],
            lenX = this.matrix[0].length,
            lenY = this.matrix.length;

        for (var y = 0; y < lenY; y++) {
            var py = y === 0 ? lenY -1 : y -1,      // prev y
                ny = y === lenY -1 ? 0 : y +1;       // next y

            res[y] = [];
            for (var x = 0; x < lenX; x++) {
                var px = x === 0 ? lenX -1 : x -1,  // prev x
                    nx = x === lenX -1 ? 0 : x +1;   // next x

                // возвращаемый функцией результат присваивается текущей клетке
                res[y][x] = this.handler(this.matrix, py, px, y, x, ny, nx);
            }
        }
        this.memory = this.matrix.slice();  // cохранить старую версию
        this.matrix = res;  // обновить матрицу

        this.render();
    },

    // Отрисовка матрицы
    render: function () {

        for (var y = 0, lenY = this.matrix.length; y < lenY; y++) {
            for (var x = 0, lenX = this.matrix[y].length; x < lenX; x++) {

                if (this.matrix[y][x] === this.memory[y][x]) continue;

                this.ctx.fillStyle = this.matrix[y][x] === 0 ? '#0d2a37': '#CCC';
                this.ctx.fillRect(x * this.coefX, y * this.coefY, this.coefX, this.coefY);
            }
        }
    },
};

[0xD34F]

Ди Ма,
Ну, для начала разберём всего одну строку:

this.ctx.fillStyle = this.memory[y][x] === 0 ? '#0d2a37': '#CCC';

Почему memory[y][x] === 0 ? бла-бла-бла (и почему memory, а не matrix? - отрисовывать надо новое состояние, а не прошлое)? Неужели количество доступных состояний у вас ограничено всего лишь двумя? А как же картинка из вопроса, где есть клетки в шести различных состояниях? Лучше сделайте объект, где ключ - состояние, а значение - цвет:

var colors = {
  0: какой-то цвет,
  1: ещё какой-то цвет,
  2: и ещё,
  3: да сколько угодно,
  ...
};

Тогда установка цвета будет выглядеть так:
this.ctx.fillStyle = colors[this.matrix[y][x]];

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

var groups = [...Array(numCellStates)].map(() => []);

При обходе матрицы вместо рисования клетки кладёте её индексы в соответствующий её состоянию массив:
groups[this.matrix[y][x]].push(x, y);

После того, как все клетки будут раскиданы по группам, обходите группы и отрисовываете их содержимое:

for (var state = 0; state < groups.length; state++) {
  this.ctx.fillStyle = colors[state];

  var cells = groups[state];
  for (var i = 0; i < cells.length; i += 2) {
    this.ctx.fillRect(cells[i] * this.coefX, cells[i + 1] * this.coefY, this.coefX, this.coefY);
  }
}

[Ди Ма]

0xD34F,

почему memory, а не matrix?

Механическая ошибка. Не сразу заметил, т.к. работало и так

количество доступных состояний у вас ограничено всего лишь двумя?

Нет, я переделывал, упростил, и еще не успел добавить. Раньше цвет задавался через класс, так-же как с объектом ._1 {background-color: #879195;}
Сейчас сделал через объект.

Про группы и цвета- здорово!
this.groups[this.matrix[y][x]].push(x, y); вынес в цикл, который в calc.
А в render оставил только обход групп (куда добавляются только изменившиеся клетки).

[0xD34F]

Ди Ма,

this.groups[this.matrix[y][x]].push(x, y); вынес в цикл, который в calc.

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

А главное - совсем не обязательно, что каждое поколение клеток должно быть отрисовано. Представьте, что в будущем вы захотите добавить такую функциональность, как прокрутку на N поколений вперёд - типа, не хотите наблюдать за эволюцией, нужен только результат. Или возникнет необходимость реализовать отображение только одного поколения из двух или трёх или ... - для того же ускорения работы (не только, для этого есть и другие причины). В этом случае группировка клеток, выполняемая вместе с расчётом новых состояний отрицательно скажется на производительности.

[Ди Ма]

0xD34F,

Это зря - так вы смешиваете код, выполняющий разные задачи

Тоже об этом думал, но лишний цикл в цикле показался мне хуже

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

Пожалуй да. calc и render лучше разделить)

В общем, спасибо за ответ и пояснения)
То, что было нужно)

Answer 2

[Владимир Проскурин]

С нормальной частотой или скоростью? Если матрица не изменилась, то зачем ее перерисовывать?
Предлагаю использовать canvas, легко сможете рисовать очень большие матрицы.

Comments

[Ди Ма]

Если матрица не изменилась, то зачем ее перерисовывать?

Матрица меняется после каждого такта.
Попробую канвас