Я работаю над HTML5-игрой типа Тетрис, и мне нужно усовершенствовать алгоритм оптимизации пространства.Прямоугольные блоки различного размера должны быть добавлены к холсту наиболее эффективным способом.Я знаю, сколько места занимает блок, мне нужно найти ближайшую точку, в которую можно добавить блок с фиксированной координатой x, - лучше иметь абсолютную ближайшую точку.
Я реализовал версию, котораявыполняет поиск с использованием попиксельной проверки значения на холсте, который перемещается вниз, пока не находит достаточно свободного места для фигуры, а затем добавляет его.Это работает (медленно), только если пространство заполняется слева направо - алгоритм может с уверенностью предположить, что первый столбец пикселей безопасен, тогда можно добавить весь блок.
Мне нужно сделать это более надежным, вот гдеЯ думаю, что так и должно быть.
Хранение четырехугольного дерева для представления состояния доски дает мне более быстрый способ определить, где есть место.
4 узла сохраняются для каждого уровня глубины - каждый узел либо 0 для полностью пустого, либо 1 для «где-то есть вещи».Каждый прогрессивный уровень глубины дает все больше и больше информации о плате.
given(boardstate, block width, block height)
-calculate the largest grid space the block must span
// a block which is 242x38 MUST span a 16x16 free space
// (based on 1/2 of smallest dimension)
-the block width requires n consecutive free spaces
// (242/16) = 15
-find the first available 15x1 spaces in the board
-check the surrounding tiles at the next level of depth for collisions
-check the surrounding tiles at the next level of depth for collisions... etc
-if there's a fit
draw the block
mark all affected nodes at all depths as 'filled'
Какая структура данных javascript является наилучшей для представления сетки?
Things I 'мы уже рассмотрели:
A.Создайте полный объект tree с указателями на дочерние элементы и значения и набор методов для навигации по нему.Это было бы интуитивно понятно и, возможно, занимало мало места, но я подозреваю, что это очень медленно
B.Посмотрите на каждую сетку как на 4 бита и сохраните глубины как шестнадцатеричные массивы или объекты.Если это делает человек, более умный, чем я, это, вероятно, оптимизирует не только хранилище, но и делает доступными умные битовые операции для сравнения соседних ячеек, включения и выключения блоков и т. Д. Я думаю, это было бы невероятно быстро, невероятно эффективно, но это за пределамимои навыки для построения.
C.Сохраните каждую глубину в массиве.Depth[0]=[1,0,0,0]; Depth[1][1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0] и т. Д. Вот куда я сейчас направляюсь.Он не очень компактен и, вероятно, не будет невероятно быстрым, но я думаю, что смогу обдумать это.
Практическое ограничение для любой структуры - количество глубин (массив для хранения доступности).из 4x4 пробелов в моем последнем подходе - более 65 тысяч), после чего выполнение дорогостоящего вызова для проверки последних нескольких пикселей данных изображения с холста с помощью обычного итератора неизбежно.
Итак, A, B, C, другие?
Как обычно, все идеи приветствуются.