Sujet Précédent Sujet Suivant

Recherche de chemin / pathfinding particulier

Fermé
John - Modifié par John le 25/08/2010 à 17:24
Defouille Messages postés 388 Date d'inscription mercredi 13 janvier 2010 Statut Membre Dernière intervention 15 novembre 2011 - 27 août 2010 à 14:06
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.

1 réponse

Réponse 1 / 1
Defouille Messages postés 388 Date d'inscription mercredi 13 janvier 2010 Statut Membre Dernière intervention 15 novembre 2011 54
25 août 2010 à 17:10
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
0
John
25 août 2010 à 17:24
Ce qui me pose problème en fait c'est trouver le chemin le plus court avec un nombre déterminé de vortex (raccourci) et le temps de calcul.
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.
0
Defouille Messages postés 388 Date d'inscription mercredi 13 janvier 2010 Statut Membre Dernière intervention 15 novembre 2011 54
25 août 2010 à 17:35
Pourquoi avoir besoin d'un nombre précis de vortex ?
0
John
25 août 2010 à 17:49
parce que au-delà de 3 le trajet devient trop complexe pour l'utilisation qui en est faite par la suite et que si par exemple on se limite a un on peux avoir un résultat très rapidement.

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 :)
0
Defouille Messages postés 388 Date d'inscription mercredi 13 janvier 2010 Statut Membre Dernière intervention 15 novembre 2011 54
26 août 2010 à 08:38
Tu stockes comment les relations entre les points ? (savoir de quel point au point aller à partir d'un autre, et avec quel cout ?)
0
John
26 août 2010 à 09:48
Chaque points (morceau de carte) a des coordonnées X et Y. Comme il n'y a pas d'obstacle il est possible d'aller vers n'importe quel point depuis n'importe quel autre point. Le cout de ce chemin sans emprunter de vortex se calcul a peu près de cette façon :

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
0

Discussions similaires

recherche à partir de la barre d'adresse
Sylviane -
Lulin -

11 réponses
numero de tel de particulier au maroc
ancremary -
rolex33 -

1 réponse
annuaire telephonique de maroc telecom IAM
dina -
alo -

14 réponses
Rechercher dans l'annuaire téléphonique
maryse4499 -
piquesous -

2 réponses
1fichier
titi342 -
bazfile -

1 réponse