לברוא את העולם ב-C#

היי,

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

מה שמיוחד במשחק הזה הוא שהדגש לא על הגרפיקה אלא על המשחקיות.

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

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

בפוסט זה אסביר על יצירת האדמה וקצת מעבר.

MineCraft

הכלי שנראה לי הכי מתאים לפרוייקט הוא XNA, ממספר סיבות:

השפה האהובה עלי היא C#.
אני מכיר את אופן העבודה עם XNA ויש לי ניסיון עם סביבת העבודה הזאת (בדו מימד בעיקר).
XNA נותן גישה ישירה לורטקסים (vertices) שירונדרו. כלומר אני אוכל לשלוט על כל נקודה ונקודה בעולם התלת מימדי באופן ישיר.

לאחר שהחלטתי על XNA גיליתי שאני צריך לרענן את הידע שלי בעבודה עם 3D, לשם כך נעזרתי בסדרת מדריכים שאני ממליץ עליה מאוד:
http://www.riemers.net/
(בצד ימין למטה תוכלו לראות את רשימת המדריכים, 3D series 1 ו-3D series 2 ילמדו את הידע הבסיסי הנדרש בעבודה ב-3D עם XNA).

לאחר שרעננתי את הידע שלי הייתי צריך למצוא דרך ליצור קוביות.

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

לכן הייתי צריך למצוא דרך לכתוב למערך את הורטקסים של הקוביה.

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

הקוד

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

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

התחלתי בניסיונות:

ניסיון 1:

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

הקוד:
לינק

מה הקוד בעצם עושה?
קודם כל הוא יוצר שורה בציר ה-Z, את גובה הנקודה הראשונה בשורה (0, 0) הוא מגריל, לאחר מכן כל גובה תלוי בגובה שלפניו ונוסף אליו מספר רנדומלי (0, 1, 1-).
לאחר מכן הקוד יוצר שורה בציר ה-X, שנוצרת באותה דרך כמו השורה הקודמת.

על מנת להמחיש את כל התהליך הכנתי אנימציה:

המשבצות האדומות הן השורות הראשונות בציר ה-Z וציר ה-X.
לאחר מכן מתחיל תהליך בו כל משבצת צהובה נוצרת על סמך ממוצע הגבהים בין כל 2 משבצות בצבע תכלת.

התוצאה:


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

התוצאה נחמדה ביותר, יש בעיה עם יצירת מישורים אבל ההרים נראים מצויין.
בעיה די מציקה עם האלגוריתם היא שהוא נוטה להנמיך את המפה ככל שמתרחקים מנק' ההתחלה.
כלומר אם בנקודה (0, 0) היה גובה של 10 קוביות, בנקודה (30, 30) בדרך כלל יהיה גובה של 2 קוביות ומטה.

הבעיות האלה די הפריעו ולכן ניסיתי לחשוב על פתרון אחר.

ניסיון 2:

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

הקוד:
לינק

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

התוצאה:


ניסיון 2. עובד טוב לרוחב אבל לא לאורך

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

עברתי לניסיון הבא.

ניסיון 3:

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

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

אז איך ממשים את זה? בעזרת תור!

האלגוריתם מתחיל כך שנבחר גובה רנדומלי בסיסי שישמש אותנו בהמשך.

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

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

מהאלגוריתם הזה יכולות לצאת מגוון מפות הרריות ומישוריות.

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

והתוצאה: