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

Soyez le premier à donner votre avis sur cette source.

Vue 37 301 fois - Téléchargée 5 073 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

Ajouter un commentaire

Commentaires

Pym Corp
Messages postés
167
Date d'inscription
jeudi 9 décembre 2004
Statut
Membre
Dernière intervention
18 novembre 2007
-
Du très beau boulot :D
JJDai
Messages postés
291
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
13 mars 2015
-
Merci:
J'enchaine sur une version avec recherche dans les 8 directions maintenant.
Ca devrait pas être trop compliqué.
mongol77
Messages postés
75
Date d'inscription
dimanche 2 octobre 2005
Statut
Membre
Dernière intervention
24 juin 2007
-
trés interressant tout ca, moi j'utilise vb6 , mais je vais peut etre m'en servir pour un projet de jeu.

note : 8/10 rien que pour nous avoir filer l'algo
JJDai
Messages postés
291
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
13 mars 2015
-
Le plus embetant avec vb6 c'est l'afichage qu'il vaut réalisé avec l API plutot qu'en faisant des groupe de controles (comme j'ai vu dans certains exemples) qui sont très consomateur de ressource et de temps d'affichae.
cs_Stephane33
Messages postés
630
Date d'inscription
samedi 15 février 2003
Statut
Modérateur
Dernière intervention
9 octobre 2011
-
Personnellement j'ai réalisé un programme sous eVb (VB pour Pocket PC) intégrant djikstra afin de déterminer une distance kilométrique et c'est pas facile.
En tout cas bon travail
Perso je me suis appuyé sur ce site http://www.nimbustier.net/publications/djikstra/index.html

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.