Pathfind astar : recherche du chemin le plus cours entre deux points

Soyez le premier à donner votre avis sur cette source.

Vue 8 493 fois - Téléchargée 579 fois

Description

Dans le monde de l'infographie, il arrive forcément un moment où l'on doit mettre un objet en mouvement. En mouvement pour faire quoi ? Pour aller d'un point à un autre. Dans certain cas, c'est une ligne droite. je doit bien admettre que faire une source qui explique comment deplacer un point en ligne droite m'a effleuré l'esprit, mais je me suis vite ravisé. Dans la majorité des cas, c'est dans un univers parsemmé d'obstacle que ce point se déplacera. Dans ce cas, pour trouver le meilleur chemin possible (le chemin qui neccessite le moins de déplacement) entre des murs, il nous faut un algorithme de pathfinding. Les algo de pathfinding, c'est comme les algo de tri. il y en a plein de différent, et ils ont tous des avantages et des inconvénients, selon la configuration dans laquelle ils travaillent. L'Astar est à mon sens le plus intuitif des algo de pathfinding. Pas forcément le plus rapide (en temps de calcul), mais il a le mérite d'être fiable en ce sens où chaque possibilité est étudiée et comparée aux autres.

Dans ce programme, on évolue sur une matrice de 20*20 noeud (soit 400 noeuds). On dessine les murs, on place le départ et l'arrivé, on clique sur un bouton, et on regarde :D

J'ai fait de mon mieux pour commenter le code au maximum (je crois qu'il y a plus de commentaire que de code...) et je recomande vivement à tous ceux qui veulent essayer de comprendre l'Astar de lire l'article d'une personne que je remercie chaleureusement de l'avoir écrit à cette adresse :
http://lalex.media-box.net/post/2003/09/15/Traduction-:-article-sur-le-pathfinding-A
Merci LAlex !

Bon pathfind !

Daemonight, pour vous servir
daemonight@yahoo.fr

Source / Exemple :


Public Sub telecharger(byval fichier as fichier_zip)
.
.
.
End Sub

Conclusion :


Je ne pense pas que l'algorithme en lui-même subira des modifications. Bien sûr, il peut être optimisé en matière de volume d'écriture, mais difficilement, je pense, en matière de temps de traitement.

Si vous trouvez des bugs, merci de me le signaler, screenshot à l'appui, mais a priori je n'ai pas trouvé de soucis.

En cas de questions auxquelles la lecture de l'article de LAlex n'aurait pas apporté de réponse, vous pouver m'envoyer un mail, je tenterais de vous répondre le plus clairement possible !

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
40
Date d'inscription
mardi 24 août 2004
Statut
Membre
Dernière intervention
29 décembre 2010
1
ouuuhh, le déterrage de source ^^ je me suis demandé si je rêvais pas en voyant un commentaire sur VB.Net, j'ai pas touché au VB depuis bien deux ans ...
Enfin ravi que cela te serve ! Et je ne suis pas "génial" j'ai juste uilisé un algo deja existant et éprouvé, enfin ca fait plaisir quand même ! Tiens moi au courant pour ton jeu en ligne, il se pourrait que je sois un utilisateur.
Si tu as des questions sur le pathfinding n'hésite pas.
Bon courage !
Messages postés
1
Date d'inscription
mercredi 19 octobre 2005
Statut
Membre
Dernière intervention
9 décembre 2009

T'es génial merci beaucoup! J'ai trouvé ton source super rapidement via google (2ième lien sous "asp.net pathfinding") Je compte l'implémenter dans mon jeu en ligne et te mettrai dans les credits du jeu!

@+
Messages postés
40
Date d'inscription
mardi 24 août 2004
Statut
Membre
Dernière intervention
29 décembre 2010
1
Mais absolument aucun Julien !
Je dirais même qu'elle est là pour ça :-)
J'ai essayé de rendre le code aussi clair que possible afin que justement il puisse être adapté dans un maximum d'applications.
Si tu as des questions n'hésite pas, j'essayerais de te répondre !
Bon courage ;)
Messages postés
883
Date d'inscription
vendredi 3 novembre 2000
Statut
Membre
Dernière intervention
3 mars 2009
6
Je suis en train de faire un petit moteur de jeu de stratégie et je comptais bientôt implémenter cet algorithme pour le déplacement des unités, tu ne vois aucun inconvénient à ce que j'utilise ta source ?
Merci !

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.