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

הרקע הצבעוני

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

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

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

מתחת לאף

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

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

בואו נראה

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

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

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

המשך יבוא…