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

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

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

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

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

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

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

שלב 1: אתחול

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

שלב 2: לולאת יצירת מבוך

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

שלב 3: סיום

• האלגוריתם מסתיים כאשר אין עוד תאים ברשימה, כלומר כל המבוך גולף.

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

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

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

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

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

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

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

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

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

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

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

קריאה נוספת

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

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