في الآونة الأخيرة ، غالبًا ما أشاهد زملائي في الفصل يلعبون لعبة متاهة في غرفة الكمبيوتر. إنه أمر مثير للاهتمام للغاية. أستخدم أيضًا Java لكتابة خوارزمية لتنفيذ جيل عشوائي من المتاهات. في الواقع ، إنها خوارزمية اجتياز عمق للعمق للرسم البياني. الفكرة الأساسية هي أن كل نقطة في المتاهة لديها أربعة جدران ، وبعد ذلك.
1. ابدأ الوصول من أي نقطة (يتم إصلاح الخوارزمية الخاصة بي للبدء من النقطة (0،0)) ، وزيارة واحدة عشوائية من الاتجاهات الأربعة (في كل مرة يمكنك فيها الوصول إلى نقطة يمكن الوصول إليها ، قم بإزالة الجدار في هذا الاتجاه من تلك النقطة) ، وتستمر النقطة التي تم الوصول إليها في الوصول إليها في هذا الاتجاه.
2. يتم تحديد كل نقطة زيارة كما تم الوصول إليها. عندما تصل نقطة ما إلى اتجاه معين ، سنحدد أولاً ما إذا كانت النقطة التي تم الوصول إليها قد تم الوصول إليها أو لمس الحدود. إذا تم الوصول إلى جميع الاتجاهات الأربعة للنقطة أو غير قادرة على الوصول ، فأعود إلى النقطة السابقة. النقطة السابقة تواصل العملية.
بعد اجتيازها بهذه الطريقة ، يمكن التأكيد على أن كل نقطة قد تمت زيارتها. علاوة على ذلك ، نظرًا لأن اتجاه كل وصول عشوائي ، سيتم تشكيل العديد من المواقف المختلفة. في الوقت نفسه ، يكون المسار بين كل نقطتين فريدًا ، والذي يشكل متاهة مختلفة ، ولا يوجد سوى مسار فريد من نقطة البداية إلى نقطة النهاية. يتم تحديد ذلك من خلال خصائص خوارزمية عبور العمق للرسم البياني. في تنفيذ الخوارزمية ، فإن الشيء الرئيسي هو استخدام المكدس. في المرة الأولى ، اضغط أولاً على النقطة الأولى في المكدس. في كل مرة يتم فيها الوصول إلى نقطة ما ، يتم دفع النقطة إلى المكدس ، ثم نصل إلى النقطة في الجزء العلوي من المكدس في أربعة اتجاهات ، والوصول إلى النقطة الجديدة ، ثم اضغط على النقطة الجديدة. حتى جميع النقاط في مخرج المكدس ، سيكون اجتيازنا ناجحًا. هذه عملية عودية. يمكن تنفيذ هذه الخوارزمية بشكل طبيعي بالطرق العودية. ومع ذلك ، أقوم بذلك هنا ، لكنني أقوم بتنفيذه يدويًا مع صفيف كمكدس. هاها ~~ بعد قول الكثير ، لا أعرف ما إذا كان ما أريد التعبير عنه يتم التعبير عنه. ومع ذلك ، أشعر أن تصميم الكود الخاص بي ليس مكتوبًا جيدًا ، ولا يزال هناك العديد من الأماكن التي يوجد فيها نقص في التحسين والتحسين. إنه مجرد تمرين خوارزمية. فيما يلي الرموز الأساسية للفئتين الرئيسيتين. أما بالنسبة لرمز طبقة العرض التقديمي ، فلن أقوم بنشرها لأن هذه هي تافهة للغاية.
هنا هو العرض:
فئة المتاهة:
// المؤلف: Zhongzw // البريد الإلكتروني: [email protected] حزمة cn.zhongzw.model ؛ استيراد java.util.arraylist ؛ استيراد java.util.random ؛ الطبقة العامة mazemodel {private int width = 0 ؛ ارتفاع int الخاص = 0 ؛ RND العشوائي الخاص = جديد عشوائي () ؛ mazemodel العامة () {this.width = 50 ؛ // عرض متاهة هذا. HIEGH = 50 ؛ // Maze height} public int getWidth () {return width ؛ } public void setWidth (int width) {this.width = width ؛ } public int getheight () {return height ؛ } public void setheight (int height) {this.height = height ؛ } mazemodel العامة (عرض int ، ارتفاع int) {super () ؛ this.width = العرض ؛ this.height = الارتفاع ؛ } ArrayList public <MazePoint> getMaze () {ArrayList <MazePoint> maze = new ArrayList <MazePoint> () ؛ لـ (int h = 0 ؛ h <height ؛ h ++) {for (int w = 0 ؛ w <width ؛ w ++) {mazepoint point = new mazepoint (w ، h) ؛ maze.add (point) ؛ }} return createmaze (maze) ؛ } ArrayList الخاص <MazePoint> CreateMaze (ArrayList <MazePoint> maze) {int top = 0 ؛ int x = 0 ؛ int y = 0 ؛ ArrayList <MzePoint> Team = new ArrayList <MazePoint> () ؛ Team.add (maze.get (x + y * width)) ؛ بينما (TOP> = 0) {int [] val = new int [] {-1 ، -1 ، -1 ، -1} ؛ الأوقات الداخلية = 0 ؛ العلم المنطقي = خطأ ؛ MazePoint Pt = (MazePoint) team.get (Top) ؛ x = pt.getx () ؛ y = pt.gety () ؛ pt.visted = صحيح ؛ RO1: بينما (مرات <4) {int dir = rnd.nextint (4) ؛ إذا (val [dir] == dir) متابعة ؛ آخر 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 * width) .SetRight () ؛ Team.add (maze.get (x - 1 + y * width)) ؛ أعلى ++ ؛ العلم = صحيح ؛ كسر RO1 ؛ } استراحة؛ الحالة 1: // اليمين إذا ((x + 1) <width && maze.get (x + 1 + y * width) .visted == false) {maze.get (x + y * width) .setRight () ؛ maze.get (x + 1 + y * width) .setleft () ؛ Team.add (maze.get (x + 1 + y * width)) ؛ أعلى ++ ؛ العلم = صحيح ؛ كسر RO1 ؛ } استراحة؛ الحالة 2: // if ((y - 1)> = 0 && maze.get (x + (y - 1) * width) .visted == false) {maze.get (x + y * width) .setup () ؛ maze.get (x + (y - 1) * width) .setDown () ؛ Team.add (maze.get (x + (y - 1) * width)) ؛ أعلى ++ ؛ العلم = صحيح ؛ كسر RO1 ؛ } استراحة؛ الحالة 3: // أدناه if ((y + 1) <height && maze.get (x + (y + 1) * width) .visted == false) {maze.get (x + y * width) .setDown () ؛ maze.get (x + (y + 1) * width) .setup () ؛ Team.add (maze.get (x + (y + 1) * width)) ؛ أعلى ++ ؛ العلم = صحيح ؛ كسر RO1 ؛ } استراحة؛ } مرات += 1 ؛ } if (! flag) {team.remove (top) ؛ أعلى -= 1 ؛ }} إرجاع متاهة ؛ }}
المتاهة
// المؤلف: Zhongzw // البريد الإلكتروني: [email protected] حزمة cn.zhongzw.model ؛ استيراد java.util.*؛ استيراد java.lang.*؛ الطبقة العامة mazepoint {private int left = 0 ؛ int int inter = 0 ؛ private up = 0 ؛ int private down = 0 ؛ Private Int X ؛ الخاص int y ؛ شهدت منطقية عامة. MazePoint (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 getDown () {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 ؛ }}
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.