Baru -baru ini, saya sering menonton teman sekelas saya bermain game labirin di ruang komputer. Itu cukup menarik. Saya juga menggunakan Java untuk menulis algoritma untuk mengimplementasikan generasi labirin acak. Faktanya, ini adalah algoritma traversal yang kedalaman untuk grafik. Ide dasarnya adalah bahwa setiap titik dalam labirin memiliki empat dinding, dan kemudian.
1. Mulai akses dari titik mana pun (algoritma saya diperbaiki untuk memulai dari titik (0,0)), dan kunjungi salah satu dari empat arah (setiap kali Anda mengakses titik yang dapat diakses, lepaskan dinding ke arah titik itu), dan titik yang diakses terus mengaksesnya ke arah ini.
2. Setiap titik yang dikunjungi diidentifikasi sebagai diakses. Ketika suatu titik mengakses arah tertentu, pertama -tama kita akan menentukan apakah titik yang diakses telah diakses atau menyentuh batas. Jika keempat arah titik telah diakses atau tidak dapat mengakses, kembali ke poin sebelumnya. Poin sebelumnya melanjutkan proses.
Setelah traversal dengan cara ini, dapat dikonfirmasi bahwa setiap titik telah dikunjungi. Selain itu, karena arah masing -masing akses bersifat acak, banyak situasi traversal yang berbeda akan dibentuk. Pada saat yang sama, jalur antara setiap dua titik adalah unik, yang membentuk labirin yang berbeda, dan hanya ada jalur unik dari titik awal ke titik akhir. Ini ditentukan oleh karakteristik algoritma traversal kedalaman grafik. Dalam implementasi algoritma, yang utama adalah menggunakan tumpukan. Pertama kali, pertama tekan titik pertama ke tumpukan. Setiap kali titik diakses, titik didorong ke tumpukan, kami kemudian secara acak mengakses titik di bagian atas tumpukan dalam empat arah, mengakses titik baru, dan kemudian menekan titik baru. Setelah empat arah titik ini tidak dapat diakses, biarkan titik mundur dari tumpukan, dan kemudian mengakses empat arah titik di atas tumpukan, dan sebagainya. Sampai semua poin di pintu keluar tumpukan, traversal kami akan berhasil. Ini adalah proses rekursif. Algoritma ini secara alami dapat diimplementasikan dengan metode rekursif. Namun, saya melakukan ini di sini, tetapi secara manual menerapkannya dengan array sebagai tumpukan. Haha ~~ Setelah mengatakan begitu banyak, saya tidak tahu apakah apa yang ingin saya ungkapkan diungkapkan. Namun, saya merasa bahwa desain kode spesifik saya tidak ditulis dengan baik, dan masih ada banyak tempat di mana ada kurangnya perbaikan dan optimasi. Ini hanya untuk menjadi latihan algoritma. Berikut ini adalah kode inti dari dua kelas utama. Adapun kode lapisan presentasi, saya tidak akan mempostingnya karena itu sangat sepele.
Ini renderingnya:
Kelas Labirin:
// Penulis: Zhongzw // Email: [email protected] Paket cn.zhongzw.model; impor java.util.arraylist; impor java.util.random; kelas publik mazemodel {private int width = 0; Tinggi int private = 0; private acak rnd = acak baru (); mazemodel publik () {this.width = 50; // Maze width this.height = 50; // labirin tinggi} public int getWidth () {return width; } public void setWidth (int lebar) {this.width = width; } public int getHeight () {return height; } public void setHeight (int tinggi) {this.height = tinggi; } public mazemodel (int width, int tinggi) {super (); this.width = lebar; this.height = tinggi; } Public ArrayList <Mazepoint> getMaze () {ArrayList <Mazepoint> maze = ArrayList baru <Mazepoint> (); untuk (int h = 0; h <tinggi; h ++) {untuk (int w = 0; w <lebar; w ++) {mazepoint point = mazepoint baru (w, h); maze.add (point); }} return createMaze (labirin); } Private ArrayList <MazePoint> createMaze (ArrayList <Mazepoint> labirin) {int top = 0; int x = 0; int y = 0; ArrayList <Mazepoint> tim = ArrayList baru <mazepoint> (); Team.add (Maze.get (x + y * width)); while (top> = 0) {int [] val = int int [] {-1, -1, -1, -1}; int kali = 0; bendera boolean = false; Mazepoint pt = (mazepoint) tim.get (atas); x = pt.getX (); y = pt.gety (); pt.visted = true; ro1: while (kali <4) {int dir = rnd.nextInt (4); if (val [dir] == dir) lanjutkan; lain val [dir] = dir; switch (dir) {case 0: // left if ((x - 1)> = 0 && maze.get (x - 1 + y * width) .visted == false) {maze.get (x + y * width) .setLeft (); maze.get (x - 1 + y * lebar) .setright (); Team.add (Maze.get (x - 1 + y * lebar)); top ++; bendera = true; Break Ro1; } merusak; case 1: // kanan if ((x + 1) <width && maze.get (x + 1 + y * lebar) .visted == false) {maze.get (x + y * lebar) .setright (); maze.get (x + 1 + y * lebar) .setleft (); Team.add (Maze.get (x + 1 + y * lebar)); top ++; bendera = true; Break Ro1; } merusak; Kasus 2: // if ((y - 1)> = 0 && maze.get (x + (y - 1) * lebar) .visted == false) {maze.get (x + y * lebar) .setup (); maze.get (x + (y - 1) * lebar) .setDown (); Team.add (Maze.get (x + (y - 1) * lebar)); top ++; bendera = true; Break Ro1; } merusak; Kasus 3: // di bawah if ((y + 1) <height && maze.get (x + (y + 1) * lebar) .visted == false) {maze.get (x + y * lebar) .setDown (); maze.get (x + (y + 1) * lebar) .setup (); Team.add (Maze.get (x + (y + 1) * lebar)); top ++; bendera = true; Break Ro1; } merusak; } kali += 1; } if (! flag) {Team.remove (atas); Atas -= 1; }} return maze; }}
Labirin
// Penulis: Zhongzw // Email: [email protected] Paket cn.zhongzw.model; impor java.util.*; impor java.lang.*; kelas publik mazepoint {private int left = 0; private int right = 0; private int up = 0; private int down = 0; int x x; int y private; Boolean publik menyaksikan; mazepoint publik (int x, int y) {this.x = x; this.y = y; } public int getLeft () {return left; } public void setLeft () {this.left = 1; } public int getRight () {return right; } public void setRight () {this.right = 1; } public int getUp () {return up; } public void setup () {this.up = 1; } public int getown () {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 sety (int y) {this.y = y; }}
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.