Commentçamarche.net
CodeS-SourceS
Rechercher un code, un tuto, une réponse

Calcul optimisé du chemin le plus court entre 2 points d'une grille

4/5 (21 avis)

Vue 35 665 fois - Téléchargée 4 829 fois

Description

Ce projet permet de calculer le chemin d'un point à un autre dans une matrice comportant des obstacles.
J'ai utiliser le principe de Djikstra.

Adresse à voir:
<http://www.cs.utexas.edu/users/EWD/>
<http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra>

Source / Exemple :


Utilisation:
1 - Définir la taille de la matrice
2 - Dessiner les obstacles (Sélectionnez le bouton radio "obstacle" et cliquer sur la zone de dessin en déplaçant la souris.
3 - Définissez le point de départ: cliquer sur le bouton radio "départ" et cliquer sur la zone de dessin.
4 - Calculer les pois : bouton de commande "calculez les poids".
5 - Clique sur la matrice pour définir le point d'arrivée, le chemin s'affiche s'i il existe.

Options:
1 - sens de rotation: dans la recherche du chemin les cellules sont analysées dans le sens des aiguille d'une montre par défaut. Cette option permet d'inverser le sens de rotation pour l'analyse.
2 - Start Rotation: par défaut la recherche du chemin sont analysée à partir de la cellules se trouvant au nord de la précédente. Cette option permet de commencer l'analyse dans une autre direction (nord, ouest, sud, est)
3 - Optimisation: 3 niveaux. dans tous les cas il s'agit de diminuer le nombre de virages. Le nombre de points est toujours le plus cours chemin quelque soit le niveau d'optimisation. Le niveau 0 est le plus rapide à calculer et le 3 le moins rapide car il recherche tous les chemin possible et retient celui qui a le moins de virages.

Résultat :
Le « GroupeBox » en bas à droite du formulaire indique le nombre de points et de virages du chemin.

Exemple :
Le bouton de commande « Exemple » génère une grille pré remplie et se place automatique sur le niveau 2..
Modifiez les options et cliquez sur la grille pour faire apparaître les chemins.

Codes Sources

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.