Développement XNA pour la XBox et le PC
188
À présent, il nous faut définir leur parent, c’est-à-dire le nœud qui permet d’y arriver.
Pour l’instant, dans notre cas, il s’agit du nœud de départ. Ensuite, choisissez le nœud
que vous devrez inspecter après le nœud de départ. Pour cela, déterminez lequel de ces
nœuds est le plus proche du nœud de destination.
Pour déterminer cette distance, il faut calculer ce que l’on appelle la distance de Manhattan.
Cette distance correspond au nombre de déplacement horizontaux et verticaux qui devront
être effectués pour aller d’un point à un autre. Si nous reprenons l’exemple des figures
précédentes, cela donne dans les deux cas 16 déplacements à effectuer. Pour le nœud audessus du nœud de départ, il y a 15 déplacements horizontaux et un vertical. Pour le nœud
à droite du nœud de départ, il y a 14 déplacements horizontaux et 2 verticaux.
Nous pouvons donc utiliser n’importe lequel des deux nœuds pour continuer notre recherche.
Choisissez-en un, retirez-le de la liste ouverte et ajoutez-le à la liste fermée. Puis répétez
les opérations d’analyse et de détermination du meilleur nœud voisin, jusqu’à arriver au
nœud de destination. Une fois à destination, remontez de nœud en nœud grâce au nœud
parent que vous avez défini pour chacun d’entre eux, jusqu’à arriver au nœud de départ
qui n’aura pas de parent.
Déplacement oblique
Ici, les déplacements se font uniquement à la verticale et à l’horizontale. Cependant, vous pouvez bien sûr
utiliser l’algorithme avec des déplacements obliques.
Attention
Si, à un moment donné, la liste ouverte ne contient plus de nœud, mais que vous n’êtes pas encore arrivé
au nœud de destination, c’est qu’il n’existe pas de chemin possible vers ce nœud.
Figure 9-2
Analyse
du second nœud
et de ses voisins…
=Labat FM.book Page 188 Vendredi, 19. juin 2009 4:01 16
188
À présent, il nous faut définir leur parent, c’est-à-dire le nœud qui permet d’y arriver.
Pour l’instant, dans notre cas, il s’agit du nœud de départ. Ensuite, choisissez le nœud
que vous devrez inspecter après le nœud de départ. Pour cela, déterminez lequel de ces
nœuds est le plus proche du nœud de destination.
Pour déterminer cette distance, il faut calculer ce que l’on appelle la distance de Manhattan.
Cette distance correspond au nombre de déplacement horizontaux et verticaux qui devront
être effectués pour aller d’un point à un autre. Si nous reprenons l’exemple des figures
précédentes, cela donne dans les deux cas 16 déplacements à effectuer. Pour le nœud audessus du nœud de départ, il y a 15 déplacements horizontaux et un vertical. Pour le nœud
à droite du nœud de départ, il y a 14 déplacements horizontaux et 2 verticaux.
Nous pouvons donc utiliser n’importe lequel des deux nœuds pour continuer notre recherche.
Choisissez-en un, retirez-le de la liste ouverte et ajoutez-le à la liste fermée. Puis répétez
les opérations d’analyse et de détermination du meilleur nœud voisin, jusqu’à arriver au
nœud de destination. Une fois à destination, remontez de nœud en nœud grâce au nœud
parent que vous avez défini pour chacun d’entre eux, jusqu’à arriver au nœud de départ
qui n’aura pas de parent.
Déplacement oblique
Ici, les déplacements se font uniquement à la verticale et à l’horizontale. Cependant, vous pouvez bien sûr
utiliser l’algorithme avec des déplacements obliques.
Attention
Si, à un moment donné, la liste ouverte ne contient plus de nœud, mais que vous n’êtes pas encore arrivé
au nœud de destination, c’est qu’il n’existe pas de chemin possible vers ce nœud.
Figure 9-2
Analyse
du second nœud
et de ses voisins…
=Labat FM.book Page 188 Vendredi, 19. juin 2009 4:01 16