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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קריאה נוספת

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

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