¿Cómo haría para generar un mapa estelar?

8

Estoy tratando de generar un mapa estelar.

Mi intento sería:

  1. Tener un ancho y alto para el mapa.
  2. Coloque puntos (estrellas) al azar en el área de ancho y alto.

Un enfoque simple, pero tiene el problema de colocar al azar estrellas extremadamente cercanas entre sí.

Para resolver este problema, un enfoque sería tener una distancia mínima y al generar una estrella, se compara la distancia desde la nueva estrella a cada estrella generada y si está por debajo de la distancia mínima, se genera una nueva, pero no sé si Eso es eficiente. ¿Algun consejo?

zebleckDAMM
fuente
3
Puede haber formas más eficientes de hacerlo, pero ¿por qué no funciona para usted? ¿Tienes problemas con esta implementación? ¿Estás optimizando prematuramente?
Vaillancourt
¿Cuál es el propósito del mapa estelar? ¿Es un fondo o más como un campo de juego?
Erik
@AlexandreVaillancourt sí, todavía no sé cuántas estrellas quiero generar y parece que es una forma muy ineficiente.
zebleckDAMM
@Erik no es un fondo, estrellas con las que puedes interactuar
zebleckDAMM
Y ... ¿lo harás en tiempo de ejecución o sin conexión?
Vaillancourt

Respuestas:

13

Una distribución de muestreo de Poisson-Disk le permitirá seleccionar puntos aleatorios a una distancia mínima y el algoritmo de Bridson puede resolver el problema de manera eficiente en O (n), lo suficientemente rápido en tiempo real siempre que su recuento de estrellas no sea demasiado grande.

El algoritmo de Bridson divide la región de salida en una cuadrícula de celdas con un tamaño relativo a la distancia mínima permitida, de modo que solo puede aparecer un punto en cada celda. Luego, cuando considere agregar un nuevo punto, solo necesita verificar una colección en forma de disco de celdas vecinas en lugar de toda la lista de puntos. Por ejemplo, considere la siguiente imagen:

ingrese la descripción de la imagen aquí

Al verificar para ver si el punto azul candidato está demasiado cerca de los puntos existentes, no necesita verificarlo con cada punto existente. En cambio, puede restringir la búsqueda a los puntos en las celdas vecinas (que puede encontrar rápidamente usando una tabla de búsqueda). Mike Bostock tiene una bonita animación que muestra el algoritmo en progreso.

La implementación estándar solo se refiere a una distancia mínima fija entre puntos. El artículo de muestreo Poisson Disk de Herman Tulleken (incluye código fuente) cubre una adaptación para variar la distancia mínima en diferentes partes de la imagen; básicamente como un algoritmo de tramado . El uso del ruido perlin / ruido simplex como se muestra en el artículo nubes podría dar un mapa estelar más natural. Por ejemplo, usé la imagen de la izquierda para generar la derecha:

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Para hacer esto, cuando considero un punto candidato, primero verifico el valor de la imagen de entrada, que produce un valor de 0 a 1. Luego escalo esto a mi distancia mínima y máxima deseada entre puntos; en este caso seleccioné 5 y 20 píxeles. Entonces, cuando coloco un punto en las regiones oscuras, mis estrellas pueden estar tan cerca como 5 píxeles entre sí y cuando coloco estrellas en las regiones claras, pueden tener una separación de hasta 20 píxeles.

Vale la pena señalar que la aceleración de Bridson no funciona exactamente con muestreo de distancia variable porque los puntos de salida no están utilizando una distancia mínima uniforme. Sin embargo, aún puede utilizar una cuadrícula de salida para reducir la búsqueda. Una cuadrícula más pequeña resulta en una búsqueda más rápida de vecinos más cercanos a expensas de una mayor memoria para una tabla de búsqueda más grande.

Pikalek
fuente
2
Los enlaces son muy bonitos. Sin embargo, podrían perderse con el tiempo. Podría ser aún mejor incluir más detalles aquí.
Trilarion
Se agregó un poco más de explicación e ilustración para protegerse contra eso.
Pikalek
1

Una solución muy ingenua pero simple sería simplemente saltar siempre la distancia "mínima", y luego agregar una cantidad aleatoria encima de eso. Esto significa que las estrellas nunca serán demasiado amigas, y al menos tendrás un poco de desviación.

p.ej

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

(Insertar su función favorita de generación de números aleatorios)

Huxellberger
fuente
Pero, ¿y si golpeas a otra estrella allí? (También tus estrellas deberían estar en una banda inclinada si haces esto.)
Trilarion
1
¿Es posible golpear a otra estrella? Asumo solo una iteración sobre toda la imagen. ¿Los dos números que siempre cambian por una separación mínima lo detienen? Escuché que las fusiones estelares son bastante desordenadas, así que estoy de acuerdo en que es bueno asegurarse de que no sucedan. Causar una supernova sería un error muy desconsiderado.
Huxellberger
Quise decir que min_separation no está garantizado (no puede ser con este algoritmo) porque siempre agrega números aleatorios. Al menos asegúrese de que los números aleatorios no pueden ser mayores que min_separation. La distancia mínima garantizada es entonces min_separation - max (generate_Random). Pero no es un enfoque realmente malo. +1
Trilarion
Este enfoque tenderá a producir columnas de estrellas en líneas verticales ordenadas, ya que no varía la coordenada x a medida que cambia y. Es poco probable que parezca aleatorio o natural para colecciones densas.
DMGregory
0

Si conoce el tamaño XYZ de su espacio de juego, puede elegir un lugar aleatorio en ese espacio

y luego haga un SphereCast para verificar si ya hay algo demasiado cerca.

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

El problema con esto es que probablemente no será muy bueno en tiempo real, sin embargo, para pregenerado, está bien y es bastante rápido.

Josh Kirkpatrick
fuente
1
Sea lo que sea un SphereCast, ¿no es esta exactamente la solución que se menciona en la pregunta y se considera ineficiente?
Trilarion
1
Creo que te refieres a OverlapSphere. SphereCast dispara una esfera a lo largo de una línea, por lo que tiene una huella de detección en forma de cápsula.
DMGregory