Bonjour,
 
Je m'essaie en ce moment à la réalisation d'un jeu vidéo. Mon idée étant de reproduire le jeu Dragon Crystal (version Sega Master System). J'ai d'ailleurs presque tout terminé pour la partie programmation, il va encore falloir que je récupère quelques sriptes pour compléter les animations mais globalement je suis assez satisfait du résultat.
 
Par contre il y a un point sur lequel ne ne m'en sort pas du tout... c'est la génération aléatoire des map de chaque niveau.
 
Les map de ce jeu sont construites ainsi :

• On a des chemins plus ou moins aléatoires
• Des rectangles vides de dimensions variables dans lesquels apparaissent les monstres et les objets que l'on peut ramasser
• Tous les rectangles doivent être connectés par des chemins
• Les entrées/sorties des rectangles se situent sur le côté mais jamais dans les angles
• Le joueur spawn dans un rectangle
• La sortie du niveau peut se trouver sur le côté de n'importe quel rectangle (c'est un télé-porteur, donc pas nécessairement situé sur un côté de la map)

Pour que ce soit bien clair, j'ai extrait une map générée par le jeu (la sortie étant représenté par la tile avec une sorte d'étoile) :
 

 
Je tiens à préciser, puisque cet exemple ne le montre pas, que les map ne sont pas forcément complètement pleines et que certaines zones sont parfois inaccessibles. Et, à noter également, que parfois le jeu sort des map où la sortie n'est pas accessible (ce qui me conforte dans l'idée que ces map sont générées aléatoirement). A propos des dimensions, elles ne sont pas figées. Plus on passe des niveau et plus les map sont grandes.
 
J'ai essayé de me documenter sur les algorithmes de générations de map mais je suis surtout tombé sur la génération de terrain basé sur l'élévation, ce qui ne répond pas à mon besoin. J'ai trouvé aussi quelques rares documentations sur la génération de labyrinthes. C'était déjà plus proche de ce que je cherche mais encore insuffisant...
 
La solution que j'utilise actuellement :

• Au départ, on a une map pleine, on ne peut pas y circuler
• En partant du centre, je me déplace aléatoirement sur la map pour créer des chemins
• Je parcours ensuite aléatoirement ma map point par point, si c'est un chemin alors il y a une certaine probabilité que le programme place un rectangle de dimensions aléatoires sur ce chemin.

Ceci fonctionne et créé bien des map avec une sortie et quelques rectangles tous accessibles. Par contre, pour l'aspect général on est loin du résultat attendu. Voici un exemple ce que ça donne (en vert les zones ou le perso peut circuler) :
 

 
Ça fait un moment que je suis là dessus et je commence un peu a désespérer... Peut être que je ne fais pas les bonnes recherches ? En tout cas, si vous avez la moindre idée, suggestion ou remarque, n'hésitez pas !
 
Et merci par avance

Ta solution actuelle a l'air d'être un bon début, en la raffinant tu devrais arriver à quelque chose de satisfaisant.
 
Généralement on a aussi des bons résultats en faisant mumuse avec des automates cellulaires sur ce genre de problème; combiner cela avec ton approche devrait t'amener quelque part.