Chemin le plus court A*
esiee_amiens
Messages postés
1
Date d'inscription
lundi 20 mars 2006
Statut
Membre
Dernière intervention
21 mai 2006
-
21 mai 2006 à 20:50
Akoril Messages postés 3 Date d'inscription dimanche 18 décembre 2005 Statut Membre Dernière intervention 31 juillet 2006 - 30 mai 2006 à 10:03
Akoril Messages postés 3 Date d'inscription dimanche 18 décembre 2005 Statut Membre Dernière intervention 31 juillet 2006 - 30 mai 2006 à 10:03
A voir également:
- Chemin le plus court A*
- Vba chemin relatif ✓ - Forum VB.NET
- Mvn : le terme «mvn» n'est pas reconnu comme nom d'applet de commande, fonction, fichier de script ou programme exécutable. vérifiez l'orthographe du nom, ou si un chemin d'accès existe, vérifiez que le chemin d'accès est correct et réessayez. - Forum Java
- Chemin relatif ✓ - Forum C# / .NET
- Image chemin - Forum Visual Basic
- Chemin relatif/absolu fichier ✓ - Forum VB.NET
4 réponses
nightlord666
Messages postés
746
Date d'inscription
vendredi 17 juin 2005
Statut
Membre
Dernière intervention
23 mai 2007
10
22 mai 2006 à 06:24
22 mai 2006 à 06:24
Va voir le tutorial de Pathfinding sur jpeglauden.free.fr, tu y trouvera une source qui utilise A* pour chercher le chemin entre deux points.
tekila_bandita
Messages postés
248
Date d'inscription
mercredi 15 juin 2005
Statut
Membre
Dernière intervention
15 mars 2007
33
23 mai 2006 à 19:33
23 mai 2006 à 19:33
Moi je dirais simplement que tu devrais faire une fonction te cherchant
un reponse possible, tu stoque la reponse dans un string, et ensuite tu
regarde ça longueur...
La fonction prendrait un int en argument, et selon le int, elle
testerai une possibilité plutot qu'une autre, pour te souvenir de la
bonne reponse, les reponses seront plutot stoqué dans un tableau de
string avec le int argument de la fonction correspondant a l'index de
la case du tableau correspondant...
Je ne suis pas très clair mais bon, j'ai essayé...
un reponse possible, tu stoque la reponse dans un string, et ensuite tu
regarde ça longueur...
La fonction prendrait un int en argument, et selon le int, elle
testerai une possibilité plutot qu'une autre, pour te souvenir de la
bonne reponse, les reponses seront plutot stoqué dans un tableau de
string avec le int argument de la fonction correspondant a l'index de
la case du tableau correspondant...
Je ne suis pas très clair mais bon, j'ai essayé...
Akoril
Messages postés
3
Date d'inscription
dimanche 18 décembre 2005
Statut
Membre
Dernière intervention
31 juillet 2006
30 mai 2006 à 10:00
30 mai 2006 à 10:00
Javascript:Insert_Emoticon('/imgs2/smile_wink.gif'); Un algo simple… Méthode Barby dit d’inondation
Tu remplaces 1, 2 et 3 respectivement par X, 1 et B. On démarre donc à 1 et on va vers B, ensuite…
Tant qu’on a fait une affectation…
Tu parcours ta matrice, pour chaque élément (i, j)…
Pour chacun de ces voisins (o, p) soit pour (o, p) les valeurs (i-1, j-1) - > (i + 1, j + 1) si tu autorises les diagonales si nom c’est plutôt (i-1, J), (i + 1, j), (i, j-1) et (i, j + 1)…
Si l’un deux a la valeur X ou B tu passes au suivant
Si les deux on la valeur 0 tu passes au suivant
Soit dist la distance entre les points, 1 ou 1.414 (pour les diagonales), mais on peut avoir n’importe quelle pondération en fonction du terrain par exemple.
Tu regardes si (i, j) est supérieur > 0 et si (o, p) = 0 ou-bien (o, p) > (i, j) + dist ==> auquel cas (o, p) = (i, j) + dist.
Sinon si (i, j) = 0 ==> (i, j) = (o, p) + dist.
Voilà. Attention on ne s’arrête vraiment que quand un passage de toute la matrice ne génère pas une affectation… On peut arriver en B par un premier chemin calculer, mais en trouver un autre plus tard…
C’est algo est plutôt fait pour un graphe ou la distance entre les nœuds est variable, ici c’est peut-être pas le cas.
Les avantages de l’algo sont :
Il est simple d’interrompre (n’importe ou) le calcul pour faire une autre tache, et reprendre au début de l’algo. C’est nécessaire pour une interaction rapide avec l’utilisateur.
On peut avoir une solution provisoire, (qui n’est pas forcément la bonne), au fur et à mesure la solution va s’affiner.
On a les solutions (si elles existent) pour n’importe quel point de destination de la matrice. Avantage si la destination (cible) se déplace…
On peut limiter l'algo a une portion de la matrice.
La (es) solution (s) ?
On par de B on cherche dans ses voisins, celui qui a la plus petite valeur (différent de X évidement) et on remonte le chemin a rebrousse poil, en choisissant toujours le plus petit
Rien n'est tout noir ou tout blanc...Javascript:Insert_Emoticon('/imgs2/smile.gif');
Tu remplaces 1, 2 et 3 respectivement par X, 1 et B. On démarre donc à 1 et on va vers B, ensuite…
Tant qu’on a fait une affectation…
Tu parcours ta matrice, pour chaque élément (i, j)…
Pour chacun de ces voisins (o, p) soit pour (o, p) les valeurs (i-1, j-1) - > (i + 1, j + 1) si tu autorises les diagonales si nom c’est plutôt (i-1, J), (i + 1, j), (i, j-1) et (i, j + 1)…
Si l’un deux a la valeur X ou B tu passes au suivant
Si les deux on la valeur 0 tu passes au suivant
Soit dist la distance entre les points, 1 ou 1.414 (pour les diagonales), mais on peut avoir n’importe quelle pondération en fonction du terrain par exemple.
Tu regardes si (i, j) est supérieur > 0 et si (o, p) = 0 ou-bien (o, p) > (i, j) + dist ==> auquel cas (o, p) = (i, j) + dist.
Sinon si (i, j) = 0 ==> (i, j) = (o, p) + dist.
Voilà. Attention on ne s’arrête vraiment que quand un passage de toute la matrice ne génère pas une affectation… On peut arriver en B par un premier chemin calculer, mais en trouver un autre plus tard…
C’est algo est plutôt fait pour un graphe ou la distance entre les nœuds est variable, ici c’est peut-être pas le cas.
Les avantages de l’algo sont :
Il est simple d’interrompre (n’importe ou) le calcul pour faire une autre tache, et reprendre au début de l’algo. C’est nécessaire pour une interaction rapide avec l’utilisateur.
On peut avoir une solution provisoire, (qui n’est pas forcément la bonne), au fur et à mesure la solution va s’affiner.
On a les solutions (si elles existent) pour n’importe quel point de destination de la matrice. Avantage si la destination (cible) se déplace…
On peut limiter l'algo a une portion de la matrice.
La (es) solution (s) ?
On par de B on cherche dans ses voisins, celui qui a la plus petite valeur (différent de X évidement) et on remonte le chemin a rebrousse poil, en choisissant toujours le plus petit
Rien n'est tout noir ou tout blanc...Javascript:Insert_Emoticon('/imgs2/smile.gif');
Akoril
Messages postés
3
Date d'inscription
dimanche 18 décembre 2005
Statut
Membre
Dernière intervention
31 juillet 2006
30 mai 2006 à 10:03
30 mai 2006 à 10:03
Ben c’est un peu le bazar, la présentation a sauté Javascript:Insert_Emoticon('/imgs2/smile_dissapprove.gif');
Rien n'est tout noir ou tout blanc...Javascript:Insert_Emoticon('/imgs2/smile.gif');
Rien n'est tout noir ou tout blanc...Javascript:Insert_Emoticon('/imgs2/smile.gif');
