Réduisez le nombre d'arêtes d'un graphique en le maintenant connecté

Je conçois un jeu avec des donjons générés aléatoirement. J'aimerais voir cela comme un graphique connecté et non orienté dans lequel les nœuds sont des pièces et les bords sont des portes ou des couloirs. Ensuite, je choisis un nœud "latéral" comme entrée de donjon, je calcule la distance entre cette entrée et tous les autres nœuds, et décide que l'un des nœuds les plus éloignés est le "but" du donjon (l'emplacement du trésor, patron, princesse, etc.).

J'ai vu 2 façons de générer la topographie finale du donjon:

• Générez d'abord un graphique aléatoire, puis essayez de remplir le monde 2D avec des pièces à des emplacements aléatoires, en respectant les connexions de bord. J'ai pensé que ce serait parfois difficile parce que la génération de pièce pourrait être "verrouillée" en essayant de placer des pièces dans des endroits impossibles.
• Générez les premières pièces, en les plaçant au hasard à leur place, puis mappez le résultat sur les nœuds et les bords. J'ai décidé d'essayer ça.

Mon idée consiste à:

• Générez d'abord une grande pièce qui contiendrait tout le donjon.
• Placez un mur à l'intérieur de la grande pièce, à un endroit aléatoire, en divisant la grande pièce en 2 petites pièces de surface différente.
• Ensuite, je continue à diviser chaque pièce en 2, jusqu'à ce qu'elles soient trop petites ou que le nombre total de pièces atteigne un maximum (ou toute autre condition). Chaque nouvelle salle est un nœud.
• Une fois terminé, je vérifie chaque pièce et trouve toutes les autres pièces adjacentes, marquant les 2 nœuds comme connectés par un bord.

De cette façon, je m'assure que toutes les pièces ont un emplacement possible dans le monde 2D et sont correctement cartographiées par un graphique connecté.

Mon problème est qu'il y a trop de portes et de couloirs reliant les chambres.

Je voudrais donc un algorithme qui réduit le nombre d'arêtes d'un graphe connecté non orienté , mais en le gardant connecté (tous les nœuds restent accessibles) à la fin.

Utilisez l'algorithme de Prim pour obtenir l'arbre couvrant minimum pour votre graphique (ajoutez des poids aléatoires, ou ajoutez les poids les plus élevés près de l'entrée, ou faites un algorithme de votre choix) et rajoutez des portes / bords au hasard. De cette façon, vous aurez toutes les pièces connectées et quelques chemins supplémentaires redondants.

Vous pouvez également essayer l'algorithme de Kruskal

Certains des générateurs de donjons de cette liste d'Inkwell Ideas sont open source ou fournissent une documentation sur leurs algorithmes. Google vous en donnera également beaucoup en recherchant «Générateur de donjon [ProgrammingLanguagename]». Malheureusement, mon préféré n'est introuvable par aucune de ces méthodes, bien qu'il soit le plus bien documenté que j'aie jamais rencontré, et je ne me souviens pas de son nom car je l'ai perdu suite à un accident de disque dur récemment. Je mettrai à jour cette réponse après avoir effectué la récupération sur ce lecteur.