J'essaie de créer un petit roguelike et je suis allé jusqu'à des salles et des couloirs de génération aléatoire. Chaque pièce est un objet instancié et contient une liste des autres pièces reliées par un couloir.
Je peux distinguer des pièces non connectées mais comment puis-je connaître les pièces qui ne sont reliées entre elles mais pas à la plupart des autres, formant une île?
pour mieux illustrer le problème voici une image de la console à un niveau enlisé. Les chambres 5 et 6 sont connectées uniquement entre elles. Quel algorithme puis-je utiliser pour détecter cela?
Réponses:
Commencez avec une liste complète des chambres. Choisissez une salle de départ. Naviguez de cette pièce vers toutes les pièces connectées. Pour chaque pièce que vous visitez, retirez- la de la liste des chambres et l' ajouter à la liste A . Une fois que vous avez visité toutes vos connexions, les chambres restantes sur la liste ne sont pas connectés à la salle de départ ou l' une des chambres sur la liste A .
Vous pouvez ensuite continuer en sélectionnant une pièce dans ce qui reste de la liste complète et en naviguant à nouveau. Cette fois -ci d' ajouter à la liste B . Continuez ce processus jusqu'à ce que vous n'ayez plus de chambres sur la liste d'origine. Vous avez maintenant des listes de tous les ensembles de pièces connectés.
Des problèmes comme celui-ci sont facilement adaptés aux problèmes de théorie des graphes. Par exemple, le problème que vous avez décrit ci-dessus est directement lié à la connectivité .
la source
Votre collection de pièces est essentiellement un graphique, et votre problème se résume à trouver des composants connectés ("îles") dans ce graphique.
Un moyen simple de trouver des composants connectés consiste à effectuer une BFS (recherche en largeur d'abord) à partir de chaque sommet. Faire BFS à partir d'un sommet A vous obtiendra tous les sommets du composant connecté auquel le sommet A appartient.
Donc, fondamentalement, vous commencez avec un sommet arbitraire, effectuez un BFS et marquez chaque sommet rencontré comme membre du 1er "îlot". Ensuite, vous passez au prochain sommet non marqué et effectuez à nouveau un BFS, cette fois en étiquetant les sommets rencontrés en tant que membres du 2e "îlot", et ainsi de suite.
la source
Vous pouvez imaginer les chambres comme sommets sur un graphique orienté . En faisant cela, vous pourrez appliquer des algorithmes bien connus pour résoudre votre problème.
L'algorithme de Dijkstra , par exemple, produit un arbre de chemin le plus court pour un sommet de départ donné sur un graphique. Cet arbre contiendra tous les sommets accessibles depuis le point de départ. Vous pouvez alors en déduire que les sommets non présents dans l'arbre font partie d'autres îles. Vous pouvez appliquer l'algorithme à ces sommets afin d'obtenir des arbres représentant chaque île.
la source