2

頻繁に呼び出されるかなり大きな A* パスファインディング関数があり、別のスレッドに配置する必要があります。そうしないと、ゲームが途切れてしまうからです。私は Java のバックグラウンドを持っており、最近、HashMap (本質的には NSDictionary と同等) の速度と、使用できるさまざまな実装についての議論を読みました。私は NSDictionary がどれだけ速いか、また多くの即時および一時的なオブジェクトの割り当てを処理するための実行可能なオプションであると誰かが知っているかどうか、またはそれには遅すぎるかどうかに興味があります。

現在、私は A* アルゴリズムのオープン リストとクローズ リストに NSMutableArray を使用しています。O(1) setObject:forKey と removeObject:forKey により、クローズ リストを NSMutableDictionary に置き換え、「公開リストをミラーリングします。パス データは大きな NSMutableArray に格納されます。インデックス アクセスは (もちろん) 十分に高速であるため、これをそのままにしておきます。

だから私の質問は...これは顕著な速度の改善ですか、それとも独自のリストやマップを展開する必要がありますか? NSDictionary が何をするかわからないので、知りたいです。

4

2 に答える 2

3

を最適化する方法A*を知りたい場合は、まず、Iterative Deepening A*(別名IDA*) などのプラットフォームに依存しない拡張機能を使用しているか、どのような種類のヒューリスティックを使用しているか、キャッシングを使用しているか (転置テーブル、パターンデータベース)。あなたが求めている質問は、現時点では金属に近すぎます。システムの一部を最適化しているため、妨げられていない可能性があります.

これらのコースのスライドを見てください(特に講義 10と講義 11 ) 。

于 2009-10-21T18:50:48.610 に答える
0

絶対に違いがあります - 私は最近、NSDictionary (リストにある? objectForKey!) のリストと隣接する NSArray を使用して A* の単純な実装を変更し (リストに何かありますか? 見つけるために繰り返します...)、パフォーマンスを向上させました。あまり仕事をせずに、受け入れられないものから受け入れられるものまで。

于 2011-03-21T11:30:59.373 に答える