Bonjour à tous,
 
 
Je suis en train de réaliser une application en c, la partie graphique est réalisée avec sdl. Un robot doit se deplacement de facon autonome dans une piece (un labyrinthe) ou il y a des murs et divers obstacles. J'ai codé la génération du labyrinthe et le déplacement du robot mais je bloque sur l'intelligence artificielle.
 
En effet mon robot utilise une stratégie "vers la gauche" c'est a dire qu'il se déplace dans une direction tant qu'il le peut et quand il est bloqué (par un mur par exemple) il effectue diverses rotations (vers la gauche) jusqu'a pouvoir se deplacer dans une direction. Il tient compte aussi de la priorité c'est a dire qu'il passera en priorité dans un chemin qu'il n'a pas emprunté auparavant.
 
Mon problème est que le robot doit explorer TOUTE la salle et cela en un minimum de temps. J'ai regardé des algorithmes de pathfing comme celui de dijstra ou le A* mais j'ai l'impression que je fais fausse route ... car ces algorithmes sont utilisés pour trouver les chemins les plus court et non pas parcourir tout en ensemble ?
 
Pourriez vous m'aider   !
Merci d'avance!

bah solution super bourine :  
Dans une liste, tu mets toutes les salles de ton labyrinthe, et tu fais un parcours entre ton robot et la pièce, tu dépille, et tu continue comme ça, jusqu'a ne plus avoir de pièce dans ta liste.
 
spa génial mais bon  

j'y avait justement pensé a chaque case on empile ses voisines mais je ne suis pas convaincu que ca va bien marcher... car on va totu de meme repasser par certaines cases un bon nombre de fois non?  
Mais est ce que c'est la seule solution personne ne connait des algorithmes permettant de resoudre ce problème?

algo de couverture de sommet dans un graphe,
algo du voyageur de commerce

Si tu ne connais pas à l avance le labyrinthe, mais que les salles sont de même taille, ton idée de dijstra c est mieux.
 
Tu est obligé de tester tous les murs du labyrinthe, soit avec le robot, soit avec la carte (salles adjacentes déjà explorées), mais c est avec un algo de plus court chemin seulement que tu peut te déplacer d un bout à l autre du labyrinthe de façon efficace.

Les solutions de nargy seront très efficaces.
Sinon il existe une solution tout bête qui marche (sauf dans le cas de murs orphelins), c'est de suivre le mur qu'on a à droite.

Quel rapport avec le langage C ? Il y a une section ALGO sur ce site.
 

Théorie des graphes;
 
plus d'explications:
http://www.vieartificielle.com/art [...] php?id=161

J ai essayé de formaliser un peu le problème.
 
D abord il s agit d une structure de graphe, dans tous les cas, aussi on a le choix entre 3 types d algos:
- parcours non cyclique: O(n)
- plus courts chemin: O(n*n)
- couverture de sommet: O(n^n)
 
Si on considère que l on ne peut connaître que la place des murs, on ne connait pas par avance ni la géométrie des salles, ni la disposition du labyrinthe:
le graphe est composé de:
- les coins
- les murs
Il y a exactement 2 murs pour 1 coin (car les murs ont une épaisseur):

Le seul algo possible est celui du tournant à gauche.
 
Si on considère que l on connait par avance la géométrie des salles, par exemple elles ont toutes la même taille:

alors on est pas obligé de parcourrir tous les murs, on peut faire des supposition sur les salles adjacentes. Par exemple les mur marqués dune astérisque: quand on découvre un couloir on est pas obligé de le traverser si on a déjà exploré la salle à l autre bout.
Dans ce cas on peut utiliser un algo de plus court chemin.
 
Si on connait le labyrinthe à l avance, on peut utiliser un algo de couverture de sommet.
 
Dans le cas particulier du robot, il me semble que tu te trouve dans le cas n°1, mais tu peut te trouver dans le cas n°2 sans faire de supposition sur la géométrie des salles. Le robot, lorsqu il détecte un mur, a une précision. Il ne peut détecter des murs trop petits (même s il bloque dessus) ou des passages trop petits. Tu mesure la précision de mesure de ton robot, et alors tu te trouve dans le cas n°2: tu peut diviser le labyrinthe en carrés de taille égale à la précision. Le robot se met alors à parcourrir le labyrinthe en optimisant les trajectoires, et peut choisir le plus court chemin entre une zone explorée et non explorée.
 
Reste à traiter le cas particulier du mur trop petit sur lequel le robot bloque: dans ce cas tu agrandi le mur sur ta carte de carrés pour le représenter, et tu maintient une deuxième carte avec les position exactes mesurées.
 

Merci à tous!

C'est le cas ici en fait le labyrinthe et générer de facon aléatoire et le robot ne connait pas le labyrinthe il l'explore case par case
 

Les salles ou plutot les pieces ont en effet toutes la meme taille et en fait chaque piece (case) peut avoir une cloison en haut en bas a gauche et a droite. L'ensemble des pieces formant le labyrinthe.
 
Je vais regarder tout ca cette apres midi je vous tiens au courant. Merci.

Bonjour,
 
Je me permets de vous contacter au Sujet de votre post : Intelligence artificielle dans un labyrinthe.
Je suis actuellement en école d’ingénieur et j'ai le même projet à réaliser a quelques détails près qui sont que le robot peut se déplacer en diagonale et qu'il doit trouver la sortie en un minimum de coup.
Ayant redigé un code assez complexe et plutot long je voulais savoir si il vous été possible de m'envoyer vos sources (code source C) ou tout simplement de m'aider si vous  
en avez le temps.
 
Cordialement Hakim.
 

Utilise le A*, c'est le plus optimisé je pense.
T'as des exemples sur le net, nous on ne peut te donner du code tout fait, par contre on est là pour t'aider.

Bonjour, je viens juste de commencer le même travail que toi avec un robot a base d'arduino, mais j'arrive pas a trouvé une solution de parcours de toute la  labyrinthe en enregistrant les chemins non parcourus          

Bonjour, je viens juste de commencer le même travail que toi avec un robot a base d'arduino, mais j'arrive pas a trouvé une solution de parcours de toute la  labyrinthe en enregistrant les chemins non parcourus