Wie würde ich eine Sternenkarte erstellen?

Ich versuche eine Sternenkarte zu generieren.

Mein Versuch wäre:

1. Haben Sie eine Breite und Höhe für die Karte.
2. Platzieren Sie Punkte (Sterne) zufällig über den Bereich von Breite und Höhe.

Ein einfacher Ansatz, der jedoch das Problem hat, Sterne extrem nahe beieinander zu platzieren.

Um dieses Problem zu lösen, besteht ein Ansatz darin, einen Mindestabstand zu haben. Wenn Sie einen Stern erzeugen, vergleichen Sie den Abstand zwischen dem neuen Stern und jedem erzeugten Stern. Wenn der Abstand unter dem Mindestabstand liegt, erzeugen Sie einen neuen, aber ich weiß nicht, ob das ist effizient. Irgendwelche Tipps?

Mit einer Poisson-Disk-Sampling- Verteilung können Sie zufällige Punkte in einem Mindestabstand auswählen. Der Bridson-Algorithmus kann das Problem in O (n) effizient lösen - schnell genug für Echtzeit, vorausgesetzt, Ihre Sternzahl wird nicht zu groß.

Der Bridson-Algorithmus unterteilt den Ausgabebereich in ein Raster von Zellen, die relativ zum minimal zulässigen Abstand dimensioniert sind, sodass in jeder Zelle nur ein Punkt erscheinen kann. Wenn Sie dann einen neuen Punkt hinzufügen möchten, müssen Sie nur eine scheibenförmige Sammlung benachbarter Zellen im Gegensatz zur gesamten Liste der Punkte überprüfen. Betrachten Sie beispielsweise das folgende Bild:

Wenn Sie prüfen, ob der blaue Punkt des Kandidaten zu nahe an vorhandenen Punkten liegt, müssen Sie ihn nicht mit jedem vorhandenen Punkt vergleichen. Stattdessen können Sie die Suche auf die Punkte in den benachbarten Zellen beschränken (die Sie mithilfe einer Nachschlagetabelle schnell finden können). Mike Bostock hat eine schöne Animation, die den laufenden Algorithmus zeigt.

Die Standardimplementierung befasst sich nur mit einem festen Mindestabstand zwischen Punkten. Der Poisson Disk-Sampling-Artikel von Herman Tulleken (einschließlich Quellcode) behandelt eine Anpassung zum Variieren des Mindestabstands an verschiedenen Stellen des Bildes. im Grunde wie ein Dithering- Algorithmus. Die Verwendung von Perlin-Rauschen / Simplex-Rauschen, wie in den Artikelwolken gezeigt, kann zu einer natürlicheren Sternenkarte führen. Zum Beispiel habe ich das Bild links verwendet, um das Bild rechts zu erzeugen:

Um dies zu tun, überprüfe ich bei der Betrachtung eines Kandidatenpunkts zuerst den Wert des Eingabebildes, der einen Wert von 0 bis 1 ergibt. Dann skaliere ich diesen auf meinen gewünschten minimalen und maximalen Abstand zwischen Punkten; In diesem Fall habe ich 5 & 20 Pixel ausgewählt. Wenn Sie also einen Punkt in den dunklen Bereichen platzieren, können meine Sterne bis zu 5 Pixel voneinander entfernt sein. Wenn Sie Sterne in den hellen Bereichen platzieren, können sie bis zu 20 Pixel voneinander entfernt sein.

Es ist erwähnenswert, dass die Beschleunigung von Bridson bei Stichproben mit variabler Entfernung nicht genau funktioniert, da die Ausgabepunkte keine einheitliche Mindestentfernung verwenden. Sie können jedoch weiterhin das Ausgaberaster verwenden, um die Suche zu reduzieren. Je kleiner das Raster ist, desto schneller wird die Suche nach den nächsten Nachbarn auf Kosten eines größeren Speichers für eine größere Nachschlagetabelle durchgeführt.

Eine sehr naive, aber einfache Lösung wäre, einfach immer die "minimale" Entfernung zu überspringen und dann einen zufälligen Betrag darüber zu hängen. Dies bedeutet, dass Sterne niemals zu Kumpel werden und Sie zumindest ein wenig Abweichung bekommen.

z.B

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

(Einfügen Ihrer bevorzugten Zufallszahlengenerierungsfunktion)

Wenn Sie die XYZ-Größe Ihres Spielfelds kennen, können Sie einen zufälligen Punkt in diesem Bereich auswählen

Führen Sie dann einen SphereCast durch, um zu überprüfen, ob bereits etwas zu nahe ist.

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

Das Problem dabei ist, dass es wahrscheinlich nicht sehr gut für Echtzeit ist, aber für vorgenerierte ist es in Ordnung und ziemlich schnell.