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