Optimizing A * Pathfinding iPhone - Will NSDictionary do the trick?
I have a rather large A * tracking function that gets called frequently and needs to be put on another thread because otherwise it will make my game stutter. I'm coming from a Java background, and recently read a discussion about the speed of a HashMap (essentially equivalent to an NSDictionary) and the various implementations you can use. I'm curious how fast NSDictionary is and if anyone has found a viable option for dealing with a lot of immediate and temporary object allocations, or too slow for that.
I am currently using NSMutableArray for public and private lists in the A * algorithm - I would replace the private list with NSMutableDictionary because of the O (1) setObject: forKey and removeObject: forKey, and also create an NSMutableDictionary that "mirrors" the open list. The path data is stored in a large NSMutableArray - I would leave that as it is, because the index access is fast enough (of course).
So my question is, will this be a noticeable speed improvement or should I flip my own lists and / or maps? I just don't know what NSDictionary does, and I would like to know.
source to share
If you are wondering how to optimize A*
, I would first ask if you are using platform-independent extensions like Iterative Deepening A*
(aka IDA*
), what heuristic you're using, and if you are using caching (transposition tables, template databases) ... At this point, the questions you are asking are too close to the metal because you are optimizing parts of the system that are probably not holding you back.
Watch these course slides (especially Lecture 10 and Lecture 11 )
source to share