Travaux : Php
Générateur et solveur de labyrinthes (dans Php, le 02/01/2010 à 19h 17min)
Je vais vous présenter ici le script que j'ai écrit dans le cadre du concours PHP organisé sur le Site du Zér0. L'énoncé ainsi que le topic du concours se trouve ici : sujet du concours.
Pour la petite histoire, j'ai fini 1er ex-æquo de ce concours. :)
Le compte-rendu est disponible ici : résultat sur le SdZ.
Exemple de rendu
Sans rentrer dans les détails (le sujet explique bien le principe, et expose des liens explicatifs sur Wikipédia), le but était d'écrire un générateur de labyrinthes dits "parfaits" (c'est à dire dont toutes les cases sont accessibles par un et un seul chemin). Il fallait ensuite écrire un solveur pour ce labyrinthe, c'est à dire un script permettant de trouver le chemin de l'entrée à la sortie (logique, me direz-vous), et étant indépendant de la partie "génération" (la seule donnée que possède le solveur est le labyrinthe en lui même : aucune information sur le processus de génération n'est fournie).
J'ai globalement documenté ce projet ici : documentation du script, donc je ne vais pas m'attarder sur le code.
Le programme est disponible ici : démo du programme, mais il se peut que sur cet hébergement ça pédale un peu : Free me fourni un hébergement gratuit, mais il n'est pas très performant. Enfin c'est déjà pas mal :). Essayez donc de ne pas trop pousser le script (de toute manière Php s'exécute en safe_mode, donc il se bloquera tout seul). Je vous conseil de valider au moins une fois le formulaire avec les réglages par défaut, ça donne un bon résultat :).
Au niveau de la recherche de la solution, je crée l'arbre des chemins possibles (chaque nœud représente une case, chacun des fils étant les cases atteignables depuis celle-ci), parcouru en profondeur : on avance tant qu'on peut, et si on se retrouve bloqué, on revient en arrière jusqu'à ce qu'on ai un autre choix possible. Puis on recommence à partir de là.
Pour optimisé la recherche, j'ai rajouté une heuristique à peu près pertinente, que je n'ai pas cherché très loin : "si c'est possible, aller vers la droite ou vers le bas". En effet, étant donné qu'on part du coin supérieur gauche, pour aller vers le coin inférieur bas, on aura nécessairement plus de déplacement vers le bas que vers le haut, et plus vers la droite que vers la gauche.
La totalité du projet est disponible ici : http://theclemsweb.free.fr/demo/labyrinthe/laby_clems.rar. Faites-en bon usage !
L'essentiel du script est dans le fichier labyrinthe.class.php. En fait, tout se trouve la dedans, ce qui nuit un peu (beaucoup ?) à la lisibilité (on apprend de nos erreurs, j'étais encore jeune et insouciant). La doc est votre amie ;)
Si vous avez des questions / remarques, vous pouvez bien entendu utiliser les commentaires de l'article pour vous faire entendre. J'y jette régulièrement un coup d'œil.
Have fun !
Je vais vous présenter ici le script que j'ai écrit dans le cadre du concours PHP organisé sur le Site du Zér0. L'énoncé ainsi que le topic du concours se trouve ici : sujet du concours.
Pour la petite histoire, j'ai fini 1er ex-æquo de ce concours. :)
Le compte-rendu est disponible ici : résultat sur le SdZ.
Exemple de rendu
Sans rentrer dans les détails (le sujet explique bien le principe, et expose des liens explicatifs sur Wikipédia), le but était d'écrire un générateur de labyrinthes dits "parfaits" (c'est à dire dont toutes les cases sont accessibles par un et un seul chemin). Il fallait ensuite écrire un solveur pour ce labyrinthe, c'est à dire un script permettant de trouver le chemin de l'entrée à la sortie (logique, me direz-vous), et étant indépendant de la partie "génération" (la seule donnée que possède le solveur est le labyrinthe en lui même : aucune information sur le processus de génération n'est fournie).
J'ai globalement documenté ce projet ici : documentation du script, donc je ne vais pas m'attarder sur le code.
Le programme est disponible ici : démo du programme, mais il se peut que sur cet hébergement ça pédale un peu : Free me fourni un hébergement gratuit, mais il n'est pas très performant. Enfin c'est déjà pas mal :). Essayez donc de ne pas trop pousser le script (de toute manière Php s'exécute en safe_mode, donc il se bloquera tout seul). Je vous conseil de valider au moins une fois le formulaire avec les réglages par défaut, ça donne un bon résultat :).
Au niveau de la recherche de la solution, je crée l'arbre des chemins possibles (chaque nœud représente une case, chacun des fils étant les cases atteignables depuis celle-ci), parcouru en profondeur : on avance tant qu'on peut, et si on se retrouve bloqué, on revient en arrière jusqu'à ce qu'on ai un autre choix possible. Puis on recommence à partir de là.
Pour optimisé la recherche, j'ai rajouté une heuristique à peu près pertinente, que je n'ai pas cherché très loin : "si c'est possible, aller vers la droite ou vers le bas". En effet, étant donné qu'on part du coin supérieur gauche, pour aller vers le coin inférieur bas, on aura nécessairement plus de déplacement vers le bas que vers le haut, et plus vers la droite que vers la gauche.
La totalité du projet est disponible ici : http://theclemsweb.free.fr/demo/labyrinthe/laby_clems.rar. Faites-en bon usage !
L'essentiel du script est dans le fichier labyrinthe.class.php. En fait, tout se trouve la dedans, ce qui nuit un peu (beaucoup ?) à la lisibilité (on apprend de nos erreurs, j'étais encore jeune et insouciant). La doc est votre amie ;)
Si vous avez des questions / remarques, vous pouvez bien entendu utiliser les commentaires de l'article pour vous faire entendre. J'y jette régulièrement un coup d'œil.
Have fun !