Comment optimiser le Find ?

Question

Salut à tous,

Je suis actuellement en train de travailler sur un projet de pathfinding et j'ai un problème avec la fonction Find.

Dans une map de 512 cases par 512 cases je chrche les cases voisines à chacune (pour la recherche de chemin), pour cela j'utilise la fonction Find sur ma liste de plus de 100000 cases comme ca : 

nNode m_NodesList.Find(delegate(Node n) { return ((n.Position.X vPosition.X + 1) && (n.Position.Y == vPosition.Y)); });

Mon problème : dans des petites ca marche parfaitement, mais la en 512x512 mon pc tourne depuis 15minutes pour calculer les cases voisines.
Y'a t'il un moyen d'optimiser la recherche ?

Shaolyne · Answer

Bien le bonjour,

La méthode Find ne semble pas être la plus adaptée pour ton besoin.
En effet, cette méthode parcourt tous les noeuds contenus dans ta liste, un par un. Ce qui implique, à titre d'exemple, que pour trouver le voisin du noeud en position 300, il faudra (512 * 299) + y-1 tests infructueux si on considère le premier élément comme étant en x = 1.

Pourquoi ne pas travailler avec un tableau à 2 entrée et ainsi ne vérifier que les cases en +/- 1 directement, sans tester toutes les possibilités inutiles?
Cela demande plus de code mais les performances seront drastiquement améliorées.

Shao.

cs_faucheuse · Answer

Merci de ta réponse.
J'y ai déjà penser en effet, mais je voulais tout de même savoir si il n'y a pas d'optimisation possible en gardant mon tableaux simple.
Au final c'est certainement ce que je ferais, le projet etant à rentre pour jeudi ^^(il me reste plus que ca a réglé en fait).

Comment optimiser le Find ?

2 réponses

Votre réponse

Discussions similaires