Recherche de chemin / pathfinding particulier
John
-
Defouille Messages postés 388 Date d'inscription Statut Membre Dernière intervention -
Defouille Messages postés 388 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
mon problème concerne une recherche du chemin le plus court mais dans un cas un peu spécial.
Je me suis déjà documenté sur Djikstra et A* mais j'aimerai avoir votre avis et votre aide car mon cas n'est pas celui qui est décrit un peu partout.
Je possède une carte bidimensionnelle découpée en petits carrés. Elle est de taille n*n (plus particulièrement 100*100).
Tout les points (carrés) sont atteignables depuis n'importe ou (il n'y a pas d'obstacle).
les distances entre les points (poids des arcs) sont de 1 pour un déplacement horizontal ou vertical et de 1.5 pour un déplacement diagonale.
Jusqu'ici rien de bien particulier je vous l'accorde a la limite y a pas trop a chercher vu qu'il n'y a pas d'obstacle...
La subtilité c'est que la carte possède des raccourcis c'est a dire que certains point de la carte sont reliés (par 2) par un chemin de poids 0.
Mon but est de trouver le chemin le plus court entre 2 points de la carte en empruntant 1, 2 ou 3 de ces raccourcis et sans que ça prenne 10 minutes de calcul.
Voila j'espère avoir été clair et pas trop long.
J'attends vos idées avec impatience.
Merci d'avance a ceux qui voudrons bien m'aider.
Edit:
Je précise que les données de départ sont une liste de paires de coordonnées caractérisant les extrémités des vortex (raccourcis) plus les coordonnées des points de départ et d'arrivée.
mon problème concerne une recherche du chemin le plus court mais dans un cas un peu spécial.
Je me suis déjà documenté sur Djikstra et A* mais j'aimerai avoir votre avis et votre aide car mon cas n'est pas celui qui est décrit un peu partout.
Je possède une carte bidimensionnelle découpée en petits carrés. Elle est de taille n*n (plus particulièrement 100*100).
Tout les points (carrés) sont atteignables depuis n'importe ou (il n'y a pas d'obstacle).
les distances entre les points (poids des arcs) sont de 1 pour un déplacement horizontal ou vertical et de 1.5 pour un déplacement diagonale.
Jusqu'ici rien de bien particulier je vous l'accorde a la limite y a pas trop a chercher vu qu'il n'y a pas d'obstacle...
La subtilité c'est que la carte possède des raccourcis c'est a dire que certains point de la carte sont reliés (par 2) par un chemin de poids 0.
Mon but est de trouver le chemin le plus court entre 2 points de la carte en empruntant 1, 2 ou 3 de ces raccourcis et sans que ça prenne 10 minutes de calcul.
Voila j'espère avoir été clair et pas trop long.
J'attends vos idées avec impatience.
Merci d'avance a ceux qui voudrons bien m'aider.
Edit:
Je précise que les données de départ sont une liste de paires de coordonnées caractérisant les extrémités des vortex (raccourcis) plus les coordonnées des points de départ et d'arrivée.
A voir également:
- Recherche de chemin / pathfinding particulier
- Meilleur site de vente entre particulier - Guide
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Rechercher ou entrer l'adresse mm - recherche google - Guide
- Fréquence tnt recherche manuelle - Forum Téléviseurs
- Recherche photo - Guide
1 réponse
Bonjour,
un algorithme A* est adapté à ton problème, il faut juste que dans ta méthode de stockage des liens entres 2 points tu prennes en compte les raccourcis.
Et donc lors du déroulement de l'algo tu traites les raccourcis comme des points atteignables.
un article sur A* (en anglais, mais très bien expliqué)
https://www.gamedev.net/reference/articles/article2003.asp
un algorithme A* est adapté à ton problème, il faut juste que dans ta méthode de stockage des liens entres 2 points tu prennes en compte les raccourcis.
Et donc lors du déroulement de l'algo tu traites les raccourcis comme des points atteignables.
un article sur A* (en anglais, mais très bien expliqué)
https://www.gamedev.net/reference/articles/article2003.asp
En effet s'il n'y a pas de vortex le chemin le plus court c'est la ligne droite entre les 2 points donc considérer les points de la carte ne possédant pas de raccourci me semble superflus.
Je précise que les données de départ sont une liste de paires de coordonnées caractérisant les extrémités des vortex (raccourcis) plus les coordonnées des points de départ et d'arrivée.
En tous cas merci pour le lien il est effectivement pratique.
j'ai déjà un bout de code qui me permet de calculer des chemins avec 1 ou 2ou 3 vortex mais ce n'est pas du tout optimisé et ne se repose sur aucune théorie. et un calcul avec 3 vortex eut prendre plus de 30 secondes ce qui est embêtant si je veux l'héberger sur un serveur mutualisé qui coupe les exécution qui dure plus de 30 sec....
Et puis surtout je voudrais faire un truc optimisé pour le principe. Je sens bien qu'il doit y avoir une solution mais je bute encore un peu :)
Soit Xa, Xb, Ya, et Yb les coordonnées en X et Y des points A et B.
X= | Xb-Xa |
Y= | Yb-Ya |
le cout entre A et B sans vortex est de : c= sqrt ( X²+Y²)
Pour éviter de me trimballer des flottant et d'utiliser la racine carrée je fais des comparaison sur les carrés. donc c = X²+Y²
Pour ce qui est du stockage du chemin s'il n'y a pas de vortex alors il c'est une paires de coordonnées celles de départ et d'arrivé.
S'il y a des vortex alors entre les 2 coordonnées précédente vienne s'insérer des couple de coordonnées représentants l'entrée et la sortie des vortex.
Je sais pas si c'est clair mais bon si c'était simple je ne demanderai pas d'aide en même temps :D