Quel algorithme est utilisé par GameplayKit pathfinding?

Question

Est-ce que quelqu'un a trouvé une référence à quel type d'algorithme GameplayKit utilise pour la recherche de chemin? J'ai examiné la documentation d'Apple et je n'ai rien trouvé. En fin de compte, je suis curieux de sa performance par rapport à A * mis en œuvre sans GameplayKit. Même si je suis sûr qu'Apple a fait un travail remarquable, je ne veux pas payer de frais supplémentaires pour les fonctionnalités que je n'utiliserai pas.

Je suis aussi simplement curieux parce que j'aime apprendre de ces types de mécanique.

Merci, E

Answer 1

Seul Apple peut dire à coup sûr. Mais la présence de méthodes à la fois pour le coût et le coût estimé suggère fortement A *, ou du moins une variante avec une complexité algorithmique assez similaire.

Si vous êtes vraiment préoccupé par les performances, installez des cas de test et mettez-les en profil. Vous pouvez commencer par quelque chose comme leur projet de code Pathfinder ... réexécutez pathfinding avec beaucoup de différents labyrinthes et voyez comment l'heure (qui est déjà sacrément courte) change avec la taille du labyrinthe.