asal:
Tahun lalu (semester pertama sekolah menengah pertama), saya suka menulis game kecil, jadi saya ingin mencoba menulis labirin.
Efek program:
Tekan ruang untuk menampilkan jalur:
Proses Berpikir:
Labirin terdiri dari kisi -kisi, hanya membutuhkan satu jalan dari pintu masuk ke pintu keluar.
Setelah memikirkan berbagai struktur data, tampaknya pohon lebih cocok, dengan hanya satu jalur dari simpul akar ke setiap node anak. Dengan asumsi bahwa pintu masuk adalah simpul akar dan pintu keluar adalah simpul anak di pohon, kemudian jalan dari simpul akar ke simpul anak benar -benar unik.
Jadi jika pohon dapat dibangun untuk menutupi semua kisi, labirin dapat dibuat.
Selain itu, diperlukan bahwa node orang tua dan anak dari pohon harus berdekatan pada antarmuka.
Saat menampilkan antarmuka, jika tepi yang dibagikan antara simpul induk dan simpul anak tidak ditarik, dan tepi lainnya ditarik, labirin dapat ditarik.
Lalu saya berpikir tentang cara menerapkan pohon seperti itu.
Dua pertanyaan pertama:
1. Bagaimana pohon mewakili?
2. Bagaimana cara membangun pohon ini?
1. Bagaimana pohon mewakili?
Dengan asumsi bahwa pohon ini diimplementasikan seperti menulis pohon biner, setiap simpul pohon perlu menyimpan koordinat (x, y) untuk mewakili kisi, dan empat pointer harus disimpan. Beberapa petunjuk kosong, beberapa tidak kosong, dan pointer yang tidak kosong ke node anak, dan node anak menyimpan koordinat kisi tetangga. Masalah terbesar dengan melakukan ini adalah tidak mungkin untuk menentukan apakah semua kisi ada di pohon. Mungkin array dua dimensi juga digunakan sebagai array bendera.
Misalkan Anda menggunakan array dua dimensi untuk mewakili kisi labirin. Setiap elemen array menyimpan referensi ke node induk, yang juga dapat membentuk pohon virtual. Jadi array dua dimensi n*n mewakili n*n grid, dan masing-masing elemen array (kisi) memiliki referensi ke node induk. Selain itu, untuk dengan mudah mendapatkan koordinat grid, informasi koordinat juga harus disimpan.
2. Bagaimana cara membangun pohon ini?
Pertama -tama pilih grid sebagai simpul root. Untuk membuat bentuk labirin cukup acak, saya memilih untuk secara acak menghasilkan koordinat sebagai simpul akar. Bahkan, juga tidak masalah untuk memilih koordinat yang ditentukan.
Lalu, bagaimana cara menambahkan node ke pohon ini?
Saya mengambil banyak jalan memutar di sini. Awalnya saya memikirkan sebuah algoritma yang tampaknya mirip dengan backtracking sekarang (saya tidak tahu algoritma backtracking pada waktu itu ...), tetapi kompleksitas waktu sangat tinggi. Mungkin ketika labirin adalah 64*64, algoritma tidak akan menghasilkan hasil apa pun.
Kemudian, metode pencarian kedalaman pemindaian juga mundur. Setiap kali saya memindai, saya menemukan sebuah simpul di pohon saat ini untuk melihat apakah jaringan tetangganya ada di pohon. Jika tidak ada di pohon, tambahkan jaringan tetangga ke pohon. Jika sudah ada di pohon, lihat grid tetangga berikutnya. Jika semua kisi -kisi tetangga dari simpul ada di pohon, temukan simpul berikutnya dan lanjutkan operasi yang sama. Selain itu, untuk membuat labirin yang dihasilkan secara acak, posisi awal pemindaian hanya acak. Namun, jalur dalam labirin yang dihasilkan oleh metode ini selalu tidak cukup dalam untuk memiliki efek berliku dan mendalam yang saya inginkan. Bagaimanapun, ini adalah metode yang mirip dengan pencarian luas. Selain itu, melakukan ini sepertinya selalu mengandalkan Brute Force, dan algoritma tidak cukup pintar dan cukup ringkas.
Akhirnya, saya akhirnya berpikir untuk menggunakan pencarian mendalam. . Mungkin karena saya telah belajar struktur data selama setahun dan belum terlalu banyak mempraktikkannya, saya tidak pernah memikirkan metode pertama yang harus saya pikirkan. .
Pilih secara acak kisi -kisi sebagai simpul root, mulailah darinya dan cari secara mendalam, dan buka cara sampai tidak ada cara untuk pergi, mundur satu langkah, mengubah cara lain, dan kemudian berjalan tanpa cara untuk pergi, mengambil satu langkah mundur, mengubah yang lain ... siklus ini berlangsung sampai tidak ada cara untuk pergi. . . Bahkan, itu masih mundur.
Dalam program ini, proses berikut adalah (lihat fungsi createMaze () dalam kode untuk detail):
Pilih kisi secara acak sebagai simpul root dan dorong ke dalam tumpukan.
Kemudian jalankan loop berikut saat tumpukan tidak kosong:
Keluarkan sebuah kisi -kisi, atur bendera intree ke 1, lalu dorong semua jaringan tetangganya yang tidak ada di pohon ke dalam tumpukan (cerita secara acak), dan biarkan bapak kisi -kisi tetangga ini menunjuk ke kisi -kisi.
Setelah menyelesaikan dua masalah ini, sisa gambar labirin, menampilkan jalur, dan bola bergerak relatif sederhana.
Kode
Paket labirin; impor java.awt.color; impor java.awt.graphics; impor java.awt.event.keyadapter; impor java.awt.event.keyevent; impor java.util.random; impor java.util.stack; impor javax.swing.jframe; javax.swing.jpanel; kisi kelas {static final int intree = 1; statis final int notintree = 0; private int x = -1; int y = -1; private int bendera = notintree; ayah kisi pribadi = null; kisi publik (int xx, int yy) {x = xx; y = yy; } public int getX () {return x; } public int gety () {return y; } public int getFlag () {return flag; } kisi publik getFather () {return ayah; } public void setFather (kisi f) {ayah = f; } public void setFlag (int f) {flag = f; } public string toString () {return new string ("(" + x + "," + y + ")/n"); }} labirin kelas publik memperluas jpanel {private static final long serialversionuid = -8300339045454852626l; private int num, lebar, padding; // lebar lebar dan tinggi setiap kisi kisi pribadi [] [] labirin; private int ballx, Bally; Private Boolean Drawpath = false; Labirin (int m, int wi, int p) {num = m; lebar = wi; padding = p; labirin = kisi baru [num] [num]; untuk (int i = 0; i <= num- 1; i ++) untuk (int j = 0; j <= num- 1; j ++) labirin [i] [j] = kisi baru (i, j); createMaze (); setKeyListener (); this.setFocusable (true); } private void init () {for (int i = 0; i <= num- 1; i ++) untuk (int j = 0; j <= num- 1; j ++) {maze [i] [j] .setfather (null); labirin [i] [j] .setflag (lattice.notintree); } ballx = 0; Bally = 0; drawpath = false; createMaze (); // setKeyListener (); this.setFocusable (true); ulang (); } public int getCenterx (int x) {return padding + x * lebar + lebar / 2; } public int getCentery (int y) {return padding + y * lebar + lebar / 2; } public int getCenterx (kisi p) {return padding + p.gety () * lebar + lebar / 2; } public int getCentery (kisi p) {return padding + p.getx () * lebar + lebar / 2; } private void checkIswin () {if (ballx == num- 1 && balally == num- 1) {jOptionPane.showmessagedialog (null, "Anda menang!", "Anda berjalan keluar dari labirin.", joptionpane.plain_message); init (); }} Sinkronisasi Private Void Move (int C) {int tx = ballx, ty = bally; // System.out.println (c); switch (c) {case keyevent.vk_left: ty--; merusak; case keyevent.vk_right: ty ++; merusak; case keyevent.vk_up: tx--; merusak; case keyevent.vk_down: tx ++; merusak; case keyevent.vk_space: if (drawpath == true) {drawpath = false; } else {drawpath = true; } merusak; Default:} if (! isoutofborder (tx, ty) && (maze [tx] [ty] .getFather () == maze [ballx] [bally] || maze [ballx] [balally] .getFather () == maze [tx] [ty]))) {ballx = tx; Bally = ty; }} private void setKeyListener () {this.addKeyListener (keyAdapter baru () {public void keypressed (keyevent e) {int c = e.getKeyCode (); pindahkan (c); ulang (); checkiswin ();}}); } private boolean isoutofborder (kisi p) {return isoutofborder (p.getx (), p.gety ()); } private boolean isoutofborder (int x, int y) {return (x> num - 1 || y> num - 1 || x <0 || y <0)? Benar: false; } kisi privat [] getneis (kisi p) {int int [] menambahkan = {-1, 0, 1, 0, -1}; // urutannya adalah atas, kanan, kiri, if (isoutofborder (p)) {return null; } Kisi [] ps = kisi baru [4]; // Urutannya atas, kanan, kiri, int xt; int yt; untuk (int i = 0; i <= 3; i ++) {xt = p.getX ()+menambahkan [i]; yt = p.gety () + menambahkan [i + 1]; if (isoutofborder (xt, yt)) lanjutkan; ps [i] = maze [xt] [yt]; } return ps; } private void createMaze () {acak acak = acak baru (); int rx = math.abs (acak.nextInt ()) % num; int ry = math.abs (acak.nextInt ()) % num; Stack <Prattice> S = new Stack <Lattice> (); Kisi p = labirin [rx] [ry]; Kisi neis [] = null; S.Push (P); while (! s.isempty ()) {p = s.pop (); p.setflag (lattice.intree); neis = getneis (p); int ran = math.abs (acak.nextInt ()) % 4; untuk (int a = 0; a <= 3; a ++) {ran ++; berlari %= 4; if (neis [ran] == null || neis [ran] .getFlag () == lattice.intree) lanjutkan; s.push (neis [ran]); neis [ran] .setfather (p); }} // changefather (labirin [0] [0], null); } private void changefather (kisi p, kisi f) {if (p.getFather () == null) {p.setFather (f); kembali; } else {changefather (p.getFather (), p); }} private void clearfence (int i, int j, int fx, int fy, grafik g) {int sx = padding + ((j> fy? j: fy) * lebar), sy = padding + ((i> fx? i: fx) * lebar = dx = (i == fx? sx + width), fx) * width), dx = (i == fx? sx + width), dy = dx = dx = (i == fx? sx + width), dy = dx = dx = (i == fx? sx + width), dy = dy = dx = (i == fx? sx + width), dy = dy = dx = (i == fx? Sx + width), if (sx! = dx) {sx ++; DX--; } else {sy ++; dy--; } G.Drawline (SX, SY, DX, DY); } protected void catcomponent (grafik g) {super.paintComponent (g); untuk (int i = 0; i <= num; i ++) {g.drawline (padding + i * lebar, padding, padding + i * lebar, padding + num * lebar); } untuk (int j = 0; j <= num; j ++) {g.drawline (padding, padding + j * lebar, padding + num * lebar, padding + j * lebar); } g.setColor (this.getBackground ()); untuk (int i = num-1; i> = 0; i--) {for (int j = num-1; j> = 0; j--) {kisi f = maze [i] [j] .getFather (); if (f! = null) {int fx = f.getX (), fy = f.gety (); Clearfence (I, J, FX, TA, G); }}} g.drawline (padding, padding + 1, padding, padding + lebar - 1); int last = padding + num * lebar; G.Drawline (terakhir, terakhir - 1, terakhir, terakhir - lebar + 1); G.SetColor (Color.Red); G.Filloval (getCenterx (Bally) - Lebar / 3, getCentery (ballx) - lebar / 3, lebar / 2, lebar / 2); if (drawpath == true) drawpath (g); } private void drawpath (grafik g) {color path_color = color.orange, keduanya_path_color = color.pink; if (drawpath == true) g.setColor (path_color); lain G.SetColor (this.getBackground ()); Kisi p = labirin [num - 1] [num - 1]; while (p.getFather ()! = null) {p.setFlag (2); p = p.getFather (); } g.filloval (getCenterx (p) - lebar / 3, getCentery (p) - lebar / 3, lebar / 2, lebar / 2); p = labirin [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 ()), getCenteryy (p.getFather ())); p = p.getFather (); } g.setColor (path_color); p = labirin [num - 1] [num - 1]; while (p.getFather ()! = null) {if (p.getFlag () == 3) break; G.Drawline (getCenterx (p), getCentery (p), getCenterx (p.getFather ()), getCenteryy (p.getFather ())); p = p.getFather (); }} public static void main (string [] args) {final int n = 30, width = 600, padding = 20, lx = 200, ly = 100; Jpanel p = labirin baru (n, (lebar - padding - padding) / n, padding); JFrame frame = jframe baru ("labirin (tunjukkan atau sembunyikan jalan setapak dengan bilah ruang)"); frame.getContentPane (). Add (p); frame.setDefaultCloseOperation (jframe.exit_on_close); frame.setsize (lebar + padding, lebar + padding + padding); frame.setlocation (LX, LY); frame.setVisible (true); }}