spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Zitat von »Schorsch«

Wenn du eine bestimmte Feuerwache suchst dann macht das mehr Sinn mit A* dran zu gehen. Wenn du aber 5 Feuerwachen in der Stadt hättest und du wolltest den Weg zur nächsten Feuerwache berechnen, dann würde sich Dijkstra anbieten.

Ich verstehs nicht. Wieso soll man einmal den Algo nehmen, einmal den fuer essentiell die gleiche Aufgabe? Wobei die Algorithmen vom Prinzip sogar noch der gleiche Algo sind. A* ist ja nichts weiter als Dijkstra mit einer Heuristik, welche die Reihenfolge der besuchten Wegpunkte steuert.

Hilfe zur Selbsthilfe:

Beide implementieren, am Besten in verschiedenen Varianten und mit guter Debug-Ausgabe damit du siehst wie die Algorithmen funktionieren und wie sich Änderungen auswirken. Die Algorithmen sind beide sehr simpel im Prinzip und der Implementationsaufwand sollte sich in sehr engen Grenzen halten.

Da es den meisten Leuten in diesem Forum beim Spiele programmieren hauptsächlich um den eigenen Lernerfolg geht halte ich diese "Lösung" für die Beste.

Wenn du gut englisch kannst und was spezielles suchst ist Google Scholar auch ein guter Ansatzpunkt.

@TGGC:
Natürlich handelt es sich im Prinzip um den selben Algorithmus. Wie du selbst sagst, erweitert A* den Dijkstra ja nur um eine Heuristik. Normalerweise würde man eine Heuristik benutzen um den Abstand vom aktuellen Knoten zum Zielknoten abzuschätzen. So möchte man dann die passenden Knoten auswählen und sich nicht unnötig in eine falsche Richtung bewegen. Wenn ich jetzt aber 5 mögliche Zielknoten habe, müsste ich diese 5 Knoten in meiner Heuristik verwenden und auswerten. Ansonsten müsste ich den Algorithmus vermutlich 5 mal durchlaufen berechnen. Der Punkt ist jetzt, wenn ich mir über mein Ziel noch nicht im klaren bin, bis ich dann da bin, dann bringt mir die Heuristik nichts und der einfache Dijkstra ist besser geeignet. Dieser breitet sich ja im Prinzip zu allen Seiten hin gleich aus (kommt natürlich auf den Graphen an). Dadurch dass sich Dijkstra überall hin gleich ausbreitet kann ich so relativ schnell Ziele finden ohne vorher ihren genauen Ort zu kennen. Diese Ziele könnten zum Beispiel bestimmt getagte Knoten sein, Knoten mit bestimmten Eigenschaften (Hier im Beispiel die Feuerwehrwache). Eine Heuristik würde da aber vermutlich nicht groß hilfreich sein. Wenn du mit deinem Navi unterwegs bist und dir den schnellsten Weg zur nächsten Tankstelle anzeigen lassen willst, möchtest du ja auch nicht, dass erst die Wege zu verschiedenen Tankstellen berechnet werden. Wobei hier ja vermutlich noch mal anders gearbeitet wird.
Die Idee hinter diesem Anwendungsfall bei dem Dijkstra besser geeignet ist, ist mir übrigens nicht selbst eingefallen. Mat Buckland benutzt dies in seinem Buch "Programming Game AI By Example". Dort ist der Anwendungsfall ein Top Down Shooter, bei welchem die Bots eigenständig die nächstgelegene Heilquelle, die nächstgelegene Munition, etc finden. Es ist beim Aufruf nicht klar wo sich diese Items befinden und ob sie aktuell vorhanden sind. Beim durchlaufen des Graphen durch Dijkstra werden dann bestimmte Eigenschaften der Knoten abgefragt. Dadurch wird gecheckt, ob der aktuelle Knoten in frage kommt. Die Heuristik würde hier einfach nicht helfen.
Wie stark sich das am Ende auf die Geschwindigkeit auswirkt kann ich nicht sagen. Ich hab mir den ganzen Spaß nicht ausgerechnet, sehe aber den Sinn dahinter. Wenn mein Kram hier nur verwirrt, überlest ihn einfach und beachtet es nicht. Wer sich dafür interessiert kann sich aber sicher mal selbst Gedanken dazu machen.

Zitat von »Schorsch«

@TGGC:Wenn ich jetzt aber 5 mögliche Zielknoten habe, müsste ich diese 5 Knoten in meiner Heuristik verwenden und auswerten. Ansonsten müsste ich den Algorithmus vermutlich 5 mal durchlaufen berechnen. Der Punkt ist jetzt, wenn ich mir über mein Ziel noch nicht im klaren bin, bis ich dann da bin, dann bringt mir die Heuristik nichts und der einfache Dijkstra ist besser geeignet.

Na und, wo ist das Problem? Die Heuristik für n Ziele ist trivial, wenn man sie schon fuer 1 Ziel hat, einfach das Minimum der n einzelnen Heuristiken. Auch die Interpretation davon ergibt viel Sinn, naemlich das der Algorithmus nun zu dem der 5 Zielpunkte strebt der am naechsten ist. Also kein Grund auf einmal Dijkstra zu benutzen.

Zitat von »Schorsch«

den schnellsten Weg zur nächsten Tankstelle anzeigen lassen willst, möchtest du ja auch nicht, dass erst die Wege zu verschiedenen Tankstellen berechnet werden.

Eben, warum dann also Dijkstra, der die Wege zu allen Knoten berechnet?

Weil du die Position deines Ziels nicht kennst. Du weißt das sich irgendwo in deinem Graphen ein Knoten mit einer bestimmten Zusatzinformation bestimmt. Das ist doch die Voraussetzung von der ich rede. Und du musst Dijkstra nicht komplett durchlaufen lassen. Sobald du bei dem Knoten mit der gesuchten Eigenschaft ankommst brichst du ab. Ist so ein Knoten nicht vorhanden wird natürlich dann der komplette Graph durchsucht. Ich habe mich da ziemlich ungünstig ausgedrückt indem ich Dinge gemischt habe. Wie gesagt, du suchst einen Knoten den du vorher nicht kennst. Ich finde diese Lösung in dem Fall sehr schön, das muss man aber nicht Man kann natürlich auch gucken das Problem von einer anderen Seite her zu lösen, indem man zum Beispiel interessante Knoten die man möglicherweise suchen möchte vorher gesondert speichert.
Und zum Beispiel deiner Heuristik für 5 mögliche Ziele. Würde ich einfach über die Heuristik gucken welches Ziel das interessanteste ist, muss ich nicht zwangsweise das beste Ziel bekommen. Beispiel wieder die Feuerwehrwachen. Es gibt 5 Stück davon und als Heuristik dient der direkte Abstand. Ich nehme also die Wache, welche am nächsten an meinem Startknoten ist. Da ich aber nicht Luftlinie durch den Graphen laufen kann, sondern dessen Kanten folgen muss kann es ja gut sein, dass die Eigentliche Verbindung zu diesem Knoten viel länger ist, als zu einem, welcher erst als ungünstig scheint. Ich denke aber hier kommt es auch immer stark auf den gegebenen Fall an.

Vorhin hast du konkret von 5 Feuerwachen, damit waeren die Ziele genauso bekannt wie bei einer Feuerwache. Und natuerlich wird A* dir den richtigen Wert berechnen, wenn die Heuristik korrekt ist (so wie oben von mir beschrieben). Je mehr Knoten in Richtung des zuerst favorisierten Ziels angeschaut werden um so genauer wird die eigentliche Distanz dorthin ja bekannt. Sollte dies nicht der korrekte Weg sein, wo wird irgendwann ein Knoten auf dem Weg zum richtigen Ziel interessanter und dann auch dieser Weg untersucht. Beide stehen dann im Wettstreit und der kuerzere gewinnt, so einfach ist das. Also entweder hast du diesen "Mat Buckland" nicht verstanden oder der hat selbst Unsinn geschrieben. A* funktioniert mit beliebig vielen Zielpunkten, solange die Heuristik korrekt ist (Kosten nie ueberschaetzt). Wenn du z.b. weisst, das alle Zielpunkte innerhalb eines bestimmten Kreis liegen, dann kannst du einfach im Kreis 0, sonst Entfernung zum Kreis nehmen. (Konkrete Anwendung waere eine Angriffsposition in Schussweite). Du musst vorher nicht wissen, welcher dieser Knoten begehbar sind oder wieviele es sind, es funktioniert trotzdem. Die einzig sinnvolle Aussage dazu ist, eine optimale Heuristik schaetzt immer moeglichst grosse Abstaende, findet man nichts groesseres als h(x) = 0, dann ist A* zu Dijkstra vereinfacht.

Ich hatte dich nicht richtig verstanden. Ich hatte es so rausgehört, als sollte die Heuristik am Anfang ein festes Ziel auswählen und dieses dann den ganzen Algorithmus beibehalten. Wenn mann alle Ziele betrachtet und immer das aktuell sinnvollste Ziel nimmt bleibt das ganze natürlich korrekt. Und wie gesagt, ich meinte den Fall, bei dem das Ziel wirklich nicht bekannt ist. Nicht weil es mehrere Möglichkeiten gibt, sondern im Prinzip so gut wie jeder Knoten des Graphen in frage kommt. Ist natürlich nicht die einzige Möglichkeit. Mann könnte die Knoten in linearer Zeit durchlaufen und die Möglichen Kandidaten suchen. Sicherlich könnte man auch viele andere Dinge machen. Aber einen korrekten Weg gibt es selten und ich wollte hier lediglich diesen Fall zeigen. Wie gesagt, du darfst solche Probleme gerne anders lösen Jeder wie er möchte. Unsinnig finde ich es aber nicht.

Jap.