A * Pathfinding iPhone Optimierung - Wird NSDictionary der Trick?

Question

Ich habe eine ziemlich große A * Pathfinding Funktion bekommt, die häufig aufgerufen werden und haben in einem anderen Thread gestellt werden, denn sonst wird es mein Spiel Stottern machen. Ich komme aus einem Java-Hintergrund, und vor kurzem eine Diskussion über die Geschwindigkeit der HashMap ist (im Wesentlichen das Äquivalent von NSDictionary) lesen und die verschiedenen Implementierungen Sie verwenden können. Ich bin gespannt, wie schnell NSDictionary ist und ob jemand es seinen gangbarer Weg für den Umgang mit vielen sofortigen und temporären Objekt Zuweisungen gefunden hat, oder ob es zu langsam für die.

Zur Zeit verwende ich eine NSMutableArray für die offene und geschlossene Listen in der A * -Algorithmus - ich würde die geschlossene Liste mit NSMutableDictionary aufgrund der O (1) setObject ersetzen: forKey und removeObject: forKey, und auch die Schaffung die offene Liste NSMutableDictionary, dass „Spiegel“. Die Wegfindung Daten werden in einem großen NSMutableArray gespeichert - ich dies verlassen würde, wie sie ist, weil Indexzugriff ist schnell genug, (natürlich)

.

Also meine Frage ist ... wäre dies eine spürbare Verbesserung der Geschwindigkeit sein oder soll ich meine eigenen Listen rollen und / oder Karten? Ich bin nur nicht sicher, was NSDictionary hat und ich würde gerne wissen.

Answer 1

Wenn Sie sich fragen, wie A* zu optimieren, würde ich fragen Sie zuerst, wenn Sie verwenden plattformunabhängige Erweiterungen, wie Iterative Vertiefen A* (aka IDA*), welche Art von heuristischen Sie verwenden, und wenn Sie verwenden Caching (Umsetzungstabellen, Musterdatenbanken). Die Fragen Sie fragen, sind zu nahe an das Metall für den Moment, da Sie Teile des Systems sind die Optimierung, die wahrscheinlich nicht hält Sie zurück.

Hier finden Sie aktuelle diesen Kurs Dias ( insbesondere Vorlesung 10 und < a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer"> Vortrag 11 )

Answer 2

Absolut macht es einen Unterschied - ich kürzlich eine naive Implementierung von A * mit NSArray geändert für die Listen und adjacents für NSDictionary (etwas in der Liste iterieren ... um herauszufinden?) (In der Liste objectForKey?!) und erhöhte Leistung von nicht akzeptabel akzeptabel mit nicht zu viel Arbeit.