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

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

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

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

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

1. חייבת להיות אפשרות לשמור את מצב המשחק הנוכחי במלואו לקובץ, וכמובן לטעון אותו בחזרה.

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

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

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

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

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

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

*** זהירות ספוילרים – אם אתם עדיין רוצים לפתור את החידה לבד, עיצרו כאן! ***

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

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

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

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