PathFinding

De Wiki SIO EDM
Révision de 26 janvier 2019 à 22:54 par Pirmk (discussion | contributions)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher

Qu'est-ce qu'un PathFinding ?

Un PathFinding aussi appelé recherche d'un chemin. Cela s' apparente à de l'intelligence artificielle à partir du moment où l'ordinateur doit trouver le chemin pour aller d'un point A à un point B.

Le but d' un PathFinding est donc de déterminer le chemin le plus court entre deux points.

Ce problème peut paraître facile pour ce type de chemin sans obstacles :

PasObs.png

Mais peut s' avérer plus complexe pour des chemins de ce type avec obstacles :

Obs.PNG

Applications d'un PathFinding

Le principe du PathFinding est utilisé de plusieurs façons. En effet, la recherche de chemins est beaucoup utilisée car l'intelligence artificielle et beaucoup d' autres technologies émergentes y font appelle.

La recherche de chemins dans les jeux vidéos

Dans des jeux vidéos tel que League of Legends où l'utilisateur clique sur la carte pour déplacer sont joueur, le pathfinding est sans cesse utilisé :

Lol.gif

Il y a donc des plaintes sur les forums de ce genre de jeux qui utilisent en grande partie le pathfinding concernant l' optimisation et la réussite de la rapidité des chemins trouvés qui n'est pas toujours la bonne.

En effet, sur ce genre de jeux où tous les personnages sont amenés à bouger en même temps, il devient compliqué de prédire ce qu'il se passera dans un court instant. De plus certains personnages sont utilisés par d' autres utilisateurs donc leur future position devient parfois impossible. On se retrouve donc parfois avec des chemins non optimisés de par un obstacle non prévu (comme un personnage par exemple).

Cependant, la recherche de chemin dans les jeux vidéos est tout de même plus simple que d' autres types de situations.

La recherche de chemins en robotique

La recherche de chemins en robotique est très intéressante car le robot ne se trouve pas dans un espace dont tous les obstacles sont définis avec précision.Il y a donc une analyse permanente de l'environnement pour permettre au robot d' esquiver les éventuels obstacles.

EviterObs.gif

La mise en place d' un Pathfinding avec des connaissances de matrices

Problèmes mathématique du pathfinding

Le problème de la recherche de chemins peut être perçue comme évidente. En effet, il est tout naturel pour tout un chacun de trouver le chemin le plus court étape par étape. Le problème qui se pose est pour programmer et automatiser un pathfinding. En effet, analyser étapes par étapes les différentes possibilités serait trop long. En d' autres termes, réfléchir instinctivement pour programmer un pathfinding n'est pas possible.

La notion de Matrices doit être connue pour comprendre la suite.

Les relations entre cases:

En utilisant le principe des graphes on peut mettre en relation toutes cases voisines à partir du moment où aucune d' elles n'est un obstacle et qu'elles sont adjacentes.

Prenons l'exemple suivant :

Mat1.png

Ici, les cases A et B sont en relation car aucune d'elles n'est un obstacle et elles sont adjacentes.

Les cases A et C ne sont pas en relation car la case C est un obstacle

Pour illustrer la transformation d'un tableau en matrice en représentant les relations, prenons l' exemple suivant :

Mat2.png

La taille de la matrice sera donc (nombre de cases du tableau)^2.

Ensuite, il faut illustrer les relations donc on met un 1 partout où les cases sont en relations

On lit dans le sens de la flèche c'est à dire : "A est en relation avec B" => On met un 1 sur la case en commun avec la ligne de A et la colonne de B et ainsi de suite.

Cette matrice représente donc les chemins possibles de longueur 1 entre toutes les cases

Si on monte la matrice à la puissance 2 (voir le principe des produits matriciels) on obtient les chemins possibles de longueur 2 entre toutes les cases et ainsi de suite.

Il faut maintenant augmenter la puissance de la matrice jusqu'à ce qu'on obtienne un 1 sur la ligne correspondant au point de départ et la colonne correspondant au point d' arrivée. La nombre de la puissance sera alors la longueur minimale du chemin pour aller du départ à l' arrivée.


Prenons la matrice précédente à la puissance 2 :

Mat3.png

On remarque donc que pour aller du point A au point D il existe deux chemin de longueur 2 soit A->B->D et A->C->D.

Sur un tableau beaucoup plus grand on peut donc avoir la longueur minimale du chemin d'un point à un autre.

La découverte progressive du chemin le plus court :

En reprenant l' exemple précédent :

Mat4.png

Une fois la puissance de la matrice découverte, il suffit de la faire baisser de 1 et faire les comparaisons suivante :

  • On regarde qu'elles case sont en relation de longueur 1 avec l'arrivée (D) sur la matrice initiale.
  • On regarde ensuite parmi ces case lesquelles sont en relation de longueur dégressive de 1 par rapport au maximum avec le départ.

Dans l'exemple fourni, cela donnerait :

  • La puissance 2 est la puissance minimum pour aller du départ (A) à l' arrivée (D) donc le chemin le plus court est de longueur 2.
  • En regardant la colonne D sur la matrice initiale, on remarque que les cases en relation avec la case D de longueur 1 sont les cases B et C.
  • On regarde avec la matrice puissance 2-1 soit (puissance Maximum)-1 donc la matrice puissance 1 si A est en relation avec l'une des case B et C. Dans l' exemple fourni, A est en relation de longueur 1 avec les deux (ce qui n'est pas toujours le cas notamment quand il y a des obstacles).

Sur plus grande échelle il faudrait enregistrer les cases qui sont dans le chemin le plus court. Avec cette méthode on a donc la possibilité de programmer un pathfinding en utilisant des connaissances mathématiques : les matrices !













--Gustave d' Amécourt--