Инвентарь браузерной игры в двоичном массиве

Есть динамический двумерный массив. Есть база итемов. Итем может занимать произвольное количество ячеек массива. У итема есть параметр [координаты], где указаны координаты ячейки, где находится левый-верхний угол итема и дополнительно указаны его длинна и высота. Примерно вот такая схема имеется ввиду. В данном случае: [crossbow:2-2:2:4]. Для переноса итема юзается drag-n-drop. НО, так как в базе инвентаря фактически итем находится в координатах одной клетки, то итемы элементарно накладываются один на другой. А если итем приходит извне, то инвентарь вообще не генерируется: система проверяет записи координат, делает поправки x+width, y+height и вставляет итем в пустое место, если оно есть. Но такие проверки очень монструозны и затратны, так как все поправки должны упасть во временное хранилище занятых клеток и не учитываться при проверке на их свободность. Можно подпереть костылём с другой стороны: при каждоё операции с инвентарём отсылать в базу новую версию маски занятых секторов в массиве, но тесты показали, что 4 человека усиленно переставляя итемы в инвентаре ложат нахрен всю базу и выедают непростительно много памяти. Кто-то разрабатывал подобные системы? Решал подобные проблемы? Каким макаром такое можно оптимизировать? Или может я не замечаю какой нить более простой подход к теме?

Ответ

Пример из камента: Есть (слева) инвентарь (занятые - 1, пустые - 0), 10х5 И есть (справа) предмет, допустим на данный момент в позиции [7;2], размером 2х3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 При их сложении получится следующее: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 2 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 Тут мы видим двойку - это значит, предметы накладываются и сюда поставить нельзя. Накидал вам простенькую функцию подстановки предмета в матрицу. Вам остается только сложить массивы и проверить в сумме наличие двоек :) Соответственно, при "добавлении в инвентарь" вам надо пробежаться по инвентарю и поискать в нем такие места, при добавлении предмета в которые этих самых двоек не возникает. function getItemMatrix( $item /* x, y, w, h */ ) { $invWidth = 10; $invHeight = 5; $result = array(); if ($item->x + $item->w > $invWidth or $item->y + $item->h > $invHeight) return false; // сюда ставить нельзя for ($i = 1; $i <= $invWidth; $i++) { $result[$i] = array(); for ($j = 1; $j <= $invHeight ; $j++) $result[$i][$j] = ($i >= $item->x and $i <= $item->x + $item->w and $j >= $item->y and $j <= $item->y + $item->w ) ? 1 : 0; } return $result; }
/* - Аааа, я видел двойку! - Успокойсся, Бендер, это был сон, двоек не бывает... © futurama */