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

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

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

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

אודות אלגוריתם וילסון

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

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

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

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

שלב 1: אתחול

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

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

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

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

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

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

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

קריאה נוספת

אם נהניתם מהפוסט הזה, אולי תאהבו גם את ההצעות הבאות:

• מצוד והרוג מחולל מבוך
• מחולל מבוך רקורסיבי Backtracker
• מחולל מבוך האלגוריתם של קרוסקל