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

לפני שנתחיל, פריט טריוויה קטן: המשחק Elite פותח על ידי שני מתכנתים עצמאיים, דיוויד בראבן ואיאן בל, והופץ על ידי חברת Acornsoft, שהיתה למעשה חטיבת התוכנה של חברת Acorn Computers – שהפכה לאחר מכן לחברת ARM Holdings, שמפתחת כיום מיקרו-בקרים פופולריים להפליא.

עולמות אקראיים

במשחק Elite, שפותח במקור עבור מחשבי BBC Micro, השחקן הטיס חללית (בתלת מימד!), נלחם בחלליות אחרות, עבר בין כוכבים שונים וגם קנה ומכר סחורות. יקום המשחק כלל שמונה "גלקסיות" עם 256 כוכבים בכל אחת. לכל כוכב היה מיקום קבוע במרחב, שם, תיאור קצר ועוד מספר פרמטרים. כמות המידע הזו נראית בלתי אפשרית, בהתחשב בזה שהמשחק כולו – כולל גם המנוע הגרפי, דגמי החלליות, ניהול המלאי וכו' – נכנס ב-32 קילובייטים בלבד של זיכרון RAM שהיה זמין בדגם BBC Mirco הנפוץ. איך בראבן ובל עשו זאת?

לפני שנתיים וחצי לערך העליתי פוסט על אופטימיזציה, שבו הראיתי (בין השאר) איך יצרתי רקע על מסך Nokia 5110 באמצעות הפקה בזמן אמת של שרשרת מספרים פסודו-אקראיים, במקום לשמור את כל המידע בזיכרון. ציינתי שם שהפקת המספרים הזו איטית – וזה עוד במיקרו-בקר מהיר פי שמונה מהמעבד של ה-BBC Micro! אך מסתבר שיש דרכים נוספות להשיג תוצאות כאילו-אקראיות, וחישוב פשוט שכזה יצר את כל היקום של Elite.

חישוב פשוט

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

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

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

0 = סנ, 1 = גה, 2 =קי, 3 = מו, 4 = אמ, 5 = הט, 6 = ש_ …

כעת, מתוך 48 הביטים של הכוכב, ניקח את הביטים 5-8 (ארבעה ביטים, כלומר 16 אפשרויות) ואת הביטים 30-33, ונשלוף מהרשימה את ההברות המתאימות. למשל, אם קיבלנו את הביטים 0101 ו-0000, שם הכוכב שלנו יהיה "הטסן", ואם קיבלנו 0001 ו-0110, שמו יהיה "גהש". הנה הרשימה השלמה של שמות ותיאורי הכוכבים במשחק המקורי – האם אתם יכולים לזהות את הדפוסים בה?

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

מהירות

עד כמה החישוב דמוי-פיבונאצ'י מהיר יותר משימוש בפונקציה "תקנית" של הפקת מספרים פסודו-אקראיים? נמדוד בעזרת לוח ארדואינו:

void setup() {
  Serial.begin(9600);
}

void loop() {

  volatile uint16_t i, f[3] = {0, 4731, 96402};
  uint32_t start, diff;

  start = millis();
  for (int n = 0; n < 10000; ++n)
    i = random(65536);
  diff = millis() - start;
  Serial.print("10K Random numbers: ");
  Serial.print(diff);
  Serial.println("ms");

  start = millis();
  for (int n = 0; n < 10000; ++n) {
    f[0] = f[1];
    f[1] = f[2];
    f[2] = f[0] + f[1];
  }  
  diff = millis() - start;
  Serial.print("10K 16-bit fibonacci numbers: ");
  Serial.print(diff);
  Serial.println("ms");

  while (1);

}

והתוצאה: 945 אלפיות השניה במקרה הראשון (עם פונקציית random), לעומת 22 אלפיות השניה במקרה השני.

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

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

טכניקת ההפקה הפרוצדורלית משמשת, בווריאציות וברמות תחכום שונות, בהמון תוכנות ומשחקי מחשב מודרניים – כולל הגלגול האחרון של Elite, משחק בשם Elite Dangerous שפותח במימון המונים והושלם בסוף 2014.