Ich erstelle ein 2D-Spiel für eine Website, auf der das Universum extrem groß werden kann (im Grunde unendlich groß). Das Universum besteht zunächst aus 6 Sternen, die gleich weit vom Ursprung entfernt sind (0, 0). Meine Aufgabe ist es, mehr Sterne zu erzeugen, die "Pfade" (Kanten) haben, die miteinander verbunden sind. Wie kann ich einen Algorithmus entwerfen, der diese Einschränkungen erfüllt:
- Sterne werden zufällig nach außen erzeugt. (zB (x, y) -Koordinaten für neue Sterne gehen langsam von (0, 0) in alle Richtungen nach außen, vorzugsweise im Spiralformat)
- Kanten werden NICHT gekreuzt.
- Obwohl es einige Abweichungen geben sollte, sollten neue Sterne nicht zu weit oder zu nahe an anderen Sternen sein. (ZB muss es einen Mindestradius geben)
- Kein Stern / Punkt sollte eine Vielzahl von mehr als 3 haben.
- Da all dies in einer Datenbank gespeichert wird, kann der Algorithmus nicht zu kostspielig sein. Mit anderen Worten, ich würde gerne etwas von O (n) -Komplexität erreichen (ich weiß nicht, ob dies machbar ist).
Im Wesentlichen strebe ich eine spiralförmig aussehende Galaxie an, in der die Sterne Punkte in der Grafik sind und die Bewegung zwischen Sternen durch Kanten zwischen diesen Sternen dargestellt wird.
Die besonderen Schritte, die ich lösen muss, sind:
- Erzeugen Sie zufällig einen Punkt in der benachbarten Umgebung anderer Sterne, die noch keine Multiplizität von 3 haben.
- Finden Sie den ersten Stern, der noch keine Multiplizität von 3 hat und keinen Kantenkonflikt erzeugt.
- Wenn der Stern einen Mindestabstand von x Einheiten hat, erstellen Sie eine Kante zwischen den beiden Punkten.
Ich habe versucht, nach Lösungen zu suchen, aber meine mathematischen Fähigkeiten (und Kenntnisse in Graphentheorie) erfordern viel Arbeit. Auch alle Ressourcen / Links zu diesem Thema wären sehr dankbar.
Hier ist ein Pseudocode, an den ich gedacht habe, aber ich bin mir nicht sicher, ob dies überhaupt funktionieren würde, und ich bin mir sicher, dass er nach ein paar 10.000 usw. Sternen nicht besonders gut funktionieren würde.
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) coordinateWenn jemand einen Rat hat, wie ich dies in einer MySQL-Datenbank speichern soll, würde ich das auch begrüßen.
Für den Fall, dass oben nichts Sinn macht, habe ich unten ein Bild von dem beigefügt, was ich erreichen möchte:
quelle
Antworten:
Vorschlag: Halten Sie das interne Universumsnetzwerk perfekt geordnet, algorithmisch und relativ einfach. Das Universum muss nur zufällig aussehen, wenn es auf dem Benutzerbildschirm angezeigt wird . Wenden Sie für die Benutzeranzeige nur zufällige Offsets auf die Sternpositionen an.
Problem: Der naheliegendste Ansatz, einen zufälligen Versatz für jeden Stern zu berechnen, kann die zugrunde liegende wahre Struktur nicht sehr gut verbergen. Sie können Sterne nur geringfügig randomisieren, bevor sie miteinander kollidieren oder sich kreuzen können.
Lösung: Sie können große zufällige Verzerrungen anwenden und ein viel zufälligeres und interessanter aussehendes Universum erhalten, wenn Sie koordinierte nicht-lokale Zufälligkeiten anwenden. Stellen Sie sich vor, Sie platzieren die Sterne auf einer Gummiplatte und stellen sich vor, Sie würden verschiedene Teile der Folie zufällig dehnen und zerquetschen. Das kann eine ganze Gruppe von Sternen um eine lange Strecke verschieben. Sie werden niemals kollidieren oder sich kreuzen, weil sich nahegelegene Sterne im Verhältnis zueinander dehnen und quetschen.
So geht's: Suchen Sie nach Generatoren für fraktales Gelände. Es gibt viele kostenlose und offene Codes dafür. Sie benötigen nur Basiscode, der für jeden Punkt auf einer Karte einen Höhenwert generiert. Wir werden es anders verwenden. Verwenden Sie diesen Code, um ZWEI unabhängige Geländehöhenkarten zu erstellen. Beginnen Sie mit der wahren X-, Y-Position des Sterns, sehen Sie sich diese Position auf jeder Karte an, verwenden Sie einen Kartenwert, um die X-Anzeigeposition des Sterns zu versetzen, und verwenden Sie den anderen Kartenwert, um die Y-Anzeigeposition des Sterns zu versetzen. Sie müssen mit einigen Skalierungsfaktoren spielen, aber das kann Ihnen den zufällig verzogenen Gummiplatteneffekt geben. Die großen Variationen in der Sternposition sollten die zugrunde liegenden geordneten Positionen vollständig verbergen. Die fraktale Natur der Zufälligkeit ergibt einen sehr natürlich aussehenden Effekt.
quelle