Je vois un soucis... imaginons qu'une fois en 6 (en partant de la fin) un mur empêche d'aller en 5. Comment ton algo sait si il doit aller vers le haut où vers le bas pour se rapprocher de son objectif ?
Autre problème, cet algo est inutile.
Si tu veux faire un chemin naif d'un point vers un autre, quelques if suffisent, tu n'as pas besoin de tout ça. A* permet de trouver un chemin dans un labyrinthe, le tiens pas. Si ton parcours en partant de la fin arrive dans une impasse, que fait tu ? une pause café en attendant que le mur disparraisse ?
Et alors ? Un algorithme doit-il pouvoir tout faire ? Pas forcément, si on connaît les limites d'utilisation et qu'il se trouve qu'il est plus performant qu'un autre algo dans un domaine alors pourquoi ne pas l'utiliser ?
De plus s'il y a une impasse, dans ce cas l'algorithme peut "remonter" le chemin jusqu'à un noeud précédent.
Ca ressemble un peu à l'A* quand même
En fait c'est bien joli ton dessin, mais il faut savoir comment tu compte le transformer en algorithme, quelles possibilités as-tu envisagé et tout, sans ca, moi je prend une grille de sudoku je fait un chemin et je demande si c'est un bon algorithme
Et alors ? Un algorithme doit-il pouvoir tout faire ? Pas forcément, si on connaît les limites d'utilisation et qu'il se trouve qu'il est plus performant qu'un autre algo dans un domaine alors pourquoi ne pas l'utiliser ?
De plus s'il y a une impasse, dans ce cas l'algorithme peut "remonter" le chemin jusqu'à un noeud précédent.
Ca ressemble un peu à l'A* quand même
Bah le problème c'est que son algorithme fait en plus compliqué et moins performant la même chose que la méthode naïve (ie : si l'objectif est plus à gauche je vais à gauche, si il est plus haut je vais en haut). A quoi bon perdre son temps à placer des nombres dans une matrice potentiellement immense pour ça ?
Pour le cas de l'impasse, remonter à un noeud précédent ne sert à rien puisse que selon son algo, après être remonté à un noeud précédent il reprendra à nouveau le chemin de l'impasse. Donc cet algorithme ne permet pas de trouver un chemin dans un labyrinthe, ce n'est bien qu'une implémentation maladroite et inutilement complexe de l'algorithme naif.
moi, ma question est : "comment as tu fait pour numéroter toutes tes cases ? " quel algo as tu employé ?
La réponse :
Programme Générer graphe
Initialisation
Variable i, x et y en entier
Variable graphe en tableau bidimentionnel
Début
i = 0 /* position de départ */
Tant que (position(x, y) <> ARRIVEE) Faire /* tant que l'ont n'est pas arrivé (point à eclaircir...) */
x = x + 1 /* on se décale d'un vers la droite */
i = i + 1 /* contient la valeur de la case */
tourner(graphe, i) /* on tourne autour du point de départ */
Fin Tant que
Fin
Procédure tourner(graphe, i)
Initialisation
Paramètre graphe en tableau bidimentionnel
Paramètre i en entier
Variable tour, signe1 et signe2 en entier
Début
/* on fait le tour */
Pour tour Variant de i à 0 Par pas de -1 Faire
Pour signe1 variant de -1 à 1 Par pas de 2 Faire
Pour signe2 variant de -1 à 1 Par pas de 2 Faire
Si ((position(i * signe1, tour * signe2) <> DEHORD) ET (position(i * signe1, tour * signe2) <> MUR)) Faire
position(i * signe1, tour * signe2) = i
Fin Si
Si ((position(tour * signe2, i * signe1) <> DEHORD) ET (position(tour * signe2, i * signe1) <> MUR)) Faire
position(tour * signe2, i * signe1) = i
Fin Si
Fin Pour
Fin Pour
Fin Pour
Fin
PS : Je prefert créer mon propre algo que réimplémenter un déjà existant. Ca m'entraine, ça me donne l'idée que j'ai réalisé quelque chose moi même et c'est ça que j'aime bien.
PS : Je prefert créer mon propre algo que réimplémenter un déjà existant. Ca m'entraine, ça me donne l'idée que j'ai réalisé quelque chose moi même et c'est ça que j'aime bien.
C'est ton droit, mais ça ne change rien au fait que ton algorithme est à revoir. Il est moins performant que la méthode la plus simple (naive), et n'est d'ailleur en rien un algo de recherche du plus court chemin.
Enfin le souci vient du fait qu'il ne sert à priori qu'à décider à chaque tour du prochain déplacement à effectuer. Or pour ça, une simple comparaison des coordonnées suffit, pourquoi utiliser un algorythme lourd pour une tâche aussi simple ? Si celà permettait de trouver un chemin ok, mais là ce n'est pas le cas (dans le cas d'un labyrinthe, tu foncerais dans l'impasse, lol).
Et le plus gros problème si tu veux créer ton propre algo, c'est le remplissage de la matrice. Si cette matrice représente un niveau d'un jeu, il peut être immense. De plus, la quasi totalité des cases que tu numérotes ne servent jamais, il serait plus pertinent de chercher leur valeur que lorsque tu en as besoin.
Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.
Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre. En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.
Au lieu de déterrer un sujet il est préférable :
soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
soit de créer un nouveau sujet décrivant votre propre contexte
ne pas répondre à un déterrage et le signaler à la modération
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html