أصل:
في العام الماضي (الفصل الدراسي الأول من مدرسة جونيور الثانوية) ، أحببت كتابة ألعاب صغيرة ، لذلك أردت أن أحاول كتابة متاهة.
تأثيرات البرنامج:
اضغط على مساحة لعرض المسار:
عملية التفكير:
تتكون المتاهة من شبكات ، تتطلب مسارًا واحدًا فقط من مدخل المخرج.
بعد التفكير في هياكل البيانات المختلفة ، يبدو أن الأشجار أكثر ملاءمة ، مع مسار واحد فقط من عقدة الجذر إلى كل عقدة طفل. على افتراض أن المدخل هو عقدة الجذر والخروج هو عقدة طفل في الشجرة ، فإن المسار من عقدة الجذر إلى عقدة الطفل فريدة من نوعها بالتأكيد.
لذلك إذا كان يمكن بناء شجرة لتغطية جميع الشبكات ، فيمكن إنشاء متاهة.
بالإضافة إلى ذلك ، يجب أن تكون العقد الوالد والطفل للشجرة شبكات مجاورة على الواجهة.
عند عرض الواجهة ، إذا لم يتم رسم الحواف المشتركة بين العقدة الأصل والعقدة الطفل ، ويتم رسم حواف أخرى ، فيمكن رسم متاهة.
ثم فكرت في كيفية تنفيذ مثل هذه الشجرة.
السؤالين الأولين:
1. كيف تمثل الأشجار؟
2. كيف تبني هذه الشجرة؟
1. كيف تمثل الأشجار؟
على افتراض أن هذه الشجرة يتم تنفيذها مثل كتابة شجرة ثنائية ، تحتاج كل عقدة شجرة إلى تخزين إحداثي (x ، y) لتمثيل شبكة ، ويجب تخزين أربعة مؤشرات. بعض المؤشرات فارغة ، وبعضها ليست فارغة ، والمؤشرات التي ليست فارغة نقطة للعقد الفرعية ، وتوفر العقد الفرعية إحداثيات الشبكة الجار. أكبر مشكلة في القيام بذلك هي أنه من المستحيل تحديد ما إذا كانت جميع الشبكات موجودة في الشجرة. ربما يتم استخدام صفيف ثنائي الأبعاد أيضًا كصفيف العلم.
لنفترض أنك تستخدم صفيف ثنائي الأبعاد لتمثيل شبكة المتاهة. يقوم كل عنصر صفيف بتخزين إشارة إلى العقدة الأصل ، والتي يمكن أن تشكل أيضًا شجرة افتراضية. لذا فإن مجموعة ثنائية الأبعاد من N*n تمثل شبكات n*n ، ولكل عنصر صفيف (شعرية) إشارة إلى العقدة الأصل. بالإضافة إلى ذلك ، من أجل الحصول على إحداثيات الشبكة بسهولة ، يجب أيضًا حفظ المعلومات الإحداثي.
2. كيف تبني هذه الشجرة؟
حدد أولاً شبكة كعقدة الجذر. من أجل جعل شكل المتاهة عشوائيًا بما فيه الكفاية ، اخترت إنشاء إحداثي بشكل عشوائي كعقدة الجذر. في الواقع ، لا بأس أيضًا في اختيار إحداثي يتم تحديده.
ثم ، كيف تضيف العقد إلى هذه الشجرة؟
أخذت الكثير من الالتفافات هنا. في البداية فكرت في خوارزمية يبدو أنها تشبه التراجع الآن (لم أكن أعرف خوارزمية التراجع في ذلك الوقت.) ، لكن التعقيد الزمني مرتفع للغاية. ربما عندما تكون المتاهة 64*64 ، فإن الخوارزمية لن تحقق أي نتائج.
بعد ذلك ، يتم أيضًا تراجع طريقة البحث عن عمق المسح. في كل مرة أقوم فيها بالمسح الضوئي ، أجد عقدة في الشجرة الحالية لمعرفة ما إذا كانت شبكة الجوار في الشجرة. إذا لم يكن في الشجرة ، فأضف شبكة الجوار إلى الشجرة. إذا كانت موجودة بالفعل في الشجرة ، فابحث عن شبكة الجوار التالية. إذا كانت جميع شبكات العقدة في الشجرة موجودة في الشجرة ، فابحث عن العقدة التالية واستمر في نفس العملية. بالإضافة إلى ذلك ، من أجل جعل المتاهة تم إنشاؤها بشكل عشوائي ، يكون موضع بدء المسح العشوائي عشوائيًا. ومع ذلك ، فإن المسارات الموجودة في المتاهة التي تم إنشاؤها بواسطة هذه الطريقة ليست دائمًا عميقة بما يكفي للحصول على التأثير المتعمق والمتعمق الذي أريده. بعد كل شيء ، إنها طريقة مماثلة للبحث عن اتساع. علاوة على ذلك ، يبدو أن القيام بذلك يعتمد دائمًا على القوة الغاشمة ، والخوارزمية ليست ذكية وموجزة بما فيه الكفاية.
أخيرًا ، فكرت أخيرًا في استخدام البحث المتعمق. . ربما لأنني تعلمت بنية البيانات لمدة عام ولم أمارسها كثيرًا ، لم أفكر مطلقًا في هذه الطريقة الأولى التي يجب أن أفكر فيها. .
حدد الشبكة بشكل عشوائي كعقدة الجذر ، وابدأ منها وابحث بعمق ، وفتح طريقة حتى لا توجد طريقة للذهاب ، والتراجع خطوة واحدة ، وتغيير طريقة أخرى ، ثم المشي دون أي وسيلة ، خلف خطوة واحدة ، وتغيير آخر ... هذه الدورة تستمر حتى لا توجد طريقة للذهاب. . . في الواقع ، لا يزال التراجع.
في البرنامج ، العملية التالية هي (راجع وظيفة Createmaze () في الكود للحصول على التفاصيل):
حدد بشكل عشوائي شبكة كعقدة الجذر وادفعها في المكدس.
ثم قم بتنفيذ الحلقة التالية عندما لا تكون المكدس فارغًا:
أخرج شبكة ، وضبط علمها الداخلي على 1 ، ثم ادفع جميع شبكات الجوار التي لا توجد في الشجرة إلى المكدس (القصص بشكل عشوائي) ، واترك والد هذه الشبكات الجار يشير إلى الشبكة.
بعد حل هاتين المشكلتين ، تكون بقية رسم المتاهات ، وعرض المسارات ، والكرات المتحركة بسيطة نسبيًا.
شفرة
حزمة متاهة ؛ استيراد java.awt.color ؛ استيراد java.awt.graphics ؛ استيراد java.awt.event.keyadapter ؛ import java.awt.event.keyevent ؛ import java.util.random ؛ import java.util.stack ؛ import javax.swing.jframe ؛ javax.swing.jpanel ؛ class lattice {static final int intree = 1 ؛ ثابت نهائي int notintree = 0 ؛ private int x = -1 ؛ private int y = -1 ؛ علم int الخاص = notintree ؛ والد شعرية خاصة = فارغة ؛ الشبكة العامة (int xx ، int yy) {x = xx ؛ y = yy ؛ } public int getx () {return x ؛ } public int gety () {return y ؛ } public int getFlag () {return flag ؛ } شعرية عامة getFather () {return add ؛ } public void setFather (lattice f) {الأب = f ؛ } public void setFlag (int f) {flag = f ؛ } السلسلة العامة toString () {return new string ("(" + x + "،" + y + ")/n") ؛ }} يمتد متاهة الفئة العامة jpanel {private static final long serialversionuid = -8300339045454852626l ؛ Private int num ، العرض ، الحشو ؛ // عرض عرض وارتفاع كل شبكة شعرية خاصة [] [] متاهة ؛ خاص int ballx ، بالي ؛ Private Boolean DrawPath = false ؛ Maze (int m ، int wi ، int p) {num = m ؛ العرض = wi ؛ الحشو = P ؛ متاهة = شبكة جديدة [num] [num] ؛ لـ (int i = 0 ؛ i <= num- 1 ؛ i ++) لـ (int j = 0 ؛ j <= num- 1 ؛ j ++) maze [i] [j] = شبكة جديدة (i ، j) ؛ createmaze () ؛ setKeyListener () ؛ this.setFocusable (صحيح) ؛ } private void init () {for (int i = 0 ؛ i <= num- 1 ؛ i ++) لـ (int j = 0 ؛ j <= num- 1 ؛ j ++) {maze [i] [j] .setFather (null) ؛ Maze [i] [j] .setFlag (lattice.notintree) ؛ } ballx = 0 ؛ بالي = 0 ؛ DrawPath = false ؛ createmaze () ؛ // setKeyListener () ؛ this.setFocusable (صحيح) ؛ REPAINT () ؛ } public int getCenterx (int x) {return padding + x * width + width / 2 ؛ } public int getCentery (int y) {return padding + y * width + width / 2 ؛ } public int getCenterx (lattice p) {return padding + p.gety () * width + width / 2 ؛ } public int getCentery (lattice p) {return padding + p.getx () * width + width / 2 ؛ } private void checkiswin () {if (ballx == num- 1 && bally == num- 1) {joptionpane.showmessagedialog (null ، init () ؛ }} MOVERED VOID الخاص متزامن (int c) {int tx = ballx ، ty = bally ؛ // system.out.println (c) ؛ Switch (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 ؛ } آخر {drawPath = true ؛ } استراحة؛ افتراضي:} if (! isoutofBorder (tx ، ty) && (maze [tx] [ty] .getFather () == maze [ballx] [bally] || maze [ballx] [bally] .getFather () == maze [tx])) بالي = تاي ؛ }} private void setKeyListener () {this.addKeyListener (new KeyAdapter () {public void keypressed (keyevent e) {int c = } private boolean 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)؟ صحيح: خطأ } private lattice [] getNeis (lattice p) {final int [] adds = {-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 ()+add [i] ؛ yt = p.gety () + يضيف [i + 1] ؛ إذا (isoutofborder (xt ، yt)) ، تستمر ؛ ps [i] = maze [xt] [yt] ؛ } إرجاع PS ؛ } private void createMaze () {random random = new random () ؛ int rx = math.abs (random.nextint ()) ٪ num ؛ int ry = math.abs (random.nextint ()) ٪ num ؛ Stack <Wattice> s = new stack <Wattice> () ؛ lattice p = maze [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 [ran]) ؛ Neis [ran] .setfather (p) ؛ }} // changefather (maze [0] [0] ، null) ؛ } private void changefather (lattice p ، lattice f) {if (p.getFather () == null) {p.setFather (f) ؛ يعود؛ } آخر {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؟ if (sx! = dx) {sx ++ ؛ DX-- ؛ } آخر {sy ++ ؛ داي-؛ } G.Drawline (SX ، SY ، DX ، DY) ؛ } paintComponent المحمي void (Graphics g) {super.paintcomponent (g) ؛ لـ (int i = 0 ؛ i <= num ؛ i ++) {g.drawline (padding + i * width ، padding ، padding + i * width ، padding + num * width) ؛ } لـ (int j = 0 ؛ j <= num ؛ j ++) {g.drawline (padding ، padding + j * width ، padding + num * width ، padding + j * width) ؛ } g.setColor (this.getBackground ()) ؛ لـ (int i = num-1 ؛ i> = 0 ؛ i--) {for (int j = num-1 ؛ j> = 0 ؛ j--) {lattice f = maze [i] [j] .getFather () ؛ if (f! = null) {int fx = f.getx () ، fy = f.gety () ؛ Clearfence (I ، J ، FX ، FY ، G) ؛ }}} g.drawline (padding ، padding + 1 ، padding ، padding + width - 1) ؛ int last = padding + num * width ؛ G.Drawline (الأخير ، الأخير - 1 ، الأخير ، الأخير - العرض + 1) ؛ G.SetColor (color.red) ؛ G.Filloval (getCenerx (bally) - width / 3 ، getCentery (ballx) - width / 3 ، width / 2 ، width / 2) ؛ if (drawPath == true) drawpath (g) ؛ } private void drawpath (Graphics g) {color path_color = color.orange ، very_path_color = color.pink ؛ if (drawPath == true) g.setColor (path_color) ؛ else g.setColor (this.getbackground ()) ؛ lattice p = maze [num - 1] [num - 1] ؛ بينما (p.getFather ()! = null) {p.setFlag (2) ؛ p = p.getFather () ؛ } g.filloval (getCenerx (p) - width / 3 ، getCentery (p) - width / 3 ، width / 2 ، width / 2) ؛ P = متاهة [0] [0] ؛ بينما (p.getFather ()! = null) {if (p.getFlag () == 2) {p.setFlag (3) ؛ G.SetColor (pother_path_color) ؛ } g.drawline (getCenerx (p) ، getCentery (p) ، getCenterx (p.getFather ()) ، getCenerery (p.getFather ())) ؛ p = p.getFather () ؛ } g.setColor (path_color) ؛ p = maze [num - 1] [num - 1] ؛ بينما (p.getFather ()! = null) {if (p.getFlag () == 3) break ؛ G.Drawline (getCenerx (p) ، getCentery (p) ، getCenerx (p.getFather ()) ، getCentery (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 = maze new (n ، (العرض - padding - padding) / n ، padding) ؛ JFrame Frame = New JFrame ("Maze (عرض أو إخفاء المسارات حسب شريط الفضاء)") ؛ frame.getContentPane (). add (p) ؛ frame.setDefaultCloseOperation (jframe.exit_on_close) ؛ Frame.SetSize (عرض + حشوة ، عرض + حشوة + حشوة) ؛ frame.setLocation (lx ، ly) ؛ frame.setVisible (صحيح) ؛ }}