Optimisation de l'iPhone A * Pathfinding - NSDictionary fera-t-il l'affaire?

Question

J'ai une assez grosse fonction de recherche de cheminement A * qui doit être appelée fréquemment et doit être insérée dans un autre fil car sinon, cela fera bégayer mon jeu. Je viens d'un environnement Java et viens de lire une discussion sur la vitesse de HashMap (essentiellement l'équivalent de NSDictionary) et les différentes implémentations que vous pouvez utiliser. Je suis curieux de voir à quel point NSDictionary est rapide et si quelqu'un a trouvé cette option viable pour gérer de nombreuses affectations d'objets immédiates et temporaires, ou s'il est trop lent pour cela.

Actuellement, j'utilise un tableau NSMutableArray pour les listes ouvertes et fermées de l'algorithme A *. Je remplacerais la liste fermée par NSMutableDictionary en raison de O (1) setObject: forKey et removeObject: forKey, et créerais également un NSMutableDictionary qui "miroir" " la liste ouverte. Les données de cheminement sont stockées dans un grand NSMutableArray - je le laisserais tel quel car l'accès à l'index est assez rapide (bien sûr).

Ma question est donc la suivante: s'agirait-il d'une amélioration notable de la vitesse ou devrais-je créer mes propres listes et / ou cartes? Je ne sais tout simplement pas ce que NSDictionary fait et j'aimerais savoir.

Answer 1

Si vous vous demandez comment optimiser A * , je voudrais tout d'abord vous demander si vous utilisez des extensions indépendantes de la plate-forme, telles qu'Iterative Deepening A * ( IDA * ), quel type d’heuristique vous utilisez et si vous utilisez le cache (tables de transposition, bases de données de modèle). Les questions que vous posez sont trop proches du métal pour le moment, car vous optimisez des parties du système qui ne vous retiendront probablement pas.

Consultez ces diapositives du cours ( en particulier lecture 10 et < a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer"> lecture 11 )

Answer 2

Absolument cela fait une différence - j'ai récemment modifié une implémentation naïve de A * à l'aide de NSArray (quelque chose dans la liste? itérer pour le savoir ...) pour les listes et les adjacents de NSDictionary (dans la liste? objectForKey!) et une performance accrue de non acceptable à acceptable avec pas trop de travail.