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

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

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

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

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

האלגוריתם של אלר הוצג על ידי דיוויד אלר.

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

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

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

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

שלב 1: אתחול השורה הראשונה

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

שלב 2: חבר כמה תאים סמוכים בצורה אופקית

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

שלב 3: צור חיבורים אנכיים לשורה הבאה

• עבור כל קבוצה שמופיעה בשורה, לפחות תא אחד חייב להתחבר כלפי מטה (כדי להבטיח קישוריות).
• בחר באקראי תא אחד או יותר מכל סט כדי להתחבר לשורה הבאה.

שלב 4: עבור לשורה הבאה

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

שלב 5: חזור על שלבים 2-4 עד שתגיע השורה האחרונה

• המשך בעיבוד שורה אחר שורה.

שלב 6: עבד את השורה האחרונה

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