A*-Algo und Performance

Hallo,
ich habe grade ein paar bedenken aufgrund der Performance und dem A* Algo.
Kurze Erläuterung zu der Karte:
Ist im Prinzip ne normale x*y Felder große Karte mit Bergen Flüssen usw. nun hätten wir aber gern das die Einheiten eines Spielers um den Berg "rumlaufen"
So jetzt zu meiner Frage:
wenn die Karte größer wird, nehmen wir mal an 500*500 Felder und einer schickt seine Einheiten von oben links nach unten rechts, dann ist das doch ein unglaublicher Aaufwand an Berechnung? Der Algo findet ja auch nicht auf anhieb den richtigen weg sowie ich das verstanden habe. Und man muss ja auch noch die Abfragen aus der Datenbank berücksichtigen.
Da kann es doch locker passieren das die Wegberechnung mehrere Sekunden dauert, wenn nich sogar noch länger?

nehmen wir mal an 500*500 Felder und einer schickt seine Einheiten von oben links nach unten rechts, dann ist das doch ein unglaublicher Aaufwand

Korrekt. Im allerschlimmsten Fall hast du 25.000 Felder zu prüfen, der ist allerdings sehr unwahrscheinlich.
Daher sollte man sich bei solchen Karten überlegen, ob man diese nicht im Speicher hält (500*500 sind lächerliche 25 Tausend Datensätze), oder ob man nicht mit Heuristiken oder vorberechneten 'Masterwegen' arbeitet.

man könnte auch schauen ob nicht andere wegfindungs algorithmen optimaler sind
hat ja jeder seine schwächen und stärken
und sonst hat der untote natürlich recht

Wenn man nur einen weg (start-ziel) berechnen möchste is A* schon die optimalste wahl. wenn man alle kürzesten wege auf einmal berechen möchte gibts auch andere alogrithmen.
A* hat immer eine heuristik, ohne wärs der dijkstra algo.
bei so einer "normalen" karte empfiehlt sich die euklidnorm (sqrt(x^2+y^2)) zu nehmen.
um so besser die heuristik, um so weniger felder müssen geprüft werden, also is auch der gesamnt aufwand kleiner.
eine wesenetlich faktor bei der gschwindikeit is die wahl der liste in der die knoten gespeichert werden. es muss sichergestellt sein das man möglischst schnell den knoten mit den geringsgten kosten ermittelt. dazu bietet sich nen binary heap an.
falls ich das nochmal genauer erklären soll einfach sagen oder googeln
also ich habs bei mir mal getestet in c#. bei 1.000.000 felder braucht man < 1 sekunde. wobei ich vermute das php dabei um einiges langsamer sein dürfte
.

Da kann es doch locker passieren das die Wegberechnung mehrere Sekunden dauert, wenn nich sogar noch länger?

Richtig. Ich habe vor einer ganzen weile mal den A* in php geschrieben. Hab es gerade getestet: 4.6 sec von 0/0 bis 500/500. Optimiert hatte ich ihn damals etwas. Ich habe in mal in den Anhang angehängt -> wer ihn braucht soll ihn nehmen.
mfg Roland
*Edit*
Mit Einer kleinen Optimierung waren 3 sec möglich. Allerdings ist die CPU(dual-core) in den 3 Sec bei 50% gestanden.

Bei mir hat der A* in PHP 0,5 Sekunden gebraucht.
Hab das Programm dann in C++ geschrieben und bin dann auf wenige Millisekunden gekommen.
Sprich für sowas ist PHP recht ungeeignet.

Das Forum hat hunger...
kurz gefasst: Leg doch nen größeres Raster drüber. 10x10 zb. Dann musste über 50x50 Felder suchen und dann schließt du viele aus und kannst dann über weniger Felder suchen.

Hallo zusammen,

da es zu dem Thema hier schon einige Beiträge gibt, mache ich keinen neuen auf, sondern poste mal hier. Wir haben A* auch in unserem neuen Projekt (PHP) programmiert und sind mit der bisherigen Perfomance alles andere als zufrieden. In unserem neuen Game gibt es verschiedene Feldarten mit unterschiedlichen "Durchreisekosten". Des Weiteren können bestimmte Einheiten, bestimmte Felder gar nicht überqueren (z.B. kann ein Schiff nicht über Land fahren oder ein Panzer schwimmen :-)).

Da es hier ja schon einige gibt, die mit dem Problem zu kämpfen hatten und es scheinbar auch so gelöst haben, dass der Weg in einer für ein BG annehmbaren Zeit gefunden wird, frage ich hier einfach mal (auch wenn ich gut verstehen kann, wenn es kein positives Feedback geben wird), ob jemand über einen PHP Code verfügt, der entsprechend schnell läuft und bereit wäre, ihn hier zu posten oder ihn mir auf anderem Wege zur Verfügung zu stellen?

Ich kenne deine Welt nicht, aber wenn sich diese nicht verändert (bis auf die Beschränkungen, dass manche Felder nicht passierbar sind, weil da nen Berg steht, kannst du deine kurzesten Wege auch vorberechnen.

Hast du allerdings sehr grosse Graphen, wird das mit O(|V|²) sehr speicherintensiv (|V|=Anzahl der Knoten).

Im Grunde genommen speicherst du dir für jeden Knoten in einer Matrix ab:"Ich bin auf Feld x=(12,87) und ich möchte zu Feld y=(77,42)...was ist der nächste Knoten, den ich besuchen muss (das ist dann der Wert in der Matrix)...so kannst du von einem beliebigen Punkt aus zu jedem anderen Punkt kommen, indem du vom Start rekursiv läufst, bis du dein Ziel erreicht hast und das in O(Vmin) Laufzeit, wobei Vmin die Länge des kürzesten Weges ist.

Problematisch wird es, wenn verschiedene Einheiten verschiedene Gewichte auf deinem Graphen haben (das Katapult darf nicht durch Wälder fahren, der Waldläufer aber schon). Da musst du dann für jeden "Bewegungstypen" eine seperate WegeMatrix halten.

Wenn diese Bewegungen in deinem Spiel ein Kernelement sind,  das bei sehr vielen Clicks ausgeführt wird, dann solltest du darüber nachdenken, wie du jegliche Graphenalgorithmen von deinem Server fernhälst, denn ansonsten wirst du irgendwann in Performanceprobleme laufen...ganz besonders, wenn du sie in PHP realisierst. A* ist ne feine Sache und wird in Spielen viel verwendet...CLIENTSPIELEN vor allem...denk dran, das sich all deine User einen Server teilen (ausser du hast deine Anwendungs verteilt...dann n Server teilen).

Schau einfach, dass du das vorberechnest und in nem Memcached ablegst.

Das ist jetzt nur ein Vorschlag...ich hab keinen Plan, ob das bei dir wirklich anwendbar ist, denn ich kenne deine Spielwelt nicht und auch nicht die typischen Anwendungsfälle deiner User.

So long...

Maxx

EDIT: jetzt seh ich erst, dass Undead das schon gesagt hat :( buhuuu...wer lesen kann ist klar im Vorteil...

Hey MrMaxx. Vielen Dank für die ausführliche Antwort.

Wie ich sehe, hätte ich schreiben sollen, dass unsere Spielwelt sich ständig verändern kann/wird. Z.B. baut ein gegnerischer Spieler eine Stadt, so kann ich dieses Feld nicht mehr passieren. Oder es wird eine Strasse gebaut, dann sinken die Überquerungskosten des Feldes, genauso können Städte und Strassen wieder abgerissen werden, etc.

Wenn du davon ausgehst, dass dein Graph nur sehr dunn von solchen Blockern (Burgen/Stadten) besiedelt ist, dann kannst du das trotzdem so machen, wie ich vorgeschlagen habe (oder in Erwägung ziehen).

Nehmen wir an, dass das Bauen einer Stadt nicht so häufig vorkommt...z.B. auf einem 20x20 grossem Teil-Feld nur 1-2 Mal pro Tag.  Baut jemand also eine Stadt wird nur die direkte Umgebung von 10 Feldern in jede Richtung geheilt. Wir gehen dabei davon aus, dass bei diesem Vorgang nur kleine "Umwege" in die Matrix eingepflegt werden.

Das gleiche kannst du auch für Strassen machen. Hier musst du dann jedoch grössere Entfernungen neu berechnen (wenn ganze Strassen gebaut werden...nicht wenn nur einzelne Strassenstücke gebaut werden).

Nachts würde ich dann die gesamte Wege-Matrix nochmal durchrechnen um wirklich wieder 100% korrekt zu sein. Eventuell längere Wege musst du hierbei in Kauf nehmen. Diese sollten jedoch nur in Ausnahmefällen auftreten bemerkt werden...z.B. wenn du durch das Bauen einer Stadt Teil-Bereiche wirklich partitionierst. Aebr auch das kannst du erkennen und darauf dann reagieren.

Ist wie gesagt nur eine Idee...

Maxx

Nur aus neugier: Von welchen Berechnungszeiten reden wir denn hier?

Muss der Weg wirklich immer optimal sein? Weil wenn man auf ne Karte guckt nimmt man mit Sicherheit auch nicht immer den besten Weg. Dafür gibt es auch Algorithmen, teste mal ob das schneller ist.

Du solltest den A* in einer anderen Sprache einsetzen - PHP ist dafür wirklich ungeeignet. Ich denke mit C / C++ fährst du hier am besten. Selbst wenn du ihn per exec() aufrufst, dürfte das massiv schneller sein.

Den fertigen Weg würde ich mit der Route in die Datenbank schreiben. Wenn der Weg dann wieder berechnet werden soll, musst du nur den Weg abgehen, und weißt ob sich was zum negativen verändert hat. Sonst würde ich den Weg für ein paar Tage cachen. Den Weg abprüfen müsste recht einfach über ein Subselect machbar sein.

Wenn es ein Performance Problem gibt, könntest du die Wegberechnung auch im Client laufen lassen (der User bastelt sich den Weg also selbst, evtl. mit Unterstützung von JavaScript). Der Server muss den Weg dann nur noch validieren.

> Du solltest den A* in einer anderen Sprache einsetzen - PHP ist dafür wirklich ungeeignet.

So schlimm ist PHP auch nicht (mehr) :-)

Da wird mit Stacks gearbeitet - was man in PHP eigentlich nicht über Arrays (eigentlich Hashmaps) abbilden müssen - das kann PHP halt nicht, soll es auch gar nicht.

Wäre aber sicher interessant zu sehen wie performant die Browser sind. Da zu müssten jedoch alle 25.000 Felder an den Client gemeldet werden, könnte ja auch n bissi was sein.

Hier wurden schon sehr gute Lösungen genannt, bzw. ich würde es auch so machen.

Konkret wäre das der Algorithmus von Floyd/Warshall, der in einem Rutsch die kürzesten Wege von allen Punkten zu allen Punkten berechnet. Die schmeißt du dann in eine Datenbank mit Attributen {Start, Ziel, Pfad (bzw. nur der nächste Knotenl)} und nem Index auf Start+Ziel.

Je nachdem wie "teuer" ein Durchlauf ist, generierst du das stündlich/täglich neu und iterierst anschließend über alle Einheiten, die unterwegs sind. Für diese setzt du dann einen neuen Pfad basierend auf deren aktueller Position.

Sollte doch eine Einheit mal vor ein Hindernis laufen, dann kannst du versuchen, sie ein paar Schritte drumherum zu schicken. Das kommt natürlich drauf an, wie groß die neu gebauten Strukturen sind. Alternativ eine Meldung an den eingeloggten Spieler, der sie manuell manövrieren kann. Wenn keiner eingeloggt ist: Pech! Dann wartet sie eben bis zur nächsten Berechnung. Das liefert nen Vorteil für den Spieler, öfter online ist (wenn du das gut findest).

Original von Phoscur

Wenn es ein Performance Problem gibt, könntest du die Wegberechnung auch im Client laufen lassen (der User bastelt sich den Weg also selbst, evtl. mit Unterstützung von JavaScript). Der Server muss den Weg dann nur noch validieren.

Genau die Idee kam mir auch, als ich den OP gelesen habe. Der Client sollte den Teil der Karte kennen, den er darstellen kann. Ausserdem kann der Spieler dann einfach mal ein bischen rum probieren, welchen Weg eine Figur nehmen würde, bevor man sich entscheidet. Der Server bekommt dann nur noch den berechneten Weg.

@mar1us habt ihr mal mit verschiedenen Heuristiken gespielt? Die schlechteste Laufzeit sollte ja erreichbar sein, wenn man die Heuristik die restlichen Kosten immer mit 0 schätzt. Die Heuristik muss die Kosten aber immer unterschätzen, damit wirklich der beste Weg gefunden wird. Irgend wo dazwischen sollte die optimale Heuristik liegen. Habt ihr mal geguckt, wie große Teile des Lösungsbaum von eurem Algorithmus untersucht wurden.

Gibt es eigentlich keine Möglichkeit C code von PHP aus aufzurufen? Wenn dem so wäre, könnte das doch ne Möglichkeit sein. Bei einer C++ Lösung wäre ich evtl. sogar behilflich (allerdings erst ab Montag).

mfg Torsten

Bei uns haben wir es auch Clientseitig gemacht. Wir haben realtiv große Karten, unsere Testwelt ist jetzt 1000x1000. Unsere größte war bisher 4000x4000. Die Welten setzten sich aus Inseln zusammen. Dabei ist der Ozean theoretisch eine verbundene Masse. 

Wenn der User eine Route berechnet, dann wird eine Javascript Routine gestartet, welche sich während der Suche immer wieder Kartenstücke vom Server nachläd bei Bedarf. Das ganze geht bisher sehr fix. Ist aber auch nur auf Landmasse getestet.

Durch die Berechnung auf dem Client spart man auf dem Server massiv Rechenzeit.

Guten Morgen zusammen,

wow, ich bin begeistert wie viele Antworten ich schon bekommen habe. Also schon mal vielen Dank an alle Poster. Es sind bereits einige sehr interessante Ansätze genannt worden.

Ich muss zugeben, dass wir uns mal ein paar Dokus zu A* im Netz rausgesucht und danach entsprechende Funktionen geschrieben haben. Wie man in meiner Sig. sehen kann, hatten wir bisher mit Strategiespielen nicht viel zu tun und merken immer wieder, dass es sich hier um viel Neuland handelt. Der Optimierungsversuch kommt quasi jetzt erst und da es wohl recht offensichtlich ist, dass wir nicht die ersten sind, die sich über solche Probleme den Kopf zerbrechen, habe ich im Netz gesucht (ohne allzu großen Erfolg) und eben hier gepostet, um von möglichen Erfahrungen anderer profitieren zu können. Momentan haben unsere Funktionen wohl noch so einige Macken. Wenn sich einige Hindernisse im Weg befinden, kommt es vor dass bereits eine Entfernung von 10 Feldern zu einem Hänger führt. 

Die Vorberechnung der optimalen Routen ist sicherlich ein möglicher Ansatz. Aber da es wohl täglich zu hunderten/tausenden Veränderungen der Kartentypen kommen wird (insofern das Game so läuft, wie von uns etwa geplant), denke ich dass hier viel Potential für Frust beim User vorhanden sein könnte, wenn das System offensichtlich veraltete Pfade vorschlägt.

Wir sind noch nicht ganz sicher, wie groß wir die einzelnen Welt werden lassen. Momentan testen wir mit einer Größe von 256x256. Der Ansatz von Murmeli klingt auf jeden Fall sehr interessant. Zumal er sich scheinbar als recht schnell erweist.

wäre es denn möglich die map in teilmaps(areas) zu unterteilen und dann in der jewaligen area nach der optimalen route ermitteln, wenn man aus der area rausgeht, dann kann man ja die route anzeigen und die gespeicherte matrix leeren.

Original von BlackScorp

wäre es denn möglich die map in teilmaps(areas) zu unterteilen und dann in der jewaligen area nach der optimalen route ermitteln, wenn man aus der area rausgeht, dann kann man ja die route anzeigen und die gespeicherte matrix leeren.

 Aber wo willst Du den Ausgang in einem Areal setzen?

hm.. ich habe nur eine theorie aufgestellt;) vllt könnte man einmal über areale eine route berechnen und dann durch die einzelnen areale durchgehen, damit wäre es möglich zu ermitteln, in welcher richtung , der ausgang sich befinden soll. jedoch wüsste jetzt nicht auf anhieb wie man den genauen punkt ermitteln könnte..

ach ja habe gerade bei wiki folgendes gefunden:

Nachteile 

Der begrenzende Faktor bei A* ist oft nicht die Rechenzeit, sondern der Speicherplatz....... Im Abschnitt Verwandte Algorithmen finden sich ähnliche Algorithmen, die versuchen, den Speicherplatzverbrauch zu beschränken.

vllt hilft das irgendwie weiter.

Laut wiki gibt es zu dem A* auch ein D* Algorithmus, der dient für den Dynamischen weg , also wie auf deiner karte, die ist ja dynamisch soweit ich es verstanden habe

Original von BlackScorp

hm.. ich habe nur eine theorie aufgestellt;) vllt könnte man einmal über areale eine route berechnen und dann durch die einzelnen areale durchgehen, damit wäre es möglich zu ermitteln, in welcher richtung , der ausgang sich befinden soll. jedoch wüsste jetzt nicht auf anhieb wie man den genauen punkt ermitteln könnte..

Vielleicht könnte man aber auch Kosten von Kante zu Kante eines Areals vorberechnen und so einen Weg über die Areale suchen, um so evtl. den Teil der Karte zu reduzieren, der untersucht werden soll. Das wäre evtl. Sinnvoll, wenn man die Kartenteile erst aus der DB lesen muss, oder an einen Client übertragen muss. Das garantiert dann zwar nicht mehr, dass man den kürzesten Weg findet, aber wahrscheinlich noch, dass man einen vernünftigen Weg findet.

jep, aufjedenfall denke ich dass man hier genauso vorgehen muss wie in großen projekten, dass man eine aufgabe in teilaufgaben zerlegt.

Original von Todi42

Gibt es eigentlich keine Möglichkeit C code von PHP aus aufzurufen?

 http://www.php.net/manual/en/internals2.php

 Ich habe da mal schnell drüber geguckt und eigentlich sollte es damit möglich sein, C/C++ Funktionen von PHP aus aufzurufen.