Как бы я начал создавать звездную карту?

Я пытаюсь создать звездную карту.

Моя попытка будет:

1. Иметь ширину и высоту для карты.
2. Разместите точки (звезды) случайным образом по ширине и высоте.

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

Чтобы решить эту проблему, одним из подходов было бы иметь минимальное расстояние, и при создании звезды вы сравниваете расстояние от новой звезды до каждой сгенерированной звезды, а если расстояние ниже минимального, вы генерируете новую, но я не знаю, это эффективно. Какие-нибудь советы?

Пуассона-диска выборки распределение позволит выбрать случайные точки минимальное расстояние друг от друга и алгоритм Bridson в может эффективно решить эту проблему в O (N) - достаточно быстро , в режиме реального времени , если Ваш счетчик звезда не слишком велик.

Алгоритм Бридсона делит выходную область на сетку ячеек, размер которых соответствует минимально допустимому расстоянию, так что в каждой ячейке может появиться только одна точка. Затем, когда вы рассматриваете возможность добавления новой точки, вам нужно только проверить набор соседних ячеек в форме диска, а не весь список точек. Например, рассмотрим следующее изображение:

При проверке, чтобы увидеть, находится ли синяя точка кандидата слишком близко к существующим точкам, вам не нужно проверять ее по каждой существующей точке. Вместо этого вы можете ограничить поиск точками в соседних ячейках (которые вы можете быстро найти с помощью таблицы поиска). Майк Босток имеет приятную анимацию, показывающую алгоритм в процессе.

Стандартная реализация касается только фиксированного минимального расстояния между точками. В статье « Выборка диска Пуассона» Германа Таллекена (включая исходный код) рассматривается адаптация к изменению минимального расстояния в разных частях изображения; в основном, как алгоритм дизеринга . Использование перлин-шума / симплекс-шума, как показано в статье, может дать более естественную карту звезд. Например, я использовал изображение слева для генерации справа:

Для этого при рассмотрении точки кандидата я сначала проверяю значение входного изображения, которое дает значение от 0 до 1. Затем я масштабирую его до желаемого минимального и максимального расстояния между точками; в этом случае я выбрал 5 и 20 пикселей. Таким образом, при размещении точки в темных областях мои звезды могут располагаться на расстоянии до 5 пикселей друг от друга, а при размещении звезд в светлых областях они могут находиться на расстоянии до 20 пикселей.

Стоит отметить, что ускорение Bridson не совсем работает с выборкой с переменным расстоянием, потому что выходные точки не используют одинаковое минимальное расстояние. Однако вы все равно можете использовать выходную сетку, чтобы уменьшить поиск. Меньшая сетка приводит к более быстрому поиску ближайших соседей за счет увеличения памяти для большей справочной таблицы.

Одним из очень наивных, но простых решений было бы просто прыгнуть на «минимальное» расстояние, а затем добавить к нему случайную сумму. Это означает, что звезды никогда не станут слишком приятелями, и вы, по крайней мере, получите немного отклонений.

например

for (int x = 0; x < MAX_WIDTH; x+= MIN_SEPERATION_X)
{
  x += generateRandom();

  for (int y = 0; y < MAX_HEIGHT; y+= MIN_SEPERATION_Y)
  {
    y += generateRandom();

    if (x < MAX_WIDTH && y < MAX_HEIGHT)
    {
      image[x + y * width] = STAR;
    }
  }
}

(Вставка вашей любимой функции генерации случайных чисел)

Если вы знаете размер XYZ вашего игрового пространства, вы можете выбрать случайное место в этом пространстве

и затем сделайте SphereCast, чтобы проверить, есть ли что-нибудь уже слишком близко.

//pseudo code

SpawnStar(){
 Vector3 spot = new vector3(random(0,world size),random(0,world size,random(0,world size)

  while(true){
  SphereCast(spot, radius)
   if(hit something){
      spot = get new random spot
    }else{
     SpawnStar();
     brake;
    }
  } 
}

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