ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
במרחק נגיעה 
 
 איך מגלים שזה קורה? פקמן ובלינקי נפגשים   
לפרק את הבייט |
 

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

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

פתרונות חד-ממדיים

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

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

פיתוחים וקירובים

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

טכניקות מתקדמות

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

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

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

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