מחולל מבוך האלגוריתם של ווילסון

האלגוריתם של ווילסון הוא שיטת הליכה אקראית שנמחקה בלולאה המייצרת עצים משתרעים אחידים ליצירת מבוך. המשמעות היא שכל המבוכים האפשריים בגודל נתון צפויים להיווצר באותה מידה, מה שהופך אותו לטכניקת יצירת מבוך חסרת פניות. האלגוריתם של ווילסון יכול להיחשב כגרסה משופרת של אלגוריתם אלדוס-ברודר, מכיוון שהוא מייצר מבוכים בעלי מאפיינים זהים, אך הוא פועל הרבה יותר מהר, כך שלא טרחתי ליישם את האלגוריתם של אלדוס-ברודר כאן.

מבוך מושלם הוא מבוך שבו יש בדיוק נתיב אחד מכל נקודה במבוך לכל נקודה אחרת. זה אומר שאתה לא יכול בסופו של דבר להסתובב במעגלים, אבל לעתים קרובות תתקל במבוי סתום, מה שיאלץ אותך להסתובב ולחזור.

מפות המבוך שנוצרות כאן כוללות גרסת ברירת מחדל ללא כל עמדות התחלה וסיום, כך שתוכלו להחליט על אלו בעצמכם: יהיה פתרון מכל נקודה במבוך לכל נקודה אחרת. אם תרצו השראה, תוכלו לאפשר עמדת התחלה וסיום מוצעת - ואפילו לראות את הפתרון בין השניים.

על האלגוריתם של ווילסון

האלגוריתם של ווילסון ליצירת עצים משתרעים אחידים באמצעות קיר אקראי שנמחק בלולאה נוצר על ידי דייוויד ברוס ווילסון.

וילסון הציג במקור את האלגוריתם הזה ב-1996 תוך כדי מחקר על עצים משתרעים אקראיים ושלשלאות מרקוב בתורת ההסתברות. למרות שעבודתו הייתה בעיקר במתמטיקה ובפיסיקה סטטיסטית, האלגוריתם אומץ מאז באופן נרחב ליצירת מבוכים בשל יכולתו לייצר מבוכים אחידים לחלוטין.

איך האלגוריתם של ווילסון עובד עבור דור המבוך

האלגוריתם של וילסון מבטיח שהמבוך הסופי מחובר במלואו ללא לולאות על ידי גילוף איטרטיבי של שבילים מתאי לא ביקרו תוך שימוש בהליכות אקראיות.

שלב 1: אתחול

• התחל עם רשת מלאה בקירות.
• הגדר רשימה של כל תאי המעבר האפשריים.

שלב 2: בחר תא התחלה אקראי

• בחר כל תא אקראי וסמן אותו כמבקר. זה משמש כנקודת המוצא של המבוך במהלך הדור.

שלב 3: הליכה אקראית עם מחיקת לולאה

• בחר תא שלא ביקר והתחל בהליכה אקראית (נע בכיוונים אקראיים).
• אם ההליכה מגיעה לתא שכבר ביקר, מחק לולאות כלשהן בנתיב.
• לאחר שההליכה מתחברת לאזור המבקר, סמן את כל התאים בנתיב כביקור.

שלב 4: חזור עד לביקור בכל התאים :

• המשך לבחור תאים שלא ביקרו ולבצע הליכות אקראיות עד שכל תא יהיה חלק מהמבוך.