Алгоритм случайного появления объектов

Question

Алгоритм случайного появления объектов

поэтому я играю в сноуборд, и когда игрок едет вниз, я хочу, чтобы ландшафт генерировался случайным образом. Прямо сейчас я использую этот код:

void Biome::draw()
{
srand(seed); // seed is generated elsewhere
for (int x = 0; x < maxObstAmount; x++)
{
int xLoc = rand() % 640;
int yLoc = rand() % 480;
int obst = rand()%obstsInBiome.size();
obstsInBiome[obst].drawObstacle(xLoc, yLoc);
}
}

Функция выбирает случайное препятствие в биоме и порождает его в случайном месте на экране, что по сути и является тем, что я хочу. Тем не менее, это приводит к тому, что объекты перекрываются и так далее, поэтому мне просто интересно, может ли кто-нибудь помочь мне придумать лучший алгоритм для их появления, чтобы они не перекрывались? Спасибо

2

algorithm c++overlap random

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

РЕДАКТИРОВАТЬ:

Вот описание алгоритма, который я бы использовал, учитывая сценарий, который вы описали:

Я представляю что-то подобное с географией X-Y. Где oЭто объекты, о которых идет речь. C это горизонт создания.

     |--------------------------------------------------------------------------------
|     o         o
|          o          o
|o            o                        <-- Player moves this direction
^  |        o    o    o
|  |  o               o
y  |--------------------------------------------------------------------------------
C   x-->

Если у вас есть только один объект на x-позицию, тогда проблема довольно тривиальна. На приведенной выше диаграмме рядом o являются объектами с размером в направлении у.

Это вторая диаграмма для четкого разграничения отдельных объектов:

     |--------------------------------------------------------------------------------
|     7         3
|          5          1
|9            4                        <-- Player moves this direction
^  |        6    4    2
|  |  8               2
y  |--------------------------------------------------------------------------------
C   x-->

Создайте свой первый объект.
Создайте следующий объект в области, не занятой предыдущим объектом.
Повторите шаг 2 столько, сколько вы хотите.

Если у вас может быть более одного объекта на x-позицию, или если объекты имеют некоторую ширину в x-направлении:

     |--------------------------------------------------------------------------------
|     o         o
|            o          o
|o         oooo                        <-- Player moves this direction
^  |        o       ooo
|  |  o             ooo
y  |--------------------------------------------------------------------------------
C   x-->

или же

     |--------------------------------------------------------------------------------
|     7         3
|     7      5          1
|     7    4444                        <-- Player moves this direction
^  | 88     6       222
|  | 88             222
y  |--------------------------------------------------------------------------------
C   x-->

Вашу проблему перекрытия становится немного сложнее отследить, но она все же решаема.

Создайте свой первый объект.
Проверять объекты, начиная с непосредственно предыдущего объекта до первого объекта без измерений, которые вмешиваться или пересечь горизонт создания Cи исключите занимаемое ими пространство из пула выбора позиций для создания нового объекта.
Повторите шаг 2.

Чтобы уточнить шаг, я приведу пример:

     |--------------------------------------------------------------------------------
|
11|1
11|1                                     <-- Player moves this direction
^  |
|  |
y  |--------------------------------------------------------------------------------
C   x-->

Скажем, у нас есть этот сценарий, мы должны создать object 1только треть этого объекта еще видна, но мы можем видеть, создадим ли мы другой объект до того, как этот объект появится, это будет проблематично. Чтобы избежать наложения, мы можем выбрать случайную позицию и ширину, которые могут существовать в пространстве выше или ниже object 1, Следующее будет правильным выбором:

       |--------------------------------------------------------------------------------
|
1|11
1|11                                     <-- Player moves this direction
^    |
| 22 |
y    |--------------------------------------------------------------------------------
C   x-->

Дальнейший сценарий может быть примерно таким:

      |--------------------------------------------------------------------------------
|     33
|     33           111
4|4                 111                      <-- Player moves this direction
^  4|4          22
|   |
y   |--------------------------------------------------------------------------------
C   x-->

Вы можете не захотеть разместить свой object 5 где object 4 нарисовано, но объекты 3, 2, а также 1 на этом пути и не должны рассматриваться. Таким образом, вы можете проверить алгоритм по последнему созданному объекту, 4, (и возможно 3 в зависимости от того, как вы настроите свою игру) и установите лимиты создания соответственно.

Конечно, это упрощенное управление версиями, и я предполагаю, что вы дадите себе гораздо больше места для создания этих объектов, надеюсь, это иллюстрирует алгоритм, который решит проблему, с которой вы столкнулись.

3