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

#алгоритм #php #разработка_игр

Есть динамический двумерный массив.
Есть база итемов.
Итем может занимать произвольное количество ячеек массива.
У итема есть параметр [координаты], где указаны координаты ячейки, где находится
левый-верхний угол итема и дополнительно указаны его длинна и высота.
Примерно вот такая схема имеется ввиду.

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

Ответы

Ответ 1

Пример из камента:
Есть (слева) инвентарь (занятые - 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
*/