iphone - 优化 A* Pathfinding iPhone - NSDictionary 能解决问题吗？

Question

我有一个相当大的 A* 寻路函数，它会被频繁调用，并且必须放入另一个线程中，否则它会让我的游戏卡顿。我有 Java 背景，最近阅读了一篇关于 HashMap(本质上相当于 NSDictionary)的速度以及可以使用的不同实现的讨论。我很好奇 NSDictionary 有多快，以及是否有人发现它是处理大量即时和临时对象分配的可行选择，或者它是否太慢了。

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

所以我的问题是...这是否会带来明显的速度提升，或者我应该推出自己的列表和/或 map 吗？我只是不确定 NSDictionary 做什么，我想知道。

Answer 1

如果您想知道如何优化 A*，我首先会问您是否使用与平台无关的扩展，例如迭代深化 A* (又名 IDA*)，您使用的是哪种启发式方法，以及您是否使用缓存(换位表、模式数据库)。目前您提出的问题太接近实际情况了，因为您正在优化系统的某些部分，而这些部分可能不会阻碍您。

看看these course slides (特别是 lecture 10 和 lecture 11 )