Что было бы лучшим решением для добавления объектов разного размера в мир?

Я работаю над игрой, в которой я использую объекты разного размера, такие как дома, деревья и т. д. Мой вопрос в том, каким образом я должен определить, является ли место, где я собираюсь разместить свой объект, свободным или нет? Мир генерируется случайным образом при каждом запуске игры.

(Я использую только координаты x и z). Например, у меня есть дерево в пуле предметов размером 10x10, в локации 10, 0, 10, и я собираюсь добавить камень размером, например, 5x5. Итак, как мне сказать камню: «Эй, ты не можешь расположить себя в координатах от 5 до 15 по оси X и от 5 до 15 по оси Z, помести куда-нибудь еще».

Да простым способом было бы просто записать все взятые координаты (5,6,7...14,15), но что если у меня 1000 деревьев? Есть ли лучший и более быстрый способ найти свободное место для элемента, кроме перебора списка координат, которые также зациклены для записи при занятии слота?


unity3d optimization location generate coordinate
person user9534568    schedule 22.03.2018    source источник
comment
Возможно, stackoverflow.com/questions/28891679   -  person Marc L.    schedule 22.03.2018

Ответы (2)


arrow_upward
0
arrow_downward

Логика поиска по хеш-таблицам может вдохновлять.

Чтобы напомнить нам о хеш-таблице:

При поиске n в хеш-таблице

  • сначала мы смотрим на h(n), где h — это хэш-функция.
  • Сообщите о рекорде, если он попадет, перейдите к h(n)+1, если он промахнется.
  • Сообщите о рекорде, если он попадет, перейдите к h(n)-1, если он промахнется.
  • Сообщите о рекорде, если он попадет, перейдите к h(n)+2, если он промахнется.
  • Сообщите о рекорде, если он попадет, перейдите к h(n)-2, если он промахнется.
  • Сообщите о рекорде, если он попадет, перейдите к h(n)+4, если он промахнется.
  • Сообщите о рекорде, если он попадет, перейдите к h(n)-4, если он промахнется.
  • ...

Мы устанавливаем размер шага для чисел в последовательности 2^i и их отрицательных значений (0,1,-1,2,-2,4,-4,8,-8,16,...)

Теперь в вашем сценарии:

  • сначала мы смотрим на t, где t — это целевое местоположение.
  • Сообщите о местоположении, если оно свободно, переместитесь в [t.x,t.y+1], если нет.
  • Сообщите о местоположении, если оно свободно, перейдите в [t.x, t.y-1], если нет.
  • ...
  • Сообщите о местоположении, если оно свободно, перейдите в [t.x-1,t.y-1], если нет.
  • Сообщите о местоположении, если оно свободно, перейдите в [t.x,t.y+2], если нет.
  • ...
  • Сообщите о местоположении, если оно свободно, переместитесь в [t.x,t.y+4], если нет.
  • ...

Теперь, как мы узнаем, свободна ли локация или нет? Вы можете создать настоящую хэш-таблицу для хранения в ней позиций всех объектов. Теперь, когда вам нужно проверить свободное место вокруг [x,y], чтобы поставить камень, вам придется искать h(x,y) в хеш-таблице.

Если вам нужно разместить более крупный объект, например, круглый фонтан 3x3, в точке [x, y], вам также нужно будет проверить эти записи: h(x+1,y), h(x-1,y), h(x,y+1), h(x,y-1). Поскольку это круглый объект, вы можете аппроксимировать область для упрощения и, таким образом, удалить четыре относительных местоположения, таких как h(x+1,y+1), h(x+1,y-1), h(x-1,y+1), h(x-1,y-1), из вашего поиска.

После этого вы должны добавить все эти позиции в хеш-таблицу, чтобы потом было легче найти занятые позиции. например добавление объекта 3x3 требует добавления 9 записей в хеш-таблицу.

Обратите внимание, что хеш-функция должна отражать двухмерный (или трехмерный) мир. например h(x,y) = x*N + y, где N — максимальный размер мира по оси Y.

person Bizhan    schedule 22.03.2018
comment
Я имел в виду использование хеш-таблиц, а также пытался упростить свое местоположение, но упрощение приводит меня к ошибке - например, если объект имеет размер 3x3 в позиции (x, y), а моя система помещает элемент 3x3 в позицию x+3 y-3, то будут перекрытия по позициям (x+1,y-1), (x+1, y-2), (x+2,y-1),(x+2,y- 2) или я неправильно мыслю? - person user9534568; 23.03.2018
comment
реальный размер в этом примере будет 6x6 :) - person user9534568; 23.03.2018
comment
@ user9534568 Вы правы, я отредактировал ответ. однако мои предположения по вашему вопросу выглядят так: pasteboard.co/HdzkHPm.png, где два прямоугольника сталкиваются в ( +1,5,-1,5). Итак, если эта позиция уже занята, вам нужна запись в вашей хеш-таблице, сообщающая, что эта позиция занята, т. Е. Наличие прямоугольника 3x3 равно 9 записям в хэш-таблице. Это все еще может быть намного более эффективным с точки зрения использования памяти, чем разреженный поиск bool[,] (например, растровое изображение). - person Bizhan; 25.03.2018
comment
Под разреженным поиском bool[,] я подразумеваю преобразование карты в 1-битное растровое изображение MxN, где его элементами являются логические значения, говорящие о том, занят ли этот пиксель или нет. Использование хеш-таблицы обеспечивает большую гибкость и требует меньше памяти для больших разреженных карт. - person Bizhan; 25.03.2018

arrow_upward
0
arrow_downward

Вы можете работать с сеткой. Или, чтобы предотвратить перекрытие объектов при их размещении, вы можете просто добавить коллайдер к объекту, установить его как триггер и проверить, не сталкивается ли он с другим объектом, прежде чем размещать его. Если вы хотите сохранить некоторое расстояние между объектами, вы можете увеличить коллайдеры.

person Steffan Venema    schedule 22.03.2018