Algorithmus um (System)Karten zu erzeugen?

[odenter]

Ich habe eine Liste vom Typ System, wobei jedes Objekt wiederrum eine Liste von Systemem hat.
Ich will nun irgendwie, wie weiss ich noch nicht, diese Systeme verbinden, natürlich so das am Ende alle Verbunden sind und idealerweise alle nicht einfach nur eine Kette bilden, das hätte ich hinbekommen. :)

Gibt es dafür etwas fertiges?
Und wenn nein, wie macht man sowas? Hab sowas selbst noch nie gemacht und weiss auch gar nicht so richtig wonach ich suchen soll.
Die Liste der Systeme erzeuge ich aktuell mit rand() genauso wie deren Inhalte, schön wäre etwas, dass ich mit einer Nummer füttere und mir mit der gleichen Nummer auch immer wieder die gleichen Systeme erzeugt.

Ich vermute mal ich brauche dafür mindestens einen echten Zufallszahlengenerator, gibt es da einen guten der zu empfehlen ist?

In einem anderen Forum ist mir das hier http://jongware.com/galaxy1.html empfohlen worden, habe das allerdings nur kurz überflogen, sieht doch etwas komplex aus. :)

[eXile]

Wäre gut, wenn du noch sagen würdest, was du überhaupt mit "System" meinst, und wofür du das eigentlich brauchst.

Ansonsten hört sich das Problem nach einem planaren Graph an, man könnte darauf z.b. einen minimalen Spannbaum berechnen.

[Aramis]

Ich denke mal, es geht um (Sternen)-Systeme.

Die Liste der Systeme erzeuge ich aktuell mit rand() genauso wie deren Inhalte, schön wäre etwas, dass ich mit einer Nummer füttere und mir mit der gleichen Nummer auch immer wieder die gleichen Systeme erzeugt.

Du kannst den CRT-Zufallsmixer mit srand neu aussähen, dann sind die 'Zufalls'-zahlen die er ausspuckt bei jeder Programmausführung identisch.

[odenter]

Mit "Systeme" meine ich Planeten-Systeme. Und ich will damit eine Galaxy erzeugen und diese eben mit Systemen und jedes System mit Planeten erzeugen.

[Despotist]

Ich will nun irgendwie diese Systeme verbinden,

Ich nehme an damit meinst du Portale, Jumprouten oder ähnliches also rein navigatorisch? Ansonsten ist meine Antwort nutzlos.
Deine Systeme werden ja sicher 2d oder 3d Koordinaten haben. Dann könntest du einfach für jeden Stern den Abstand zu allen anderen Sternen berechnen. Dann bestimmst du mit einer Funktion die abstandsabhängige Wahrscheinlichkeit dass eine Verbindung existiert. Mit einer Zufallszahl kannst du dann gegen diese Wahrscheinlichkeit prüfen ob eine Verbindung erzeugt wird oder nicht.
Beispiel:
Deine Abstandswskfunktion verläuft linear zwischen 2 und 6 Lichtjahren. Also bei Abständen unter 2 ly wird immer eine Verbindung erzeugt und bei größer 6 nie. Du ermittelst also zwischen zwei Systemen einen Abstand von 4 ly und daraus folgt eine Wsk von 0,5. Dann bemühst du deinen Zufallszahlengenerator zwischen 0 und 1 und der spuckt dir 0,7 aus. Also kannst du in diesem Fall eine Verbindung erzeugen. Alle Verbindungen kannst du in eine eigene Klasse packen die die Systeme an beiden Enden kennt und die Positionen in den Systemen und evtl eine Reisedauer/Länge oder sowas. Die beiden Systeme kennen dann zb bloß den Index oder die Referenz des Verbindungsobjektes.

schön wäre etwas, dass ich mit einer Nummer füttere und mir mit der gleichen Nummer auch immer wieder die gleichen Systeme erzeugt.

Das ist beim Pseudozufallszahlengenerator gegeben. Mit demselben Seed erzeugt er immer dieselbe Abfolge von Zufallszahlen. Im Idealfall kannst du so mit einem Seed das ganze Universum kreiren und speichern. Wenn du allerdings einen echten Zufallsgenerator (weißes Rauschen) nimmst ist dein Universum jedes mal anders und du musst es selbst speichern.
Es gibt einige hübsche Artikel zum Thema prozedurale Universen. Wenn du nichts findest sag bescheid dann such ich mal ein paar Links aber im Moment bin ich zu faul ;) Da werden aus einem Wert ganze Galaxien mit Planeten mit Echtzeit-Oberfläche gebaut. Z.B. Infinity Universe.

Ich vermute mal ich brauche dafür mindestens einen echten Zufallszahlengenerator, gibt es da einen guten der zu empfehlen ist?

Das sind extra Bauteile (zb Radioempfänger oder Geigerzähler) die zufällige Prozesse messen. Alle Zufallszahlen im Computer sind algorithmisch berechnet und damit deterministisch was aber auch seine Vorteile hat. Wichtig sind die Eigenschaften der Zufallszahlen da alle Methoden früher oder später die Reihe wieder von vorn beginnen. Auch die Qualität der Zahlen ist wichtig (gleichverteilt). Schau dir mal "Mersenne Twister" an.
Was du auch machen kannst ist immer neu zu seeden. Z.B. lässt du dir für ein System die Anzahl der Planeten bestimmen (z.B. 5). Dann gehst du durch alle durch und bestimmst zufällig den Seed für jeden (4, 167, 59, 213, 80). Wenn du jetzt die eigenschaften eines Planeten erzeugst (Masse, Größe, Atmosphäre) fütterst du den Seed für jeden.

Ich befasse mich auch mit sowas (bisher nur theoretisch). wir können uns also mal bei Gelegenheit austauschen.

Gruß
Despotist

[odenter]

Austauschen können wir uns gerne mal.

Ich hab heute mal ein bischen gebastelt und ich mache nun folgendes. Ich erzeuge beim Start eine Galaxy mit Systemen und Planeten, allerdings erstmal recht simpel.
Jedes System hat einen Vector, anhand dessen bestimme ich später, auch sehr simpel, die Entfernung zu bis zu 10 anderen Systemen und verbinde diese so.

Funktioniert recht gut, allerdings muss ich jetzt erstmal Code schreiben um die Map zu rendern, damit ich mal sehe wie das tatsächlich aussieht.

[odenter]

Also es geht zumindest schonmal, allerdings ist das was ich da aktuell mache nur bei wenigen Sternen-Systemen brauchbar (Bild im Anhang).
Wenn es mehr werden dann sieht das aus wie ein Salat aus Linien. :D

Da werde ich wohl noch ein bischen Zeit investieren müssen.

[Despotist]

Du bist leider ein wenig unklar was deine Fragen und Probleme betrifft und auch was deinen Status betrifft. Beschreibe doch grob was du gemacht hast und wie du es dir vorstellst und wir können versuchen dir zu helfen da hin zu kommen. Einfach ein Bild posten ist zu vage ;)

Falls du es so ähnlich gemacht hast wie ich vorgeschlagen habe kannst du es einfach über die 3 Parameter Minimum, Maximum und Wahrscheinlichkeitsfunktion dazwischen steuern. In dem Bild sieht es aus als würdest du fast jeden Stern mit jedem verbinden also musst du an den Parametern schrauben bis sie deinen Vorstellungen entsprechen.

Und ich weiß ja noch nichteinmal ob meine Vermutungen bezüglich deiner Ziele stimmen ;) Also das mit den Routen die jeweils 2 Sterne verbinden.

Gruß
Despotist

[exploid]

...

[odenter]

Status ist ich erzeuge eine Galaxie mit Sternen-Systemen und verbinde diese Systeme, bisher nur über die X-Koordinate des Vectors, eines Systems mit dem nächsten System sofern diese einen bestimmten Wert unterschreitet. Sobald eine bestimmte Anzahl Verbindungen, aktuell 4, erreicht ist gehts zum nächsten System.

Die Verbindungen sollen, wie Du vermutet hast, "Reise-Verbindungen" zwischen den Systemen sein.

Aktuell sind das 3D Koordinaten, ich bin mir noch nicht sicher ob ich bei 3D bleibe, oder doch erstmal nur 2D-Koordinaten verwende. Ursprünglich wollte ich eine 3D Karte haben, wie gesagt 2D wird wohl erstmal einfacherer sein.

Mein Problem aktuell ist das es einfach scheisse aussieht, das liegt aber daran wie ich die Systeme bzw. deren Position erzeuge. Also die Sternen-Systeme sind völlig zufällig verteilt.

Code: Alles auswählen

irr::core::vector3df Galaxy::getRandomSectorCoordinates(irr::u32 maxSectors, irr::u32 systemIndex) {
  irr::s32 x, y, z;
  srand(maxSectors + (systemIndex * 10) );
  irr::u32 init = rand();
  srand(init);
  //init = rand();
  //srand(init);
  x = rand() % maxSectors;
  y = rand() % maxSectors;
  z = rand() % maxSectors;
  x = (x >> 1);
  y = (y >> 1);
  z = (z >> 1);
 irr::core::vector3df rtnVal(x, y, z);
  return rtnVal;
}

Habe mir dazu heute mal das hier
http://www.gamedev.net/reference/articl ... le1337.asp
kurz angeguckt, solch eine Verteilung gefällt mir besser.

In meinen Augen ist alles soweit fertig, nur der Algorithmus zum erzeugen muss jetzt angepasst werden so das auch vernünftige Ergebnisse produziert werden.

Naja was noch fehlt ist eine Prüfung auf doppelt vorhandene Koordninaten, das war bisher unperformant was ich da gemacht habe, jeden Vector in eine List und dann jeden erzeugten gegen die Liste prüfen und ggf. solange neue erzeugen bis ein wirklich neuer erzeugt wurde. Schon bei 1000 Systemen, lief das mehrere Minuten. Ist ja auch klar bei steigener Anzahl Objekte muss immer mehr geprüft werden.

EDIT:
Danke für den Link, werde ich mir die Tage mal genauer anschauen.

[odenter]

Ja, das sieht doch schonmal nach ner Galaxy aus, muss jetzt nur noch performant werden und die Verbindungen müssen besser hergestellt werden. :)

[Despotist]

verbinde diese Systeme, bisher nur über die X-Koordinate des Vectors, eines Systems mit dem nächsten System sofern diese einen bestimmten Wert unterschreitet. Sobald eine bestimmte Anzahl Verbindungen, aktuell 4, erreicht ist gehts zum nächsten System.

Wenn ich dich richtig verstehe erzeugst du ein System und fügst gleich im Anschluss die Verbindungen ein bevor das nächste System erzeugt wird?
Wenn ja ist das quatsch. Du musst erst alle Systeme an den Positionen erzeugen wo sie deiner gewünschten Verteilung entsprechen (z.B. Milchstrasse) und DANACH die Verbindungen hinzufügen. Sonst kann es sein dass nur weit entfernte Systeme vorhanden sind nach der Erzeugung.

Wenn jedes System fest mit 4 anderen verbunden ist das evtl nicht so schön. Vielleicht solltest du die Zahl auch zwischen 3 und 5 oder 2 und 7 würfeln.

Auch kannst du nicht nur über die x-Koordinate gehen.

Mach ruhig 3d. Wenn du dieselbe Anzahl Sterne in 2d quetschst wirds nicht übersichtlicher ;)

Mein Problem aktuell ist das es einfach scheisse aussieht, das liegt aber daran wie ich die Systeme bzw. deren Position erzeuge. Also die Sternen-Systeme sind völlig zufällig verteilt.

Ich nehme an mit der Verteilung der Sterne bist du zufrieden nur die Zuweisung der Routen stört dich? Dann musst du auch nur das ändern ;)

Mein Vorschlag in pseudocode:

Code: Alles auswählen

int actnumberofstars = 0
vector3d position
bool badstar
for i = 0 to numberofstars
{// für die gewünschte anzahl an sternen
	do{
		badstar = false
		position = randomvector()	// erzeuge eine position im 3d raum
		for(j = 0 to actnumberofstars)
		{// gehe durch alle bereits erzeugten sterne und prüfe ob die abstände größer als ein grenzwert sind
			if(distance(position, stararray[j].position) < mindistance)
			{// prüfe den abstand des aktuellen sterns (j-schleife) zur erzeugten position wenn zu klein erzeuge neue
				badstar = true
			}
		}
	}while(!badstar)
	// sobald also eine position gefunden wurde die nicht zu nah an einem anderen stern liegt wird schleife verlassen und neuer stern mit der position erzeugt
	stararray[i] = new star(position)
}
// nun hast du alle sterne mit ausreichendem abstand zueinander platziert und kannst die verbindungen erzeugen
for i = 0 to numberofstars
{// für die gewünschte anzahl an sternen
	for j = 0 to numberofstars
	{
		if i != j
		{// nicht mit sich selbst testen
			if(distance(stararray[i].position, stararray[j].position) < maxroutedistance)
			{// prüfe den abstand beider sterne, wenn klein genug erzeuge verbindung
				createroute(stararray[i],stararray[j])
			}
		}
	}
}

Dadurch werden erstmal alle Sterne mit ihren nächsten Nachbarn verbunden die näher als maxroutedistance dran sind und zwar unabhängig von deren Anzahl. Wenn du aus diesen potentiell vielen z.B. eine bestimmte Anzahl raussuchen willst musst du dir die Indices merken und wenn du alle hast deine Routen erzeugen.
Bedenke aber das je nach Abstand und Positionierung deiner Sterne auch einige mit garkeinen Verbindungen vorkommen können. Diese musst du dann verschieben oder löschen oder mit langen Routen/Wurmlöchern verbinden oder sowas.

Naja was noch fehlt ist eine Prüfung auf doppelt vorhandene Koordninaten, das war bisher unperformant was ich da gemacht habe, jeden Vector in eine List und dann jeden erzeugten gegen die Liste prüfen und ggf. solange neue erzeugen bis ein wirklich neuer erzeugt wurde. Schon bei 1000 Systemen, lief das mehrere Minuten. Ist ja auch klar bei steigener Anzahl Objekte muss immer mehr geprüft werden.

Bei der einmaligen Erzeugung der Galaxis spielt Zeit nicht so die Rolle wobei viele Minuten schon lange sind. Nimm statt einer Liste ein Array das spart dir ne Menge Zeigerdereferenzierung.

Gruß
Despotist

[odenter]

Natürlich werden erst alle Systeme erzeugt und dann im Anschluss alle Verbindungen, werde den Code von Dir morgen mal einbauen.

[Despotist]

Eine weitere Möglichkeit den Vergleich zu beschleunigen ist, bei der Berechnung des Abstandes nicht die Wurzel zu ziehen. Dann musst du natürlich auch gegen das quadrierte Element (z.B. sqauredmaxdistance) testen.
Die Squareddist-Funktion könnte also so aussehen:

Code: Alles auswählen

sqDistance(star *a, star *b)
{
    return ((a->pos.x * b-> pos.x) + (a->pos.y * b-> pos.y) + (a->pos.z * b-> pos.z))
}

Ansonsten ist sowas schwer zu sagen. Wie viele Sterne hast du denn insgesamt? Und werden die bisher nur mit ihrer Position erzeugt oder auch mit Eigenschaften und Planeten?

Despotist

[klickverbot]

Die Squareddist-Funktion könnte also so aussehen:

Code: Alles auswählen

sqDistance(star *a, star *b)
{
    return ((a->pos.x * b-> pos.x) + (a->pos.y * b-> pos.y) + (a->pos.z * b-> pos.z))
}

Und wo genau berechnest du hier einen Abstand? (Stichwort: Subtraktion)

[odenter]

Ich hab 100.000 Sterne mit bis zu 10 Planeten,teilweise werden die Eigenschaften schon dynamisch erzeugt/gesetzt.

Allerdings hab ich noch ein anderes schönes Performance Problem, hab schon im Forum zur Engine nachgefragt. Das rendern der 100.000 Sterne, die alle als Sphere dargestellt werden ist hochgradig unperformant. Allerdings kann ich so einfach das angeklickte Objekte bekomme, sind alles sog. Nodes, durch klick auf einen bekomme ich mein internes System-Objekt wo ich dann Name, Beschreibung und Liste der Planeten habe.

Hab schon überlegt quasi ein Bild zu rendern, in dem einzelne Pixel, eben ein Stern sind. Wäre mit Sicherheit deutlich schneller, aber dann kann ich nicht so zoomen wie ich mir das ursprünglich vorgestellt habe. Naja darüber diskutier ich ja auch im Engine-Forum.

[Aramis]

Für so enorm viele Objekte wird es nicht ausreichend sein sie einfach als ganz normale Nodes im 'flachen' Szenengraph zu halten .. das ganze wird dann viel zu langsam, von den Such&Cullzeiten her. Auch das von dir beschriebene Problem nur mit enormem Zeitaufwand (O[n^2]) doppelte Koordinaten herausfischen zu können, deutet auf eine mangelhafte Datenstruktur hin ...

Ein Octree wäre der Klassiker um spatial partitioning in einem 3D-Raum zu betreiben .. ggf. ist eine auf die typische Form einer Galaxis spezialisierte Datenstruktur aber geschickter (nur so als unausgegorene Idee: Spiralarme der Galaxis als erste Ebene, dann jeden Spiralarm nochmals in Untersektoren unterteilen ..).

Zum Rendern: LOD! Alle Sterne die nah genug sind, dass man sie wirklich wahrnimmt als Spheren rendern, mit (von irrLicht vermutlich nicht unterstützem :-)) Instancing kein Problem von der Grafikleistung her. Entfernte Sterne .. naja, Krishty's Sternenartikel ist die Nobelvariante, nur einzelne Pixel zu zeichnen wird hemmungsloses Flimmern produzieren. Als letzte Optimierung ganze Sektoren in Billboards vorrendern und nur alle paar Frames aktualisieren.

[Despotist]

Und wo genau berechnest du hier einen Abstand? (Stichwort: Subtraktion)

Sorry, muss natürlich

Code: Alles auswählen

return ((a->pos.x - b->pos.x)^2 + (a->pos.y - b->pos.y)^2 + (a->pos.z - b->pos.z)^2)

heißen. Wenn man müde ist sollte man keinen Code raushauen der einem nicht selbst um die Ohren fliegen kann ;)

Darum geh ich jetzt auch ins Bett.

Trotzdem wäre korrigieren besser als nörgeln ;)

@odenter:
Ich hatte dich schonmal auf Infinity Universe geschubst aber du scheinst es verpasst zu haben. Darum hier nochmal ein expliziter Link der einige deiner Fragen adressieren dürfte.

Despotist

[Krishty]

Den Operator ^ gibt es für Floats nicht ;) Ist vielleicht Klugscheißerei, aber einen Thread, warum ^ nicht wie gewollt funktioniert, gibt es alle paar Monate.

Code: Alles auswählen

template <
    typename t_Type
> inline t_Type Square(
    t_Type const & p_Value
) {
    return (p_Value * p_Value);
}

return (Square(a->pos.x - b->pos.x) + Square(a->pos.y - b->pos.y) + Square(a->pos.z - b->pos.z));

& durch & ersetzen.

[odenter]

Das ganze auf einen Octree umzustellen wäre kein Problem, dafür müsste ich nur ein paar Zeilen anpassen.
EDIT:
Problem hat sich beseitig, einfach nur einmal an die Graka senden und rendern, statt 100.000 mal und schon gehts schnell. :D

Wie ich das suchen nach doppelten beschleunigen kann weiss ich schon, muss dafür allerdings den Code zum erzeugen der Sterne nochmal anpassen, so dass keine floats rauskommen sondern nur Ganzzahlen, diese kann ich dann als Indizes verwenden.
Oder mit ner std::map<intX, std::map<intY, std::map<intZ, System*>>>, dann geht das suchen maximal schnell.

Also die Engine zeigt schon nur Objekte an die man sieht, also weiter entfernte werden nicht gerendert bis man näher kommt, keine Ahnung nach welcher Regel die das machen, hat mich auch nie interessiert ich wollt das ja nur benutzen. :D
Das ganze nochmal in Sektoren zu zerlegen gefällt mir eigentlich ganz gut, ich denke das ist auch nicht dramatisch.
Das würde auch mein Problem beim rendern der Map erledigen, da ich das dann zwei Stufig machen könnte, alle Sektoren rendern und bei Auswahl eines Sektors eben die enthaltenen Sterne.

Das infinity Universe habe ich auch nur kurz überflogen, 24h pro Tag sind einfach zu wenig. :) Ich komme eh erst wieder richtig ab Donnerstag dazu was zu machen. Spätestens nächstes Wochenende gucke ich mir das nochmal genauer an.

[odenter]

So hab mal ein bischen rumprobiert und den Code zum erzeugen der Galaxy inkl. Systeme nochmal überarbeitet, um mal ein bischen die Geschwindigkeiten zu testen.

Also Galaxy wird zerhackt in Sektoren, die jeweils eine bestimmte Anzahl Sterne haben sollen. (Später für das rendern der Map)
Lange Rede kurzer Sinn ich benötige jetzt 48 Sekunden um um bei einer Eingabe von 1.000.000 Sternen, wobei ein Stern 10 Planeten enthalten soll) 100489 Sektoren mit jeweils 10 Sternen zu erzeugen und jeder Stern enthält 10 Planeten.
Also werden 1.004.890 Sterne erzeugt und 10.048.900 Planeten.
Der Speicehrverbrauch geht dafür nur einmal auf knapp 600 MB hoch, ist die Liste der schon vorhandenen Positionen.
Da dies allerdings nur Testcode ist, muss ich jetzt wohl aufpassen bei den Eigenschaften die ich meinen Sternen und Planeten gebe, also vielleicht nicht ein 32 Bit Int für einen Wert sondern einen 32 Bit Int für 32 Werte. :x

Werde den Testcode nun so abändern, das nur die Positionen erzeugt werden und das Objekt selbst (also Sternen-System inkl. Planeten) tatsächlich lazy initialisiert wird. So dürfte der Speicherverbrauch nochmal deutlich absinken. :)

[Krishty]

Ein paar Tipps für geringeren Speicherverbrauch am Rande:

Falls du noch XP nutzt, aktiviere den Low-Fragmentation-Heap.

Ein besonderer Allocator für die ::std::maps könnte die Effizienz enorm steigern, wenn du schon vorher weißt, wieviele Sterne und Planeten du erzeugst.

Achte auf das Alignment der Klasse, d.h. sortiere die Elemente der Größe nach oder trickse mit #pragma pack. Das kann manchmal genauso viel bringen wie Bit-Fields.

Falls deine Planeten virtuelle Funktionen enthalten, sind das schon 40 MB allein für die vftables. Da könnte ein anderes Dispatching-Verfahren vielleicht was rausholen – kA, ob es dir die 7 % wert sind.


Schon Ideen für das Rendern weit entfernter Sterne?

[odenter]

Hier auf der Arbeit habe ich noch ein WindowsXP (32Bit) zuhause habe ich ein Windos 7 (64Bit). Werde mir das mit dem Heap trotzdem mal angucken.

Ansonsten bin ich jetzt bei ~16 MB Speicherverbrauch. :-P
Dafür erzeuge ich nun natürlich auch kaum noch was, sondern nur noch die Anzahl der Sektoren, diese werden mit Ihren Koordinaten (0,0), (0,1), (0,2) usw. in meine

Code: Alles auswählen

std::map<int, std::map<int, Sector*>> _sectorList;

geschrieben.
Und alle sichtbaren Sektoren werden halt just in Time initialisiert, genauso wie dann auch die Planeten. Muss nur noch Code zum speichern/laden bauen.
Ich werde die Sternen-Karte erstmal in 2D rendern, so brauche ich dann nur die Sektoren rendern in dem man sich befindet und die angrenzenden. Damit ist das Problem erstmal weg.

Sollte dann später, falls ich mal Lust habe, aber auch relativ leicht auf 3D umstellbar sein, so wie der Code aktuell ist.
So mach nun Feierabend und muss zur Mathe Nachhilfe (ich hasse Mathe). :)

[odenter]

So das Problem das da mal war ist keins mehr.

Nur zur Info für alle die sich hier rege beteiligt haben. :)
Ich zerlege die Galaxy nun in Sektoren (Test-Screenshot) im Anhang. Verbindungen zwischen den Systemem wird es nicht mehr geben. Es gibt einfach verschiedene Jumpdrives mit unterschiedlichen maximal Entfernungen.

Rendern werde ich nun nur eine Handvollsektoren (im Screenshot sind noch mehr), nämlich diejenigen die in Reichweite liegen, diese werden auch entsprechend initialisiert. Die Galaxy/Sektoren-Karte wird nun also doch 3D statt 2D.

[Loebl]

Wenn ich dich richtig verstehe sollen
1. alle Sterne irgendwie miteinander verbunden werden (man kommt von jedem beliebigen punkt via Route zu jedem anderen beliebigen Stern)
2. nicht zu lang
3. nicht überkreuzen

Ich hatte mal was ähnliches, hab dann aber umkonzipiert und bin übers drübergucken nicht hinausgekommen.
Vielleicht hilft dir das weiter?
http://de.wikipedia.org/wiki/Delaunay-Triangulation

[eXile]

Wenn ich dich richtig verstehe sollen
1. alle Sterne irgendwie miteinander verbunden werden (man kommt von jedem beliebigen punkt via Route zu jedem anderen beliebigen Stern)
2. nicht zu lang
3. nicht überkreuzen

Ich hatte mal was ähnliches, hab dann aber umkonzipiert und bin übers drübergucken nicht hinausgekommen.
Vielleicht hilft dir das weiter?
http://de.wikipedia.org/wiki/Delaunay-Triangulation

Eine Delaunay-Triangulation ist 1. keine Triangulation minimaler Länge, und 2. nur eine Triangulation - vielleicht will man ja sowas wie Vierecke im Wegenetz haben, etc. Meiner Meinung nach lediglich als Ansatz verwendbar, danach müsste man viele Verbindungen zufällig wieder löschen, und "lange" Verbindungen (kreuzungsfrei) wieder hinzufügen.

[exploid]

...

[dronus]

Eine Delaunay-Triangulation ist 1. keine Triangulation minimaler Länge, und 2. nur eine Triangulation - vielleicht will man ja sowas wie Vierecke im Wegenetz haben, etc.

Eine Triangulation minimaler Länge ist NP-hart. das möchte man lieber nicht in Spielen haben ...sowas scheints in Office schon genug zu geben :-]
Ich denk Delaunay sieht für den Betrachter angenehm und plausibel aus. Man kann dann ja contentbasiert Linien löschen, z.B. wenn Sternenvölker im Clinch liegen ...