spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Welches Beispiel meinst du? In Wikipedia?
Das muss nicht so sein. Du kannst die Breitensuche auch ohne Zielknoten benutzen, dann hast du am Ende für jedes erreichbare Feld die minimalen Kosten, um dahinzukommen. Man würde abbrechen, wenn keine neuen Felder mehr dazukommen bzw. im konkreten Fall hier wenn die Kosten zu hoch werden.

Ja, dann wäre es das gleiche Verfahren.

In dem Wikipedia Beispiel wurde halt beim erreichen des Zielknotens abgebrochen.

Zitat von »TGGC«

Ob es "maximal schnell" ist, haengt vom konkreten Graph, Kosten und Reichweite ab. Breitensuche hat das Problem, das es oft quer durch den Speicher springt, wodurch es oft langsamer als erwartet läuft auf modernen Maschinen. Ich vermute aber in dem Fall ist das wenig relevant.

Für den jeweiligen Spieler (zB in einem rundenbasierten Spiel) muss man dann ja nur einmal die Map (pro Runde) berechnen, und kann dann jeden Pfad zu jedem Tile ohne weitere Berechnung erhalten (nur noch rückwärts vom Ziel-tile den Pfad nach absteigen Kosten zusammenstellen).
Ich hab das Verfahren bei einem rundenbasierten Taktikspiel verwendet, damit der Spieler für jeden Endpunkt sofort den Pfad berechnen konnte, oder man markieren kann welche Tiles mit 10 Actionpoints (Kosten) erreichbar sind.

Bei einem Spiel mit sehr vielen Einheiten, die verteilt auf der Karte sind, aber den gleichen Zielpunkt haben, kann man mit einer Berechnung den Pfad ALLER Einheiten erhalten. Das ist dann oft schneller als mit A* für jede Einheit separat.

Zitat von »TGGC«

P.S: Der Unterschied zu einem Floodfill ist lediglich das man Knoten wieder oeffnet, wen man einen kuerzeren Weg findet. Da ist im Algorithmus eine if Abfrage anders, man ersetzt ein != durch ein <.

Ja, genau, man muss schauen ob die Verbindung zu einem schon vormals besuchten Knoten möglicherweise besser ist (aus einer anderen Richtung aus).

Man sollte hier dazu sagen dass es unterschiedliche Varianten der Breitensuche gibt. An sich ist Breitensuche ein Konzept welches man in Verschiedenen Situationen einsetzen kann. So nutzen auch viele anderen Algorithmen Breitensuche um Teilprobleme zu lösen. Man kann die Breitensuche so implementieren dass man kürzeste Pfade in einem Graphen findet. Man kann die Breitensuche so implementieren dass man lediglich von einem Knoten alle erreichbaren Knoten im Graphen findet, man kann einen oder aber auch den besten Weg von einem Knoten zu einem anderen finden und vieles mehr. Das Konzept dahinter ist immer gleich, wobei dies eben genutzt wird um das jeweilige Problem zu lösen. Floodfill kann man dazu durchaus als verwandt sehen. Hier hat man einfach eine spezielle Form eines ungerichteten Graphens welche im Normalfall eben durch eine Grafik kodiert ist. Der Punkt ist hier eben dass Knoten normal nicht mehrfach besucht werden. Das muss bei der Breitensuche aber auch nicht unbedingt der Fall sein. Ein Beispiel ist die Variante welche im deutschen Wikipedia Beitrag genannt wird. Dort werden Knoten auch niemald mehrfach durchlaufen.