Récemment, je regarde souvent mes camarades de classe jouer à un jeu de labyrinthe dans la salle informatique. C'est assez intéressant. J'utilise également Java pour écrire un algorithme pour implémenter une génération aléatoire de labyrinthes. En fait, il s'agit d'un algorithme de traversée en profondeur d'abord pour un graphique. L'idée de base est que chaque point du labyrinthe a quatre murs, puis.
1. Commencez à accéder à partir de n'importe quel point (mon algorithme est fixé pour commencer à partir du point (0,0)), et visitez un aléatoire l'une des quatre directions (chaque fois que vous accédez à un point accessible, retirez le mur dans ce sens de ce point), et le point accessible continue d'y accéder dans cette direction.
2. Chaque point visité est identifié comme accessible. Lorsqu'un point accède à une certaine direction, nous déterminerons d'abord si le point accédé a été accessible ou touche la frontière. Si les quatre directions du point sont accessibles ou ne sont pas en mesure d'accéder, revenez au point précédent. Le point précédent continue le processus.
Après la traversée de cette manière, on peut confirmer que chaque point a été visité. De plus, comme la direction de chaque accès est aléatoire, de nombreuses situations de traversée différentes seront formées. Dans le même temps, le chemin entre chaque deux points est unique, qui forme un labyrinthe différent, et il n'y a qu'un chemin unique du point de début au point final. Ceci est déterminé par les caractéristiques de l'algorithme de traversée de profondeur du graphique. Dans la mise en œuvre de l'algorithme, l'essentiel est d'utiliser la pile. La première fois, appuyez d'abord le premier point dans la pile. Chaque fois qu'un point est accessible, le point est poussé dans la pile, nous accédons ensuite au point au hasard en haut de la pile en quatre directions, accédons au nouveau point, puis appuyons sur le nouveau point dedans. Une fois que les quatre directions de ce point sont inaccessibles, laissez le point de se retirer de la pile, puis accédez aux quatre directions du point en haut de la pile, etc. Jusqu'à tous les points de la sortie de la pile, notre traversée réussira. Il s'agit d'un processus récursif. Cet algorithme peut naturellement être mis en œuvre par des méthodes récursives. Cependant, je le fais ici, mais l'implémentez manuellement avec un tableau comme pile. Haha ~~ Après avoir dit autant, je ne sais pas si ce que je veux exprimer est exprimé. Cependant, je pense que ma conception de code spécifique n'est pas bien écrite, et il y a encore de nombreux endroits où il y a un manque d'amélioration et d'optimisation. C'est juste pour être un exercice d'algorithme. Voici les codes principaux des deux classes clés. Quant au code de la couche de présentation, je ne les publierai pas car ceux-ci sont très triviaux.
Voici le rendu:
Classe de labyrinthe:
// Auteur: Zhongzw // Courriel: [email protected] Package cn.zhongzw.model; import java.util.arraylist; import java.util.random; classe publique MazEModel {private int width = 0; private int hauteur = 0; Randal privé rnd = new Random (); public mazemodel () {this.width = 50; // la largeur du labyrinthe this.height = 50; // Maze Height} public int getWidth () {width de retour; } public void setWidth (int largeth) {this.width = width; } public int getheight () {return height; } public void Setheight (int height) {this.height = height; } public mazemodel (int largeur, int hauteur) {super (); this.width = largeur; this.height = hauteur; } public ArrayList <AmazEpoint> getmaze () {ArrayList <AmazEpoint> Maze = new ArrayList <AmazePoint> (); pour (int h = 0; h <height; h ++) {for (int w = 0; w <width; w ++) {mazepoint point = new mazepoint (w, h); Maze.add (point); }} return CreateMaze (Maze); } Private ArrayList <AmazEpoint> CreateMaze (ArrayList <AmazEpoint> Maze) {int top = 0; int x = 0; int y = 0; ArrayList <AmazEpoint> Team = new ArrayList <AmazePoint> (); team.add (kaze.get (x + y * largeur)); while (top> = 0) {int [] val = new int [] {-1, -1, -1, -1}; int times = 0; booléen drapeau = false; MazEpoint PT = (Mazepoint) Team.get (en haut); x = pt.getx (); y = pt.gety (); pt.VistEd = true; ro1: while (fois <4) {int dir = rnd.nextint (4); if (val [dir] == dir) continue; else val [dir] = dir; switch (dir) {case 0: // Left if ((x - 1)> = 0 && kaze.get (x - 1 + y * largeur) .vist == false) {Maze.get (x + y * width) .setLeft (); kaze.get (x - 1 + y * largeur) .setright (); team.add (kaze.get (x - 1 + y * largeur)); top ++; Flag = true; Break Ro1; } casser; cas 1: // droit if ((x + 1) <width && kaze.get (x + 1 + y * largeur) .visted == false) {Maze.get (x + y * width) .setright (); kaze.get (x + 1 + y * largeur) .setLeft (); team.add (kaze.get (x + 1 + y * largeur)); top ++; Flag = true; Break Ro1; } casser; cas 2: // if ((y - 1)> = 0 && kaze.get (x + (y - 1) * largeur) .vist == false) {Maze.get (x + y * width) .setup (); kaze.get (x + (y - 1) * largeur) .setDown (); team.add (kaze.get (x + (y - 1) * largeur)); top ++; Flag = true; Break Ro1; } casser; cas 3: // ci-dessous if ((y + 1) <height && kaze.get (x + (y + 1) * largeur) .vist == false) {kaze.get (x + y * width) .setDown (); kaze.get (x + (y + 1) * largeur) .setup (); team.add (kaze.get (x + (y + 1) * largeur)); top ++; Flag = true; Break Ro1; } casser; } fois + = 1; } if (! Flag) {Team.Remove (top); supérieur - = 1; }} Retour Maze; }}
labyrinthe
// Auteur: Zhongzw // Courriel: [email protected] Package cn.zhongzw.model; import java.util. *; importer java.lang. *; classe publique Mazepoint {private int Left = 0; private int droit = 0; private int up = 0; private int down = 0; Int x privé; privé int y; Boolean public a été témoin; public Mazepoint (int x, int y) {this.x = x; this.y = y; } public int getleft () {return à gauche; } public void SetLeft () {this.left = 1; } public int getRight () {return droit; } public void setRight () {this.Right = 1; } public int gepup () {return up; } public void setup () {this.up = 1; } public int Gotdown () {return down; } public void Setdown () {this.down = 1; } public int getX () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sey (int y) {this.y = y; }}
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.