סיפורי אופטימיזציה: אקראיות זולה

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

צילום מסך מתוך Yar's Revenge, באמולטור Atari 2600 ל-PC
צילום מסך מתוך Yar's Revenge, באמולטור Atari 2600 ל-PC

הרקע הצבעוני

המשחק Yar's Revenge הופיע בשנת 1981*, והיה אחד הלהיטים הגדולים ביותר של קונסולת המשחקים Atari 2600 המיתולוגית. החומרה באותם ימים היתה מוגבלת במידה שנראית לנו כיום בלתי נתפסת כמעט, אך המשחק הזה סחט ממנה ביצועים מרשימים עד כדי כך, שעדיין אפשר ליהנות ממנו (אפרופו, לצורך התנסות ולצילומי המסך השתמשתי באמולטור Stella).

* יש מקורות שטוענים שהמשחק הופיע דווקא ב-1982, אבל הם טועים 🙂

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

הפיצוץ שנגרם מהשמדת הקוטייל (Qotile)
הפיצוץ שנגרם מהשמדת הקוטייל (Qotile)

מתחת לאף

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

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

בואו נראה

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

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

לצורך הבדיקה המעשית העליתי מן האוב את תוכנית המלבנים המעופפים שכתבתי ל-MSP430G2 Launchpad ולמסך Nokia 5110 (קישור בתחילת הפוסט), ושלדברי סביבת הפיתוח Energia מתקמפלת לאוסף פקודות מכונה בגודל 1,739 בייטים. לרוע המזל, אין לנו גישה ישירה וקלה לאוסף הזה. בדומה לארדואינו, רצף הבייטים שמיועד לצריבה על המיקרו-בקר נשמר בקובץ HEX, שבנוי בעצמו לפי פורמט שדורש פיענוח. כמו יאר, ה"זבוב" גיבור המשחק, גם אנחנו נצטרך לפרוץ את מעטפת השריון אשר כלי הפיתוח המודרניים הציבו בפנינו כדי לפתור את החידה!

המשך יבוא…

להרשמה
הודע לי על
5 תגובות
מהכי חדשה
מהכי ישנה לפי הצבעות
Inline Feedbacks
הראה את כל התגובות

לא קשור ישירות, אבל זה מזכיר לי פוסט אחר שראיתי עכשיו –
http://trixter.oldskool.org/2015/04/07/8088-mph-we-break-all-your-emulators/

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

מרתק.
דומני שביצעו משהוא דומה(להשתמש בשורות הקוד עצמן כנתונים) באחת מהתחרויות של http://www.ioccc.org. אם אני לא טועה התוכנה הייתה צריכה לעשות hello word בדרך הזאת.
ואם אתה כבר שם, ממליץ לך ללכת לתחרות של 1990 ולפתוח את הקובץ שנקרא westley.c.
זה קוד שבנוי בצורת מחזה תוך כדי שימוש במילות מפתח שמשעשע לקרוא. השמועה אומרת שזה אפילו אמור להתקמפל ואשכרה לעשות משהוא.

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

תודה רבה