Okay, eine Kleinigkeit ist mir eingefallen: Wenn ich vom Ziel zum Start hin suche, dann spar ich mir das path.reverse() beim Rekonstruieren des Weges.

Tatsächlich habe ich schonmal Guido Rossums Style Guide gelesen, aber es ist vermutlich keine schlechte Idee das ganze mal aufzufrischen. :oops:

Ich hoffe das hier ist besser:


from Edge2 import Edge
from heapq import heappush, heappop

def useAStar(start, goal):
""" A*: -Uses a Hash ...

Habs masterDict genannt, weil in Game Programming Gems 1 etwas von einer masterNodeList oder so stand... Aber knownNodes hört sich gut an, ich benenne den Kram mal um und ändere die Kommentare.

Zur while Schleife:
Bei 9000 Aufrufen auf einem 6*5 Feld war deine Version schneller. Wenn ich das ...

Stimmt.

So hab den A* nochmal neu implementiert, und beim schrittweise optimieren wieder zu Heap und Hash für die geöffneten Knoten gegriffen, denn das ständige Sortieren eines Arrays war bei mir immer sehr viel langsamer.
Das Hash mit den geschlossenen Knoten habe ich mit dem Hash der geöffneten Knoten ...

Gibts wirklich keinen der mir helfen kann?

Hi,

danke für den Link, ich bin allerdings nach reichlicher Überlegung zum Schluss gekommen, dass ich ohne Hilfe nicht verstehe warum deine Implementation schneller ist als meine. :oops:

So wie ich das sehe, müsste es doch schneller sein, wenn man ausnutzt, dass die Liste mit geöffnete Knoten ...

Danke für den Pythoncode Tipp, war gestern anscheinend zu müde um diesen Button im Forum zu sehen. Bis in die Puppen dran gebastelt, und als letzten Verzweiflungsakt hier um Hilfe gebeten. :wink:


Ich habe das ganze bereits mit profile untersucht, wie man in der Demo sehen kann (da ist eine ...

Der Threadtitel sagt eigentlich schon alles: Ich habe den A* implementiert unter Verwendung von heapq und dicts, aber das ganze ist dennoch viel zu langsam, und mir sind die Ideen ausgegangen was ich noch verbessern könnte.
Das ganze braucht auf einem 160*116 Feld schon mal gut und gerne 1-2 ...

Ich habe mir heapq angesehen, und dort werden diverse Sachen anders gemacht (zb bei remove nicht den letzten Knoten an die Stelle vom gelöschten Knoten packen), aber was ich bei heapq und generell nicht verstehe, ist warum ein array benutzt wird anstatt einer dynamischen Datenstruktur..?

Hi,

ich habe meinen eigenen Heap geschrieben und musste feststellen, dass er um einiges langsamer ist als heapq. Da es mir nicht nur darum geht, etwas schnelles zu haben, sondern auch zu verstehen warum mein Heap langsamer ist, dachte ich mir post einfach mal.

Ich habe den Heap auf einer 2 fach ...