Calcul chemin le plus court à partir d'un labyrinthe

Signaler
Messages postés
111
Date d'inscription
mercredi 19 mai 2010
Statut
Membre
Dernière intervention
2 juin 2015
-
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
-
Bonjour,


J'ai un mini projet à réaliser en JAVA dont le but est qu'à partir d'une image, générer un labyrinthe et calculer le chemin le plus court de celui ci labyrinthe.

Exemple : Image en Exemple

Comment pourrais-je réaliser cela en JAVA ?


Merci d'avance pour ceux qui se pencheront sur mon problème
A voir également:

5 réponses

Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
Ton problème, c'est l'algorithme de recherche du plus court chemin ou bien la création d'un labyrinthe à partir de l'image ?
Messages postés
111
Date d'inscription
mercredi 19 mai 2010
Statut
Membre
Dernière intervention
2 juin 2015
1
Pour être honnête les deux mais savoir quels types d'algo appliquer pour le chemin le plus court me permettra de savoir déjà si je transforme mon image en graph connexe ou en matrice
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
Je ne l'ai jamais fait mais je partirai sur Dijkstra, plus simple que A* et plus adapté aux labyrinthes je pense.
Messages postés
111
Date d'inscription
mercredi 19 mai 2010
Statut
Membre
Dernière intervention
2 juin 2015
1
Dijstra s'applique qu'aux graph connexes non ?

Cet exemple (voir post 2) ressemble à Disjtra mais pour les matrice, est il facile d'adapter le code en JAVA ?


Merci encore
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
Je pense qu'un labyrinthe est assimilable à un graphe connexe. Au pire, tu peux ignorer toutes les zones non atteignables du labyrinthe et tu obtiendras un graphe connexe (chaque case représente un nœud et chaque "non-mur" une arête de poids = 1).