¿Cómo podría generar un map estelar?

Estoy tratando de generar un map de estrellas.

Mi bash sería:

  1. Tener un ancho y alto para el map.
  2. Coloque puntos (estrellas) random en el área de ancho y alto.

Un enfoque simple, pero tiene el problema de colocar estrellas random muy cerca unas de otras.

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

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

El algorithm de Bridson divide la región de salida en una cuadrícula de celdas de 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 la list completa de puntos. Por ejemplo, considere la siguiente image:

enter image description here

Cuando compruebe si el punto azul candidato está demasiado cerca de los puntos existentes, no necesita verificarlo contra cada punto existente. En su lugar, 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 animation que muestra el algorithm 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 el código fuente) cubre una adaptación para variar la distancia mínima en diferentes partes de la image; básicamente como un algorithm de ttwigdo . Usar el ruido de perlin / ruido simple como se muestra en las nubes del artículo podría dar un map estelar de aspecto más natural. Por ejemplo, utilicé la image de la izquierda para generar el derecho:

enter image description here enter image description here

Para hacer esto, cuando considero un punto candidato, primero verifico el valor de la image de input, que arroja un valor de 0 a 1. Luego escalo esto a la distancia mínima y máxima deseada entre los puntos; en este caso, seleccioné 5 y 20 píxeles. Por lo tanto, al colocar un punto en las regiones oscuras, mis estrellas pueden tener hasta 5 píxeles de diferencia y al colocar estrellas en las regiones claras, pueden tener una separación de hasta 20 píxeles.

Vale la pena señalar que la velocidad de Bridson no funciona exactamente con el muestreo de distancia variable porque los puntos de salida no utilizan una distancia mínima uniforme. Sin embargo, aún puede usar una cuadrícula de salida para networkingucir la búsqueda. Una cuadrícula más pequeña da como resultado una búsqueda más rápida de los vecinos más cercanos a expensas de una mayor memory para una tabla de búsqueda más grande.

Una solución muy ingenua pero simple sería simplemente saltar la distancia "mínima" y luego agregar una cantidad aleatoria sobre eso. Esto significa que las estrellas nunca serán demasiado amigas, y al less obtendrá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 function favorita de generación de numbers aleatorios)

Si conoces el tamaño XYZ de tu espacio de juego, podrías elegir un lugar random 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 sea muy bueno para el time real, sin embargo, para pregenerado, está bien y es bastante rápido.