מצוד והרוג מחולל מבוך

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

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

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

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

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

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

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

שלב 1: התחל מתא אקראי

• מצא תא אקראי ברשת וסמן אותו כ"נצפה".

שלב 2: שלב ההליכה (הליכה אקראית)

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

שלב 3: שלב הציד (חזרה לאחור באמצעות סריקה)

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

קריאה נוספת

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

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