Estoy creando un juego 2D para un sitio web donde el universo puede crecer extremadamente grande (básicamente infinitamente grande). Inicialmente, el universo está compuesto de 6 estrellas que están a la misma distancia del origen (0, 0). Mi tarea es poder generar más estrellas que tengan "caminos" (bordes) que se conecten entre sí. ¿Cómo puedo diseñar un algoritmo que cumpla con estas restricciones?
- Las estrellas se generan aleatoriamente hacia afuera. (por ejemplo, las coordenadas (x, y) para las nuevas estrellas irán lentamente hacia afuera desde (0, 0) en todas las direcciones, preferiblemente en formato espiral)
- Los bordes NO se cruzarán.
- Aunque debería haber alguna variación, las nuevas estrellas no deberían estar demasiado lejos o demasiado cerca de otras estrellas. (Por ejemplo, debe haber un radio mínimo)
- Ninguna estrella / punto debe tener una multiplicidad de más de 3.
- Dado que todo esto se almacenará en una base de datos, el algoritmo no puede ser demasiado costoso. En otras palabras, me encantaría lograr algo de complejidad O (n) (no sé si esto es factible).
Esencialmente, lo que estoy buscando es una galaxia de aspecto espiral donde las estrellas son puntos en el gráfico y el viaje entre estrellas está representado por bordes entre esas estrellas.
Los pasos particulares que necesito resolver son:
- Genera aleatoriamente un punto en la vecindad vecina de otras estrellas que aún no tienen una multiplicidad de 3.
- Encuentra la primera estrella que aún no tiene una multiplicidad de 3 que no generará conflicto de borde.
- Si la estrella está a una distancia mínima de x unidades de distancia, cree un borde entre los dos puntos.
Traté de buscar soluciones, pero mis habilidades matemáticas (y conocimiento en teoría de gráficos) necesitan mucho trabajo. Además, cualquier recurso / enlace sobre este asunto sería muy apreciado.
Aquí hay un pseudocódigo en el que estaba pensando, pero no estoy seguro de si esto incluso funcionaría y estoy seguro de que no funcionaría terriblemente bien después de unas 10,000 estrellas, etc.
newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
for (star in the known universe):
if(distance between newStar and star > x units):
if(star has < 3 multiplicity):
if(path from newStar to star does not intersect another path):
connect the star to the other star
break;
newStar = new random (x, y) coordinateAdemás, si alguien tiene algún consejo sobre cómo debo almacenar esto en una base de datos MySQL, también agradecería eso.
Finalmente, en caso de que nada tenga sentido arriba, he incluido una imagen de lo que me gustaría lograr a continuación:
fuente
Respuestas:
Sugerencia: Mantenga la red del universo interno perfectamente ordenada, algorítmica y relativamente simple. Solo necesita que el universo se vea aleatorio cuando se muestra en la pantalla del usuario . Solo aplique compensaciones aleatorias a las posiciones de estrella para la visualización del usuario.
Problema: el enfoque más obvio de calcular un desplazamiento aleatorio para cada estrella no hará un muy buen trabajo al ocultar la verdadera estructura subyacente. Solo puedes aleatorizar las estrellas en una pequeña cantidad antes de que corran el riesgo de chocar entre sí o cruzarse.
Solución: puede aplicar grandes distorsiones aleatorias y obtener un universo mucho más aleatorio e interesante si aplica aleatoriedad coordinada no local. Imagine colocar las estrellas en una lámina de goma e imagine estirar y aplastar al azar diferentes partes de la lámina. Eso puede desplazar grupos enteros de estrellas a larga distancia. Nunca chocarán ni se cruzarán porque las estrellas cercanas se estiran y aplastan en relación entre sí.
Cómo hacerlo: busca generadores de terreno fractal. Hay un montón de código libre y abierto para ello. Solo necesita un código básico que genere un valor de altura para cada punto en un mapa. Vamos a usarlo de una manera diferente. Use ese código para generar DOS mapas independientes de altura del terreno. Comience con la verdadera posición X, Y de la estrella, mire esa ubicación en cada mapa, use un valor de mapa para compensar la posición de visualización X de la estrella y use el otro valor del mapa para compensar la posición de visualización Y de la estrella. Tendrás que jugar con algunos de los factores de escala, pero eso puede darte el efecto de lámina de goma deformado al azar. Las grandes variaciones en la posición de la estrella deberían ocultar completamente las posiciones ordenadas subyacentes. La naturaleza fractal de la aleatoriedad dará un efecto muy natural,
fuente