Aber dann hoffentlich aus dem Graphen-Teil... Nicht aus dem InsBettBringen ^^

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Ohje. Das gibts ja was.
Aber ich muss eh alles nochmal neu aufziehn.
Da mir die Struktur der klassen usw. net so gefällt.

Damit warte ich aber bis ich das menü von lossy nutzen kann

Ich baue erstmal keine KI rein, soll anfangs rein netzwerk(internet) sein.

_________________
www.audi32.de

Da bist du nicht der einzige ^^

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

denk ich mir ^^
sieht aber auch geil aus...

_________________
www.audi32.de

Darum geht's nicht. Es geht darum, dass das Konzept der GUI so genial ist. Wie das Ergebnis dann ausschaut, hängt ja von deinem Skin ab

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Also die Wegberechnung geschieht in mehreren Schritten:
1. Aufstellen der ersten Entfernungstabelle (Grunddaten, ist fix)

2. Aufstellen der Entfernungsmatrix zwischen den Planeten (Wenn Distanz in beide Richtungen gleich ist, kann man eine Dreiecksmatrix nehmen)
In dieser Matrix gibt es 4 Spalten und n^2 bzw. n+(n-1)+(n-2)+..+1 Zeilen (je nachdem ob volle oder dreieck). Die Spalten heissen: Start, Ziel, Zwischenstopp, Entfernung und werden so gelesen: Von A nach B über C ist 5 Parsecs weit. In diese Matrix trägst Du nun in Abhängigkeit der Reichweite des Schiffes für jeden möglichen Start und Zielpunkt entweder die Entfernung ein, falls das Schiff direkt fliegen kann oder unendlich, falls die Reichweite des Schiffes nicht ausreicht. Die Zwischenstopps bleiben erstmal leer, da alles Direktrouten sind.

3. Berechnen der gesamten Distanzmatrix
Dies geschieht in mehreren Durchläufen. Im Idealfall reicht einer, im Extremfall werdens log(n).
In jedem Durchlauf wird jeder Planet als theoretisches Zwischenziel C für den Flug von jedem Startplaneten A zu jedem Endplaneten B geprüft. Als Zwischenziel kommt C dann in Frage, wenn die Distanz von A nach C plus die Distanz von C nach B kleiner ist, als die Distanz von A nach B. Diese drei Distanzen werden aus der halbfertigen Matrix ausgelesen.
Wenn diese Bedingung erfüllt ist, so wird die Summe A > C + C > B in die Matrixzeile für A > B in die Spalte 'Entfernung' und C in die Spalte 'Zwischenstopp' eingetragen.
Wenn alle Cs gegen alle A > Bs geprüft sind, wird beim ersten C von vorne begonnen.
Der Algorithmus endet dann, wenn einmal alle Cs geprüft wurden, ohne dass eine kürzere Strecke gefunden wurde, d.h. keine Aktualisierung der Matrix vorgenommen wurde.

4. Diese Matrix kannst du dann theoretisch speichern und immer wieder verwenden (für alle Schiffe mit der gleichen Reichweite).

Die Matrix wird natürlich jedesmal ein anderes Ergebnis auswerfen, falls sich die Reichweite des Schiffes ändert, da dann ja mehr sinnvolle Entfernungen am Anfang in der Matrix stehen.

Die Matrix wird wie folgt benutzt:
Wenn das Schiff von A nach B will, sucht man diesen Eintrag aus (Start A, Ziel B). Wenn im Zwischenstopp nix steht, isses ein Direktflug und Du bist fertig. Wenn ein Zwischenziel drinsteht, ist dieses der Erste 'Navigationspunkt' der Route. Jetzt wiederholt man die Anfrage mit C > B un fährt fort, wie Oben (als Beispiel: D steht im Zwischenziel, dann sucht man nach D > B in der Matrix usw.).
Wenn nur die Entfernung (gesamt) zwischen A und B wichtig ist, ist man schon nach dem ersten nachschauen fertig.
Eine Besonderheit ist noch zu beachten: Bei der Nutzung einer Dreiecksmatrix (also wenn Distanz in beiden Richtungen IMMER gleich ist) muss man falls A > B nicht zu finden ist, B > A suchen und dann die Wegpunkte in der Reihenfolge umdrehen.

Die Dreiecksmatrix empfiehlt sich aber nur bei sehr vielen möglichen Quellen und Zielen und wenn es a) nicht möglich ist, die matrix vorher auszurechnen und b) der Speicherplatz begrenzt ist (sind ja mindestens drei Integer und eine Float zu speichern je Entfernungsangabe)
Fast hätt ichs vergessen: Man kann auch sofort sehen, ob ein bestimmtes Ziel überhaupt von einer bestimmten Quelle aus überhaupt erreichbar ist, nämlich wenn die Entfernung unendlich ist.

soooooooo.....

lange hab ich geschrieben, ich hoffe, das war jetzt deutsch genug

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Hmmm ja wars... Aber irgendwie isses bisl umständlich oder...
Also ich mein, dass musst du ja dann quasi für jeden Schiffstyp machen bzw. für jede Mögliche Reichweite.

Mal ne allgemeine Frage: Kann sich die Reichweite ändern, wärend des Fluges? Also der Tank langsam alle werden, und man muss nachtanken? Oder bedeutet Reichweite, dass immer beim letzten Stop wieder die Volle Reichweite zur verfügung steht.

Also ich bin der Meinung, dass es mit nem Einfachen Wegfindealgorithmus der auf nem gewichteten (ungerichteten) Graphen läuft am einfachsten ist.

Und das ginge so:
1. Du legst fest wie groß die größte Reichweite sein kann die ein Schiff haben kann. (MAXDIST)
2. Du nimmst dein Universum und machst einen Graph daraus (Musst du nur einmal machen. Beim Karte generieren):
2.1. Alle Planeten, raumbasen, Nachschubpunkte sind Knoten
2.2. Alle Planeten die zueinander eine Kürzere Entferung haben als MAXDIST besitzen eine Verbinung -> Kante -> die musst du speichern (Entweder Adjazenzmatrix(Mehr Speicher, kürzere Zugriffszeiten), oder Adjazenzliste(Minimaler Speicher, längere Zugriffszeit)) Wobei die tatsächliche Entferung als Kantengewichtung mitgespeichert wird

Du hast dein Schiff bei Planet/Knoten A stehen und möchtest nach Planet/Knoten B:
Du startest einen modifzierten A* Algorithmus, der nur über die Kanten laufen kann, welche eine kleinere Gewichtung haben, als die Reichweite deines Schiffs. Der A* liefert dir dann den Kürzesten Weg von A nach B. Wenn du bestimmte Planeten nicht passieren willst, dann könntest du den Knoten noch ne Eigenschaft mitgeben welche der A* ebenfalls beachtet. Dann nimmt liefert er dir nen Weg ohne die entsprechenden Planeten.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

ich würd auch sagen um dir ne passende antwort geben zu können müssen alle karten offen liegen: wieviel routenplanungen kommen da auf die CPU zu ?
Also Routen pro frame alle neu und das für zig schiffe oder nur alle paar sekunden für nich al zu viele schiffe usw...
Wieviele Planeten soll deine Galaxie beinhalten usw...

_________________
www.extrawurst.org

Der Trick dabei ist, dass mein Algorithmus ALLE kürzesten Distanzen und Wege auf einmal raussucht.
Das kannste dann je Schiffstyp einmal machen und speichern.
Die Entfernung findest Du dann mit einem Zugriff, die Route mit n Zugrifffen, wobei n die Anzahl der Zwischenstopps ist.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

@Sidorion: Ist dein Algorithmus zufällig der "Floyd Warshall"? Den hatten wir heute in der Vorlesung drann, und das kam mir gleich bekannt vor.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Wird nur beim angeben einer neuen Route neu berechnet...
Ist ja alles kompliziert :-/ Oh man

_________________
www.audi32.de

Keine Ahnung, aber wenn er Dir bekannt vorkam ... [edit] isser [edit]

Man kann den auch noch erweitern, indem man Gruppen bildet und von einer Gruppe in die nächste nur über bestimmte Knoten, die in beiden Gruppen vohanden sind wechseln. In den Gruppen kann man dan z.B.: nur in einer bestimmten Richtung (reihenfolge der Elemente, Einbahnstrasse) oder karthesisch (nicht diagonal) zulassen .. man kann das so kompliziert machen wie man will.
Diese Gruppeneinteilung ist z.B. eine prima Sache für Wegsuche in einem Gebäude. Die Wegpunkte in einem Raum (z.b.: an jeder Tür und in der Mitte einer) werden immer zu einer Gruppe zusammengefasst (Gang ist auch ein Raum). Die Gruppen verbindet man dann über die Punkte in den Türen, und ... vóilà kein NPC latscht mehr durch Wände (weil sie sich von Punkt zu Punkt bewegen)
[edit] der Trick ist dabei tatsächlich der, dass man in der äussersten Schleife die Zwischenstopps durchgeht, da er sonst O(n^4) hätte. Der eigentliche algorithmus hat O(n^3), aber da wird zunächst nur eine 'gute' Lösung gefunden, bzw wenn vorher nicht alle Wege uv einen sinnvollen Wert hatten, muss man den ganzen Rums nochmal machen, bis sich im letzten Durchlauf keine Verbesserung im Graphen mehr ergibt. Deshalb insgesamt O(n^3 log(n))[edit][/quote]

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Sodale ... damit ihr beim Pathfinding-Tutorial nicht mehr unbedingt davon ausgehen müsst dass die Welt in Tiles zerlegt wurde hab ich mal eine etwas allgemeinere Beschreibung der entsprechenden Algorithmen rauf gegeben :-). Das Tutorial überlass ich dann aber doch lieber euch Delphi-Programmierern. Und Grafiken hätten wohl die diversen Algorithmen auch noch not, aber ich hoffe sie sind auch so zumindest annähernd verständlich (oder ist dem etwa nicht so?).

@Flash:
Mir kam der Algo auch irgendwie bekannt vor ... jedoch is das so lange her das ich den Namen nimmer gewusst hätte. Danke da wär ich nie drauf gekommen :-).

@Topic & Sidorion:
Obwohl sich Adler (der Autor des Thread) bisher nur beschränkt dazu geäussert hat wie oft eine derartige Abfrage statt findet, und vor allem wie viele Planeten eine Galaxie hat, gibt es an deiner Methode (bzw. dem "Floyd Warshall"-Algo) diverse Schwächen die man nicht ausser Acht lassen sollte:
- Wie du bereits erwähnt hast Speicherbedarf von O(n^2) und Laufzeit zur Generierung O(n^3)
- Wenn sich das Terrain (bzw. allgemein der Graph) auch nur minimal ändert, so muss sehr viel neu berechnet werden. Planetenbewegungen werden also zur Galaxiereform
Wenn diese beiden Aspekte jedoch nebensächlich sind, so ist es wahrscheinlich tatsächlich die beste mögliche Vorgehensweise. Und da es bei mir wie bereits erwähnt eine Zeit lang her ist das ich mich mit diesem Algo beschäftigt habe, bin ich mal so frech und lasse dir im Wiki den Vortritt :-).

Da jedoch Pathfinding-Algorithmen mit Level of Detail ebenfalls eine verhältnismäßig statische Umgebung bevorzugen, wäre hier diesbezüglich auch die ein oder andere Variation von nöten, jedoch wäre dabei der Speicherbedarf verhältnismäßig gering ( O(n*log(n) einmal, also für alle NPCs (Raumschiffe) ausreichend ), jedoch wird hier nicht zwingendermaßen der optimale Weg gefunden. Wenn also Bedarf daran besteht (in diesem Thread hoff ich mal primär von Adler wenn überhaupt :-) ), dann meldet euch, denn dann werd ich das in nächster Zeit noch schreiben.

Ich ging davon aus, dass verschiedene Sonnensysteme gemeint waren, die Navigation innerhalb eines Systems ist hierbei nicht berücksichtigt. Aber da kann man ja auch noch eine Ebene einfügen: In jedem System gibt es Sprunkpunkte (wie z.b.: Elite, Privateer, .....) und welcher davon angeflogen werden muss (unterlicht) kann man ja über andere Geschichten klären.
Nach aussen hin (überlicht) ist das System dann ein Knoten und Sonnensysteme bewegen sich eigentlich in (für eine Weltraumhandelssimulation) unbedeutender Geschwindigkeit.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Wir ham nen Floyd-Warshall gelernt der nicht prüft ob sich in der Matrix was verändert hat, und trotzdem geht:
!PSEUDOCODE!

_________________
Blog: kevin-fleischer.de und fbaingermany.com