Das setzt aber eine sortierte Matrix vorraus, in der die initialen Verbindungen am Anfang stehen, im Allgorithmus alle Wege <k bereits als kürzeste vorrausgesetzt werden.
Kann dies nicht gewährleistet werden, ist das Ergebnis des ersten Durchlaufs eine Näherungslösung, nicht jedoch die fertige.

_________________
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.

Nun das was unter Initialisierung steht muss natürlich gemacht sein.
Aber auch wenn die direkte Verbindung nicht die kürzeste ist geht das, denn die FUnktion Minimum() regelt das dann. Ich habs mal an nem kleinen Beispiel durchprobiert und es ging. Hat mich auch verblüfft

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

Die äußerste Schleife (repeat.. until) ist ja nur dafür da, sich vorher die Sortierung zu sparen und wird im Idealfall 2mal durchlaufen. Einmal zur Berechnung und nochmal zur 'Überprüfung'.

_________________
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.

Gut, zu deiner Auswahlgeschichte:

Du spannst den Vektor von deinem aktuellen Ort in Richtung des Ziels. (Dieser Vektor ändert sich bei jedem Planeten)

Nun berechnest Du den Winkel zwischen diesem Vektor und jedem Vektor vom jetzigen Standpunkt zu einem der Planeten. Ist dieser Winkel größer als 90°, dann liegt der Planet hinter Dir und kann ignoriert werden.

Nun berechnest Du aus allen Planeten, die vor Dir sind eine Liste, in der die Entfernungen vom jetzigen Standpunkt zum Planet enthalten ist. Weiterhin noch alle Entfernungen zwischen den Planeten, sowie die Entfernung zum Ziel-Planeten.

Ziel ist es nun, die Kombination zu finden, für die gilt:
Minimum(Restabstand) AND WegZuPlanet<TankReststrecke AND (Minimum(WegZuPlaneten) OR WegZuPlaneten + WegZuNächstemPlaneten)

Es zeigt sich übrigens, dass diese Funktion rekursiv zum Pathfinding genutzt werden kann, wenn Du als Rückgabewert den Index des nächstliegenden Planeten immer zurückgibst.

Edit: Evtl. könnte man diese Methode des Pathfindings noch im Pathfinding2-Tutorial ergänzen\erwähnen.

_________________
Administrator of Project Omorphia

Das kostet doch massiv zeit. (Du musst ständig irgendwelche Winkel berechnen. Wenn du die per dynamischen Programmieren mitloggst, dann hast du ohne Ende Speicher verbraucht.)

Und es ist nicht sichergestellt, dass das Ziel gefunden wird, denn u.U könnte der Einzige weg zum Ziel der sein, der erstmal nach hinten führt und dann im "weiten Bogen" wieder nach vorn. Klingt nach Erbsenzählen, muss aber beachtet werden.

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

@Flash: Gut, dass die Winkel-Optimierung jetzt nicht die schnellste ist und stellenweise sogar falsch ist (wenn es keinen Planeten zwischen Player und Ziel gibt, von dem aus man direkt, ohne Nachtanken zum Ziel gelangen kann) stimmt. Hier ging's aber auch um die Theorie...

Zu den Winkel-Berechnungen: Stimmt nicht ganz: Die Winkel zwischen den Planeten können statisch berechnet werden. Ein Update ist nur dann, wenn sich irgendwelche Abstände (durch Planetenbewegung) ändern. Aber selbst dann wäre diese Tabelle maximal n^2 Einträge groß.

Weiterhin sei angemerkt, dass man dieses Vorgehen stark vereinfachen kann, wenn man die Map zwischen den Planeten in eine dynamische Backtracing-Map einträgt, wie ich in der Diskussion des 2. Pathfinding-Tuts auf eine von mir (ich weiß) grausam programmierte bereits hingewiesen hab. Dann reicht es nämlich, einen der nächstgelegensten Planeten anzufliegen, die gerade noch erreichbar sind und den niedrigsten Kostenfaktor haben. Bei Fragen zu dieser Unit bitte bei mir melden ... Dann wären nämlich gleich mehrere Probleme auf einmal behoben:
1. Man fliegt IMMER den kürzesten Weg
2. Nur gültige Wege werden überhaupt angeboten
3. Eine Winkelbestimmung ist nicht notwendig
4. Die Distanz-Bestimmung beschränkt sich auf den kartesischen Abstand zweier Punkte (wenn keine Hindernisse im Weg sind).
5. Diese Cost-Map kann einmalig berechnet werden und ist dann IMMER gültig, solange sich Abstände nicht ändern. Eine Neuberechnung ist relativ schnell möglich (mit meinem Algo bei 1280x1024 Datenpunkten in ca. 3 Sekunden bei 1,4 GHz.

_________________
Administrator of Project Omorphia

Ich stör' euch ja nur ungern... Aber das hier ist das Einsteiger-Forum

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