Faire un labyrinthe 3D en Java
Objectif
Je fais un programme qui génère un labyrinthe 3D et j'ai un peu de mal avec l'algorithme de création. Pour faciliter l'interaction, elle sera un prisme rectangulaire avec une entrée et une sortie.
Algorithme
Le problème est le codage réel de l'algorithme: j'ai pensé que la meilleure façon d'y aller est de créer une classe appelée MazeBlock, qui a six états booléens (haut, bas, gauche, droite, dedans, dehors) qui signifient dans quelle direction le labyrinthe peut aller prochain. en utilisant un tableau 3D de MazeBlock s, je veux remplir le labyrinthe, chaque itération de remplissage vérifiant les blocs à gauche, à droite, au-dessus, en dessous, devant et derrière pour voir s'il y a une ouverture de ce côté à laquelle attacher.
J'en ai déjà un qui fera les bords, en plaçant des fentes ouvertes aléatoires vers l'intérieur du labyrinthe. Tout ce que j'ai du mal avec est l'intérieur réel, en veillant à ce que le labyrinthe ait une entrée, une sortie et une solution pour le traverser (j'ai une fois résolu un labyrinthe 3D" difficile " dans un livre popup en allant seulement quelques pas en face de la direction prévue.
Question
En tant que siad, je pense avoir l'idée de base de l'algorithme, mais je ne sais pas comment le coder. Quelqu'un peut-il trouver un algorithme Java pour Cela qui accomplit la tâche relativement rapidement?
La solution ne doit pas utiliser de bibliothèques externes.
1 answers
Il existe de nombreux algorithmes de génération de labyrinthe qui fonctionnent assez bien ici, dont la plupart sont basés sur la création d'une sorte de spanning tree dans un graphique de la grille 3D.
À titre d'exemple, supposons que nous ayons une grille 2D de cellules (que je peux réellement rendre en utilisant l'art ASCII!) qui ressemble à ceci:
*---*---*---*
| | | |
*---*---*---*
| | | |
*---*---*---*
| | | |
*---*---*---*
Nous pouvons penser à cela comme un graphe où chaque cellule est un sommet et chacune des connexions entre les cellules est une arête. Notre objectif est de trouver un arbre qui relie tous les nœuds. Si nous faisons cela, alors toutes les cellules seront accessibles les unes des autres (car un arbre est connecté), mais il n'y a pas de boucles (car un arbre est un graphe minimalement connecté). Il y a beaucoup d'arbres différents que nous pourrions utiliser; par exemple, voici un arbre:
*---*---*---*
| | | |
* * * *
| | | |
* * * *
| | | |
* * * *
Et en voici un autre:
* *---* *
| | | |
*---* * *
| |
*---*---*---*
| |
*---* *---*
Si vous recherchez une sorte d'arbre reliant les cellules du labyrinthe, une option serait d'utiliser une recherche en profondeur sur le graphique, en ordonnant aléatoirement les bords qui besoin d'être visité. Cette stratégie est un algorithme de génération de labyrinthe bien connu et produit de longs labyrinthes sinueux pleins d'impasses et de ramifications déroutantes.
Une autre approche couramment utilisée pour créer des labyrinthes consiste à la réduire au problème de trouver un spanning tree minimum d'un graphique. En particulier, supposons que vous créez un graphique où chaque cellule est un nœud avec des liens vers chacun de ses voisins. Choisissez des poids aléatoires pour chacun des bords, puis construisez un arbre couvrant minimum pour le graphique. Cet arbre n'a pas de cycles et il y a un chemin unique de chaque nœud à l'autre nœud, ce qui signifie que le labyrinthe a une solution unique. De plus, l'algorithme est très efficace - dans un cube 3D de taille n x n x n, alors vous avez O(n3) les nœuds, O(n3) bords, et vous pouvez trouver les MST en O(n3 lg n) le temps en utilisant soit l'algorithme de Prim ou Kruskal algorithme de. Ceux-ci produisent également des labyrinthes de haute qualité, bien que leur les propriétés sont très différentes des labyrinthes créés à l'aide de la recherche randomisée en profondeur.
J'espère que cela aide!