优化A * Pathfinding iPhone - NSDictionary能否做到这一点？

Question

我有一个非常大的A *寻路功能，经常被调用，必须放在另一个线程中，否则会让我的游戏口吃。我来自Java背景，最近阅读了关于HashMap的速度（基本上相当于NSDictionary）以及您可以使用的不同实现的讨论。我很好奇NSDictionary的速度有多快以及是否有人发现它是处理大量即时和临时对象分配的可行选项，或者它是否太慢了。

目前我正在使用NSMutableArray作为A *算法中的打开和关闭列表 - 由于O（1）setObject：forKey和removeObject：forKey，我将用NSMutableDictionary替换闭合列表，并且还创建一个NSMutableDictionary，“镜像”公开名单。路径数据存储在一个大的NSMutableArray中 - 我会保持原样，因为索引访问速度足够快（当然）。

所以我的问题是......这会是一个明显的速度提升还是我应该滚动自己的列表和/或地图？我只是不确定NSDictionary 做了什么并且我想知道。

Answer 1

如果您想知道如何优化 A * ，我首先会问您是否使用与平台无关的扩展，例如Iterative Deepening A * （又名 IDA * ），你正在使用什么样的启发式，以及你是否正在使用缓存（转置表，模式数据库）。你问的问题目前与金属太接近了，因为你正在优化系统中可能没有阻碍你的部分。

查看这些课程幻灯片（特别是讲座10 和< a href =“http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf”rel =“nofollow noreferrer”>讲座11 ）

Answer 2

绝对有所不同 - 我最近使用NSArray改变了一个简单的A *实现（列表中的内容？迭代以找出...）用于NSDictionary的列表和邻接（在列表中？objectForKey！）并且从不可接受的性能提高性能，而不是太多的工作。