Mots-clé : laby

Labyrinthes Trackmania : ça a fonctionné !

J’ai écrit un énorme générateur de labyrinthes pour Trackmania :

Forum Trackmania sur mes labyrinthes

Et plein de personnes ont répondu, il y en a même une qui a crée un topic sur un forum Espagnol :

http://tm.maniazones.com/forum/index.php?topic=20292.0

Enfin, comme les liens ne fonctionnent pas forcément, voilà le lien pour aller récupérer tous les fichier de folie que mon générateur a fait :

http://olivier.pons.free.fr/archives/

Et n’oubliez pas la meilleure page concernant ces labyrinthes, qui se trouve directement sur ce site même :

Trackmania et 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