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

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

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

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

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

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

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

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

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

• מצא תא אקראי ברשת וסמן אותו כמבקר.

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

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

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

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