ต้นทาง:
ปีที่แล้ว (ภาคเรียนแรกของโรงเรียนมัธยมต้น) ฉันชอบเขียนเกมเล็ก ๆ ดังนั้นฉันจึงอยากลองเขียนเขาวงกต
ผลของโปรแกรม:
กดพื้นที่เพื่อแสดงเส้นทาง:
กระบวนการคิด:
เขาวงกตประกอบด้วยกริดซึ่งต้องการเส้นทางเดียวจากทางเข้าสู่ทางออก
หลังจากคิดถึงโครงสร้างข้อมูลต่าง ๆ ดูเหมือนว่าต้นไม้จะเหมาะสมกว่าโดยมีเส้นทางเดียวจากโหนดรากไปยังโหนดเด็กแต่ละแห่ง สมมติว่าทางเข้าเป็นโหนดรูทและทางออกเป็นโหนดเด็กในต้นไม้จากนั้นเส้นทางจากโหนดรูทไปยังโหนดเด็กนั้นมีความพิเศษอย่างแน่นอน
ดังนั้นหากต้นไม้สามารถสร้างขึ้นเพื่อครอบคลุมกริดทั้งหมดสามารถสร้างเขาวงกตได้
นอกจากนี้จำเป็นต้องมีโหนดผู้ปกครองและลูกของต้นไม้จะต้องอยู่ติดกับกริดบนอินเทอร์เฟซ
เมื่อแสดงอินเทอร์เฟซหากขอบที่ใช้ร่วมกันระหว่างโหนดพาเรนต์และโหนดลูกจะไม่ถูกวาดและขอบอื่น ๆ จะถูกวาดขึ้นเขาวงกตสามารถวาดได้
จากนั้นฉันคิดเกี่ยวกับวิธีการใช้ต้นไม้ดังกล่าว
คำถามสองข้อแรก:
1. ต้นไม้เป็นตัวแทนได้อย่างไร?
2. จะสร้างต้นไม้นี้ได้อย่างไร?
1. ต้นไม้เป็นตัวแทนได้อย่างไร?
สมมติว่าต้นไม้นี้ถูกนำไปใช้เช่นการเขียนต้นไม้ไบนารีแต่ละโหนดต้นไม้จำเป็นต้องเก็บพิกัด (x, y) เพื่อเป็นตัวแทนของกริดและต้องเก็บพอยน์เตอร์สี่ตัว พอยน์เตอร์บางตัวว่างเปล่าบางตัวไม่ว่างเปล่าและพอยน์เตอร์ที่ไม่ได้เป็นจุดว่างเปล่าไปยังโหนดเด็กและโหนดลูกจะบันทึกพิกัดของกริดเพื่อนบ้าน ปัญหาที่ใหญ่ที่สุดในการทำเช่นนี้คือมันเป็นไปไม่ได้ที่จะตรวจสอบว่ากริดทั้งหมดอยู่ในต้นไม้หรือไม่ อาจจะใช้อาร์เรย์สองมิติเป็นอาร์เรย์ธง
สมมติว่าคุณใช้อาร์เรย์สองมิติเพื่อเป็นตัวแทนของกริดของเขาวงกต แต่ละองค์ประกอบอาร์เรย์เก็บข้อมูลอ้างอิงไปยังโหนดพาเรนต์ซึ่งสามารถสร้างต้นไม้เสมือนจริงได้ ดังนั้นอาร์เรย์สองมิติของ n*n หมายถึง n*n กริดและแต่ละองค์ประกอบอาร์เรย์ (lattice) มีการอ้างอิงถึงโหนดพาเรนต์ นอกจากนี้เพื่อให้ได้พิกัดของกริดได้อย่างง่ายดายจะต้องบันทึกข้อมูลพิกัด
2. จะสร้างต้นไม้นี้ได้อย่างไร?
ก่อนอื่นเลือกกริดเป็นโหนดรูท เพื่อที่จะทำให้รูปร่างของเขาวงกตแบบสุ่มเพียงพอฉันเลือกที่จะสร้างพิกัดแบบสุ่มเป็นโหนดราก ในความเป็นจริงมันก็โอเคที่จะเลือกพิกัดที่กำหนด
ถ้าอย่างนั้นจะเพิ่มโหนดลงในต้นไม้นี้ได้อย่างไร?
ฉันใช้เวลาหลายทางที่นี่ ตอนแรกฉันนึกถึงอัลกอริทึมที่ดูเหมือนจะคล้ายกับการย้อนรอยในตอนนี้ (ฉันไม่รู้จักอัลกอริทึมการย้อนรอยในเวลานั้น) แต่ความซับซ้อนของเวลาสูงมาก บางทีเมื่อเขาวงกตคือ 64*64 อัลกอริทึมจะไม่ให้ผลลัพธ์ใด ๆ
จากนั้นวิธีการสแกนการค้นหาความลึกก็คือการย้อนรอย ทุกครั้งที่ฉันสแกนฉันพบโหนดในต้นไม้ปัจจุบันเพื่อดูว่ากริดเพื่อนบ้านอยู่ในต้นไม้หรือไม่ หากไม่ได้อยู่ในต้นไม้ให้เพิ่มกริดเพื่อนบ้านลงในต้นไม้ หากอยู่ในต้นไม้แล้วให้ดูที่กริดเพื่อนบ้านถัดไป หากกริดเพื่อนบ้านทั้งหมดของโหนดอยู่ในต้นไม้ให้ค้นหาโหนดถัดไปและดำเนินการต่อไป นอกจากนี้เพื่อที่จะทำให้เขาวงกตแบบสุ่มตำแหน่งเริ่มต้นของการสแกนเป็นเพียงการสุ่ม อย่างไรก็ตามเส้นทางในเขาวงกตที่สร้างขึ้นโดยวิธีนี้มักจะไม่ลึกพอที่จะมีเอฟเฟกต์คดเคี้ยวและเชิงลึกที่ฉันต้องการ ท้ายที่สุดมันเป็นวิธีที่คล้ายกับการค้นหาความกว้าง ยิ่งไปกว่านั้นการทำเช่นนี้ดูเหมือนจะพึ่งพาพลังเดรัจฉานและอัลกอริทึมก็ไม่ฉลาดและรัดกุมเพียงพอ
ในที่สุดฉันก็นึกถึงการใช้การค้นหาเชิงลึก - อาจเป็นเพราะฉันได้เรียนรู้โครงสร้างข้อมูลเป็นเวลาหนึ่งปีและไม่ได้ฝึกฝนมากเกินไปฉันไม่เคยคิดถึงวิธีแรกที่ฉันควรนึกถึง -
สุ่มเลือกกริดเป็นโหนดรูทเริ่มต้นจากมันและค้นหาในเชิงลึกและเปิดทางจนกว่าจะไม่มีทางไปถอยไปหนึ่งขั้นตอนเปลี่ยนวิธีอื่นแล้วเดินไปที่จะไม่ไปหนึ่งก้าวกลับเปลี่ยนอีก ... รอบนี้ดำเนินต่อไปจนกว่าจะไม่มีทางไป - - ในความเป็นจริงมันยังคงย้อนรอย
ในโปรแกรมกระบวนการต่อไปนี้คือ (ดูฟังก์ชั่น createMaze () ในรหัสสำหรับรายละเอียด):
สุ่มเลือกกริดเป็นโหนดรูทและกดลงในสแต็ก
จากนั้นเรียกใช้ลูปต่อไปนี้เมื่อสแต็กไม่ว่างเปล่า:
นำกริดออกมาตั้งค่าสถานะการเสแสร้งเป็น 1 จากนั้นผลักกริดเพื่อนบ้านทั้งหมดที่ไม่ได้อยู่ในต้นไม้เข้าไปในสแต็ก (แบบสุ่ม) และให้พ่อของกริดเพื่อนบ้านเหล่านี้ชี้ไปที่กริด
หลังจากแก้ปัญหาทั้งสองนี้ส่วนที่เหลือของการวาดภาพเขาวงกตการแสดงเส้นทางและลูกบอลที่เคลื่อนที่นั้นค่อนข้างง่าย
รหัส
แพ็คเกจเขาวงกต; นำเข้า java.awt.color; นำเข้า java.awt.graphics; นำเข้า java.awt.event.keyadapter; นำเข้า java.awt.event.KeyEvent; นำเข้า java.util.random; นำเข้า Java.util.stack; javax.swing.jpanel; lattice class {int final int สุดท้าย = 1; int สุดท้าย int notintree = 0; ส่วนตัว int x = -1; ส่วนตัว int y = -1; ธง int ส่วนตัว = notintree; พ่อตาข่ายส่วนตัว = null; ตาข่ายสาธารณะ (int xx, int yy) {x = xx; y = yy; } สาธารณะ int getx () {return x; } สาธารณะ int getey () {return y; } public int getFlag () {return flag; } Public Lattice Getfather () {Return Father; } โมฆะสาธารณะ setfather (lattice f) {พ่อ = f; } โมฆะสาธารณะ setFlag (int f) {flag = f; } สตริงสาธารณะ toString () {ส่งคืนสตริงใหม่ ("(" + x + "," + y + ")/n"); }} เขาวงกตระดับสาธารณะขยาย jPanel {ส่วนตัวคงที่สุดท้าย Long SerialVersionUid = -8300339045454852626L; ส่วนตัว int จำนวน, ความกว้าง, ช่องว่าง; // ความกว้างความกว้างและความสูงของแต่ละกริดตาข่ายส่วนตัว [] [] เขาวงกต; ballx int ส่วนตัว, Bally; บูลีนส่วนตัว DrawPath = FALSE; เขาวงกต (int m, int wi, int p) {num = m; ความกว้าง = wi; Padding = P; เขาวงกต = ใหม่ตาข่าย [num] [num]; สำหรับ (int i = 0; i <= num- 1; i ++) สำหรับ (int j = 0; j <= num- 1; j ++) เขาวงกต [i] [j] = lattice ใหม่ (i, j); createMaze (); SetKeyListener (); this.setFocusable (จริง); } โมฆะส่วนตัว init () {สำหรับ (int i = 0; i <= num- 1; i ++) สำหรับ (int j = 0; j <= num- 1; j ++) {เขาวงกต [i] [j] .setfather (null); เขาวงกต [i] [j] .setflag (lattice.notintree); } ballx = 0; Bally = 0; DrawPath = FALSE; createMaze (); // setKeyListener (); this.setFocusable (จริง); ทาสีใหม่ (); } สาธารณะ int getCenterx (int x) {return padding + x * width + width / 2; } public int getcentery (int y) {return padding + y * width + width / 2; } สาธารณะ int getCenterx (lattice p) {return padding + p.gety () * ความกว้าง + ความกว้าง / 2; } public int getcentery (lattice p) {return padding + p.getx () * ความกว้าง + ความกว้าง / 2; } โมฆะส่วนตัว checkiswin () {if (ballx == num- 1 && bally == num- 1) {joptionpane.showMessagedialog (null, "คุณชนะ!", "คุณเดินออกจากเขาวงกต", joptionpane.plain_message); init (); }} การย้ายโมฆะส่วนตัวที่ซิงโครไนซ์ (int c) {int tx = ballx, ty = bally; // system.out.println (c); สวิตช์ (c) {case keyevent.vk_left: ty--; หยุดพัก; Case KeyEvent.vk_right: TY ++; หยุดพัก; Case KeyEvent.vk_up: TX--; หยุดพัก; Case KeyEvent.vk_down: TX ++; หยุดพัก; Case KeyEvent.vk_space: if (drawPath == true) {drawPath = false; } else {drawPath = true; } หยุดพัก; ค่าเริ่มต้น:} if (! isoutofBorder (tx, ty) && (เขาวงกต [tx] [ty] .getfather () == เขาวงกต [ballx] [bally] || เขาวงกต [ballx] [bally] .getfather () == เขาวงกต [tx] Bally = ty; }} โมฆะส่วนตัว setKeyListener () {this.addkeyListener (keyadapter ใหม่ () {โมฆะสาธารณะ keypressed (keyevent e) {int c = e.getKeyCode (); ย้าย (c); repaint (); checkiswin ();}}); } บูลีนส่วนตัว isoutofBorder (lattice p) {return isoutofBorder (p.getx (), p.gety ()); } บูลีนส่วนตัว isOutofBorder (int x, int y) {return (x> num - 1 || y> num - 1 || x <0 || y <0)? จริง: เท็จ; } lattice ส่วนตัว [] getneis (lattice p) {int สุดท้าย [] เพิ่ม = {-1, 0, 1, 0, -1}; // คำสั่งคือบน, ขวา, ซ้าย, ซ้าย, ถ้า (isoutofBorder (p)) {return null; } lattice [] ps = new lattice [4]; // คำสั่งคือบน, ขวา, ซ้าย, ซ้าย, int xt; int yt; สำหรับ (int i = 0; i <= 3; i ++) {xt = p.getx ()+เพิ่ม [i]; yt = p.gety () + เพิ่ม [i + 1]; ถ้า (isoutofBorder (xt, yt)) ดำเนินการต่อ; ps [i] = เขาวงกต [XT] [yt]; } return ps; } โมฆะส่วนตัว createMaze () {สุ่มสุ่ม = ใหม่สุ่ม (); int rx = math.abs (random.nextint ()) % num; int ry = math.abs (random.nextint ()) % num; สแต็ค <Latice> S = New Stack <Latice> (); lattice p = เขาวงกต [rx] [ry]; lattice neis [] = null; s.push (p); ในขณะที่ (! s.isempty ()) {p = s.pop (); P.SetFlag (lattice.intree); neis = getneis (p); int ran = math.abs (random.nextint ()) % 4; สำหรับ (int a = 0; a <= 3; a ++) {ran ++; วิ่ง %= 4; if (neis [ran] == null || neis [ran] .getFlag () == lattice.intree) ดำเนินการต่อ; s.push (neis [วิ่ง]); neis [วิ่ง] .setfather (p); }} // ChangeFather (เขาวงกต [0] [0], null); } โมฆะส่วนตัว ChangeFather (Lattice P, Lattice F) {ถ้า (P.GetFather () == NULL) {P.SetFather (F); กลับ; } else {ChangeFather (P.GetFather (), P); }} Void Private Clearfence (int i, int J, int fx, int fy, กราฟิก g) {int sx = padding + ((j> fy? j: fy) * ความกว้าง), sy = padding + ((i> fx? i: fx) * width), dx = (i == fx? if (sx! = dx) {sx ++; dx--; } else {sy ++; Dy--; } G.Drawline (SX, SY, DX, DY); } Void PaintComponent (กราฟิก G) {super.paintComponent (G); สำหรับ (int i = 0; i <= num; i ++) {g.drawline (padding + i * width, padding, padding + i * ความกว้าง, padding + num * width); } สำหรับ (int j = 0; j <= num; j ++) {g.drawline (padding, padding + j * width, padding + num * ความกว้าง, padding + j * width); } G.SetColor (this.getBackground ()); สำหรับ (int i = num-1; i> = 0; i--) {สำหรับ (int j = num-1; j> = 0; j--) {lattice f = เขาวงกต [i] [j] .getFather (); if (f! = null) {int fx = f.getx (), fy = f.gety (); Clearfence (I, J, FX, FY, G); }}} G.Drawline (การขยาย, padding + 1, padding, padding + ความกว้าง - 1); int last = padding + num * width; G.Drawline (สุดท้าย, สุดท้าย - 1, สุดท้าย, สุดท้าย - ความกว้าง + 1); G.SetColor (color.Red); G.Filloval (getCenterx (Bally) - ความกว้าง / 3, getCentery (ballx) - ความกว้าง / 3, ความกว้าง / 2, ความกว้าง / 2); ถ้า (drawPath == true) drawPath (g); } โมฆะส่วนตัว DrawPath (กราฟิก g) {color path_color = color.orange, ทั้งสอง _path_color = color.pink; if (drawPath == true) g.setColor (path_color); else g.setColor (this.getBackground ()); lattice p = เขาวงกต [num - 1] [num - 1]; ในขณะที่ (p.getfather ()! = null) {p.setflag (2); p = p.getfather (); } G.Filloval (getCenterx (p) - ความกว้าง / 3, getCentery (p) - ความกว้าง / 3, ความกว้าง / 2, ความกว้าง / 2); p = เขาวงกต [0] [0]; ในขณะที่ (p.getfather ()! = null) {ถ้า (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 = เขาวงกต [num - 1] [num - 1]; ในขณะที่ (p.getfather ()! = null) {ถ้า (p.getFlag () == 3) break; G.Drawline (GetCenterx (P), GetCentery (P), GetCenterx (P.GetFather ()), GetCentery (P.GetFather ())); p = p.getfather (); }} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int สุดท้าย n = 30, ความกว้าง = 600, padding = 20, lx = 200, ly = 100; jpanel p = เขาวงกตใหม่ (n, (ความกว้าง - ช่องว่างภายใน - ช่องว่างภายใน) / n, ช่องว่าง); jframe frame = new JFrame ("เขาวงกต (แสดงหรือซ่อนเส้นทางตามแถบอวกาศ)"); frame.getContentPane (). เพิ่ม (P); frame.setDefaultCloseoperation (jframe.exit_on_close); frame.setsize (ความกว้าง + ช่องว่าง, ความกว้าง + padding + padding); frame.setLocation (lx, ly); frame.setVisible (จริง); -