Hallo an alle,

ich hab vor kurzem Bots in meine 3D-Engine eingebaut. Da Bots aber leider einen roten Faden brauchen, den sie langgehen können, hab ich eine Pathfinding-Routine erstellt. Hatte sie bisher nur etwas ausprobiert und hab sie deswegen noch nicht so ganz optimiert. Doch jetzt bäucht ich halt eine etwas schnellere Routine, da ich jetzt ein paar mehr Pathnodes in ein Level gesetzt hatte und die Berechnung nach über 20 Sekunden immer noch nicht fertig war. Ich habe schon sehr viel versucht, sachen zu optimieren, doch ich bin mit meinem Latein am Ende. Ich poste mal meine Routine:

Vorab aber noch ein paar Erklährungen:
- TLevel_PathNode: der einzelne Knotenpunkt. Jeder Punkt hat eine Liste mit erreichbaren Knotenpunkten. Diese Liste wird bereits im Editor festgelegt
- TLevel_PathNodeList: eine Liste mit mehreren PathNodes. Die Liste enthällt die Gesammtentfernung (Aufwandskosten * (Positions-Entfernung))
- TDoubleList: eine einfache Liste, nur halt mit double-Werten
- die gesammte Funktion erstellt am Anfang nur 2 neue Objekte (PathList, Path) - Referenze wird erstellt, sobald es zum ersten mal
gebraucht wird. Die Liste mit den fertigen Pfaden wird erst erstellt, nachdem einer gefunden wurde.

Ich hoffe ihr könnt was damit anfangen


Ok, ich weiß, das ist nicht gerade der übersichtlichste Code. Ich hab versucht, eine Baumstrucktur wie im Tutorial Tutorial_pathfinding2 zu erstellen, doch so wirklich zufrieden mit der Geschwindigkeit bin ich nicht.

Nun meine Frage, könntet ihr mir helfen, die Routine zu verbessern? Oder vieleicht einen Tip geben, was deutlich schneller funktionieren würde? Vieleicht sogar ein komplett anderer Ansatz?

Danke schonmal im voraus,

Grüße

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

Bin jetzt zu faul, deinen Code zu analysieren, aber ich denke, der Ansatz ist schon ungünstig.

Du brauchst eine Tabelle mit folgendem Aufbau:

VonNode, BisNode, NextNode, Distance (Distance wird nur für die Berechnung gebraucht, später nichtmehr).

In diese Tabelle trägst Du nun alle von-bis-Kombinationen mit Distanz unendlich ein. Danach werden alle direkt erreichbaren Wege eingetragen (entfernung ohne Zwischenknoten) hier musst du dann auch next=bis setzen.

Jetzt kommt die Berechnung:


Ist die Tabelle fertig berechnet, kennst Du alle kürzesten Strecken und weisst welche Knoten nicht erreichbar sind.

Füe die Wegsuche musst du nur noch den von und den bisknoten ermitteln und in der Tabelle nachsehen, welcher nextknoten für von und bis eingetragen ist. Erreicht dein Bot den nextknoten, wird dieser zum von und das Spiel beginnt von vorne.

p.s. die Tabelle solltest Du nur einmal berechnen, da dies sehr lange dauern kann.
edit: Code-Tag eingeführt, da die Einrückungen verloren gingen.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Das mit der Tabelle fand ich bisher nicht so toll, da der Speicherverbrauch mich etwas abgeschreckt hat. Aber ich glaube, dass das wirklich eine bessere Idee ist, als den Pfad jedesmal komplett neu zu berechnen. Werd das mal ausprobieren und wenn ich noch Probleme haben sollte oder ich es doch schaffen sollte, werd ich mich nochmal melden.

Danke für die Antwort

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

Es kommt drauf an, welchen Algo du verwenden willst.
In Physical Factor hab ich dijkstra pathfinding benutzt, da hast du nen graph und die wichtungen zu den nachbarn.
Der Algo maskiert Nodes und daher geht er nodes ned mehrmals durch.
Dijkstra hab ich gewählt, weil er nicht immer das gleiche Ergenis produziert, er nimmt auch mal ein etwa ungünstigeren weg, das wirkt Menschlicher.
Beim A* hast du immer ein Optimalen weg, also immer das gleiche Ergebnis.
https://svn.linuxprofessionals.org/filedetails.php?repname=physical_factor&path=%2Ftrunk%2Fai.pas
Bei meiner neuen Engine brauche ich zum glück kein Pathfinding Algo, ich habe Wege festgelegt und die Bots laufen dann diese von anfang bis ende durch.
Im Script kann ich dann die Wege wechseln und fertig.
Deine Wegpunkte solltest du in arrays of TWegpunkt speichern, dass ist schneller bei zugriffen aber langsamer beim entfernen von wegpunkten(fällt aber weg da die wegpunkte immer existieren). Den zu laufenden weg auch in nen array of ^TWegpunkt, wenn der weg abgelaufen ist kannst den ganzen array löschen und nen neuen weg erstellen. Ich habe bei Physical Factor die wegpunkte als Stütze verwendet und wenn er am letzten wegpunkt ankam, dann ist er von den wegpunkten zum letzten punkt des spieler gegangen. Wenn der Spieler sich bewegt und damit ein anderen wegpunkt näher an sich hat, dann wurde der suchalgo wieder bemüht und eine neue strecke ausgerechnet.

In Karmarama hab ich für ein Bot ein Luascript, im dem dann WegIDs zugewiesen werden können , diese kann man im script durch eine Logik prima verpacken.
Ala wenn du aufgestanden bist, dann ziehe dich an, bist du angezogen und es ist morgen, dann nimm WegID=1(weg zur arbeit). Bist du bei der Arbeit angekommen, dann WegID=0(bleib stehen) und aktiviere die handelsfunktion. So leicht kann man dann Händler ein bischen Leben einhauchen und muss nicht Wegfindung verwenden.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Danke für den Hinweis. Sidorion hat mir ja geraten, eine Tabelle zu machen, in der alle möglichen Kombinationen gespeichert sind. Das hab ich auch versucht zu implementieren und es klappt auch wunderbar - der Performanceschub ist wirklich erkennbar. Doch leider kann ich das bisher nur an einem Level testen, da die Tabellenerstellung doch etwas Zeit braucht. Für ein Level mit 50 Nodes und eine Durschnittliche Anzahl von erreichbaren Nodes von einem Node aus von 3,5 hat die Tabellenerstellung ca. 4 bis 7 Stunden gebraucht (habs über nacht gemacht, deswegen weiß ich nicht genau wie lange). Das ist wirklich sehr lange, ich weiß. Aber wenn die Tabelle einmal erstellt ist, klappt alles wunderbar. Auch der Speicherverbrauch der Tabelle hab ich schon minimiert. Die komplette Tabelle braucht in der Level-Datei nur 82 KB. Da die Daten komprimiert gespeichert werden sogar nur 8 KB. Während der Laufzeit kommen kaum noch zusätzliche Bytes hinzu, also worst-case: 20 KB drauf, und 100 KB Arbeitsspeicher kann ich schon verkraften.

Das mit den Arrays ist so ne Sache, ich mag sie einfach nicht. Ich benutzte stattdessen TList, die ja intern auch ein array ist. Somit sollte sich der Performanceunterschied beim Zugriff doch eher in Grenzen halten, oder?

Durch meine ScriptEngine kann ich auch auf meine Bots zugreifen, wenn auch im Moment nur rudimentär. Ich kann ihn befehlen z.B stehenzubleiben, zu rennen oder zu strafen. Aber wenn die Tabellenimplementierung läuft, dann werd ich auch noch implementieren, dass sich die Bots per Skript On-The-Fly einen neuen Wegpunkt suchen, oder eine neue Liste von Wegpunkten an die aktuell vorhandene anhängen (z.B. wenn ein PowerUp erscheint, und dem Bot auffällt, dass es vorhanden ist (Sichtbarkeitstest oder Distanz zum Objekt wegen Höhrbarkeitstest, einfach den Weg zum PowerUp hinzufügen, oder gegebenfalls wieder entfernen, falls wer anders schneller war)

Grüße

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

Wie hast du denn Deine Tabelle angelegt? Wie sieht ein einzelner Datensatz aus?

Sowas kann man mir einer sortierten Stringliste sehr schnell machen:
Für jeden Weg ein Record, jeweils mit new angelegt (kannst auch ein Objekt nehmen, ist aber beim Anlegen etwas langsamer, aber das sollte nicht unbedingt ins Gewicht fallen).
Dieser wird nun mit einem Schlüssel per AddObject in die sortierte Liste eingefügt. Als Schlüssel empfehle ich NameVon+NameBis. Solange die Stringliste sortiert ist, macht er nämlich eine Binärsuche O(lb(n)) beim Zugriff und beim Einfügen (Die Vergleiche finden mit AnsiCompareText/String je nach Fallsensitivität statt, was auch sehr schnell ist). Dadurch sollte sich die Berechnung nochmal beschleunigen lassen.
Bei ner TList hättest Du O(n) beim Zugriff, allerdings O(1) beim Einfügen. Da diese Liste aber hauptsächlich zugegriffen wird um zu suchen sollte der Zeitgewinn doch bemerkbar sein.

Zudem kannst Du bei der Berechnung auch eine Höchstzykluszahl n angeben, nach der aufgehört wird. Dann werden alle Wege mit n Zwischenschritten gefunden, alle mit n-m Schritten m mal verbessert. Ist zwar dann nicht immer der kürzeste Weg, aber nobody is perfect .

[edit]
Du kannst auch anstelle des Änderungsflags auch einen Änderungszähler nehmen. Dann hörst Du z.B. auf wenn weniger als 5% der Wege geändert wurden. Dann ist die Tabelle zwar auch nicht optimal aber doch sehr genau.

Wobei: Die Berechnung kann doch eig. bleiebig lange dauern, weil das Ergebnis wird ja gespeichert
[/edit]

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Ich habe einen Art Baum erstellt. In der ersten Ebene sind die Pointer der Start-Nodes. Zu Jedem Baumknoten eines StartNodes ist eine Liste mit allen Wegen zu allen anderen Nodes vom gesammten Level. Da ein Pointervergleich genauso schnell ist wie ein Integer-Vergleich (ist ja eigentlich das selbe), brauch ich das mit der StringList nicht wirklich. Dadurch würde ich unnötigen Speicher verbrauchen.



TLevel_PathNodeList ist dabei wieder eine Liste von TLevel_PathNode. Diese Liste beinhaltet die einzelnen Wegpunkte, die abgegangen werden muss. Das mit dem Höchstzykluszahl ist mir auch schon durch den Kopf gegangen. Werd ich vieleicht auch noch einbauen. Da die Berechnung aber sowieso außerhalb des Hauptprogramms, nähmlich im Editor, stattfindet, ist die Performance beim erstellen der Tabelle nicht so wichtig, da es ja nicht RealTime ist.

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

Na dann hast Du sogar O(n^2) um einen bestimmten Weg zu finden. Das erste n, um in Deiner Liste die Quelle zu finden, das zweite n, um in deren Liste das Ziel zu finden.

Wenn Du in der Stringliste lauter strings marke Quellenname(Trennzeichen)Zielname, mit jeweils einem Zeiger auf den Weg stehen hast, verbrauchst Du nicht wesentlich mehr Speicher. Allerdings ist der Zufriff extrem schneller.
Du musst ja in jedem Schleifendurchlauf n^3 Wege aus der Liste suchen. 1. den Weg von->über, 2. den Weg über->nach und 3. den Weg von->nach.
Wenn jetzt der Zugriff wie in Deiner Liste n^2 ist, hasst Du O(n^5)! Im Fall der SL hasst Du dann O(n^3lb(n)) (eigentlich O(n^3) weil lb(n) mbMn vernachlässigt wird). Das ist DEUTLICH günstiger.

Hier ist dann noch garnicht mitgezählt, dass sich dieser Spass im worstcase theorethisch noch n-mal wiederholt, bis sich nichts mehr ändert.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Das mit dem O(n^2) würd ich anders sehen. Ich will versuchen, es an einem Beispiel zu erklären.

Ich habe nun in einem Level 6 PathNodes. Daher gibt es zu jedem PathNode 5 Wege zu jedem anderen PathNode in der fertigen Tabelle.

Also, wenn ich eine Liste habe, wie du sie mir vorschlägst, dann hat die Liste 6*5 = 30 Einträge. Wenn ich jetzt den unterersten Eintrag suche, muss ich 29 Einträge durchgehen bis ich beim letzten angekommen bin.

Bei meiner Liste sieht das anders aus. Ich gehe zuerst zu dem Eintrag, der den StartNode besitzt. Dafür muss ich 5 Einträge absuchen, bis ich schon mal den richtigen StartNode habe. Dann muss ich nochmal 4 Untereinträge untersuchen, dann hab ich die Liste also 9. Das ist um den Faktor 3 schneller.

Bei dir hätt ich also einen maximalen Aufwand von n*(n-1) und bei mir von n+(n-1) bzw. n^2-n bei dir und 2n-1 bei mir. Da bei mir ein Level 50 und mehr Nodes hat, würd ich sagen, dass meine Routine schneller ist (2499 Einträge würd ich bei dir durchsuchen und 99 bei mir )

//Edit: bei dir wären es natürlich 2450, sorry

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

Ich frage mich, wieso du eine Tabelle benutzt, die braucht ewig zum erstellen,ist ist bei dynamic völlig wertlos und nur in wenigen Fällen sinnvoll(z.B. Patrollie ohne sinn und verstand).
In der Regel wirst du ein Laufzeitalgorythmus finde, der auf A* und ähnlichem basiert.
Im Präprozess kannst du alle Wegpunkte gegeneinander auf Sichtbarkeit prüfen, die maximale Distanz und wegkosten einbauen(kann man auch beim laden der map machen aber muss ja ned sein ). So hast du nun die Möglichkeit dein Ziel und Start fest zu legen. Nimm den Startpunkt und gehe alle punkte durch, setzte negative kosten entsprechend der wichtungen. Der Weg mit den geringsten Kosten zum Start ist dein Weg. Gibt es ein Weg, dann kannst du in einer Tabelle den Weg speichern und eventuell später nochmal verwenden. So kannst du zur laufzeit knoten rausnehmen, z.B. eine Kiste verspeert nu den weg, eine tür ist zu, 5Bots verstopfen den Gang,....

Optimierungsansätze wären z.B. ein direkte gerade zwischen beiden punkten und als erstes eine prüfung aller punkte dazwischen und wenn es ned reicht, dann den suchradius um der linie erhöhen. Gewichtungen entsprechend der Hauptwege anpassen, damit man erst über die Hauptwege und dann erst die nebenwege prüft.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Das mit der Tabelle ist im Moment auch nur eine Notlösung. Wegkosten sind schon eingebaut, werden aber von mir noch nicht genutzt. Da meine Levels fast keine Dynamik haben, ist das die Tabelle auch nicht so schlimm. Wenn alles läuft, werd ich nach und nach versuchen, die fixe Tabelle durch dynamik zu ersetzen. Aber mit Kisten ist das Problem nicht all zu groß. Alle Nodes haben bereits ein Tag TempNotReachable, das per SkriptEngine auf True gesetzt werden kann. Sollte ein Bot versuchen da langgehen zu wollen, wo plötzlich eine Kiste im Weg ist, könnte die SkriptEngine einschreiten und automatisch einen neuen Weg zuweisen. Aber das ist noch garnicht mein Ziel. Im Moment möchte ich erstmal die Bots dazu bringen, überhaupt durch das Level gehen zu können.

Aber eins weiß ich schon ganz sicher - ich werde noch große Probleme mit PathFinding haben. Aber dank des Super-Forums hier werd ich das auch noch hinbekommen.

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

Im Gegentum. Ich rede von einer SORTIERTEN Liste. In dieser hättest Du die Eintraäge '001|002', '001|003' ... , '002|001', '002|003', '002|004', ... '004|005'. Hinter jedem Eintrag steht dann direkt die Verbindung mit Von, Bis, Über und Distanz. Wenn Du jetzt den Weg von 004 nach 001 suchst, suchst Du einfach in der Stringlist IndexOf('004|001'). Du suchst quasi gleichzeitig Quelle UND Ziel.
Bei einer Gesaamtzahl von 5 Knoten sind maximal drei Vergleiche Nötig, um den richtigen zu finden (Bei Dir 20). Bei 32 Knoten sinds maximal 5 Vergleiche (Bei Dir 992), bei 256 8 usw. Also lb(n). In Deiner Variante sinds bei 256 Knoten 256*255=65280 Vergleiche.
Bei Mächtigkeitsberechnungen werden übrigens Konstanten weggelassen, was Deine n(n-1) zu n^2 erweitert.

Wenn Du am Anfang nur die wirklich begehbaren 1er Wege einträgst und die Tabelle dynamisch erweiterst, sparst Du nochmal nen Haufen.

@TAK: Wenn Du alle Konten und ihre Sichtbarkeit zueinander speichern willst, hast Du doch schonwieder eine Tabelle, oder?

@Dynamik: Man kann in diese Wegtabelle neben dem Kürzesten natürlich auch den zweitkürzesten Weg speichern, der dann alternativ genutzt wird, falls der Kürzeste blockiert ist. Dieser Zweitkürzeste Weg würde bei der Berechnung sogar nebenbei mit abfallen.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Hallo,

bei dem Algorithmus den Sidorion vorgestellt hat, handelt es sich glaub ich um den Algorithmus von Floyd und Warshall, hat eine Laufzeit von O(n^3) und wird häufig bei APSPs (All Pairs Shortest Path Problem) verwendet (wenn keine negativen Kantengewichte vorhanden sind).

Viele Grüße
dj3hut1

Grünau. Die O(n^3) steht ausser Frage. Ist ja auch schon eine sehr gute für dieses Problem. Gibt auch Lösungen mit O(n^4) und O(n^5).
Wir streiten, nein diskutieren im Moment ja nurnoch über die n^3 Zugriffe auf die Tabelle.
Ich versuche LittleDave davon zu überzeugen, dass eine sortierte Liste schneller ist als sein Baum, der ja eh nur Tiefe 2 hat und deshalb die Vorteile einer Baumstruktur überhaupt nicht zum Tragen kommen.

Selbst wenn der Baum auch sortiert wäre, wäre er nicht schneller. Jede Stufe hätte dann lb(sqrt(n)) und wenn mich meine Mathekenntnisse nicht ganz verlassen haben, ist 2*lb(sqrt(n))=lb(sqr(sqrt(n))=lb(n). n ist hier m*m, m=Anzahl Knoten, darum geht der Trick mit der Wurzel. In anderen Fällen lassen sich die Os nicht zwingend vergleichen. Zudem wird hier angenommen, dass bei sehr großen n bzw. m n=n-1 und m=m-1 angenommen werden kann.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

@Sidorion:

Ich versteh immer noch nicht, wie du auf die Aufwandsberechnung kommst. Bei einer Anzahl von 5 Knoten und alle Knoten Knoten können von einem Knoten erreicht werden, hat doch die Tabelle 20 Einträge. Meine Struktur schaut doch durch den Baum etwa so aus:

Jetzt such ich den Weg von Knoten 2 zu Knoten 5. Dafür gehe ich erstmal die erste Ebene des Baums durch. Dadurch muss ich den ersten Eintrag überspringen. Die Zielknoten werden da noch garnicht beachtet. Sobald ich dann schonmal den richtigen Knoten in der Liste gefunden habe, suche ich in der Ebene 2 nach dem Zielknoten, also muss ich max. 3 Einträge durchsuchen. Summa-Sumarum würde ich doch insgesammt 6 Vergleiche machen müssen.

Die Sortierte Liste dagengen schaut doch so aus:

Unsortiert:
Wenn ich jetzt suche, müsst ich doch 8 Vergleiche ausführen, bis ich bei "Knoten2 | Knoten 5" bin.

Sortiert
Wenn ich in einer sortierten Liste suche, würd ich doch erst in die mitte Springen, schauen ob größer, kleiner oder gleich. Also bin ich bei 10. Das gleiche nochmal, dann bin ich bei Eintrag 5, dann bin ich bei 7 und dann bin ich bei 8, vieleicht auch bei 9. Doch da ich manchmal Zwei und am Schluss 3 vergleiche machen muss, ist das doch aufwendiger. Außerdem sind noch Divisionen drinnen [wenn auch nur Integer - Aber immer noch schlechter als eine schlichte Addition] und ich muss mir immer die Grenzen des Suchbereiches merken. Das ganze macht bei kurzen Listen kaum ein unterschied zur unsortierten Liste, bei gigantischen Listen ist dies dagegen ein sehr großer Unterschied zur unsortierten Liste

Ich bin immer noch der Meinung, dass sich der Mehraufwand für eine sortierte Liste nicht lohnt. Bei einer sortierten Liste hätte ich zwar 4 oder 5 Einträge, die ich durchsuchen müsste, aber durch das if a < b then else if a > b then else a = b würde ich mal davon ausgehen, dass meiner algo schneller ist.

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com