כיצד ליצור AI למשחקים: מדריך למתחילים

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

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

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

מה זה AI?

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

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

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

משחקים אינם זקוקים למערכת מורכבת כדי לחלץ מידע שכן רוב הנתונים הם כבר חלק בלתי נפרד ממנו. אין צורך להפעיל אלגוריתמים של זיהוי תמונות כדי לקבוע אם יש אויב לפנינו - המשחק כבר יודע ומזין את המידע ישירות לתהליך קבלת ההחלטות. לכן, החלק של ה-Sense של המחזור הוא לרוב הרבה יותר פשוט מהחלק של Think and Act.

מגבלות של משחק AI

ל-AI יש מספר מגבלות שיש להקפיד עליהן:

• AI לא צריך לעבור הכשרה מראש, כאילו זה היה אלגוריתם למידת מכונה. זה לא הגיוני לכתוב רשת עצבית במהלך הפיתוח כדי לנטר עשרות אלפי שחקנים וללמוד את הדרך הטובה ביותר לשחק נגדם. למה? כי המשחק לא יצא ואין שחקנים.
• המשחק צריך להיות מהנה ומאתגר, כך שסוכנים לא צריכים למצוא את הגישה הטובה ביותר נגד אנשים.
• סוכנים צריכים להיראות מציאותיים כדי ששחקנים ירגישו שהם משחקים נגד אנשים אמיתיים. תוכנית AlphaGo גברה על בני אדם, אבל הצעדים שנבחרו היו רחוקים מאוד מההבנה המסורתית של המשחק. אם המשחק מדמה יריב אנושי, התחושה הזו לא צריכה להתקיים. יש לשנות את האלגוריתם כך שיקבל החלטות סבירות ולא אידיאליות.
• AI חייב לעבוד בזמן אמת. משמעות הדבר היא שהאלגוריתם אינו יכול לעשות מונופול על השימוש במעבד לפרקי זמן ארוכים כדי לקבל החלטות. אפילו 10 מילישניות זה יותר מדי זמן, מכיוון שרוב המשחקים צריכים רק 16 עד 33 מילישניות כדי לבצע את כל העיבוד ולעבור למסגרת הגרפית הבאה.
• באופן אידיאלי, לפחות חלק מהמערכת צריך להיות מונע נתונים, כך שמקודדים לא יוכלו לבצע שינויים והתאמות יכולות לקרות מהר יותר.

בואו נסתכל על גישות בינה מלאכותית המכסות את כל מחזור החוש/חשיבה/פעולה.

קבלת החלטות בסיסיות

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

הצהרות על תנאי

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

אלגוריתם פשוט לכך, כתוב בפסאודוקוד:

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

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

גישה זו כל כך פשוטה שכל מחזור החוש/חשיבה/פעולה בקושי מורגש. אבל זה שם:

• החלק Sense הוא בשתי הצהרות אם. המשחק יודע היכן נמצא הכדור ואיפה הפלטפורמה, כך שה-AI מחפש את המידע הזה.
• החלק Think כלול גם בשתי הצהרות אם. הם מגלמים שני פתרונות, שבמקרה זה סותרים זה את זה. כתוצאה מכך, נבחרה אחת משלוש פעולות - הזז את הפלטפורמה שמאלה, הזז אותה ימינה, או אל תעשה דבר אם הוא כבר ממוקם נכון.
• החלק של האקט נמצא בהצהרות Move Paddle Left ו-Move Paddle Right. בהתאם לעיצוב המשחק, הם יכולים להזיז את הפלטפורמה באופן מיידי או במהירות מסוימת.

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

עץ החלטות

הדוגמה של הפונג מקבילה למעשה למושג AI פורמלי הנקרא עץ החלטות. האלגוריתם עובר דרכו כדי להגיע ל"עלה" - החלטה באיזו פעולה לנקוט.

בואו נעשה דיאגרמת בלוקים של עץ ההחלטות עבור האלגוריתם של הפלטפורמה שלנו:

כל חלק בעץ נקרא צומת - בינה מלאכותית משתמשת בתורת הגרפים כדי לתאר מבנים כאלה. ישנם שני סוגים של צמתים:

• צמתי החלטה: בחירה בין שתי חלופות על סמך בדיקת מצב כלשהו, ​​כאשר כל חלופה מיוצגת כצומת נפרד.
• צמתי סוף: הפעולה שיש לבצע המייצגת את ההחלטה הסופית.

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

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

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

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

תרחישים

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

כדי שהמתכנת לא יצטרך לכתוב קוד עבור התנאים Is Ball Left Of Paddle ו-Is Ball Right Of Paddle, הוא יכול ליצור מערכת שבה המעצב יכתוב תנאים לבדיקת ערכים אלו. אז נתוני עץ ההחלטות ייראו כך:

זה בעצם אותו דבר כמו בטבלה הראשונה, אבל לפתרונות בתוך עצמם יש קוד משלהם, קצת כמו החלק המותנה של הצהרת if. בצד הקוד, זה ייקרא בעמודה השנייה עבור צמתי ההחלטה, אבל במקום לחפש תנאי ספציפי לביצוע (Is Ball Left Of Paddle), הוא מעריך את הביטוי המותנה ומחזיר נכון או לא נכון בהתאם. זה נעשה באמצעות שפת הסקריפט Lua או Angelscript. באמצעותם, מפתח יכול לקחת אובייקטים במשחק שלו (כדור ומשוט) וליצור משתנים שיהיו זמינים בסקריפט (ball.position). כמו כן, שפת הסקריפט פשוטה יותר מ-C++. זה לא דורש שלב קומפילציה מלא, ולכן הוא אידיאלי להתאמה מהירה של היגיון המשחק ומאפשר ל"לא-קודנים" ליצור את הפונקציות הדרושות בעצמם.

בדוגמה שלמעלה, שפת הסקריפט משמשת רק כדי להעריך את הביטוי המותנה, אך ניתן להשתמש בה גם עבור פעולות. לדוגמה, הנתונים Move Paddle Right יכולים להפוך להצהרת script (ball.position.x += 10). כך שהפעולה מוגדרת גם בסקריפט, ללא צורך בתכנת Move Paddle Right.

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

תגובה לאירוע

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

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

זה מחזיר אותנו למחזור החוש/חשיבה/פעולה. אנחנו יכולים לקודד קטע Sense שיבדוק כל פריים אם ה-AI רואה את הנגן. אם לא, שום דבר לא קורה, אבל אם הוא רואה, אז נוצר אירוע Player Seen. לקוד יהיה קטע נפרד שאומר "כאשר מתרחש אירוע השחקן שנראה, עשה" איפה התגובה שאתה צריך כדי להתייחס לחלקים של Think ו-Action. לפיכך, תגדיר תגובות לאירוע Player Seen: עבור הדמות "המהרה" - ChargeAndAttack, ולצלף - HideAndSnipe. ניתן ליצור קשרים אלה בקובץ הנתונים לעריכה מהירה ללא צורך בהידור מחדש. ניתן להשתמש בשפת סקריפטים גם כאן.

קבלת החלטות קשות

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

מכונת מדינה סופית

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

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

• מפטרלים.
• תוקף.
• בורחים.

ותנאים אלה לשינוי מצבו:

• אם השומר רואה את האויב, הוא תוקף.
• אם השומר תוקף אך אינו רואה יותר את האויב, הוא חוזר לפטרול.
• אם שומר תוקף אך נפצע קשה, הוא בורח.

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

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

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

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

זוהי טבלת מעבר מצב - דרך מקיפה לייצוג FSM. בואו נצייר תרשים ונקבל סקירה מלאה של האופן שבו התנהגות NPC משתנה.

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

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

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

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

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

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

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

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

שינויים חשובים במצב העולם יכולים להיחשב כאירועים שיעובדו עם התרחשותם. במקום שה-FSM יבדוק את תנאי המעבר "האם הסוכן שלי יכול לראות את השחקן?" בכל פריים, ניתן להגדיר מערכת נפרדת לבדוק בתדירות נמוכה יותר (למשל 5 פעמים בשנייה). והתוצאה היא הנפקת Player Seen כשהצ'ק עובר.

זה מועבר ל-FSM, אשר אמור כעת לעבור למצב ה-Player Seen Event שהתקבל ולהגיב בהתאם. ההתנהגות המתקבלת זהה למעט עיכוב כמעט בלתי מורגש לפני התגובה. אבל הביצועים השתפרו כתוצאה מהפרדת החלק Sense לחלק נפרד של התוכנית.

מכונת מצבים סופיים היררכית

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

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

מדינות עיקריות:


מצב מחוץ לקרב:


ובצורת דיאגרמה:

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

עץ התנהגות

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

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

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

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

ניתן לשלב קבוצה קטנה זו של צמתים כדי ליצור מספר רב של התנהגויות מורכבות. בואו נדמיין את שומר HFSM מהדוגמה הקודמת כעץ התנהגות:

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

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

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

מערכת מבוססת שירות

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

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

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

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

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

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

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

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

תנועה וניווט

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

Управление

בשלב הראשוני נניח שלכל סוכן יש ערך מהירות הכולל כמה מהר הוא נע ובאיזה כיוון. ניתן למדוד אותו במטרים לשנייה, קילומטרים לשעה, פיקסלים לשנייה וכו'. כשנזכרים בלולאת Sense/Think/Act, אנו יכולים לדמיין שהחלק Think בוחר מהירות, וחלק ה-Act מחיל את המהירות הזו על הסוכן. בדרך כלל למשחקים יש מערכת פיזיקה שמבצעת את המשימה הזו עבורך, לומדת את ערך המהירות של כל אובייקט ומתאימה אותו. לכן, אתה יכול להשאיר את ה-AI עם משימה אחת - להחליט איזו מהירות צריכה להיות לסוכן. אם אתה יודע היכן הסוכן צריך להיות, אז אתה צריך להזיז אותו בכיוון הנכון במהירות מוגדרת. משוואה מאוד טריוויאלית:

מבוקש_נסיעה = מיקום_יעד – מיקום_סוכן

דמיינו עולם דו מימדי. הסוכן נמצא בנקודה (-2,-2), היעד נמצא אי שם בצפון מזרח בנקודה (2, 30), והנתיב הנדרש לסוכן להגיע לשם הוא (20, 32). נניח שהמצבים הללו נמדדים במטרים - אם ניקח את מהירות הסוכן ל-22 מטר לשנייה, אז נקנה קנה מידה של וקטור התזוזה שלנו ונקבל מהירות של בקירוב (5, 4.12). עם הפרמטרים הללו, הסוכן יגיע ליעדו תוך כמעט 2.83 שניות.

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

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

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

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

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

למצוא את הדרך

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

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

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

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

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

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

תנועה ללא רשת

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

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

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

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

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

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

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

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

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

תִכנוּן

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

בואו נסתכל על הדוגמה של משחק הלוח Magic: The Gathering. אנחנו הולכים ראשונים עם קבוצת הקלפים הבאה בידינו:

• ביצה - נותן 1 מאנה שחור (כרטיס יבשתי).
• יער - נותן 1 מאנה ירוק (כרטיס אדמה).
• אשף נמלט - דורש מאנה כחולה אחת כדי לזמן.
• Elvish Mystic - דורש מאנה ירוקה אחת כדי לזמן.

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

תכנון קל

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

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

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

1. שחקו בביצה (תוצאה: ביצה במשחק)
2. שחק ביער (תוצאה: יער במשחק)

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

1. שחקו בביצה (תוצאה: ביצה במשחק)
1.1 ביצה "הקש" (תוצאה: ביצה "מוקפת", +1 יחידה של מאנה שחורה)
אין פעולות זמינות - END
2. שחק ביער (תוצאה: יער במשחק)

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

1. שחקו בביצה (תוצאה: ביצה במשחק)
1.1 ביצה "הקש" (תוצאה: ביצה "מוקפת", +1 יחידה של מאנה שחורה)
אין פעולות זמינות - END
2. שחק ביער (תוצאה: יער במשחק)
2.1 יער "הקש" (תוצאה: היער "נקש", +1 יחידה של מאנה ירוקה)
2.1.1 לזמן Elvish Mystic (תוצאה: Elvish Mystic במשחק, -1 מאנה ירוקה)
אין פעולות זמינות - END

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

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

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

תכנון משופר

לפעמים יש יותר מדי פעולות פוטנציאליות מכדי לשקול כל אפשרות אפשרית. נחזור לדוגמה עם Magic: The Gathering: נניח שבמשחק וביד שלך יש כמה קלפי אדמה ויצורים - מספר השילובים האפשריים של מהלכים יכול להיות בעשרות. ישנם מספר פתרונות לבעיה.

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

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

1. נזק יכול להיגרם מכישוף - הוא חייב להיות ביד.
2. כדי להטיל כישוף, אתה צריך מאנה.
3. כדי לקבל מאנה, אתה צריך לשחק קלף ארץ.
4. כדי לשחק קלף קרקע, אתה צריך להחזיק אותו ביד.

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

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

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

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

אימון והתאמה

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

סטטיסטיקה והסתברויות

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

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

גישה דומה משמשת כאשר מעריכים את הסבירות לפעולות מסוימות על ידי הנחה שהעדפות העבר של השחקן יהיו זהות בעתיד. אם שחקן תוקף אותנו חמש פעמים עם כדור אש, פעמיים עם ברק ופעם אחת בתגרה, ברור שהוא מעדיף כדור אש. הבה נקסטרפול ונראה את ההסתברות לשימוש בכלי נשק שונים: כדור אש=62,5%, ברק=25% ותגרה=12,5%. AI המשחק שלנו צריך להתכונן כדי להגן על עצמו מפני אש.

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

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

התאמה מבוססת ערך

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

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

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

דגם מרקוב

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

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

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

ניתן לראות שהחדר הירוק מתאים לשחקנים - רוב האנשים עוברים מהחדר האדום אליו, 50% מהם נשארים שם יותר. החדר הכחול, להיפך, אינו פופולרי; כמעט אף אחד לא הולך אליו, ואם כן, הם לא נשארים זמן רב.

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

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

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

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

זה מראה שהסיכוי לראות את השחקן בחדר הירוק לאחר שתי תצפיות יהיה שווה ל-51% - 21% שהוא יהיה מהחדר האדום, 5% מהם שהשחקן יבקר בחדר הכחול שביניהם, וכן 25% שהשחקן לא יעזוב את החדר הירוק.

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

N-גרם

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

אחת הדרכים לעשות זאת היא לאחסן כל קלט (כגון Kick, Punch או Block) במאגר ולכתוב את כל המאגר כאירוע. אז השחקן לוחץ שוב ושוב על Kick, Kick, Punch כדי להשתמש בהתקפת SuperDeathFist, מערכת הבינה המלאכותית מאחסנת את כל התשומות במאגר וזוכרת את שלושת האחרונים ששימשו בכל שלב.

(השורות המודגשות הן כאשר השחקן משיק את התקפת SuperDeathFist.)

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

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

המעצב צריך לבחור את הגודל של N-גרם בקפידה. N קטן יותר דורש פחות זיכרון אבל גם מאחסן פחות היסטוריה. לדוגמה, 2 גרם (ביגרם) יקליט Kick, Kick או Kick, Punch, אך לא יוכל לאחסן Kick, Kick, Punch, כך שה-AI לא יגיב לשילוב של SuperDeathFist.

מצד שני, מספרים גדולים יותר דורשים יותר זיכרון וה-AI יהיה קשה יותר לאימון מכיוון שיהיו הרבה יותר אפשרויות אפשריות. אם היו לך שלוש כניסות אפשריות של Kick, Punch או Block, והיינו משתמשים ב-10 גרם, זה יהיה בערך 60 אלף אפשרויות שונות.

מודל הביגרמה הוא שרשרת מרקוב פשוטה - כל זוג מצב עבר/מצב נוכחי הוא ביגרם, וניתן לחזות את המצב השני על סמך הראשון. אפשר לחשוב על ה-N-גרם של 3 גרם ומעלה כשרשראות מרקוב, כאשר כל היסודות (למעט האחרון ב-N-גרם) יוצרים יחד את המצב הראשון והיסוד האחרון את השני. דוגמה למשחק הלחימה מראה את הסיכוי לעבור ממצב Kick and Kick למצב Kick and Punch. על ידי התייחסות לערכים מרובים של היסטוריית קלט כיחידה אחת, אנו בעצם הופכים את רצף הקלט לחלק מהמצב כולו. זה נותן לנו את המאפיין של Markov, המאפשר לנו להשתמש בשרשראות Markov כדי לחזות את הקלט הבא ולנחש איזה מהלך משולב יהיה הבא.

מסקנה

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

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

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

משאבי אינטרנט בנושא:

1. ל-GameDev.net יש מדור עם מאמרים ומדריכים על AIו - форум.
2. AiGameDev.com מכיל מצגות ומאמרים רבים במגוון רחב של נושאים הקשורים לפיתוח AI במשחק.
3. הכספת של GDC כולל נושאים מ-GDC AI Summit, שרבים מהם זמינים בחינם.
4. ניתן למצוא באתר גם חומרים שימושיים גילדת מתכנתי משחקי AI.
5. טומי תומפסון, חוקר בינה מלאכותית ומפתח משחקים, עושה סרטונים ביוטיוב AI ומשחקים עם הסבר ולימוד של AI במשחקים מסחריים.

ספרים בנושא:

1. סדרת ספרי Game AI Pro היא אוסף של מאמרים קצרים המסבירים כיצד ליישם תכונות ספציפיות או כיצד לפתור בעיות ספציפיות.

Game AI Pro: Collected Wisdom of Game AI Professionals
Game AI Pro 2: Collected Wisdom of Game AI Professionals
Game AI Pro 3: Collected Wisdom of Game AI Professionals

2. סדרת AI Game Programming Wisdom היא קודמתה של סדרת Game AI Pro. הוא מכיל שיטות ישנות יותר, אבל כמעט כולן רלוונטיות גם היום.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

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

מקור: www.habr.com