Introduction
Bonjour et bienvenue dans ma documentation :-)
Je vais tenter d'expliquer au mieux le fonctionnement général du script (pour tous les détails, il faut voir les sources php, que j'ai soigneusement commentées). J'ai essayer de faire le script le plus propre que j'ai pu. Certaines portions cependant sont moins propres que d'autres (je pense notamment à la fonction Chrono_aff (l. 216) qui m'a un peu pris la tête ^^). J'ai opté pour la POO, vu l'envergure du script. Pour l'occasion, j'ai créer un petit système de log, ce que j'appellerais ensuite "le journal", et un petit système de chronomètre. Ces deux éléments auraient pu être mis à part, dans une autre classe "monitoring" par exemple, mais je ne l'ai pas fait ^^.
Architecture
Architecture des fichiers
- dossier Exemples : contient des exemples de ce que le script est capable de faire, pour la documentation.
- dossier Generes : contient tous les fichiers images crées par le script.
- dossier Palette : contient le nécessaire au fonctionnement de la palette
- palette.css : le fichier css lié à la palette (la taille des case, la position du bloc...).
- palette.js : le fichier javascript permettant le remplissage automatique des champs.
- palette.php : le fichier php qui génére le tableau de la palette, avec un dégradé de couleur en hexadécimal.
- banniere.png : la bannière (assez moche ^^) en haut des pages.
- doc.css : le fichier CSS associé à cette documentation.
- documentation.php : la documentation du script.
- index.php : le fichier racine. Contient le formulaire de création, traite toutes les données transmises par la méthode GET, appelle la méthode de création et d'affichage du labyrinthe, et affiche tout ce qui est renvoyé par le script. Gère aussi la pré-completion des champs du formulaire.
- labyrinthe.class.php : la CHOSE. Celle qui fait tout. Absolument tout. Sauf le café, ni le ménage (ni même les massages du dos, en fait :( ).
- lisez-moi.txt : le fichier qui vous dit de lire ceci ^^.
- montrer.js : le petit fichier qui permet d'afficher/cacher les différent éléments affichés.
- style.css : le fichier qui fait le peu de mise en forme existant, pour qu'on s'y retrouve un minimum.
Architecture du script (labyrinthe.class.php)
- lignes 0 à 117 => Initialisation, Constructeur : rien de bien exceptionnel, création et initialisation des variables
- lignes 119 à 161 => Journal : le journal sert à stocker toutes les informations/erreurs renvoyées par le script durant l'exécution de celui-ci
- lignes 163 à 270 => Chronomètre : cette partie s'occupe de chronométrer chaque étapes du script, et d'afficher les résultats
- lignes 272 à 507 => Génération du labyrinthe : une des parties essentielles du script, elle s'occupe de générer un labyrinthe parfait
- lignes 276 à 343 => Méthode dite "Exploration" : génère un labyrinthe parfait selon la méthode d'exploration ( Wikipédia )
- lignes 345 à 383 => Méthode dite "Fusion" : génère un labyrinthe parfait selon la méthode de fusion ( Wikipédia )
- lignes 385 à 507 => Fonctions auxiliaires : toutes les fonctions nécessaire aux deux méthodes ci-dessus.
- lignes 509 à 565 => Résolution : cette partie sert à résoudre un labyrinthe fourni par une des deux méthode ci-dessus, de manière indépendante (consigne du défi)
- lignes 567 à 1039 => Affichage : cette partie s'occupe de la génération de l'image, via GD :
- lignes 571 à 671 => Initialisation : initialisation et/ou vérification des variables nécessaire à l'affichage, et appel des fonctions travaillant avec GD
- lignes 673 à 744 => fonction Affichage_2d : fonction qui dessine le labyrinthe en 2D via GD
- lignes 746 à 772 => fonction Affichage_sol_2d : fonction qui dessine la solution sur le labyrinthe 2D via GD
- lignes 774 à 985 => fonction Affichage_3d : fonction qui dessine le labyrinthe en 3D via GD
- lignes 987 à 1039 => fonction Affichage_sol_3d : fonction qui dessine la solution sur le labyrinthe 3D via GD
Fonctionnement
Numérotation des cases et des murs
Le début des deux méthodes consiste à numéroter les cases et les murs de façons logique, histoire de savoir sur quoi on travaille. La numérotation des cases du labyrinthe se fait de gauche à droite, du haut vers le bas. La case en haut à gauche est la case 1 (et non 0). Pour les murs, je suis le meme ordre que pour les cases.
Exemple : labyrinthe de 3*4 :
| 1 | 1 | 2 | 3 | 3 | 5 | 4 | 7 |
| 2 | 4 | 6 | 8 |
| 5 | 9 | 6 | 11 | 7 | 13 | 8 | 15 |
| 10 | 12 | 14 | 16 |
| 9 | 17 | 10 | 19 | 11 | 21 | 12 | 23 |
| 18 | 20 | 22 | 24 |
Je crée ensuite un array $this->murs_enlevables contenant les murs supprimables (ceux qui ne sont pas sur les bords), dupliqué dans $this->murs_restants au début du script, pour pouvoir travailler sur le tableau en gardant les informations de départ).
Méthode "Fusion"
Pour la génération par Fusion, je commence par attribuer à chaque case un numéro de groupe. Au début, la case N appartient au groupe N. Je tire ensuite au hasard un murs dans $this->murs_restants (fonction Enleve_Mur(), l.430) : à chaque fois qu'un mur est choisi, deux possibilités :
- Soit le mur sépare deux cases de groupes différents : je fusionne les deux groupes concernés (fonctions Groupe_cases(), l.494 et Mur_a_cases(), l.452) et je supprime totalement ce mur via un unset() sur la ligne correspondante dans $this->murs_restants. Ce n'est plus un mur restant, vu qu'il n'est plus là ^^.
- Soit le mur sépare deux cases appartenant au même groupe : je le marque comme non-supprimé mais déjà visité en mettant sa valeur dans $this->murs_restants à 0. Le mur est encore présent.
Je continue ainsi à choisir des murs au hasard parmis les murs restants non-visités, jusqu'à ce qu'il n'y ai plus qu'un seul groupe de case.
Le labyrinthe est généré !
Méthode "Exploration"
Je commence pas créer le tableau $this->cases_voisines, associant chaque case (clés) à ses voisines (valeurs). Ensuite, à partir de la case de départ, je choisis au hasard une voisine, qui devient la case courante. Cette case courante est retirée des voisines possible de ses cases voisines, afin de ne pas pouvoir revenir dessus. Tout ceci est géré par la fonction Choix_case(), l.407. Si on arrive sur une case qui n'a plus de voisine non-visitée, on revient en arrière grâce à $this->pile. Ainsi de suite, j'avance de case en case, jusqu'à ce que $this->cases_visitees contienne autant d'éléments que le labyrinthe de cases.
Le labyrinthe est généré !
Résolution
Fonction Resolution(), l.514.
La méthode de résolution du labyrinthe est sensiblement la même que celle de la génération par "exploration", à ceci prêt que pour la résolution, j'utilise l'heuristique (Wikipédia ) suivante :
- Partant du coin haut-gauche pour allez au coin bas-droit, le meilleur choix lorsque plusieurs chemins s'offrent à moi est d'aller en bas ou à gauche.
Mon script est en mesure de gérer une case de départ autre que l'angle haut-gauche et une case d'arrivée en bas à droite, mais il aurait alors fallu intégrer un petit bout de code déterminant quelle était la meilleur "direction" en cas de choix; je ne pense pas que ce soit bien difficile à faire, c'est juste que je n'ai pas le temps de m'y mettre maintenant (il est 23h35 ^^). Donc, tant que la case courante n'est pas la case d'arrivée, j'avance de cases voisines en cases voisines (en privilégiant le bas et la droite), les possibilités étant déterminées par la fonction Cases_possibles(), l.547. Si je me retrouve bloqué (aucune voisine possible), c'est que le chemin n'est pas le bon. Je l'efface jusqu'au dernier choix que j'ai eu à faire, et je prends une autre direction.
Affichage
Le dossier "palette" contient tout le nécessaire à la sélection d'une couleur et à l'auto-completion des champs du formulaire. Ce n'est pas très développé car ça fait partie des "petits plus" sur lesquels je n'ai pas passez trop de temps.
La fonction Affichage(), l.514 vérifie les paramêtre nécessaire à l'affichage, tandis que la fonction Affichage_go(), l.661 appellent les fonctions travaillant avec GD. Au niveau de l'affichage à proprement parlé, j'utilise la librairie GD, qui permet des possibilités bien supérieures à l'affichage html. Je gère deux types d'affichage :
- L'affichage standard 2D Affichage_2d(), l.671 : rien de bien palpitant. Via la numérotation des murs de $this->murs_restants, je calculs leurs coordonnées, et je les affiche. Je fais de même avec $this->chemin pour l'affichage de la solution grâce à Affichage_sol_2d, l.774.
- L'affichage 3D Affichage_3d(), l.772 : Petite fierté personelle, c'est le "plus" de mon script ^^. Le principe est le même que pour la 2D, mais les calculs sont plus lourds ^^. Je n'est pas vraiment le temps de bien expliquer (23h59), il faut que j'envoie le mail
Fusion
/!\L'algorythme "fusion" n'est pas du tout optimisé /!\
Je pense qu'il n'est pas pertinent de mettre ses performances ici, étant donné que je ne me suis pas interressé à son optimisation. J'ai hésité à le laisser dans la class, mais étant donné que je le l'ai quand même codé, ça aurait été dommage...
Exploration
Sur mon ordinateur : AMD 3200+ à 2.7Ghz et 1go de RAM Corsair Value, j'arrive à générer (avec l'aglorythme "exploration") :
- 15*15, résolu, 3D, 40px par case : 0.2sec
- 50*50, résolu, 3D, 10px par case : 5sec (dont 4.5sec pour l'affichage 3D ^^)
- 250*250, non résolu, 2D, 5px par case : 3sec
- 250*250, résolu, 2D, 5px par case : 10sec
- 500*500 (environ 500 000 murs ^^), non résolu, 2D, 2px par case : 10sec
Bug connu
soucis de récurence dans l'affichage du chrono
l'affichage ne passe bien que sur Firefox
Par contre, la source est niquelle ^^
Bugs inconnus
Je les ai pas encore trouvés ^^