Mots-clé : mazes

Trackmania 2 / ManiaScript, ManiaPlanet et Labyrinthes : génération automatique

Vous avez peut-être vu que j’avais écrit un générateur de labyrinthes en C, qui créait en bout de course un fichier Autohotkey (là aussi je vous laisse vous renseigner). Ce fichier Autohotkey lançait Trackmania United Forever et automatisait la pose de blocs, et au final il y avait une course dans… un labyrinthe de blocs de course. J’avais donc modifié Trackmania afin d’en faire un outil pour jouer dans des labyrinthes !

Trackmania 2 est sorti, en version bêta, avec achat pour 0.01 € de moins.
Comme c’était une offre extraordinaire, j’ai sauté sur l’occasion.

Et dans Trackmania 2, ils ont fait très fort (même si ça n’est pas encore 100 % terminé, c’est déjà très abouti) : dans leur éditeur de maps, ils ont fait un langage de programmation qui leur est propre, une sorte de fils caché entre le JavaScript et XML, avec quelques attouchements de C et de « principes objet ».
Je trouve que ça n’est pas très lisible, et encore moins maintenable, mais bon, c’est pour un jeu, alors il faut pas en demander trop, surtout quand on voit qu’on n’est pas que joueur, mais qu’on peut être acteur !
Ce pseudo-langage de programmation s’appelle «ManiaScript».

Je me suis dit : je vais refaire mon générateur de labyrinthes, mais pour «ManiaScript».
J’ai donc commencé à préparer le terrain en «ManiaScript» : j’ai préparé des routines de poses de blocs, des routines pour poser les montées, etc. J’en ai profité pour faire une petite copie d’écran que je vous livre avec plaisir (cliquez dessus pour agrandir) :

Image Trackmania de Labyrinthes

Puis j’en ai profité pour me repencher sur mon ancien générateur, et je me suis dit : je vais le reprendre, afin de lui faire générer des scripts «ManiaScript».

C’est ce que j’ai fait, et au bout de deux soirées passées à tout ré-analyser ce que j’avais fait (même si je mets des tonnes de commentaires, mon générateur est en C pur, donc c’est très dur (pour moi en tous les cas) de me replonger dans le bain), j’ai enfin pu recompiler et générer quelque chose. J’en ai donc fait une copie d’écran que je vous livre avec plaisir (cliquez dessus pour agrandir) :

Image Trackmania de Labyrinthes

Et puis j’ai repassé toute une soirée à réussir à lier les deux. Le plus gros problème vient du fait que je prends les repères mathématiques «classiques» c’est à dire en vertical, Y, à l’horizontal X, et en profondeur Z. Dans Trackmania, le Y et Z sont inversés. Bonjour le casse tête mais je n’étais pas à ça près. J’ai donc réussi : j’ai fait une copie d’écran que je vous livre avec un bien plus grand plaisir que les deux précédents (cliquez dessus pour agrandir) :

Image Trackmania de Labyrinthes

La pose des montées se fait avant la pose des blocs principaux. C’est assez marrant à voir, et comme je suis gentil, je vous ai même fait une copie d’écran (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Ensuite, j’ai voulu tester les limites de ma machine, et j’ai crée le plus grand labyrinthe possible pour Trackmania 2, et à mon grand plaisir, le jeu n’a pas explosé, comme il le faisait pour Trackmania United. Mattez moi ça (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Trackmania 2 a une nouveauté extraordinaire : ils précalculent les ombres avec un réalisme époustouflant, et j’ai donc demandé de précalculer avec le maximum de précision (il y a six niveaux, et le plus détaillé prend plusieurs heures de calcul), et voilà ce que ça a donné (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Ensuite, je me suis dit que les labyrinthes c’est bien joli, mais uniquement des blocs carrés, c’est pas très marrant. Donc j’ai décidé d’améliorer le tout, et j’ai trouvé un truc : après que le labyrinthe ait été posé par le script, j’ai imaginé rajouter en «ManiaScript» du code qui « décore » le labyrinthe. Par exemple, pour les tournants, j’ai mis des blocs de type « route », et j’ai ajouté un bloc « carré » pour terminer tous les cul-de-sac (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Et puis je me suis aperçu que les blocs avaient la possibilité d’avoir des néons incrustés, et que les tournants étaient éclairés, j’ai essayé de voir ce que ça donnait en mode nuit, et c’est vraiment beau (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

J’ai recalculé le même labyrinthe afin que vous puissiez comparer avec et sans les améliorations (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes
Image Trackmania de Labyrinthes

Et le même labyrinthe en mode nuit (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Ensuite, j’ai trouvé d’autres types de blocs dont j’ai pu me servir pour améliorer encore le rendu, et faire des tunnels. Le rendu de nuit des tunnels est encore plus joli (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Et puis les dernières captures, qui concernent le seul circuit que j’ai entièrement validé, sur douze étages (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Et comble de joie, le dernier étage a en plus le tout dernier type de tunnels que j’avais implémenté, mais il ne sort que très rarement sur les labyrinthes qui ne sont pas très larges (celui ci fait 4×4) (cliquez dessus pour agrandir) :
Image Trackmania de Labyrinthes

Trackmania et labyrinthes

J’ai crée un algorithme qui génère grâce à autohotkey toute une suite d’ordres clavier afin de générer des labyrinthes.

Comme beaucoup de personnes me l’ont demandé, je vous donne toutes mes sources, des heures entières de travail…
Cliquez ici pour les récupérer !
C’est le programme complet qui génère les labyrinthes, et il faut compiler tout en ligne de commande sous Linux. C’est ultra simple :

  • allez dans le répertoire « 0 » et tapez « make », et vous avez le premier programme ;
  • allez dans le répertoire « 1 » et tapez « make », et vous avez le second programme ;
  • allez dans le répertoire « 2 » et tapez « make », et vous avez le troisième programme ;

Chaque programme génère un fichier… pour qu’il soit en entrée pour le suivant. Je me suis basé sur le principe Linux : chaque programme est petit, mais fait une tâche, et la fait bien.

En voici quelques écrans :

Trackmania01

Trackmania02

Trackmania03

Trackmania04

Trackmania05

Trackmania06

Trackmania07

Vous êtes toujours là ? Ok alors, j’ai un peu mieux : j’ai développé l’algorithme de l’arbre qui grandit (regardez dans mes algorithmes de labyrinthes) et je l’ai appliqué à Trackmania. Ca fonctionne parfaitement ! Les circuits sont encore plus durs à réaliser, mais parfois si on arrive à prendre de l’élan on peut tricher et couper, mais c’est rare ! Enfin tout ça pour dire que c’est pas évident d’y arriver et que les résultats sont impressionnants, regardez les images qui suivent !

Trackmania08

Trackmania09

Trackmania10

Eh oui vous l’avez constaté peut-être mais il y a plusieurs montées possibles, et une seule est valide ! Incroyable non ? Moi je suis fier du résultat !

Pondération des liens

Concernant les labyrinthes, il n’est nulle part précisé le principe de pondération des liens. Alors je le fais !

La pondération, c’est « donner un poids ». Dans la plupart des algorithmes que j’ai donné on peut tout à fait donner un « poids » à chaque lien. Et en fonction de son poids, le lien aura plus ou moins de chances d’être tiré.
Exemple : une cellule a 4 sorties possibles : N, E, S, O. Chaque sortie a un poids.

  • Premier exemple : N = 1, E=1, S = 1, O = 1. Les chances sont toutes identiques. La pondération n’est pas utile dans ce cas, mais c’est juste pour avoir une idée.
  • Deuxième exemple : N = 40, E=10, S = 40, O = 10. La somme totale de la pondération est 100. On aura 80 chances sur 100 de tirer N ou S, et à peine 20 chances sur 100 de tirer E ou O.

Voilà sur le principe.
En pratique, voilà comment j’ai implémenté cela : j’ai, au départ, un tableau de poids. Par exemple :
poids[0] = 1, poids[1]=40 et poids[2]=10
Tous mes liens n’ont pas un poids, mais un indice vers le tableau des poids.
Reprenons les exemples :

  • Premier exemple : ma cellule aura les liens ainsi : N = 0, E=0, S = 0, O = 0 ;
  • Deuxième exemple : ma cellule aura les liens ainsi : N = 1, E=2, S = 1, O = 2.

Au moment de « tirer au hasard » un lien parmi ceux présents de la cellule : je fais la somme de tous les poids.
Reprenons les exemples :

  • Premier exemple : somme = 4 ;
  • Deuxième exemple : somme = 100.

Ensuite, je tire un chiffre entre 1 et la somme et je cherche à quelle direction cela correspond.
En pratique, il m’est ainsi possible de créer des labyrinthes avec des « orientations » dans certaines zones, et d’autres orientations dans d’autres zones.
Si cette idée vous a été utile, servez-vous en !

Les labyrinthes

Voilà je dévoile ma passion : une passion de geek : les labyrinthes. J’ai toujours été passionné par cela.

Voilà ce que j’ai crée : un générateur de labyrinthes énormes pour Trackmania ©. Cliquez ici pour halluciner un peu !

J’ai récemment (26 novembre 2008) réussi à créer un petit labyrinthe de 9000 x 9000 cases. Je ne sais pas si c’est le plus grand labyrinthe au monde, mais je pense que c’est parmi les plus grands.

Je lance avant d’aller me coucher la génération d’un labyrinthe de 15000 x 15000. Autrement dit il faudrait 4×4 formats A0 (4,5 mètres sur 4,5 mètres avec une précision de 100 points réels par pouces (600 dpi pour une imprimante laser)) pour pouvoir imprimer en entier ce labyrinthe.
Note technique : la machine est ralentie de manière impressionnante : le fichier swap est gigantesque (15 Go de swap). Les 8 Go de RAM sont entièrement alloués. On verra ça le 27 novembre !

Résultat le 27 novembre 2008 : tout a été généré correctement, le fichier texte fait 18 Go. Pour l’instant mis de côté je ne crois pas que je puisse m’en servir en l’état, il faudra que j’en re-génère un autre.

25 mars 2009 : reprise du code source et modification afin de pouvoir générer des fichiers plus courts et mieux exploitables. Exemple :

./gen 5000 5000 5000x5000.txt
Calcul d'un labyrinthe carré simple de 5000 x 5000.
- Démarrage le 24/3/2009 à 23:44:22
(1) Allocations mémoire :
- 25 000 000 cellules
- 99 980 000 liens.
Allocations réussies.
(2) Création des liens...
Terminé.
(3) Génération du fichier sortie...<5000x5000.txt>
Génération terminée.
Fin du programme le 24/3/2009 à 23:45:17