מחולל מבוך גידול אלגוריתם עצים

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

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

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

על אלגוריתם העץ הגדל

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

איך עובד אלגוריתם העץ הגדל

שלב 1: אתחול

• התחל עם רשת של תאים שלא ביקרו.
• בחר תא התחלה אקראי והוסף אותו לרשימה.

שלב 2: לולאת דור המבוך

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

שלב 3: סיום

• האלגוריתם מסתיים כאשר אין יותר תאים ברשימה, כלומר המבוך כולו נחצב.

אסטרטגיות לבחירת תאים (גמישות האלגוריתם)

התכונה המגדירה של אלגוריתם העץ הגדל היא איך אתה בוחר איזה תא לעבד הבא. בחירה זו משפיעה באופן דרמטי על מראה המבוך:

התא החדש ביותר (התנהגות דמוית מחסנית) - Backtracker רקורסיבי:

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

תא אקראי (אלגוריתם של Prim אקראי):

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

התא העתיק ביותר (התנהגות דמוית תור):

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

גישות היברידיות:

שלב אסטרטגיות למאפייני מבוך מגוונים. לְדוּגמָה:

• 90% הכי חדש, 10% אקראי: נראה בעיקר כמו מבוך חוזר רקורסיבי, אבל עם ענפים מזדמנים שמפרקים מסדרונות ארוכים.
• 50% הכי חדש, 50% הכי ותיק: מאזן מסדרונות ארוכים עם צמיחה עבותה.