Labyrinth flavours ...

Oh mazes. Amazing Mazes. I quite love maze games, and as you may have guessed, I would like to delegate parts of the level design of my next game to a maze generator. I've written a few of them so far, including some that needed little resource, but most of them were creating so-called "perfect" mazes, where two locations in the maze are always linked by exactly one path .

Bon, j'aime bien les labyrinthes. Depuis longtemps, et j'aimerais bien que le prochain jeu de Bilou puisse se dérouler dans un niveau plus labyrinthique. Mais j'ai envie d'y jouer moi-même aussi, du coup ce serait sympa si le jeu pouvait partir d'un générateur de labyrinthes et les maquiller en niveaux de Bilou. Par contre, tous les générateurs de labyrinthes que j'ai fait (ou fait faire) jusqu'ici produisaient des labyrinthes parfaits, c'est à dire des labyrinthes dans lesquels il n'y a jamais qu'un et un seul chemin entre deux endroits. Et du point de vue du gameplay, j'ai peur que ce soit loin d'être génial.

 Imho, this is not ideal for gameplay. It creates maps that are essentially trees, with lots of dead ends and narrow hallways. I believe it will reduce many of the gameplay opportunities. it means that you can hardly dodge monsters. In some way, in such mazes, you hardly have any real choice once you stop seeing it all: you merely guess which might be the correct path and turn back a lot.

I have the feeling that interconnected loops will provide more interresting behaviours. we see them in PacMan - as well as in Phantom Hourglass. They provide interesting backtracking and let you chose between fighting or sneaking when you encounter a monster.

Parce que s'il n'y a qu'un seul chemin, ça implique qu'il y a de nombreuses voies sans issues. Sans une vue globale de la situation, il est extrêmement improbable de parvenir à "trouver" son chemin, et donc pas de réel choix à faire pendant la navigation. En plus, la plupart des obstacles ne pourront pas être contournés: ou bien on les affrontes, ou bien on ignore le chemin sur lequel ils se trouvent. Bref, mieux vaudrait un environnement proche d'un niveau de pac-man, avec de nombreuses boucles, où le défi est moins de trouver le chemin que de choisir celui qui offre le meilleur rapport récompenses/risques.

So how can I make levels than feature such loops? I gave it another try this week-end, by first laying out loops of random size on the map, making their center "unbreakable" and then setting the rest of the map as cells ready to be processed by a regular "perfect maze" algorithm. 

But this time, I do not need to push the execution to the point where the maze becomes all-connected. Instead, it is sufficient that all rooms get connected. Some cells will then remain obstacles, which I'm fine with.
Je n'ai pas encore d'algorithme idéal pour ce genre de labyrinthe. Je fais quelques essais sur papier quand j'ai un peu de temps les week-end... Une des idées serait de commencer par créer un certain nombre de boucles de ce genre dans une grille avant d'y faire tourner un algorithme de "labyrinthe parfait" sur les cases restantes jusqu'à ce que toutes les boucles se retrouvent inter-connectées.