Wenn du A* nicht dutzende Male pro Frame aufrufst sollte A* effizient genug sein. Das Problem ist deine Implementierung. Das fängt schon bei der set_map Methode an. Der große Vorteil von A* gegenüber anderen Pathfinding-Algorithmen, wie z.B. Dijkstra, ist das A* im Normalfall nicht alle Felder der Map durchsuchen muss. Im Idealfall findet A* sogar sofort den Weg zum Ziel, ohne sich weitere umliegende Felder anzugucken. Du aber sagst in der Initialisierung: Lege für jedes Feld auf der Map ein neues Objekt an und speichere alle umliegenden Felder ab. Das zerschießt dir schonmal total die Performance, wenn du auf einer 500x500 Map alle Felder anguckst, obwohl du nur einen Weg suchst der 15 Felder einschließt. Ganz böse ist deine Suche nach adjazenten Knoten. Dafür iterierst du zweimal über alle Knoten, nur um rauszufinden welche Knoten adjazent sind. Bei einer 500x500 Map macht das 500^4 viele Iterationen!!! (macht genau 62500000000 viele Schleifendurchläufe...)
Prinzipiell musst du dir klar machen, das solche Modelle wie Graphen nur Abstraktionen sind. Nehmen wir mal deine Datenstruktur @node_list. Das ist ein Array, der für jedes Feld der Map ein Objekt mit folgenden Attributen enthält: x, y, adjazente Knoten und Geschwindigkeit. Ich nenne dir mal eine alternative Datenstruktur, die genau dieselben Attribute enthält: Eine Table! Eine 2D Table, deren Einträge die Kosten sind. Was ist die X/Y Koordinate des Table-Eintrages @node_table[10, 20]? Na 10 und 20. Was sind die adjazenten Knoten? 9/20, 11/20, 10/19, 10/21. Das kann ich dir sagen, ohne diese adjazenten Knoten explizit abzuspeichern.
Wenn die Map ein Schachbrettmuster ist, musst du die meisten Sachen nicht abspeichern, du kannst sie dir on the fly berechnen und das ohne Aufwand. Ist der Knoten offen? Ja, wenn seine Kosten gleich 0 sind, nein, wenn seine Kosten ungleich 0 sind.
(Natürlich musst du auch für eine solche Tabelle 500x500 viele Tabelleneinträge anlegen. Das sind aber nur Integer-Werte, die zudem alle mit dem selben Wert 0 initialisiert werden. Das wird über Memcopy gemacht und geht extrem schnell, binnen einer Mikrosekunde! Im Gegensatz dazu muss bei deiner Methode für jedes Feld ein Objekt angelegt werden, was sehr viel Zeit kostet.)
Wie könnte man den Algorithmus effizienter machen? Du definierst dir erstmal eine 2D Table für die Map. Dann iterierst du über alle Events und setzt den Tabelleneintrag, auf dem das Event sich befindet, auf -1, falls das Event nicht begehbar ist. Damit sparst du dir, jedes Mal wenn du dir ein Feld anguckst über alle Events zu iterieren (was in der Performance gewaltige Einbußen macht). Als nächstes legst du eine @open_list an und fügst die Koordinaten und Kosten des Anfangsknotens ein. @open_list = [[0, x, y]]. Danach sortierst du in jedem Schritt den Array (@open_list.sort!, beachte das beim Sortieren von Arrays, die Arrays enthalten, immer das erste Arrayelement als Sortierschlüssel verwendte wird) und holst dir das letzte Element aus dem Array (@open_list.pop). Das ist der Knoten, den du dir als nächstes ansiehst. Warum der letzte? Das ist in der Tat ein Problem, weil beim Sortieren automatisch erstmal von klein nach groß sortiert wird, du aber an den geringsten Kosten interessiert bist. Allerdings ist es effizienter einem Array von hinten Elemente zu entnehmen als von vorne. Eine Lösung des Problems ist, die Kosten immer negativ in den Array einzufügen. Dann sind die geringsten Kosten die größten Zahlen im Array. Nun fügst du alle adjazenten Knoten des soeben herausgeholten Knotens in den Array ein. Achte dabei, dass du nur Knoten einfügst, die in der Tabelle die Kosten 0 haben. Dabei berechnest du deren Kosten (kosten = kosten des herausgeholten Knotens + @map.get_movement_speed_factor(x,y)) und schreibst sie in die Table. Danach schreibst du die geschätzten Kosten in den Array. Das machst du solange, bis du einen Knoten findest der zum Ziel führt.
Zitieren