Recherche de chemin avec A* en trois dimensions

Bonjour,

J'ai implémenté A* en 2D pour un personnage qui se déplace sur une Grid et cela fonctionne très bien.

Maintenant j aimerai implémenté un dimension en plus en tenant compte de la coordonnes Z dans l'espace. Ainsi mon personnage pour monter des marches.

Il me suffit d ajouter une dimension Z dans mon algorithme (plus particulièrement dans Node ) et dans la fonction de cout (distance euclidienne en Z ?). C'est bien ça ?

Le problème si j"implémente cela est que mon personnage risque de prendre des chemins dans les airs (de voler en sorte) pour arriver a sa position cible non ?
J'aimerai que l algorithme trouve que des chemins possibles. Donc j aimerai que la node incrémente en Z seulement quand un obstacle sur lequel on peut monter est présent.

Comment implémenter cette contrainte ?

Merci pour votre Aide

Snoopy,

Bonjour,

Il te faut une matrice qui représente les coordonnées (ou les zones) qui ne sont pas accessibles.
Lors de la selection des voisins dans l'implémntation de ton algorithme A*, tu ne choisiras que des zones accessibles.
De cette façon, l'algorithme ne traitera pas les zones non accessibles et ton personnages ne volera pas ou ne traversera pas de murs.

Merci pour ta reponse.
mais j'ai toujours du mal a comprendre.

Mon terrain devient une grille 3D (X,Y,Z). Lorsque Z = 0. la matrice est la meme que mon 2D A*. Si Z = 0.5 (imaginons une resolution de 0.5), Je dois verifier si la cellule est vide ou non. Si elle est vide, je dois dire qu elle est innacessible non ?
Cela evitera que mon personnage prenne des chemins dans les airs. Mais si un obstacle est la. Je dois verifier que la hauteur de l obstacle est entre 0 et 0.5 pour marquer la cellule accessible. Si elle est superieure a 0.5 je marque la cellule occupe ?


Merci encore pour ton aide.

Tu pourrais rester dans un environnement 2D. Ta composante Z peut être vue comme un coût différent pour le déplacement. On peut imaginer que monter des escaliers d'une certaine longueur au sol est X fois plus couteux que marcher en ligne droite sur la même distance. Donc un tel environnement 3D est simplifiable en environnement 2D.
Le seul vrai problème est la superposition des environnements 2D : par exemple un immeuble. Il te faut autant de matrice de plans 2D que d'étages. Pour passer d'une matrice à une autre, ce sont des cases liées entre elles par un coût de déplacement. Ton algo A* reste en 2D.
Pour les passages d'une matrice à une autre, tu peux envisager de stocker les passages dans chaque cases. Le problème est que ça va très vite prendre beaucoup de mémoire. Si tes cartes sont petites (par rapport aux ressources disponibles de ta machine) ce ne sera pas gênant. Par contre, si tu souhaites cartographier Paris, ses métros, tunnel et égouts, ça va être un peu chaud. Une possibilité est d'avoir une matrice par niveau. Les passages d'une matrice à une autre sont stockés dans une structure de données séparée genre table de hachage par matrice qui pour une case associe une liste de cases accessibles vers d'autres matrices. Pour un escalier, c'est une case d'une matrice A liée à une case d'une matrice B. Pour un "mat de pompier", c'est une case d'une matrice A liée à une case de chaque matrice située en dessous et au dessus de A.

Cool cela me semble etre une bonne idee. On trouve pas mal de ressources sur Astar sur une grille 2D. Mais tres peu de sur 3D ou +...

Donc si j'ai bien compris, je dois construire un ensemble de 2D Terrain (X,Y) qui sont surpepose. Donc si 3 Metres en Z est le max et que ma resolution est 0.05. J'aurai 60 ensembles de matrices 2D ?
Ensuite le passage a l'autre matrice se fait lorsque je genere les voisins. Lorsque je genere les voisins, je recherche dans la table de hachage quel sont les voisins pour passer dans la matrice suivante. Dois je mettre les voisins qui sont dans la meme matrice (par exemple un case vers l'avant) dans cette meme table de hashage ou seulement ceux qui permette de monter ou descendre d un niveau ?


Merci

Dans un A* en 2D, tu es supposé ajouter à un moment les contraintes liées à l'environnement :

• Espace déjà occupé
• Zone dangereuse
• ...

Ces contraintes empêcherons tout chemins générés de passer par ces endroits.

Dans un A* en 3D, la problématique du vol est exactement la même. Il suffit de considéré l'ensemble des espaces ne touchant pas le sol comme une zone impossible d'accès.

Cependant, la solution de @dinobogan qui utilise un modèle 2D serai plus simple d'utilisation. Surtout, si tu n'as pas de tunnel ou de pont dans ton environnement.

Cordialement,
Patrick Kolodziejczyk.

Ok, je vais donc tenter cela.
Merci beaucoup pour vos aides et vos infos.