Ok, ich vestehe die Überlegung aber die Technik dahinter noch nicht ganz.
Das Attribut ".value" der Nodes wird wie es mir scheint derzeit überhaupt nicht benötigt oder irre ich mich dabei? Ich kann nicht erkennen, dass das value der Nodes an irgendeiner Stelle im Script Verwendung findet.
...
Du musst unterscheiden zwischen den EXAKTEN Kosten (die habe ich cost genannt) und den GESCHÄTZTEN Minimalkosten (die habe ich value genannt). Die geschätzten Minimalkosten sind nur um zu bestimmen, welchen Knoten du dir als nächstes anguckst. Sie werden also in der Sortierung der Knoten abgefragt. Ansonsten wird immer mit den exakten Kosten gearbeitet. Logisch, dich interessiert ja nicht ob es einen kurzen Weg zum Ziel geben KÖNNTE (denn mehr sagen dir die Minimalkosten nicht, sie sind nur eine Heuristik/Schätzung), sondern ob es auch einen gibt.
Zitat
Dieser Wert stammt noch aus einer alten Version. Er stammt daher, dass der "speed_factor" für jedes Node zwischen 125 und 1000 liegt, falls ich die Distanz im normalen Zustand einbringe würde sie kaum einen Effekt finden, das heist es würde niemals der kürzeste Weg sondern immer der Weg mit den kleinsten Kosten gesucht werden.
Der Wert 350 an dieser Stelle war nur ein Platzhalter um die Kraft des "speed_factors" auszubalancieren.
...
Wie gesagt: Es sind geschätzte Minimalkosten. Das heißt du darfst nicht einfach irgendeinen Mittelwert nehmen. Du musst den Minimalwert nehmen. Es müsste also heißen:
Wobei MINIMAL_SPEED_FACTOR eben die Konstante 125 ist.
Zitat von Cornix
Das weis ich ehrlich gesagt nicht direkt. Ich habe mir niemals Gedanken darüber gemacht ob er es kann. Ich habe die zweite Möglichkeit einfach der Vollständigkeit halber eingeführt.
Denkst du, dass dieser Fall nicht eintreten kann?
...
Ich vermute mal, du hast ja Kosten für die Felder (=Knoten), nicht für die Kanten. Mal ein Beispiel: Du weißt die Wegkosten zum Feld 5/5 und zum Feld 6/6 und möchtest wissen wie lang der kürzeste Weg zum Feld 6/5 ist. Das Feld 6/5 hat Kosten 100. Es gibt einen Weg der dich mit Kosten 500 zum Feld 5/5 und mit Kosten 600 zum Feld 6/6 führt. Der Weg von Feld 5/5 zu Feld 6/5 hätte dann logischerweise die Kosten 600, der Weg von 6/6 zu 6/5 hätte die Kosten 700. Das heißt es werden einfach nur die Kosten des Feldes 6/5 auf die Kosten des vorherigen Feldes draufaddiert. Entsprechend ist IMMER das vorherige Feld das "schnellere", welches die geringeren Kosten hat. Dein Algorithmus wird also IMMER erst vom Feld 5/5 zum Feld 6/5 gehen und erst danach den alternativen Weg von 6/6 nach 6/5 ausprobieren (und sich diesen gar nicht erst genauer anschauen, weil ja bereits ein Weg nach 6/5 gefunden wurde). Der Fall, dass der Algorithmus erst einen ineffizienten Weg findet und erst später den besseren kann also gar nicht auftreten.
Im allgemeinen Fall, wo du Kantengewichte hast, ist das anders. Angenommen das Feld 6/5 ist eine Treppe. Nun kannst du argumentieren: Es ist ineffizienter eine Treppe hochzulaufen (also von dem Feld 5/5 zum Feld 6/5 zu laufen) als eine Treppe hinunterzulaufen (also von 6/6 nach 6/5). Wenn also Richtungsangaben darüber entscheiden, wie hoch die Kosten für ein Feld sind, dann kann dieser obige Fall auftreten und der Algorithmus muss mehrere Wege ausprobieren.
Zitat
Aber falls ich die Distanz zum Endknoten nicht in die Wertung miteinarbeite, dann würden doch zu viele
Nodes überprüft werden welche vielleicht zu wenig Erfolgsversprechend sind.
Falls ich lediglich den "speed_factor" einberechne dann würden immer die effektivsten Wege gesucht werden und Kostenintensive aber kürzere Wege kategorisch ausgeschlossen.
...
Die Distanz ist nur für die Minimalkostenschätzung. Sie sagt dir aber nichts über die tatsächlichen Kosten aus. Die Distanz ist Luftlinie bzw. bei dir ist es eine Manhattan-Distanz (keine euklidische). Aber das ist ja egal. Wenn das Ziel nur 3 Schritte von dir entfernt ist, heißt das nicht, dass du nur 3 Schritte zum Ziel brauchst. Wenn nämlich vor dir 'ne Wand ist musst du drumherum laufen und brauchst plötzlich 100 Schritte Umweg ^^ Die Heuristik mit der Distanz meint nur, dass es schlau ist, erstmal den direkten Weg zu versuchen und erst dann einen anderen auszuprobieren, wenn der direkte Weg höhere Kosten verursacht (z.B. weil die Felder vor dir sumpfiges Gelände sind, oder eben weil da eine Wand steht, die sozusagen unendliche Kosten hat) als ein alternativer Weg.
Aus dem Grund errechnen sich die Wegkosten eines Knotens aus den Wegkosten des vorherigen Knotens plus den zusätzlichen "Speed-Factor" des Knotens. Lange Wege werden schon allein deswegen teuer, weil sie aus mehreren Knoten bestehen und da ja für jeden Knoten die Speed-Factor-Kosten mit einfließen wird auch der Weg teurer.
Also nochmal zusammengefasst. Du hast zwei wichtige Werte pro Knoten:
Exakte Kosten "cost"
Geschätzte Minimalkosten "value"
cost errechnet sich aus den cost-Wert des Vorgängerknotens plus den Speed-Factor des Knotens. value errechnet sich aus den cost-Faktor des Knotens plus der minimalen Zahl an Feldern, die man braucht um von diesem Knoten zum Ziel zu gelangen, multipliziert mit den minimalen Speed-Faktor-Kosten.
Der Algorithmus beginnt beim Startknoten und packt alle umliegenden (=adjazenten) Knoten in eine Liste. Von diesen berechnet er cost und value und sortiert die Liste nach den values. Er nimmt den Knoten mit dem höchsten value aus der Liste und wiederholt den Vorgang. Das ganze wird solange gemacht, bis man den Zielknoten gefunden hat.
Zitat von Cornix
Zitieren