Optimizing A* Pathfinding iPhone - Will NSDictionary do the trick?

Question

I've got a pretty big A* pathfinding function that gets called frequently and has to be put in another thread because otherwise it will make my game stutter. I come from a Java background, and recently read a discussion about the speed of HashMap's (essentially the equivalent of NSDictionary) and the different implementations you can use. I'm curious how fast NSDictionary is and whether anyone has found it to be viable option for dealing with lots of immediate and temporary object allocations, or whether it's too slow for that.

Currently I'm using an NSMutableArray for the open and closed lists in the A* algorithm - I would be replacing the closed list with NSMutableDictionary due to the O(1) setObject:forKey and removeObject:forKey, and also creating an NSMutableDictionary that "mirrors" the open list. The pathing data is stored in a big NSMutableArray - I would leave this as-is because index access is fast enough (of course).

So my question is... would this be a noticeable speed improvement or should I roll my own lists and/or maps? I'm just not sure what NSDictionary does and I'd like to know.

Answer 1

If you're wondering how to optimize A*, I'd first ask you if you're using platform-independent extensions, like Iterative Deepening A* (aka IDA*), what kind of a heuristic you're using, and if you're using caching (transposition tables, pattern databases). The questions you're asking are too close to the metal for the moment, because you're optimizing parts of the system which are likely not holding you back.

Have a look at these course slides (especially lecture 10 and lecture 11)