מחולל מבוך רקורסיבי Backtracker
פורסם: 16 בפברואר 2025 בשעה 18:19:30 UTC
מחולל מבוך באמצעות אלגוריתם Backtracker רקורסיבי ליצירת מבוך מושלם. אלגוריתם זה נוטה ליצור מבוכים עם מסדרונות ארוכים ומפותלים ופתרון ארוך מאוד ומתפתל.Recursive Backtracker Maze Generator
אלגוריתם המעקב הרקורסי הוא באמת חיפוש עומק ראשון למטרה כללית. כאשר נעשה בו שימוש ליצירת מבוך, הוא שונה מעט כדי לבחור את הנתיב באקראי, בעוד שאם נעשה בו שימוש למטרות חיפוש ממשיות, בדרך כלל היה חיפוש בכל רמה בסדר ליניארי. הוא נוטה לייצר מבוכים עם מסדרונות ארוכים ומפותלים ופתרון ארוך מאוד ומתפתל.
מבוך מושלם הוא מבוך שבו יש בדיוק נתיב אחד מכל נקודה במבוך לכל נקודה אחרת. זה אומר שאתה לא יכול בסופו של דבר להסתובב במעגלים, אבל לעתים קרובות תתקל במבוי סתום, מה שיאלץ אותך להסתובב ולחזור.
מפות המבוך שנוצרות כאן כוללות גרסת ברירת מחדל ללא כל עמדות התחלה וסיום, כך שתוכלו להחליט על אלו בעצמכם: יהיה פתרון מכל נקודה במבוך לכל נקודה אחרת. אם תרצו השראה, תוכלו לאפשר עמדת התחלה וסיום מוצעת - ואפילו לראות את הפתרון בין השניים.
אלגוריתם ה-backtracker רקורסיבי הוא שיטת חיפוש עומק ראשון ליצירת מבוכים מושלמים (מבוכים ללא לולאות ונתיב בודד בין כל שתי נקודות). זה פשוט, יעיל ומייצר מבוכים מושכים ויזואלית עם מסדרונות ארוכים ומפותלים.
למרות שמו, זה לא בהכרח חייב להיות מיושם באמצעות רקורסיה. לרוב הוא מיושם בגישה איטרטיבית באמצעות תור LIFO (כלומר מחסנית). עבור מבוכים גדולים מאוד, סביר יותר ששימוש ברקורסיה יגרום להצפת מחסנית שיחות, בהתאם לשפת התכנות ולזיכרון הזמין. תור LIFO יכול להיות מותאם ביתר קלות לטיפול בכמויות גדולות של נתונים, אפילו לשמור את התור בדיסק או במסד נתונים אם הזיכרון הפנוי אינו מספיק.
איך זה עובד
האלגוריתם פועל באמצעות גישת חיפוש עומק-ראשון מבוסס מחסנית. להלן הפירוט שלב אחר שלב:
- בחר תא התחלה וסמן אותו כביקור.
- בעוד שיש תאים שלא ביקרו:
- תראו את התאים השכנים שטרם ביקרו.
- אם קיים לפחות שכן אחד שלא ביקר:
- בחר באקראי אחד מהשכנים שלא ביקרו.
- הסר את הקיר בין התא הנוכחי לשכן הנבחר.
- עברו לשכן הנבחר וסמנו אותו כמבקר.
- דחוף את התא הנוכחי אל הערימה.
- אם אין שכנים שלא ביקרו:
- חזור על ידי הוצאת התא האחרון מהערימה.
- המשך בתהליך זה עד שהערימה תתרוקן.
עובדה מעניינת לגבי האלגוריתם הזה היא שהוא עובד גם כמחולל מבוך וגם כפותר מבוך. אם תפעיל אותו על מבוך שכבר נוצר ופשוט תעצור כשתגיע לנקודת הסיום שהוחלט, הערימה תכיל את הפתרון למבוך.
למעשה, יש לי שתי גרסאות של האלגוריתם הזה במשחק באתר הזה: תור מבוסס LIFO ליצירת מבוכים בעמוד זה ורקורסיה לפתרון מבוכים, גם מבוכים שנוצרו על ידי אלגוריתמים אחרים (ככה נוצרות המפות עם הפתרונות). שתי גרסאות שונות מיועדות רק לספורט כי אני חנון שזה מעניין אותי, כל אחד יכול היה לעבוד עבור שתיהן ;-)