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

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); 
    } 
} 

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

Answer 1

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

EDIT:

Вот описание алгоритма Я хотел бы использовать данный сценарий вы описали:

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

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

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

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

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

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

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

 |-------------------------------------------------------------------------------- 
    |  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--> 

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

1. Создайте свой первый объект.
2. Проверить объекты, начиная с немедленным предыдущим объектом до первого объекта без измерений, которые вмешиваются или пересекают горизонт созданияC и устраняющее пространству, занимаемые ими от выбора пула позиций, чтобы создать свой новый объект ,
3. Повторите шаг 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 в зависимости от того, как вы установили игру) и соответственно установить лимиты создания.

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