Travaux : Php
Pathfinding en PHP (dans Php, le 23/12/2009 à 13h 06min, édité 2 fois, dernier le 02/01/2010 à 19h 18min)
Le pathfinding, ou recherche de chemin en français, consiste grossièrement à trouver un chemin entre un point de départ et un point d'arrivé, respectant certaines contraintes (le plus court possible, par exemple).
C'est un problème qui peut se rapprocher à de la recherche opérationnelle :
J'ai implémenté un pathfinder basé sur l'algorithme A* (A étoile, A star), dont vous trouverez le principe ici : article A* sur Wikipédia.
La mise en place de cette algorithme ne pose pas de problème d'implémentation, il faut juste se choisir une heuristique à peu près pertinente; je n'ai pas cherché très loin et j'ai pris : "on part du principe qu'il n'y a plus d'obstacle sur notre route, le coût du chemin restant est donc la distance géométrique" (sqrt(a²+b²), Pythagore, vous vous souvenez ? ;) )
Vous pourrez trouver ici :
Je trouve ça fascinant de construire un mur, et de voir le chemin se dessiner au fur et à mesure (alors que finalement ce n'est pas bien compliqué). :)
Le pathfinding, ou recherche de chemin en français, consiste grossièrement à trouver un chemin entre un point de départ et un point d'arrivé, respectant certaines contraintes (le plus court possible, par exemple).
C'est un problème qui peut se rapprocher à de la recherche opérationnelle :
Citation : Wikipédia
A la base, un problème de pathfinding peut se ramèner à un problème de recherche du meilleur chemin entre deux noeuds dans un graphe. Il existe un ensemble d'algorithmes classiques pour résoudre ce type de problème. Toutefois, le pathfinding devient un problème complexe lorsque l'on cherche à prendre en compte diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc).
J'ai implémenté un pathfinder basé sur l'algorithme A* (A étoile, A star), dont vous trouverez le principe ici : article A* sur Wikipédia.
La mise en place de cette algorithme ne pose pas de problème d'implémentation, il faut juste se choisir une heuristique à peu près pertinente; je n'ai pas cherché très loin et j'ai pris : "on part du principe qu'il n'y a plus d'obstacle sur notre route, le coût du chemin restant est donc la distance géométrique" (sqrt(a²+b²), Pythagore, vous vous souvenez ? ;) )
Vous pourrez trouver ici :
- la source php
- une démonstration du script : cliquez sur les cases pour les transformer en mur
Je trouve ça fascinant de construire un mur, et de voir le chemin se dessiner au fur et à mesure (alors que finalement ce n'est pas bien compliqué). :)