ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
מבוך אוטומטי 
 
 מבוך בצורת שער בחומה הסינית (איור ממוחשב באדיבות Jie Xu & Craig S. Kaplan)   
לפרק את הבייט |
 

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

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

איך בונים מבוך?

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

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

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

אלגוריתמים לבניית מבוכים

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

1. בחר באופן אקראי אחד מתאי הצומת (בשלב הראשון יש רק אחד, כאמור)
2. בחר קיר אקראי X של תא הצומת
3. אם התא שמאחורי קיר X כולל ארבעה קירות שלמים, שבור את הקיר X והוסף את התא שמאחוריו לרשימת תאי הצומת
4. אם יש תא צומת שלא נותרו בו קירות שאפשר לשבור, הוצא אותו מרשימת תאי הצומת
5. אם נותרו תאי צומת, חזור לשלב 1

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

מבוכים אומנותיים

מבוך יוצר דיאגרמת וורונוי (צילומסך: עידו גנדל)
 מבוך יוצר דיאגרמת וורונוי (צילומסך: עידו גנדל)   
במבוך שבתמונה משמאל, הצמיחה האקראית יצרה שטחים מוגדרים. פרופסור קרייג קפלן מאוניברסיטת ווטרלו שבאונטריו, קנדה, ותלמידו ג'וּ ג'י ביצעו תהליך הפוך: הם חילקו תמונות מצולמות לשטחים מוגדרים והפכו כל שטח כזה למבוך. בעזרת התאמות שונות ומורכבות של הפרמטרים של המבוכים הללו (צפיפות, אוריינטציה, עובי קירות, פרספקטיבה וכו'), שאת רובן המחשב יודע לבצע באופן אוטומטי, ג'י וקפלן הצליחו ליצור מבוכים שמשקפים במידה טובה את הטקסטורה והגוון של השטחים בתמונה המקורית. לאחר פתיחה של נתיב אחד שמקשר בין כל השטחים השונים, התוצאה הסופית של התהליך היא מבוך אחד גדול ואומנותי שנראה ממש כמו התמונה המקורית – בדומה למבוך החומה הסינית לעיל או למבוך השבלולים שבהמשך. את המאמר המקורי של ג'י וקפלן אפשר להוריד כאן.
 
לכמות מטורפת של מידע על מבוכים, כולל אלגוריתמים, תוכנות, פרטי טריוויה ומה לא, בקרו באתר Think Labyrinth של וולטר פולן.
 
מבוך מתמונה של שבלולים (איור ממוחשב באדיבות Jie Xu & Craig S. Kaplan)
 מבוך מתמונה של שבלולים (איור ממוחשב באדיבות Jie Xu & Craig S. Kaplan) 
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by