origine:
L'année dernière (premier semestre de lycée), j'ai aimé écrire de petits jeux, donc je voulais essayer d'écrire un labyrinthe.
Effets du programme:
Appuyez sur l'espace pour afficher le chemin:
Processus de réflexion:
Le labyrinthe se compose de grilles, ne nécessitant qu'un seul chemin de l'entrée de la sortie.
Après avoir réfléchi à diverses structures de données, il semble que les arbres soient plus appropriés, avec un seul chemin du nœud racine à chaque nœud enfant. En supposant que l'entrée est le nœud racine et que la sortie est un nœud enfant dans l'arborescence, le chemin du nœud racine au nœud enfant est définitivement unique.
Donc, si un arbre peut être construit pour couvrir toutes les grilles, un labyrinthe peut être créé.
De plus, il est nécessaire que les nœuds parents et enfants de l'arbre soient des grilles adjacentes sur l'interface.
Lors de l'affichage de l'interface, si les bords partagés entre le nœud parent et le nœud enfant ne sont pas dessinés et que d'autres bords sont dessinés, un labyrinthe peut être dessiné.
Ensuite, j'ai réfléchi à la façon de mettre en œuvre un tel arbre.
Les deux premières questions:
1. Comment les arbres représentent-ils?
2. Comment construire cet arbre?
1. Comment les arbres représentent-ils?
En supposant que cet arbre est implémenté comme l'écriture d'un arbre binaire, chaque nœud d'arbre doit stocker une coordonnée (x, y) pour représenter une grille et quatre pointeurs doivent être stockés. Certains pointeurs sont vides, certains ne sont pas vides et les pointeurs qui ne sont pas vides pointent vers les nœuds enfants, et les nœuds enfants sauvent les coordonnées de la grille voisine. Le plus gros problème avec cela est qu'il est impossible de déterminer si toutes les grilles sont dans l'arbre. Peut-être qu'un réseau bidimensionnel est également utilisé comme tableau de drapeau.
Supposons que vous utilisiez un tableau bidimensionnel pour représenter la grille du labyrinthe. Chaque élément de tableau stocke une référence au nœud parent, qui peut également former une arborescence virtuelle. Ainsi, un tableau bidimensionnel de N * n représente les grilles N * n, et chaque élément de tableau (réseau) a une référence au nœud parent. De plus, afin d'obtenir facilement les coordonnées de la grille, les informations de coordonnées doivent également être enregistrées.
2. Comment construire cet arbre?
Sélectionnez d'abord une grille comme nœud racine. Afin de rendre la forme du labyrinthe suffisamment aléatoire, j'ai choisi de générer de manière aléatoire une coordonnée comme nœud racine. En fait, il est également acceptable de choisir une coordonnée déterminée.
Ensuite, comment ajouter des nœuds à cet arbre?
J'ai pris beaucoup de détours ici. Au début, j'ai pensé à un algorithme qui semble être similaire à BackTracking maintenant (je ne connaissais pas l'algorithme de retour en arrière à ce moment-là ...), mais la complexité du temps est très élevée. Peut-être que lorsque le labyrinthe est 64 * 64, l'algorithme ne produira aucun résultat.
Ensuite, une méthode de recherche de profondeur de numérisation est également de retour en arrière. Chaque fois que je scanne, je trouve un nœud dans l'arborescence actuelle pour voir si sa grille de voisin est dans l'arbre. Si ce n'est pas dans l'arbre, ajoutez la grille voisine à l'arbre. S'il est déjà dans l'arbre, regardez la prochaine grille voisine. Si toutes les grilles voisines du nœud sont dans l'arbre, trouvez le nœud suivant et continuez la même opération. De plus, afin de générer le labyrinthe au hasard, la position de début du scan est juste aléatoire. Cependant, les chemins dans le labyrinthe générés par cette méthode ne sont toujours pas assez profonds pour avoir l'effet tortueux et approfondi que je veux. Après tout, c'est une méthode similaire à la recherche d'étendue. De plus, cela semble toujours compter sur la force brute, et l'algorithme n'est pas assez intelligent et concis.
Enfin, j'ai finalement pensé à utiliser une recherche approfondie. . Probablement parce que j'ai appris la structure des données depuis un an et que je ne l'ai pas trop pratiqué, je n'ai jamais pensé à cette première méthode à laquelle je devrais penser. .
Sélectionnez au hasard une grille comme nœud racine, commencez à partir de celui-ci et recherchez en profondeur, et ouvrez un moyen jusqu'à ce qu'il n'y ait pas de chemin à parcourir, retirer une étape, modifier un autre moyen, puis marcher sans aucun moyen d'aller, prendre un pas en arrière, changer un autre ... ce cycle continue jusqu'à ce qu'il n'y ait aucun moyen d'aller. . . En fait, il est toujours en retour de retour en arrière.
Dans le programme, le processus suivant est (voir la fonction CreateMaze () dans le code pour plus de détails):
Sélectionnez au hasard une grille comme nœud racine et poussez-la dans la pile.
Exécutez ensuite la boucle suivante lorsque la pile n'est pas vide:
Sortez une grille, définissez son drapeau intré sur 1, puis poussez toutes ses grilles voisines qui ne sont pas dans l'arbre dans la pile (histoires au hasard), et laissez le père de ces grilles voisines pointer de la grille.
Après avoir résolu ces deux problèmes, le reste du dessin des labyrinthes, des chemins d'affichage et des balles mobiles est relativement simple.
Code
Maze de package; import java.awt.color; importer java.awt.graphics; import java.awt.event.keyadapter; import java.awt.event.keyevent; import java.util.random; import java.util.stack; import javax.swing.jframe; import javax.swing.joptionpane; javax.swing.jpanel; class lattice {static final int intree = 1; static final int notintree = 0; privé int x = -1; privé int y = -1; INT PRIVATE FLAG = NOTINTREE; Père de réseau privé = null; réseau public (int xx, int yy) {x = xx; y = yy; } public int getX () {return x; } public int gety () {return y; } public int getflag () {return drapeau; } Public Lattice getfather () {Return Père; } public void setfather (réseau f) {père = f; } public void setFlag (int f) {flag = f; } public String toString () {return new String ("(" + x + "," + y + ") / n"); }} La classe publique Maze étend JPanel {private statique final long SerialVersionUID = -8300339045454852626l; Int privé, largeur, rembourrage; // largeur la largeur et la hauteur de chaque réseau de réseau privé [] []; Int privé Ballx, Bally; DrawPath booléen privé = false; Maze (int m, int wi, int p) {num = m; largeur = wi; rembourrage = p; Maze = nouveau réseau [num] [num]; pour (int i = 0; i <= num - 1; i ++) pour (int j = 0; j <= num - 1; j ++) labyrinthe [i] [j] = nouveau réseau (i, j); CreateMaze (); setKeyListener (); this.setFocusable (true); } private void init () {for (int i = 0; i <= num - 1; i ++) for (int j = 0; j <= num - 1; j ++) {kaze [i] [j] .setfather (null); Maze [i] [j] .setflag (lattice.notintree); } BallX = 0; bally = 0; DrawPath = false; CreateMaze (); // setKeyListener (); this.setFocusable (true); repeindre(); } public int getCenterx (int x) {return padding + x * largeur + largeur / 2; } public int getCentery (int y) {return padding + y * largeur + largeur / 2; } public int getCenterx (réseau p) {return padding + p.gety () * largeur + largeur / 2; } public int getCentery (réseau p) {return padding + p.getx () * largeur + largeur / 2; } private void checkiswin () {if (ballx == num - 1 && bally == num - 1) {joptionpane.showMessageDialog (null, "vous gagnez!", "Vous êtes sorti du labyrinthe.", Joptionpane.Plain_Message); init (); }} Synchronized Private void Move (int C) {int tx = ballx, ty = bally; // System.out.println (C); switch (c) {case keyevent.vk_left: ty--; casser; case keyevent.vk_right: ty ++; casser; case keyevent.vk_up: tx--; casser; case keyevent.vk_down: tx ++; casser; case keyevent.vk_space: if (drawpath == true) {drawpath = false; } else {drawpath = true; } casser; par défaut:} if (! IsOutofborder (tx, ty) && (labyrinthe [tx] [ty] .getfather () == Maze [Ballx] [bally] || labyrinthe [Ballx] [bally] .getfather () == Maze [tx] [Ty])) {BallX = tx; bally = ty; }} private void setKeyListener () {this.addkeyListener (new KeyAdapter () {public void keyPressed (keyEvent e) {int c = e.getKeyCode (); move (c); repent (); checkiswin ();}}); } privé boolean isoutofborder (réseau p) {return isOutOfBorder (p.getx (), p.gety ()); } private booléen isoutofborder (int x, int y) {return (x> num - 1 || y> num - 1 || x <0 || y <0)? vrai: false; } lattice privé [] getneis (réseau p) {final int [] ajouts = {-1, 0, 1, 0, -1}; // L'ordre est supérieur, à droite, à gauche, if (isOutofBorter (p)) {return null; } Réseau [] ps = nouveau réseau [4]; // l'ordre est supérieur, à droite, à gauche, int xt; int yt; pour (int i = 0; i <= 3; i ++) {xt = p.getx () + ajoute [i]; yt = p.gety () + ajoute [i + 1]; si (isoutofborder (xt, yt)) continue; ps [i] = labyrinthe [xt] [yt]; } return ps; } private void CreateMaze () {Random Random = new Random (); int rx = math.abs (random.nextint ())% num; int ry = math.abs (random.nextint ())% num; Pile <wattice> s = new Stack <Lattice> (); Réseau p = labyrinthe [rx] [ry]; Réseau neis [] = null; S.Push (P); while (! s.Sempty ()) {p = s.pop (); p.setflag (lattice.intree); neis = getneis (p); int ran = math.abs (random.nextint ())% 4; pour (int a = 0; a <= 3; a ++) {ran ++; Ran% = 4; if (neis [ran] == null || neis [ran] .getflag () == lattice.intree) continue; S.Push (NEIS [Ran]); NEIS [Ran] .setfather (P); }} // ChangeFather (labyrinthe [0] [0], null); } private void ChangeFather (réseau p, réseau f) {if (p.getfather () == null) {p.setfather (f); retour; } else {changefather (p.getfather (), p); }} private void clearFence (int i, int j, int fx, int fy, graphics g) {int sx = padding + ((j> fy? j: fy) * width), sy = padding + ((i> fx? i: fx) * width), dx = (i == fx? sx + largeth), dy = (i == fx? Sy + width: Sy); if (sx! = dx) {sx ++; dx--; } else {sy ++; dy--; } G.Drawline (SX, SY, DX, DY); } Protected void PaintComponent (Graphics G) {super.paintComponent (g); for (int i = 0; i <= num; i ++) {g.drawline (padding + i * largeur, padding, padding + i * largeur, padding + num * largeur); } pour (int j = 0; j <= num; j ++) {g.drawline (rembourrage, padding + j * largeur, padding + num * largeur, padding + j * largeur); } g.setColor (this.getBackground ()); for (int i = num - 1; i> = 0; i--) {for (int j = num - 1; j> = 0; j--) {réseau f = kaze [i] [j] .getfather (); if (f! = null) {int fx = f.getx (), fy = f.gety (); Clearfence (i, j, fx, fy, g); }}} G.Drawline (rembourrage, rembourrage + 1, rembourrage, rembourrage + largeur - 1); int last = padding + num * largeur; G.Drawline (dernier, dernier - 1, dernier, dernier - largeur + 1); g.setColor (Color.Red); G.Filloval (getCenterx (bally) - largeur / 3, getCentery (BallX) - largeur / 3, largeur / 2, largeur / 2); if (drawpath == true) DrawPath (g); } Private void DrawPath (Graphics G) {Color Path_Color = Color.Orange, Bothing_Path_Color = Color.pink; if (drawPath == true) g.setColor (path_color); else g.setColor (this.getBackground ()); Réseau p = labyrinthe [num - 1] [num - 1]; while (p.getfather ()! = null) {p.setflag (2); p = p.getfather (); } g.Filloval (getCenterx (p) - largeur / 3, getCentery (p) - largeur / 3, largeur / 2, largeur / 2); p = labyrinthe [0] [0]; while (p.getfather ()! = null) {if (p.getflag () == 2) {p.setflag (3); g.setColor (both_path_color); } G.Drawline (GetCenterx (P), GetCentery (P), GetCenterx (P.GetFather ()), GetCentery (P.GetFather ())); p = p.getfather (); } g.setColor (path_color); p = labyrinthe [num - 1] [num - 1]; while (p.getfather ()! = null) {if (p.getflag () == 3) Break; G.Drawline (GetCenterx (P), GetCentery (P), GetCenterx (P.GetFather ()), GetCentery (P.GetFather ())); p = p.getfather (); }} public static void main (String [] args) {final int n = 30, largeur = 600, padding = 20, lx = 200, ly = 100; Jpanel p = nouveau labyrinthe (n, (largeur - rembourrage - rembourrage) / n, rembourrage); JFrame frame = new JFrame ("Maze (afficher ou masquer les chemins d'espace Bar)"); frame.getContentPane (). Add (p); frame.setDefaultCloseOperation (jframe.exit_on_close); frame.SetSize (largeur + rembourrage, largeur + rembourrage + rembourrage); frame.setLocation (lx, ly); frame.setVisible (true); }}