[Cherche]tutoriel pathfinding
Résolu/Fermé
maxime44
Messages postés
704
Date d'inscription
jeudi 1 mai 2008
Statut
Membre
Dernière intervention
3 juillet 2013
-
22 sept. 2008 à 19:10
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 23 sept. 2008 à 10:28
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 23 sept. 2008 à 10:28
A voir également:
- [Cherche]tutoriel pathfinding
- Tutoriel onedrive - Guide
- Tutoriel google drive - Guide
- Tutoriel tableau croisé dynamique - Guide
- Tutoriel table des matières word - Guide
- Tutoriel chromecast - Guide
1 réponse
mamiemando
Messages postés
33446
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
20 décembre 2024
7 812
23 sept. 2008 à 10:28
23 sept. 2008 à 10:28
Au pire tu utilises un algorithme de Dijkstra qui retourne un chemin optimal entre une source et une destination. Si ton univers est découpé en case, tu construis un graphe avec un sommet par case accessible par le personnage, et tu relies deux sommets avec un arc si les deux cases sont adjacentes. Ensuite tu mets un poids à chaque arc (1 si toutes les cases sont longues à traverser, une valeur autre si la notion de terrain impacte la vitesse de déplacement).
Supposons que tu es neuf case mais que la 8e soit un obstacle :
Ton graphe sera (si le personnage ne peut se déplacer que verticalement ou horizontalement) :
Une fois le graphe construit, il suffit de calculer un algorithme de Dijkstra partant de la case sur laquelle se trouve ton sommet. Par exemple si es sur la case 1 et que tu veux joindre la case 9, tu calcules un algorithme de DIjkstra depuis 1 et il retournera par exemple pour le sommet 9 le chemin 1,2,5,6,9.
L'avantage c'est que l'algorithme de Dijkstra est disponible presque partout (y compris sur wikipedia) ce qui évite de le coder.
Comme expliqué dans la page wikipedia suivante :
https://fr.wikipedia.org/wiki/Path-finding
... si des obstacles se déplacent sur le terrain ça devient plus compliqué, et un algorithme de type A* est peut être plus pertinent. Comme cet algorithme est moins répendu il faudra peut être faire l'effort de chercher en anglais, ou éplucher un cours d'intelligence artificielle.
Bonne chance
Supposons que tu es neuf case mais que la 8e soit un obstacle :
+-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+ | |X| | +-+-+-+
Ton graphe sera (si le personnage ne peut se déplacer que verticalement ou horizontalement) :
1-2-3 | | | 4-5-6 | | 7 9
Une fois le graphe construit, il suffit de calculer un algorithme de Dijkstra partant de la case sur laquelle se trouve ton sommet. Par exemple si es sur la case 1 et que tu veux joindre la case 9, tu calcules un algorithme de DIjkstra depuis 1 et il retournera par exemple pour le sommet 9 le chemin 1,2,5,6,9.
L'avantage c'est que l'algorithme de Dijkstra est disponible presque partout (y compris sur wikipedia) ce qui évite de le coder.
Comme expliqué dans la page wikipedia suivante :
https://fr.wikipedia.org/wiki/Path-finding
... si des obstacles se déplacent sur le terrain ça devient plus compliqué, et un algorithme de type A* est peut être plus pertinent. Comme cet algorithme est moins répendu il faudra peut être faire l'effort de chercher en anglais, ou éplucher un cours d'intelligence artificielle.
Bonne chance
