ฉันเจอเนื้อหาที่น่าสนใจเกี่ยวกับปัญญาประดิษฐ์ในเกม ด้วยการอธิบายสิ่งพื้นฐานเกี่ยวกับ AI โดยใช้ตัวอย่างง่ายๆ และภายในมีเครื่องมือและวิธีการที่มีประโยชน์มากมายสำหรับการพัฒนาและออกแบบที่สะดวก จะใช้อย่างไรที่ไหนและเมื่อไหร่
ตัวอย่างส่วนใหญ่เขียนด้วยรหัสเทียม ดังนั้นจึงไม่จำเป็นต้องมีความรู้ด้านการเขียนโปรแกรมขั้นสูง ภายใต้การตัดจะมีข้อความ 35 แผ่นพร้อมรูปภาพและ GIF ดังนั้นเตรียมตัวให้พร้อม
รปภ. ฉันขอโทษ แต่ฉันได้แปลบทความเกี่ยวกับHabréของฉันเองแล้ว . คุณสามารถอ่านเวอร์ชันของเขาได้ แต่ด้วยเหตุผลบางอย่างบทความจึงส่งผ่านฉันไป (ฉันใช้การค้นหา แต่มีบางอย่างผิดพลาด) และเนื่องจากฉันกำลังเขียนบล็อกเกี่ยวกับการพัฒนาเกมโดยเฉพาะ ฉันจึงตัดสินใจทิ้งการแปลเวอร์ชันของฉันไว้สำหรับสมาชิก (บางจุดมีรูปแบบที่แตกต่างกัน บางจุดจงใจละเว้นตามคำแนะนำของนักพัฒนา)
เอไอคืออะไร?
เกม AI มุ่งเน้นไปที่การกระทำที่วัตถุควรทำตามเงื่อนไขที่วัตถุนั้นตั้งอยู่ โดยทั่วไปเรียกว่าการจัดการ "ตัวแทนอัจฉริยะ" โดยที่ตัวแทนคือตัวละครของผู้เล่น ยานพาหนะ บอท หรือบางครั้งก็เป็นนามธรรมมากกว่านั้น: กลุ่มเอนทิตีทั้งหมด หรือแม้แต่อารยธรรม ในแต่ละกรณีเป็นสิ่งที่ต้องดูสภาพแวดล้อม ตัดสินใจโดยอิงจากสิ่งแวดล้อม และปฏิบัติตามสภาพแวดล้อมนั้น สิ่งนี้เรียกว่าวงจรความรู้สึก/คิด/กระทำ:
- ความรู้สึก: เจ้าหน้าที่ค้นหาหรือรับข้อมูลเกี่ยวกับสิ่งต่างๆ ในสภาพแวดล้อมที่อาจส่งผลต่อพฤติกรรมของตน (ภัยคุกคามในบริเวณใกล้เคียง สิ่งของที่ต้องรวบรวม สถานที่ที่น่าสนใจในการสำรวจ)
- คิด: เจ้าหน้าที่ตัดสินใจว่าจะโต้ตอบอย่างไร (พิจารณาว่าจะปลอดภัยพอที่จะรวบรวมสิ่งของหรือไม่ หรือควรต่อสู้/ซ่อนก่อน)
- พระราชบัญญัติ: ตัวแทนดำเนินการเพื่อดำเนินการตามการตัดสินใจครั้งก่อน (เริ่มเคลื่อนที่ไปหาศัตรูหรือวัตถุ)
- ...ตอนนี้สถานการณ์เปลี่ยนไปเนื่องจากการกระทำของตัวละคร ดังนั้นวงจรจึงเกิดขึ้นซ้ำพร้อมกับข้อมูลใหม่
AI มีแนวโน้มที่จะมุ่งเน้นไปที่ส่วน Sense ของลูป ตัวอย่างเช่น รถยนต์ขับเคลื่อนอัตโนมัติจะถ่ายภาพถนน รวมกับข้อมูลเรดาร์และลิดาร์ แล้วตีความข้อมูลเหล่านั้น โดยทั่วไปจะทำโดยการเรียนรู้ของเครื่อง ซึ่งจะประมวลผลข้อมูลขาเข้าและให้ความหมาย โดยดึงข้อมูลเชิงความหมาย เช่น “มีรถคันอื่นอยู่ข้างหน้าคุณ 20 หลา” สิ่งเหล่านี้เรียกว่าปัญหาการจำแนกประเภท
เกมไม่จำเป็นต้องมีระบบที่ซับซ้อนในการดึงข้อมูล เนื่องจากข้อมูลส่วนใหญ่เป็นส่วนสำคัญของข้อมูลอยู่แล้ว ไม่จำเป็นต้องเรียกใช้อัลกอริธึมการจดจำรูปภาพเพื่อพิจารณาว่ามีศัตรูอยู่ข้างหน้าหรือไม่ เนื่องจากเกมทราบและป้อนข้อมูลโดยตรงเข้าสู่กระบวนการตัดสินใจแล้ว ดังนั้นส่วน Sense ของวงจรมักจะง่ายกว่าส่วน Think and Act มาก
ข้อจำกัดของเกม AI
AI มีข้อจำกัดหลายประการที่ต้องปฏิบัติตาม:
- ไม่จำเป็นต้องฝึกอบรม AI ล่วงหน้า เหมือนกับว่าเป็นอัลกอริธึมการเรียนรู้ของเครื่อง มันไม่สมเหตุสมผลเลยที่จะเขียนโครงข่ายประสาทเทียมระหว่างการพัฒนาเพื่อติดตามผู้เล่นนับหมื่นคนและเรียนรู้วิธีที่ดีที่สุดในการเล่นกับพวกเขา ทำไม เนื่องจากตัวเกมยังไม่ออกและไม่มีผู้เล่น
- เกมควรสนุกและท้าทาย ดังนั้นตัวแทนจึงไม่ควรหาแนวทางที่ดีที่สุดในการต่อสู้กับผู้คน
- เอเจนต์ต้องดูสมจริงเพื่อให้ผู้เล่นรู้สึกเหมือนกำลังเล่นกับคนจริงๆ โปรแกรม AlphaGo มีประสิทธิภาพเหนือกว่ามนุษย์ แต่ขั้นตอนที่เลือกยังห่างไกลจากความเข้าใจแบบดั้งเดิมของเกม หากเกมจำลองฝ่ายตรงข้ามที่เป็นมนุษย์ ความรู้สึกนี้ไม่ควรมีอยู่จริง จำเป็นต้องเปลี่ยนอัลกอริธึมเพื่อให้สามารถตัดสินใจได้น่าเชื่อถือมากกว่าที่จะตัดสินใจในอุดมคติ
- AI ต้องทำงานแบบเรียลไทม์ ซึ่งหมายความว่าอัลกอริทึมไม่สามารถผูกขาดการใช้งาน CPU เป็นระยะเวลานานในการตัดสินใจได้ แม้แต่ 10 มิลลิวินาทีก็นานเกินไป เพราะเกมส่วนใหญ่ใช้เวลาเพียง 16 ถึง 33 มิลลิวินาทีในการประมวลผลทั้งหมดและไปยังเฟรมกราฟิกถัดไป
- ตามหลักการแล้ว อย่างน้อยส่วนหนึ่งของระบบควรขับเคลื่อนด้วยข้อมูล เพื่อให้ผู้ที่ไม่ใช่ผู้เขียนโค้ดสามารถทำการเปลี่ยนแปลงและปรับเปลี่ยนได้รวดเร็วยิ่งขึ้น
มาดูแนวทางของ AI ที่ครอบคลุมวงจร Sense/Think/Act ทั้งหมด
การตัดสินใจขั้นพื้นฐาน
เริ่มจากเกมที่ง่ายที่สุด - ปิงปอง เป้าหมาย: ขยับไม้พายเพื่อให้ลูกบอลกระดอนออกไปแทนที่จะบินผ่านมันไป มันก็เหมือนกับเทนนิสที่คุณจะแพ้ถ้าคุณไม่ตีลูก ที่นี่ AI มีงานที่ค่อนข้างง่าย - การตัดสินใจว่าจะย้ายแพลตฟอร์มไปในทิศทางใด
คำสั่งแบบมีเงื่อนไข
สำหรับ AI ในโป่ง วิธีแก้ไขที่ชัดเจนที่สุดคือพยายามวางแพลตฟอร์มไว้ใต้ลูกบอลเสมอ
อัลกอริธึมอย่างง่ายสำหรับสิ่งนี้เขียนด้วยรหัสเทียม:
ทุกเฟรม/อัพเดตในขณะที่เกมกำลังทำงาน:
ถ้าลูกบอลอยู่ทางด้านซ้ายของไม้พาย:
เลื่อนพายไปทางซ้าย
มิฉะนั้นหากลูกบอลอยู่ทางด้านขวาของไม้พาย:
เลื่อนไม้พายไปทางขวา
หากแพลตฟอร์มเคลื่อนที่ด้วยความเร็วของลูกบอล นี่คืออัลกอริธึมในอุดมคติสำหรับ AI ในโป่ง ไม่จำเป็นต้องซับซ้อนใดๆ หากไม่มีข้อมูลมากนักและการดำเนินการที่เป็นไปได้สำหรับตัวแทน
แนวทางนี้ง่ายมากจนแทบจะมองไม่เห็นวงจรการรับรู้/การคิด/การกระทำทั้งหมด แต่มันอยู่ที่นั่น:
- ส่วน Sense แบ่งออกเป็นสองคำสั่ง if เกมรู้ว่าลูกบอลอยู่ที่ไหนและแพลตฟอร์มอยู่ที่ไหน ดังนั้น AI จึงมองหาข้อมูลนั้น
- ส่วน Think ยังรวมอยู่ในคำสั่ง if ทั้งสองด้วย พวกเขารวบรวมสองโซลูชั่น ซึ่งในกรณีนี้จะไม่เกิดร่วมกัน เป็นผลให้มีการเลือกหนึ่งในสามการกระทำ - เลื่อนแพลตฟอร์มไปทางซ้าย เลื่อนไปทางขวา หรือไม่ทำอะไรเลยหากอยู่ในตำแหน่งที่ถูกต้องแล้ว
- ส่วน Act จะพบได้ในคำสั่ง Move Paddle Left และ Move Paddle Right พวกเขาสามารถย้ายแพลตฟอร์มได้ทันทีหรือด้วยความเร็วที่กำหนดทั้งนี้ขึ้นอยู่กับการออกแบบเกม
วิธีการดังกล่าวเรียกว่าปฏิกิริยา - มีชุดกฎง่ายๆ (ในกรณีนี้หากมีข้อความในโค้ด) ที่ตอบสนองต่อสถานะปัจจุบันของโลกและดำเนินการ
ต้นไม้การตัดสินใจ
จริงๆ แล้วตัวอย่าง Pong นั้นเทียบเท่ากับแนวคิด AI อย่างเป็นทางการที่เรียกว่าแผนผังการตัดสินใจ อัลกอริธึมจะผ่านขั้นตอนนี้เพื่อไปถึง "ใบไม้" ซึ่งเป็นการตัดสินใจว่าจะดำเนินการใด
มาสร้างบล็อกไดอะแกรมของแผนผังการตัดสินใจสำหรับอัลกอริทึมของแพลตฟอร์มของเรา:
แต่ละส่วนของต้นไม้เรียกว่าโหนด - AI ใช้ทฤษฎีกราฟเพื่ออธิบายโครงสร้างดังกล่าว โหนดมีสองประเภท:
- โหนดการตัดสินใจ: การเลือกระหว่างสองทางเลือกโดยอิงจากการทดสอบเงื่อนไขบางประการ โดยที่แต่ละทางเลือกจะแสดงเป็นโหนดแยกกัน
- โหนดสิ้นสุด: การดำเนินการที่แสดงถึงการตัดสินใจขั้นสุดท้าย
อัลกอริทึมเริ่มต้นจากโหนดแรก ("ราก" ของแผนผัง) โดยจะตัดสินใจว่าจะไปที่โหนดลูกใด หรือจะดำเนินการที่เก็บไว้ในโหนดแล้วออก
ประโยชน์ของการมีแผนผังการตัดสินใจทำหน้าที่เหมือนกับคำสั่ง if ในส่วนก่อนหน้าคืออะไร มีระบบทั่วไปที่นี่ซึ่งการตัดสินใจแต่ละครั้งมีเพียงเงื่อนไขเดียวและผลลัพธ์ที่เป็นไปได้สองประการ ช่วยให้นักพัฒนาสามารถสร้าง AI จากข้อมูลที่แสดงถึงการตัดสินใจในแผนผังโดยไม่ต้องฮาร์ดโค้ด มานำเสนอในรูปแบบของตาราง:
ในด้านโค้ดคุณจะได้รับระบบสำหรับอ่านสตริง สร้างโหนดสำหรับแต่ละโหนด เชื่อมต่อตรรกะการตัดสินใจตามคอลัมน์ที่สอง และโหนดย่อยตามคอลัมน์ที่สามและสี่ คุณยังคงต้องตั้งโปรแกรมเงื่อนไขและการกระทำ แต่ตอนนี้โครงสร้างของเกมจะซับซ้อนมากขึ้น ที่นี่คุณเพิ่มการตัดสินใจและการดำเนินการเพิ่มเติม จากนั้นปรับแต่ง AI ทั้งหมดโดยเพียงแค่แก้ไขไฟล์ข้อความคำจำกัดความแบบต้นไม้ ถัดไป คุณจะถ่ายโอนไฟล์ไปยังนักออกแบบเกม ซึ่งสามารถเปลี่ยนลักษณะการทำงานได้โดยไม่ต้องคอมไพล์เกมใหม่หรือเปลี่ยนโค้ด
แผนผังการตัดสินใจมีประโยชน์มากเมื่อสร้างขึ้นโดยอัตโนมัติจากชุดตัวอย่างจำนวนมาก (เช่น การใช้อัลกอริทึม ID3) ทำให้เป็นเครื่องมือที่มีประสิทธิภาพและมีประสิทธิภาพสูงในการจำแนกสถานการณ์ตามข้อมูลที่ได้รับ อย่างไรก็ตาม เราทำมากกว่าระบบธรรมดาสำหรับตัวแทนในการเลือกการดำเนินการ
สถานการณ์
เราวิเคราะห์ระบบโครงสร้างการตัดสินใจที่ใช้เงื่อนไขและการดำเนินการที่สร้างไว้ล่วงหน้า ผู้ออกแบบ AI สามารถจัดระเบียบ Tree ได้ตามต้องการ แต่ก็ยังต้องพึ่งพา Coder ที่ตั้งโปรแกรมไว้ทั้งหมด จะเป็นอย่างไรถ้าเราสามารถมอบเครื่องมือให้กับนักออกแบบเพื่อสร้างเงื่อนไขหรือการกระทำของตนเองได้?
เพื่อให้โปรแกรมเมอร์ไม่ต้องเขียนโค้ดสำหรับเงื่อนไข Is Ball Left Of Paddle และ Is Ball Right Of Paddle เขาสามารถสร้างระบบให้ผู้ออกแบบเขียนเงื่อนไขเพื่อตรวจสอบค่าเหล่านี้ได้ จากนั้นข้อมูลแผนผังการตัดสินใจจะมีลักษณะดังนี้:
โดยพื้นฐานแล้วจะเหมือนกับในตารางแรก แต่โซลูชันภายในตัวมันเองมีโค้ดของตัวเอง คล้ายกับส่วนที่มีเงื่อนไขของคำสั่ง if ในด้านโค้ด ข้อมูลนี้จะอ่านได้ในคอลัมน์ที่สองสำหรับโหนดการตัดสินใจ แต่แทนที่จะมองหาเงื่อนไขเฉพาะในการดำเนินการ (ลูกบอลอยู่ทางซ้ายของแป้น) ระบบจะประเมินนิพจน์ตามเงื่อนไขและส่งกลับค่าจริงหรือเท็จตามนั้น ทำได้โดยใช้ภาษาสคริปต์ Lua หรือ Angelscript เมื่อใช้สิ่งเหล่านี้ นักพัฒนาสามารถนำวัตถุในเกมของเขา (ลูกบอลและไม้พาย) และสร้างตัวแปรที่จะสามารถใช้ได้ในสคริปต์ (ball.position) นอกจากนี้ภาษาสคริปต์ยังง่ายกว่า C++ มันไม่จำเป็นต้องมีขั้นตอนการคอมไพล์ทั้งหมด ดังนั้นจึงเหมาะอย่างยิ่งสำหรับการปรับตรรกะของเกมอย่างรวดเร็ว และช่วยให้ “ผู้ที่ไม่ใช่ผู้เขียนโค้ด” สามารถสร้างฟังก์ชันที่จำเป็นได้ด้วยตนเอง
ในตัวอย่างข้างต้น ภาษาสคริปต์ใช้เพื่อประเมินนิพจน์แบบมีเงื่อนไขเท่านั้น แต่ยังใช้สำหรับการดำเนินการได้ด้วย ตัวอย่างเช่น ข้อมูล Move Paddle Right อาจกลายเป็นคำสั่งสคริปต์ (ball.position.x += 10) เพื่อให้การกระทำนั้นถูกกำหนดไว้ในสคริปต์ด้วย โดยไม่จำเป็นต้องตั้งโปรแกรม Move Paddle Right
คุณสามารถก้าวไปไกลกว่านี้ด้วยการเขียนแผนผังการตัดสินใจทั้งหมดในภาษาสคริปต์ นี่จะเป็นโค้ดในรูปแบบของคำสั่งแบบมีเงื่อนไขแบบฮาร์ดโค้ด แต่จะอยู่ในไฟล์สคริปต์ภายนอกนั่นคือสามารถเปลี่ยนแปลงได้โดยไม่ต้องคอมไพล์โปรแกรมใหม่ทั้งหมด คุณมักจะสามารถแก้ไขไฟล์สคริปต์ระหว่างการเล่นเกมเพื่อทดสอบการตอบสนองของ AI ต่างๆ ได้อย่างรวดเร็ว
การตอบสนองต่อเหตุการณ์
ตัวอย่างข้างต้นเหมาะสำหรับโป่ง พวกเขาดำเนินวงจร Sense/Think/Act อย่างต่อเนื่อง และดำเนินการตามสถานะล่าสุดของโลก แต่ในเกมที่ซับซ้อนมากขึ้น คุณจะต้องตอบสนองต่อแต่ละเหตุการณ์ และอย่าประเมินทุกอย่างในคราวเดียว ปองในกรณีนี้ก็เป็นตัวอย่างที่ไม่ดีอยู่แล้ว ให้เลือกอันอื่น
ลองนึกภาพนักกีฬาที่ศัตรูไม่เคลื่อนไหวจนกว่าพวกเขาจะตรวจจับผู้เล่นได้ หลังจากนั้นพวกเขาจะทำหน้าที่ขึ้นอยู่กับ "ความเชี่ยวชาญ" ของพวกเขา: บางคนจะวิ่งเพื่อ "เร่งรีบ" บางคนจะโจมตีจากระยะไกล มันยังคงเป็นระบบปฏิกิริยาพื้นฐาน - "หากผู้เล่นถูกพบ ให้ทำอะไรสักอย่าง" - แต่สามารถแบ่งย่อยตามตรรกะเป็นเหตุการณ์ที่ผู้เล่นเห็นและปฏิกิริยา (เลือกการตอบสนองและดำเนินการ)
สิ่งนี้นำเรากลับไปสู่วงจรความรู้สึก/คิด/การกระทำ เราสามารถเขียนโค้ดส่วน Sense ที่จะตรวจสอบทุกเฟรมว่า AI เห็นผู้เล่นหรือไม่ ถ้าไม่เช่นนั้นจะไม่มีอะไรเกิดขึ้น แต่ถ้าเห็น แสดงว่าเหตุการณ์ Player Seen จะถูกสร้างขึ้น โค้ดจะมีส่วนที่แยกต่างหากที่ระบุว่า "เมื่อเหตุการณ์ Player Seen เกิดขึ้น ให้ทำ" โดยที่คำตอบที่คุณต้องใช้เพื่อจัดการกับส่วน Think and Act ดังนั้น คุณจะตั้งค่าการตอบสนองต่อเหตุการณ์ผู้เล่นเห็น: สำหรับตัวละคร "เร่งรีบ" - ChargeAndAttack และสำหรับมือปืน - HideAndSnipe ความสัมพันธ์เหล่านี้สามารถสร้างได้ในไฟล์ข้อมูลเพื่อการแก้ไขอย่างรวดเร็วโดยไม่ต้องคอมไพล์ใหม่ สามารถใช้ภาษาสคริปต์ได้ที่นี่เช่นกัน
การตัดสินใจที่ยากลำบาก
แม้ว่าระบบปฏิกิริยาแบบธรรมดาจะทรงพลังมาก แต่ก็มีหลายสถานการณ์ที่ยังไม่เพียงพอ บางครั้งคุณจำเป็นต้องตัดสินใจที่แตกต่างกันออกไปโดยขึ้นอยู่กับสิ่งที่ตัวแทนกำลังทำอยู่ แต่ก็ยากที่จะจินตนาการว่านี่เป็นเงื่อนไข บางครั้งมีเงื่อนไขมากเกินไปที่จะนำเสนอเงื่อนไขเหล่านี้อย่างมีประสิทธิภาพในแผนผังการตัดสินใจหรือสคริปต์ได้ บางครั้งคุณต้องประเมินล่วงหน้าว่าสถานการณ์จะเปลี่ยนแปลงไปอย่างไรก่อนตัดสินใจขั้นต่อไป จำเป็นต้องใช้แนวทางที่ซับซ้อนมากขึ้นเพื่อแก้ไขปัญหาเหล่านี้
เครื่องไฟไนต์สเตท
เครื่องสถานะจำกัดหรือ FSM (เครื่องสถานะจำกัด) เป็นวิธีการบอกว่าขณะนี้ตัวแทนของเราอยู่ในสถานะที่เป็นไปได้หลายสถานะ และสามารถเปลี่ยนจากสถานะหนึ่งไปอีกสถานะหนึ่งได้ มีรัฐดังกล่าวอยู่จำนวนหนึ่ง—จึงเป็นที่มาของชื่อ ตัวอย่างที่ดีที่สุดจากชีวิตคือสัญญาณไฟจราจร มีลำดับแสงที่แตกต่างกันในแต่ละสถานที่ แต่หลักการก็เหมือนกัน แต่ละสถานะเป็นตัวแทนของบางสิ่งบางอย่าง (หยุด เดิน ฯลฯ) สัญญาณไฟจราจรจะอยู่ในสถานะเดียวเท่านั้นในเวลาใดก็ตาม และจะเคลื่อนจากที่หนึ่งไปยังอีกที่หนึ่งตามกฎง่ายๆ
มันเป็นเรื่องราวที่คล้ายกันกับ NPC ในเกม ตัวอย่างเช่น เรามาป้องกันด้วยสถานะต่อไปนี้:
- ตระเวน.
- โจมตี
- กำลังหลบหนี
และเงื่อนไขในการเปลี่ยนสถานะเหล่านี้:
- หากยามเห็นศัตรูเขาก็โจมตี
- หากยามโจมตีแต่ไม่เห็นศัตรูอีกต่อไป เขาจะกลับมาลาดตระเวนอีกครั้ง
- ถ้ายามโจมตีแต่บาดเจ็บสาหัส เขาก็วิ่งหนี
คุณยังสามารถเขียนคำสั่ง if ด้วยตัวแปรสถานะผู้พิทักษ์และการตรวจสอบต่างๆ ได้: มีศัตรูอยู่ใกล้ๆ หรือไม่ ระดับสุขภาพของ NPC คืออะไร เป็นต้น เรามาเพิ่มสถานะเพิ่มเติมกัน:
- ความเกียจคร้าน - ระหว่างการลาดตระเวน
- ค้นหา - เมื่อศัตรูที่ถูกพบหายไป
- ค้นหาความช่วยเหลือ - เมื่อพบศัตรู แต่แข็งแกร่งเกินกว่าจะต่อสู้ตามลำพัง
ทางเลือกสำหรับแต่ละคนมีจำกัด - ตัวอย่างเช่น ผู้คุมจะไม่ไปหาศัตรูที่ซ่อนอยู่หากเขามีพลังชีวิตต่ำ
ท้ายที่สุดแล้ว มีรายการ "ifs" มากมาย , ที่ " อาจยุ่งยากเกินไป ดังนั้นเราจึงจำเป็นต้องกำหนดวิธีการอย่างเป็นทางการที่ช่วยให้เราสามารถคำนึงถึงสถานะและการเปลี่ยนผ่านระหว่างรัฐได้ ในการทำเช่นนี้ เราคำนึงถึงรัฐทั้งหมด และในแต่ละรัฐ เราจะเขียนรายการการเปลี่ยนผ่านไปยังรัฐอื่นทั้งหมด พร้อมด้วยเงื่อนไขที่จำเป็นสำหรับรัฐเหล่านั้น
นี่คือตารางการเปลี่ยนสถานะ - วิธีที่ครอบคลุมในการเป็นตัวแทนของ FSM มาวาดแผนภาพและดูภาพรวมโดยสมบูรณ์ว่าพฤติกรรมของ NPC เปลี่ยนแปลงไปอย่างไร
แผนภาพสะท้อนให้เห็นถึงสาระสำคัญของการตัดสินใจสำหรับตัวแทนรายนี้ตามสถานการณ์ปัจจุบัน นอกจากนี้ ลูกศรแต่ละอันจะแสดงการเปลี่ยนแปลงระหว่างสถานะต่างๆ หากเงื่อนไขข้างๆ เป็นจริง
การอัปเดตแต่ละครั้ง เราจะตรวจสอบสถานะปัจจุบันของตัวแทน ดูรายการการเปลี่ยนแปลง และหากตรงตามเงื่อนไขสำหรับการเปลี่ยนแปลง ก็จะยอมรับสถานะใหม่ ตัวอย่างเช่น แต่ละเฟรมจะตรวจสอบว่าตัวจับเวลา 10 วินาทีหมดอายุแล้วหรือไม่ และหากเป็นเช่นนั้น การ์ดจะเปลี่ยนจากสถานะเดินเบาเป็นลาดตระเวน ในทำนองเดียวกัน สถานะโจมตีจะตรวจสอบสุขภาพของตัวแทน - หากเหลือน้อย ก็จะเข้าสู่สถานะหลบหนี
นี่คือการจัดการการเปลี่ยนผ่านระหว่างรัฐ แต่พฤติกรรมที่เกี่ยวข้องกับรัฐเองล่ะ? ในแง่ของการใช้พฤติกรรมจริงสำหรับสถานะหนึ่งๆ โดยทั่วไปจะมี "hook" สองประเภทที่เรากำหนดการดำเนินการให้กับ FSM:
- การดำเนินการที่เราทำเป็นระยะสำหรับสถานะปัจจุบัน
- การกระทำที่เราทำเมื่อเปลี่ยนจากรัฐหนึ่งไปอีกรัฐหนึ่ง
ตัวอย่างสำหรับประเภทแรก สถานะลาดตระเวนจะเคลื่อนเจ้าหน้าที่ไปตามเส้นทางลาดตระเวนแต่ละเฟรม สถานะการโจมตีจะพยายามเริ่มการโจมตีในแต่ละเฟรมหรือเปลี่ยนไปสู่สถานะที่เป็นไปได้
สำหรับประเภทที่สอง ให้พิจารณาการเปลี่ยนแปลง “หากศัตรูมองเห็นได้และศัตรูแข็งแกร่งเกินไป ให้ไปที่สถานะค้นหาความช่วยเหลือ ตัวแทนจะต้องเลือกสถานที่ที่จะขอความช่วยเหลือและจัดเก็บข้อมูลนี้เพื่อให้สถานะการค้นหาความช่วยเหลือทราบว่าจะไปที่ไหน เมื่อพบความช่วยเหลือแล้ว เจ้าหน้าที่จะกลับสู่สถานะโจมตี ณ จุดนี้ เขาต้องการบอกพันธมิตรเกี่ยวกับภัยคุกคาม ดังนั้นการดำเนินการ NotifyFriendOfThreat อาจเกิดขึ้น
อีกครั้งหนึ่งที่เราสามารถมองระบบนี้ผ่านเลนส์ของวงจรการรับรู้/การคิด/การกระทำ ความรู้สึกรวมอยู่ในข้อมูลที่ใช้โดยลอจิกการเปลี่ยนแปลง คิด - มีการเปลี่ยนผ่านในแต่ละรัฐ และพระราชบัญญัติจะดำเนินการโดยการกระทำที่ดำเนินการเป็นระยะภายในรัฐหรือในช่วงเปลี่ยนผ่านระหว่างรัฐ
บางครั้งเงื่อนไขการเปลี่ยนแปลงการโพลอย่างต่อเนื่องอาจมีค่าใช้จ่ายสูง ตัวอย่างเช่น หากเจ้าหน้าที่แต่ละคนทำการคำนวณที่ซับซ้อนทุกเฟรมเพื่อพิจารณาว่าสามารถมองเห็นศัตรูได้หรือไม่ และเข้าใจว่าสามารถเปลี่ยนจากสถานะลาดตระเวนเป็นโจมตีได้หรือไม่ การดำเนินการนี้จะใช้เวลา CPU มาก
การเปลี่ยนแปลงที่สำคัญในสถานะของโลกถือได้ว่าเป็นเหตุการณ์ที่จะถูกประมวลผลทันทีที่เกิดขึ้น แทนที่จะให้ FSM ตรวจสอบเงื่อนไขการเปลี่ยนแปลง "ตัวแทนของฉันมองเห็นผู้เล่นได้หรือไม่" ทุกเฟรม สามารถกำหนดค่าระบบที่แยกจากกันเพื่อตรวจสอบความถี่น้อยลง (เช่น 5 ครั้งต่อวินาที) และผลที่ได้คือออก Player Seen เมื่อเช็คผ่าน
สิ่งนี้จะถูกส่งไปยัง FSM ซึ่งตอนนี้ควรไปที่เงื่อนไขที่ได้รับของเหตุการณ์ Player Seen และตอบสนองตามนั้น ลักษณะการทำงานที่ได้จะเหมือนกัน ยกเว้นความล่าช้าที่แทบจะมองไม่เห็นก่อนที่จะตอบสนอง แต่ประสิทธิภาพได้รับการปรับปรุงโดยแยกส่วน Sense ออกเป็นส่วนแยกของโปรแกรม
เครื่องสถานะจำกัดแบบลำดับชั้น
อย่างไรก็ตาม การทำงานกับ FSM ขนาดใหญ่อาจไม่สะดวกเสมอไป หากเราต้องการขยายสถานะการโจมตีให้แยก MeleeAttacking และ RangedAttacking เราจะต้องเปลี่ยนการเปลี่ยนจากสถานะอื่นทั้งหมดที่นำไปสู่สถานะการโจมตี (ปัจจุบันและอนาคต)
คุณอาจสังเกตเห็นว่าในตัวอย่างของเรามีการเปลี่ยนแปลงที่ซ้ำกันจำนวนมาก การเปลี่ยนผ่านส่วนใหญ่ในสถานะ Idling จะเหมือนกันกับการเปลี่ยนในสถานะ Patrolling คงจะดีไม่พูดซ้ำ โดยเฉพาะอย่างยิ่งถ้าเราเพิ่มสถานะที่คล้ายกันมากขึ้น เหมาะสมที่จะจัดกลุ่ม Idling และ Patrolling ภายใต้ป้ายกำกับทั่วไปว่า "ไม่สู้รบ" ซึ่งมีเพียงชุดการเปลี่ยนผ่านทั่วไปเพียงชุดเดียวสำหรับรัฐต่อสู้ หากเราคิดว่าป้ายกำกับนี้เป็นสถานะ Idling และ Patrolling ก็จะกลายเป็นสถานะย่อย ตัวอย่างของการใช้ตารางการเปลี่ยนผ่านแยกต่างหากสำหรับสถานะย่อยที่ไม่ใช่การต่อสู้ใหม่:
รัฐหลัก:
สถานะไม่อยู่ในการต่อสู้:
และในรูปแบบไดอะแกรม:
มันเป็นระบบเดียวกัน แต่มีสถานะที่ไม่ใช่การต่อสู้ใหม่ซึ่งรวมถึง Idling และ Patrolling ในแต่ละรัฐที่มี FSM พร้อมด้วยรัฐย่อย (และรัฐย่อยเหล่านี้ก็มี FSM ของตัวเอง - และอื่นๆ ตราบเท่าที่คุณต้องการ) เราจึงได้ Hierarchical Finite State Machine หรือ HFSM (เครื่องสถานะจำกัดแบบลำดับชั้น) ด้วยการจัดกลุ่มสถานะที่ไม่ใช่การต่อสู้ เราได้ตัดการเปลี่ยนผ่านที่ซ้ำซ้อนออกไป เราสามารถทำเช่นเดียวกันกับรัฐใหม่ที่มีการเปลี่ยนผ่านร่วมกัน ตัวอย่างเช่น หากในอนาคตเราขยายสถานะการโจมตีเป็นสถานะการโจมตีระยะประชิดและการโจมตีด้วยขีปนาวุธ สถานะเหล่านั้นจะเป็นสถานะย่อยที่เปลี่ยนผ่านระหว่างกันตามระยะห่างจากศัตรูและความพร้อมของกระสุน เป็นผลให้พฤติกรรมที่ซับซ้อนและพฤติกรรมย่อยสามารถแสดงได้ด้วยการเปลี่ยนซ้ำขั้นต่ำ
ต้นไม้พฤติกรรม
ด้วย HFSM การผสมผสานพฤติกรรมที่ซับซ้อนจะถูกสร้างขึ้นด้วยวิธีง่ายๆ อย่างไรก็ตาม มีความยากลำบากเล็กน้อยที่การตัดสินใจในรูปแบบของกฎการเปลี่ยนผ่านมีความเกี่ยวข้องอย่างใกล้ชิดกับสถานะปัจจุบัน และในหลาย ๆ เกมนี่คือสิ่งที่จำเป็นจริงๆ และการใช้ลำดับชั้นของรัฐอย่างระมัดระวังสามารถลดจำนวนการทำซ้ำของการเปลี่ยนแปลงได้ แต่บางครั้งคุณจำเป็นต้องมีกฎที่ใช้ได้ผลไม่ว่าคุณจะอยู่ในรัฐใดก็ตาม หรือบังคับใช้ในเกือบทุกรัฐ ตัวอย่างเช่น หากสุขภาพของเจ้าหน้าที่ลดลงเหลือ 25% คุณจะต้องการให้เขาวิ่งหนี ไม่ว่าเขาจะอยู่ในการต่อสู้ ไม่ได้ใช้งาน หรือกำลังพูดคุย คุณจะต้องเพิ่มเงื่อนไขนี้ลงในแต่ละรัฐ และหากนักออกแบบของคุณต้องการเปลี่ยนเกณฑ์สุขภาพต่ำจาก 25% เป็น 10% ในภายหลัง จะต้องดำเนินการนี้อีกครั้ง
ตามหลักการแล้ว สถานการณ์นี้จำเป็นต้องมีระบบที่การตัดสินใจเกี่ยวกับ “รัฐที่จะอยู่ใน” อยู่นอกรัฐ เพื่อทำการเปลี่ยนแปลงในที่เดียวเท่านั้น และไม่แตะต้องเงื่อนไขการเปลี่ยนแปลง ต้นไม้พฤติกรรมปรากฏที่นี่
มีหลายวิธีในการนำไปใช้ แต่สาระสำคัญจะเหมือนกันสำหรับทุกคนและคล้ายกับแผนผังการตัดสินใจ: อัลกอริธึมเริ่มต้นด้วยโหนด "รูท" และแผนผังประกอบด้วยโหนดที่แสดงถึงการตัดสินใจหรือการกระทำ มีความแตกต่างที่สำคัญบางประการ:
- ตอนนี้โหนดส่งคืนค่าหนึ่งในสามค่า: สำเร็จ (หากงานเสร็จสมบูรณ์), ล้มเหลว (หากไม่สามารถเริ่มต้นได้) หรือกำลังทำงาน (หากยังคงทำงานอยู่และไม่มีผลลัพธ์สุดท้าย)
- ไม่มีโหนดการตัดสินใจให้เลือกระหว่างสองทางเลือกอีกต่อไป แต่เป็นโหนดมัณฑนากรซึ่งมีโหนดย่อยหนึ่งโหนด หากสำเร็จ พวกเขาจะรันโหนดย่อยเพียงโหนดเดียว
- โหนดที่ดำเนินการจะส่งคืนค่ากำลังทำงานเพื่อแสดงการดำเนินการที่กำลังดำเนินการ
โหนดชุดเล็กๆ นี้สามารถนำมารวมกันเพื่อสร้างพฤติกรรมที่ซับซ้อนจำนวนมากได้ ลองจินตนาการถึงยาม HFSM จากตัวอย่างก่อนหน้านี้เป็นแผนผังพฤติกรรม:
ด้วยโครงสร้างนี้ ไม่ควรมีการเปลี่ยนที่ชัดเจนจากสถานะเดินเบา/ลาดตระเวนเป็นสถานะโจมตีหรือสถานะอื่นๆ หากมองเห็นศัตรูได้และสุขภาพของตัวละครต่ำ การประหารชีวิตจะหยุดที่โหนด Fleeing โดยไม่คำนึงว่าโหนดใดที่ดำเนินการก่อนหน้านี้ - การลาดตระเวน การไม่ทำงาน การโจมตี หรืออื่น ๆ
แผนผังพฤติกรรมมีความซับซ้อน มีหลายวิธีในการจัดองค์ประกอบ และการค้นหาการผสมผสานที่เหมาะสมของมัณฑนากรและโหนดประกอบอาจเป็นเรื่องที่ท้าทาย นอกจากนี้ยังมีคำถามเกี่ยวกับความถี่ในการตรวจสอบต้นไม้ - เราต้องการผ่านทุกส่วนของต้นไม้หรือเฉพาะเมื่อเงื่อนไขข้อใดข้อหนึ่งเปลี่ยนไปเท่านั้น เราจะจัดเก็บสถานะที่เกี่ยวข้องกับโหนดได้อย่างไร - เราจะรู้ได้อย่างไรว่าเราไม่ได้ใช้งานเป็นเวลา 10 วินาทีเมื่อใด หรือเราจะรู้ได้อย่างไรว่าโหนดใดกำลังดำเนินการครั้งล่าสุด เพื่อให้เราสามารถประมวลผลลำดับได้อย่างถูกต้อง
ด้วยเหตุนี้จึงมีการใช้งานหลายอย่าง ตัวอย่างเช่น บางระบบได้แทนที่โหนดมัณฑนากรด้วยมัณฑนากรแบบอินไลน์ พวกเขาประเมินต้นไม้อีกครั้งเมื่อเงื่อนไขของมัณฑนากรเปลี่ยนแปลง ช่วยรวมโหนด และจัดให้มีการอัปเดตเป็นระยะ
ระบบสาธารณูปโภค
เกมบางเกมมีกลไกที่แตกต่างกันมากมาย เป็นที่พึงปรารถนาที่พวกเขาจะได้รับผลประโยชน์ทั้งหมดของกฎการเปลี่ยนแปลงที่เรียบง่ายและทั่วไป แต่ไม่จำเป็นต้องอยู่ในรูปแบบของแผนผังพฤติกรรมที่สมบูรณ์ แทนที่จะมีชุดตัวเลือกที่ชัดเจนหรือแผนผังของการกระทำที่เป็นไปได้ จะง่ายกว่าที่จะตรวจสอบการกระทำทั้งหมดและเลือกการกระทำที่เหมาะสมที่สุดในขณะนี้
ระบบที่ใช้ยูทิลิตี้จะช่วยได้เพียงเท่านี้ นี่คือระบบที่ตัวแทนมีการดำเนินการที่หลากหลาย และเลือกการดำเนินการตามอรรถประโยชน์ที่เกี่ยวข้องของแต่ละรายการ โดยที่อรรถประโยชน์เป็นการวัดโดยพลการว่ามีความสำคัญหรือเป็นที่ต้องการสำหรับตัวแทนในการดำเนินการนี้
ยูทิลิตี้ที่คำนวณได้ของการดำเนินการตามสถานะปัจจุบันและสภาพแวดล้อม ตัวแทนสามารถตรวจสอบและเลือกสถานะอื่นที่เหมาะสมที่สุดได้ตลอดเวลา ซึ่งคล้ายกับ FSM ยกเว้นในกรณีที่การเปลี่ยนผ่านถูกกำหนดโดยการประมาณการสำหรับแต่ละสถานะที่เป็นไปได้ รวมถึงสถานะปัจจุบันด้วย โปรดทราบว่าเราเลือกการดำเนินการที่มีประโยชน์ที่สุดเพื่อดำเนินการต่อ (หรืออยู่ต่อหากเราได้ดำเนินการเสร็จสิ้นแล้ว) หากต้องการความหลากหลายมากขึ้น นี่อาจเป็นการเลือกที่สมดุลแต่สุ่มจากรายการเล็กๆ
ระบบจะกำหนดค่าอรรถประโยชน์ต่างๆ ได้ตามใจชอบ เช่น ตั้งแต่ 0 (ไม่พึงประสงค์โดยสิ้นเชิง) ถึง 100 (เป็นที่ต้องการอย่างยิ่ง) แต่ละการกระทำมีพารามิเตอร์จำนวนหนึ่งที่ส่งผลต่อการคำนวณค่านี้ กลับมาที่ตัวอย่างผู้ปกครองของเรา:
การเปลี่ยนผ่านระหว่างการกระทำนั้นไม่ชัดเจน สถานะใดก็ตามสามารถติดตามสถานะอื่นได้ ลำดับความสำคัญของการดำเนินการจะพบได้ในค่าอรรถประโยชน์ที่ส่งคืน หากมองเห็นศัตรูได้ และศัตรูนั้นแข็งแกร่ง และสุขภาพของตัวละครต่ำ ทั้ง Fleeing และ FindingHelp จะส่งกลับค่าที่สูงที่ไม่ใช่ศูนย์ ในกรณีนี้ FindingHelp จะสูงกว่าเสมอ ในทำนองเดียวกัน กิจกรรมที่ไม่ใช่การต่อสู้จะไม่กลับมาเกิน 50 ดังนั้นกิจกรรมเหล่านั้นจะต่ำกว่ากิจกรรมการต่อสู้เสมอ คุณต้องคำนึงถึงสิ่งนี้เมื่อสร้างการกระทำและคำนวณยูทิลิตี้
ในตัวอย่างของเรา การดำเนินการจะส่งกลับค่าคงที่คงที่หรือค่าคงที่ค่าใดค่าหนึ่งจากสองค่า ระบบที่สมจริงมากขึ้นจะส่งค่าประมาณจากช่วงค่าที่ต่อเนื่องกัน ตัวอย่างเช่น การกระทำ Fleeing จะส่งกลับค่าอรรถประโยชน์ที่สูงกว่าหากสุขภาพของตัวแทนต่ำ และการกระทำการโจมตีจะส่งกลับค่าอรรถประโยชน์ที่ต่ำกว่าหากศัตรูแข็งแกร่งเกินไป ด้วยเหตุนี้ การดำเนินการ Fleeing จึงมีความสำคัญเหนือกว่าการโจมตีในทุกสถานการณ์ที่เจ้าหน้าที่รู้สึกว่าเขามีพลังชีวิตไม่เพียงพอที่จะเอาชนะศัตรู ซึ่งช่วยให้สามารถจัดลำดับความสำคัญของการดำเนินการตามเกณฑ์จำนวนเท่าใดก็ได้ ทำให้แนวทางนี้มีความยืดหยุ่นและแปรผันมากกว่าแผนผังพฤติกรรมหรือ FSM
แต่ละการกระทำมีเงื่อนไขมากมายสำหรับการคำนวณโปรแกรม สามารถเขียนเป็นภาษาสคริปต์หรือเป็นชุดสูตรทางคณิตศาสตร์ได้ The Sims ซึ่งจำลองกิจวัตรประจำวันของตัวละครจะเพิ่มการคำนวณอีกชั้นหนึ่ง - ตัวแทนจะได้รับ "แรงจูงใจ" ชุดหนึ่งที่มีอิทธิพลต่อการจัดอันดับยูทิลิตี้ หากตัวละครหิว พวกเขาจะยิ่งหิวมากขึ้นเมื่อเวลาผ่านไป และมูลค่าอรรถประโยชน์ของการกระทำ EatFood จะเพิ่มขึ้นจนกว่าตัวละครจะทำเช่นนั้น ซึ่งจะลดระดับความหิวและคืนค่า EatFood ให้เป็นศูนย์
แนวคิดในการเลือกการดำเนินการตามระบบการให้คะแนนนั้นค่อนข้างง่าย ดังนั้นระบบที่ใช้ยูทิลิตี้จึงสามารถใช้เป็นส่วนหนึ่งของกระบวนการตัดสินใจของ AI แทนที่จะแทนที่โดยสมบูรณ์ แผนผังการตัดสินใจอาจขอระดับยูทิลิตี้ของโหนดย่อยสองโหนด และเลือกโหนดที่สูงกว่า ในทำนองเดียวกัน แผนผังพฤติกรรมสามารถมีโหนดยูทิลิตี้แบบผสมเพื่อประเมินยูทิลิตี้ของการดำเนินการเพื่อตัดสินใจว่าลูกคนใดที่จะดำเนินการ
การเคลื่อนไหวและการนำทาง
ในตัวอย่างก่อนหน้านี้ เรามีแท่นที่เราเคลื่อนไปทางซ้ายหรือขวา และมียามที่ลาดตระเวนหรือโจมตี แต่เราจะจัดการกับการเคลื่อนไหวของตัวแทนในช่วงเวลาหนึ่งได้อย่างไร? เราจะกำหนดความเร็วได้อย่างไร จะหลีกเลี่ยงอุปสรรคได้อย่างไร และจะวางแผนเส้นทางอย่างไรเมื่อไปถึงจุดหมายนั้นยากกว่าการเคลื่อนตัวเป็นเส้นตรง? ลองดูที่นี้
Управление
ในระยะเริ่มแรก เราจะถือว่าแต่ละเอเจนต์มีค่าความเร็ว ซึ่งรวมถึงความเร็วที่เอเจนต์เคลื่อนที่และไปในทิศทางใด สามารถวัดได้ในหน่วยเมตรต่อวินาที กิโลเมตรต่อชั่วโมง พิกเซลต่อวินาที ฯลฯ เมื่อนึกถึงลูป Sense/Think/Act เราสามารถจินตนาการได้ว่าส่วนของ Think เลือกความเร็ว และส่วนของ Act จะใช้ความเร็วนั้นกับตัวแทน โดยทั่วไปแล้ว เกมจะมีระบบฟิสิกส์ที่ทำงานนี้ให้คุณ โดยเรียนรู้ค่าความเร็วของแต่ละวัตถุและทำการปรับเปลี่ยน ดังนั้นคุณสามารถปล่อยให้ AI มีหน้าที่เดียว - เพื่อตัดสินใจว่าตัวแทนควรมีความเร็วเท่าใด หากคุณรู้ว่าเจ้าหน้าที่ควรอยู่ที่ไหน คุณจะต้องเคลื่อนย้ายเจ้าหน้าที่ไปในทิศทางที่ถูกต้องด้วยความเร็วที่ตั้งไว้ สมการที่ไม่สำคัญมาก:
ที่ต้องการ_การเดินทาง = ตำแหน่งปลายทาง – ตำแหน่งตัวแทน
ลองจินตนาการถึงโลก 2 มิติ เจ้าหน้าที่อยู่ที่จุด (-2,-2) ปลายทางอยู่ที่ไหนสักแห่งในภาคตะวันออกเฉียงเหนือที่จุด (30, 20) และเส้นทางที่จำเป็นสำหรับตัวแทนที่จะไปที่นั่นคือ (32, 22) สมมติว่าตำแหน่งเหล่านี้วัดเป็นเมตร - หากเราใช้ความเร็วของตัวแทนเป็น 5 เมตรต่อวินาที เราจะปรับขนาดเวกเตอร์การกระจัดของเราและได้ความเร็วประมาณ (4.12, 2.83) ด้วยพารามิเตอร์เหล่านี้ เจ้าหน้าที่จะมาถึงปลายทางได้ภายในเวลาเกือบ 8 วินาที
คุณสามารถคำนวณค่าใหม่ได้ตลอดเวลา หากตัวแทนอยู่ครึ่งทางถึงเป้าหมาย การเคลื่อนที่จะมีความยาวเพียงครึ่งหนึ่ง แต่เนื่องจากความเร็วสูงสุดของตัวแทนคือ 5 เมตร/วินาที (เราตัดสินใจไว้ข้างต้น) ความเร็วจะเท่ากัน นอกจากนี้ยังใช้ได้กับเป้าหมายที่กำลังเคลื่อนที่อีกด้วย ช่วยให้ตัวแทนทำการเปลี่ยนแปลงเล็กๆ น้อยๆ ขณะที่เป้าหมายเคลื่อนที่ได้
แต่เราต้องการความหลากหลายมากขึ้น เช่น ค่อยๆ เพิ่มความเร็วเพื่อจำลองตัวละครที่เคลื่อนที่จากการยืนหนึ่งไปอีกการวิ่ง สามารถทำได้ในตอนท้ายก่อนที่จะหยุด คุณลักษณะเหล่านี้เรียกว่าพฤติกรรมการบังคับเลี้ยว ซึ่งแต่ละอย่างมีชื่อเฉพาะ: แสวงหา หลบหนี การมาถึง ฯลฯ แนวคิดก็คือแรงเร่งความเร็วสามารถนำไปใช้กับความเร็วของเจ้าหน้าที่ได้ โดยอิงจากการเปรียบเทียบตำแหน่งของเจ้าหน้าที่และความเร็วปัจจุบันกับจุดหมายปลายทางใน เพื่อที่จะใช้วิธีต่าง ๆ ในการเคลื่อนไปสู่เป้าหมาย
พฤติกรรมแต่ละอย่างมีวัตถุประสงค์ที่แตกต่างกันเล็กน้อย การค้นหาและการมาถึงเป็นวิธีการย้ายตัวแทนไปยังจุดหมายปลายทาง การหลีกเลี่ยงและแยกอุปสรรคจะปรับการเคลื่อนไหวของตัวแทนเพื่อหลีกเลี่ยงอุปสรรคระหว่างทางไปสู่เป้าหมาย การจัดตำแหน่งและการทำงานร่วมกันช่วยให้เจ้าหน้าที่เคลื่อนไหวร่วมกัน สามารถรวมพฤติกรรมการบังคับเลี้ยวที่แตกต่างกันจำนวนเท่าใดก็ได้เพื่อสร้างเวกเตอร์เส้นทางเดียวโดยคำนึงถึงปัจจัยทั้งหมด เจ้าหน้าที่ที่ใช้พฤติกรรมการมาถึง การแยก และการหลีกเลี่ยงอุปสรรค เพื่ออยู่ห่างจากกำแพงและเจ้าหน้าที่อื่นๆ วิธีการนี้ใช้ได้ผลดีในสถานที่เปิดโล่งโดยไม่มีรายละเอียดที่ไม่จำเป็น
ในสภาวะที่ยากลำบาก การเพิ่มพฤติกรรมต่างๆ จะยิ่งแย่ลง เช่น เจ้าหน้าที่อาจติดอยู่ในกำแพงได้เนื่องจากข้อขัดแย้งระหว่างการมาถึงและการหลีกเลี่ยงอุปสรรค ดังนั้น คุณต้องพิจารณาตัวเลือกที่ซับซ้อนมากกว่าการเพิ่มค่าทั้งหมด วิธีการคือ: แทนที่จะรวมผลลัพธ์ของพฤติกรรมแต่ละอย่างเข้าด้วยกัน คุณสามารถพิจารณาการเคลื่อนไหวในทิศทางที่ต่างกันและเลือกตัวเลือกที่ดีที่สุด
อย่างไรก็ตาม ในสภาพแวดล้อมที่ซับซ้อนซึ่งมีทางตันและทางเลือกว่าจะไปทางไหน เราต้องการอะไรที่ล้ำหน้ากว่านี้อีก
กำลังหาวิธี
พฤติกรรมการบังคับเลี้ยวเหมาะสำหรับการเคลื่อนไหวง่ายๆ ในพื้นที่เปิดโล่ง (สนามฟุตบอลหรือสนามกีฬา) ซึ่งการเดินทางจาก A ไป B เป็นเส้นทางตรงที่มีทางเบี่ยงเล็กน้อยรอบสิ่งกีดขวาง สำหรับเส้นทางที่ซับซ้อน เราจำเป็นต้องมีการค้นหาเส้นทาง ซึ่งเป็นวิธีหนึ่งในการสำรวจโลกและตัดสินใจเลือกเส้นทางผ่านโลกนั้น
วิธีที่ง่ายที่สุดคือการใช้ตารางกับแต่ละช่องถัดจากเอเจนต์ และประเมินว่าช่องใดได้รับอนุญาตให้ย้ายได้ หากหนึ่งในนั้นคือจุดหมายปลายทาง ให้เดินตามเส้นทางจากแต่ละจัตุรัสไปยังจัตุรัสก่อนหน้าจนกว่าจะถึงจุดเริ่มต้น นี่คือเส้นทาง หรือทำซ้ำขั้นตอนนี้กับช่องอื่นๆ ที่อยู่ใกล้เคียงจนกว่าคุณจะพบจุดหมายปลายทางหรือช่องสี่เหลี่ยมหมด (หมายความว่าไม่มีเส้นทางที่เป็นไปได้) นี่คือสิ่งที่เรียกอย่างเป็นทางการว่าการค้นหาแบบกว้างก่อนหรือ BFS (อัลกอริธึมการค้นหาแบบกว้างก่อน) ในทุกย่างก้าวพระองค์ทรงมองไปทุกทิศทุกทาง (ดังนั้นความกว้างจึงเรียกว่า "ความกว้าง") พื้นที่ค้นหาเปรียบเสมือนหน้าคลื่นที่เคลื่อนที่ไปจนถึงตำแหน่งที่ต้องการ - พื้นที่ค้นหาจะขยายในแต่ละขั้นตอนจนกระทั่งถึงจุดสิ้นสุดรวมอยู่ด้วย หลังจากนั้นจึงสามารถย้อนกลับไปยังจุดเริ่มต้นได้
เป็นผลให้คุณจะได้รับรายการช่องสี่เหลี่ยมตามเส้นทางที่ต้องการ นี่คือเส้นทาง (ดังนั้น การค้นหาเส้นทาง) - รายชื่อสถานที่ที่ตัวแทนจะเยี่ยมชมขณะติดตามจุดหมายปลายทาง
เนื่องจากเรารู้ตำแหน่งของทุกสี่เหลี่ยมในโลก เราจึงสามารถใช้พฤติกรรมการบังคับทิศทางเพื่อเคลื่อนที่ไปตามเส้นทาง - จากโหนด 1 ไปยังโหนด 2 จากโหนด 2 ไปยังโหนด 3 และอื่นๆ ทางเลือกที่ง่ายที่สุดคือมุ่งหน้าไปตรงกลางของสี่เหลี่ยมถัดไป แต่ทางเลือกที่ดีกว่าคือหยุดตรงกลางขอบระหว่างสี่เหลี่ยมปัจจุบันกับสี่เหลี่ยมถัดไป ด้วยเหตุนี้เจ้าหน้าที่จึงสามารถตัดโค้งได้เมื่อถึงโค้งหักศอก
อัลกอริธึม BFS ก็มีข้อเสียเช่นกัน โดยจะสำรวจกำลังสองในทิศทางที่ "ผิด" ได้มากเท่ากับในทิศทาง "ถูก" นี่คือจุดที่อัลกอริธึมที่ซับซ้อนกว่าที่เรียกว่า A* (A star) เข้ามามีบทบาท มันทำงานในลักษณะเดียวกัน แต่แทนที่จะตรวจสอบสี่เหลี่ยมที่อยู่ใกล้เคียงแบบสุ่มสี่สุ่มห้า (จากนั้นก็เป็นเพื่อนบ้านของเพื่อนบ้าน จากนั้นก็เป็นเพื่อนบ้านของเพื่อนบ้านของเพื่อนบ้าน และอื่นๆ) มันจะรวบรวมโหนดลงในรายการและเรียงลำดับเพื่อให้โหนดถัดไปที่ตรวจสอบอยู่เสมอ อันที่นำไปสู่เส้นทางที่สั้นที่สุด โหนดจะถูกจัดเรียงตามฮิวริสติกที่คำนึงถึงสองสิ่ง ได้แก่ "ต้นทุน" ของเส้นทางสมมติไปยังจัตุรัสที่ต้องการ (รวมถึงค่าใช้จ่ายในการเดินทาง) และการประมาณว่าจัตุรัสนั้นอยู่ห่างจากจุดหมายปลายทางมากเพียงใด (ให้น้ำหนักกับการค้นหาใน ทิศทางที่ถูกต้อง)
ตัวอย่างนี้แสดงให้เห็นว่าตัวแทนสำรวจทีละช่อง โดยแต่ละครั้งจะเลือกช่องที่อยู่ติดกันซึ่งมีแนวโน้มมากที่สุด เส้นทางผลลัพธ์จะเหมือนกับ BFS แต่กำลังพิจารณาช่องสี่เหลี่ยมน้อยกว่าในกระบวนการ ซึ่งส่งผลกระทบอย่างมากต่อประสิทธิภาพของเกม
การเคลื่อนไหวโดยไม่มีตาราง
แต่เกมส่วนใหญ่ไม่ได้วางอยู่บนตาราง และมักจะเป็นไปไม่ได้เลยที่จะทำเช่นนั้นโดยไม่สูญเสียความสมจริง จำเป็นต้องมีการประนีประนอม สี่เหลี่ยมจัตุรัสควรมีขนาดเท่าไร? ใหญ่เกินไปและไม่สามารถแสดงทางเดินหรือทางเลี้ยวเล็กๆ ได้อย่างถูกต้อง เล็กเกินไปและจะมีช่องสี่เหลี่ยมมากเกินไปให้ค้นหา ซึ่งท้ายที่สุดจะใช้เวลานานมาก
สิ่งแรกที่ต้องเข้าใจก็คือ mesh ให้กราฟของโหนดที่เชื่อมต่อกัน อัลกอริธึม A* และ BFS ใช้งานได้จริงกับกราฟและไม่สนใจเมชของเราเลย เราสามารถวางโหนดไว้ที่ใดก็ได้ในโลกของเกม ตราบใดที่มีการเชื่อมต่อระหว่างสองโหนดที่เชื่อมต่อกัน เช่นเดียวกับระหว่างจุดเริ่มต้นและจุดสิ้นสุดและอย่างน้อยหนึ่งโหนด อัลกอริธึมก็จะทำงานเหมือนเดิม ซึ่งมักเรียกว่าระบบเวย์พอยท์ เนื่องจากแต่ละโหนดแสดงถึงตำแหน่งที่สำคัญในโลก ซึ่งสามารถเป็นส่วนหนึ่งของเส้นทางสมมุติจำนวนเท่าใดก็ได้
ตัวอย่างที่ 1: ปมในแต่ละตาราง การค้นหาเริ่มต้นจากโหนดที่เอเจนต์ตั้งอยู่และสิ้นสุดที่โหนดของช่องสี่เหลี่ยมที่ต้องการ
ตัวอย่างที่ 2: ชุดโหนดขนาดเล็ก (จุดอ้างอิง) การค้นหาเริ่มต้นที่จัตุรัสของตัวแทน ผ่านโหนดตามจำนวนที่ต้องการ จากนั้นเดินทางต่อไปยังปลายทาง
นี่เป็นระบบที่ยืดหยุ่นและทรงพลังอย่างสมบูรณ์ แต่จำเป็นต้องมีความระมัดระวังในการตัดสินใจว่าจะวางตำแหน่งเวย์พอยท์ที่ไหนและอย่างไร มิฉะนั้น เจ้าหน้าที่อาจมองไม่เห็นจุดที่ใกล้ที่สุดและจะไม่สามารถเริ่มต้นเส้นทางได้ มันคงจะง่ายกว่านี้ถ้าเราสามารถวางจุดอ้างอิงตามเรขาคณิตของโลกได้โดยอัตโนมัติ
นี่คือที่ที่ตาข่ายการนำทางหรือ navmesh (ตาข่ายการนำทาง) ปรากฏขึ้น โดยปกติแล้วจะเป็นตาข่ายสามเหลี่ยม 2 มิติที่วางซ้อนอยู่บนเรขาคณิตของโลก - ไม่ว่าเจ้าหน้าที่จะได้รับอนุญาตให้เดินที่ไหนก็ตาม สามเหลี่ยมแต่ละรูปในเมชจะกลายเป็นโหนดในกราฟ และมีสามเหลี่ยมที่อยู่ติดกันมากถึงสามรูปซึ่งกลายเป็นโหนดที่อยู่ติดกันในกราฟ
ภาพนี้เป็นตัวอย่างจากเครื่องยนต์ Unity ซึ่งวิเคราะห์เรขาคณิตในโลกและสร้าง navmesh (ในภาพหน้าจอเป็นสีฟ้าอ่อน) แต่ละรูปหลายเหลี่ยมใน navmesh คือพื้นที่ที่ตัวแทนสามารถยืนหรือย้ายจากรูปหลายเหลี่ยมหนึ่งไปยังอีกรูปหลายเหลี่ยมได้ ในตัวอย่างนี้ รูปหลายเหลี่ยมมีขนาดเล็กกว่าพื้นที่ที่พวกมันตั้งอยู่ - ซึ่งทำโดยคำนึงถึงขนาดของเอเจนต์ซึ่งจะขยายเกินตำแหน่งที่ระบุ
เราสามารถค้นหาเส้นทางผ่านตาข่ายนี้ได้อีกครั้งโดยใช้อัลกอริธึม A* สิ่งนี้จะทำให้เรามีเส้นทางที่เกือบจะสมบูรณ์แบบในโลก ซึ่งคำนึงถึงเรขาคณิตทั้งหมด และไม่ต้องใช้โหนดที่ไม่จำเป็นและการสร้างจุดอ้างอิง
การค้นหาเส้นทางเป็นหัวข้อที่กว้างเกินไปซึ่งมีเพียงส่วนหนึ่งของบทความไม่เพียงพอ หากคุณต้องการศึกษารายละเอียดเพิ่มเติมสิ่งนี้จะช่วยได้ .
Планирование
เราได้เรียนรู้จากการค้นหาเส้นทางว่าบางครั้งการเลือกทิศทางแล้วเคลื่อนที่อย่างเดียวนั้นไม่เพียงพอ เราต้องเลือกเส้นทางและเลี้ยวสองสามรอบเพื่อไปยังจุดหมายปลายทางที่ต้องการ เราสามารถสรุปแนวคิดนี้ได้: การบรรลุเป้าหมายไม่ใช่แค่ขั้นตอนต่อไป แต่เป็นลำดับทั้งหมดที่บางครั้งคุณต้องมองไปข้างหน้าหลายขั้นตอนเพื่อดูว่าขั้นตอนแรกควรเป็นอย่างไร นี่เรียกว่าการวางแผน การค้นหาเส้นทางถือได้ว่าเป็นหนึ่งในส่วนขยายของการวางแผน ในแง่ของวงจรการรับรู้/การคิด/การกระทำ นี่คือจุดที่ส่วน Think วางแผนส่วน Act หลายส่วนสำหรับอนาคต
มาดูตัวอย่างเกมกระดาน Magic: The Gathering กัน เราไปก่อนด้วยชุดไพ่ต่อไปนี้ในมือ:
- Swamp - ให้มานาสีดำ 1 อัน (การ์ดแลนด์)
- ป่า - ให้มานาสีเขียว 1 อัน (การ์ดที่ดิน)
- Fugitive Wizard - ต้องใช้มานาสีน้ำเงิน 1 อันในการอัญเชิญ
- Elvish Mystic - ต้องใช้มานาสีเขียว 1 อันในการอัญเชิญ
เราเพิกเฉยต่อไพ่สามใบที่เหลือเพื่อให้ง่ายขึ้น ตามกฎแล้ว ผู้เล่นได้รับอนุญาตให้เล่นการ์ดบนบกได้ 1 ใบต่อเทิร์น เขาสามารถ "แตะ" การ์ดใบนี้เพื่อดึงมานาจากนั้นจึงร่ายคาถา (รวมถึงการเรียกสิ่งมีชีวิต) ตามจำนวนมานา ในสถานการณ์นี้ ผู้เล่นที่เป็นมนุษย์รู้ว่าต้องเล่น Forest แตะ 1 มานาสีเขียว จากนั้นเรียก Elvish Mystic แต่เกม AI จะคิดเรื่องนี้ได้อย่างไร?
การวางแผนที่ง่าย
แนวทางเล็กๆ น้อยๆ คือพยายามทำทีละอย่างตามลำดับจนกว่าจะไม่มีอันที่เหมาะสมเหลืออยู่ เมื่อดูไพ่ AI จะเห็นว่า Swamp สามารถเล่นอะไรได้บ้าง และเขาก็เล่นมัน ในเทิร์นนี้ยังมีการดำเนินการอื่นอีกหรือไม่ ไม่สามารถเรียก Elvish Mystic หรือ Fugitive Wizard ได้ เนื่องจากต้องใช้มานาสีเขียวและสีน้ำเงินตามลำดับเพื่อเรียกออกมา ในขณะที่ Swamp จะให้มานาสีดำเท่านั้น และเขาจะไม่สามารถเล่น Forest ได้อีกต่อไป เพราะเขาเล่น Swamp ไปแล้ว ดังนั้นเกม AI จึงเป็นไปตามกฎ แต่ก็ทำได้ไม่ดี สามารถปรับปรุงได้
การวางแผนสามารถค้นหารายการการดำเนินการที่ทำให้เกมอยู่ในสถานะที่ต้องการ เช่นเดียวกับทุกตารางบนเส้นทางที่มีเพื่อนบ้าน (ในการค้นหาเส้นทาง) ทุกการกระทำในแผนก็มีเพื่อนบ้านหรือผู้สืบทอดเช่นกัน เราสามารถมองหาการกระทำเหล่านี้และการกระทำที่ตามมาได้จนกว่าจะถึงสภาวะที่ต้องการ
ในตัวอย่างของเรา ผลลัพธ์ที่ต้องการคือ “เรียกสิ่งมีชีวิตถ้าเป็นไปได้” เมื่อเริ่มเทิร์น เราเห็นเพียงสองการกระทำที่เป็นไปได้ตามกฎของเกม:
1. เล่น Swamp (ผลลัพธ์: Swamp ในเกม)
2. เล่น Forest (ผลลัพธ์: Forest ในเกม)
การดำเนินการแต่ละครั้งสามารถนำไปสู่การดำเนินการเพิ่มเติมและปิดการดำเนินการอื่นๆ ได้อีกครั้ง ขึ้นอยู่กับกฎของเกม ลองนึกภาพเราเล่น Swamp - การดำเนินการนี้จะลบ Swamp ในขั้นตอนถัดไป (เราเล่นไปแล้ว) และจะเป็นการลบ Forest ด้วย (เพราะตามกฎแล้ว คุณสามารถเล่นการ์ดแลนด์ได้หนึ่งใบต่อเทิร์น) หลังจากนี้ AI จะเพิ่มมานาสีดำ 1 อันเป็นขั้นตอนต่อไปเนื่องจากไม่มีทางเลือกอื่น หากเขาเลือก Tap the Swamp เขาจะได้รับมานาสีดำ 1 หน่วย และจะไม่สามารถทำอะไรกับมันได้
1. เล่น Swamp (ผลลัพธ์: Swamp ในเกม)
1.1 “แตะ” หนองน้ำ (ผลลัพธ์: หนองน้ำ “แตะ”, มานาสีดำ +1 หน่วย)
ไม่มีการดำเนินการใด ๆ - สิ้นสุด
2. เล่น Forest (ผลลัพธ์: Forest ในเกม)
รายการการกระทำนั้นสั้น เรามาถึงทางตันแล้ว เราทำซ้ำขั้นตอนต่อไป เราเล่น Forest เปิดแอคชั่น "รับ 1 มานาสีเขียว" ซึ่งจะเปิดแอคชั่นที่สาม - เรียก Elvish Mystic
1. เล่น Swamp (ผลลัพธ์: Swamp ในเกม)
1.1 “แตะ” หนองน้ำ (ผลลัพธ์: หนองน้ำ “แตะ”, มานาสีดำ +1 หน่วย)
ไม่มีการดำเนินการใด ๆ - สิ้นสุด
2. เล่น Forest (ผลลัพธ์: Forest ในเกม)
2.1 ป่า “แตะ” (ผลลัพธ์: ป่าถูก “แตะ”, มานาสีเขียว +1 หน่วย)
2.1.1 อัญเชิญ Elvish Mystic (ผลลัพธ์: Elvish Mystic อยู่ในเกม, -1 มานาสีเขียว)
ไม่มีการดำเนินการใด ๆ - สิ้นสุด
ในที่สุด เราก็สำรวจการกระทำที่เป็นไปได้ทั้งหมดและพบแผนการเรียกสิ่งมีชีวิตออกมา
นี่เป็นตัวอย่างที่ง่ายมาก ขอแนะนำให้เลือกแผนงานที่ดีที่สุด แทนที่จะเลือกแผนใดๆ ที่ตรงตามเกณฑ์บางประการ โดยทั่วไปมีความเป็นไปได้ที่จะประเมินแผนที่เป็นไปได้โดยพิจารณาจากผลลัพธ์หรือผลประโยชน์โดยรวมของการดำเนินการ คุณสามารถให้คะแนนตัวเองได้ 1 คะแนนสำหรับการเล่นการ์ดที่ดิน และ 3 คะแนนสำหรับการอัญเชิญสิ่งมีชีวิต การเล่น Swamp จะเป็นแผน 1 แต้ม และการเล่น Forest → Tap the Forest → อัญเชิญ Elvish Mystic จะได้รับ 4 แต้มทันที
นี่คือวิธีการวางแผนใน Magic: The Gathering แต่ตรรกะเดียวกันนี้ใช้กับสถานการณ์อื่นได้ เช่น ย้ายโรงจำนำเพื่อให้มีที่ว่างให้อธิการได้เล่นหมากรุก หรือหาที่กำบังหลังกำแพงเพื่อถ่ายภาพใน XCOM อย่างปลอดภัยเช่นนี้ โดยทั่วไปแล้ว คุณจะเข้าใจแนวคิดนี้
การวางแผนที่ดีขึ้น
บางครั้งอาจมีการดำเนินการที่เป็นไปได้มากเกินไปที่จะพิจารณาทุกตัวเลือกที่เป็นไปได้ กลับมาที่ตัวอย่างด้วย Magic: The Gathering: สมมติว่าในเกมและในมือของคุณมีการ์ดที่ดินและสิ่งมีชีวิตหลายใบ - จำนวนการเคลื่อนไหวที่เป็นไปได้รวมกันอาจเป็นหลายสิบ มีวิธีแก้ไขปัญหาหลายประการ
วิธีแรกคือการผูกมัดย้อนกลับ แทนที่จะลองใช้ชุดค่าผสมทั้งหมด ควรเริ่มต้นด้วยผลลัพธ์สุดท้ายแล้วลองค้นหาเส้นทางโดยตรงแทน แทนที่จะไปจากรากของต้นไม้ไปยังใบใดใบหนึ่ง เราจะเคลื่อนที่ไปในทิศทางตรงกันข้าม - จากใบไปยังราก วิธีนี้ง่ายและรวดเร็วยิ่งขึ้น
หากศัตรูมีพลังชีวิต 1 แต้ม คุณจะพบแผน "สร้างความเสียหาย 1 หรือมากกว่า" เพื่อให้บรรลุเป้าหมายนี้ ต้องปฏิบัติตามเงื่อนไขหลายประการ:
1. ความเสียหายอาจเกิดจากการร่ายมนตร์ - จะต้องอยู่ในมือ
2. คุณต้องใช้มานาในการเสกคาถา
3. ในการรับมานา คุณต้องเล่นแลนด์การ์ด
4. ในการเล่นแลนด์การ์ด คุณต้องมีมันอยู่ในมือ
อีกวิธีหนึ่งคือการค้นหาที่ดีที่สุดก่อน แทนที่จะลองทุกเส้นทาง เราเลือกเส้นทางที่เหมาะสมที่สุด บ่อยครั้งที่วิธีนี้ให้แผนงานที่เหมาะสมที่สุดโดยไม่ต้องเสียค่าใช้จ่ายในการค้นหาที่ไม่จำเป็น A* เป็นรูปแบบหนึ่งของการค้นหาครั้งแรกที่ดีที่สุด - โดยการตรวจสอบเส้นทางที่มีแนวโน้มมากที่สุดตั้งแต่ต้น จะทำให้สามารถค้นหาเส้นทางที่ดีที่สุดได้โดยไม่ต้องตรวจสอบตัวเลือกอื่น ๆ
ตัวเลือกการค้นหาที่ดีที่สุดเป็นอันดับแรกที่น่าสนใจและได้รับความนิยมมากขึ้นเรื่อยๆ คือ Monte Carlo Tree Search แทนที่จะคาดเดาว่าแผนใดดีกว่าแผนอื่นเมื่อเลือกการกระทำแต่ละครั้งที่ตามมา อัลกอริธึมจะสุ่มเลือกผู้สืบทอดในแต่ละขั้นตอนจนกว่าจะถึงจุดสิ้นสุด (เมื่อแผนส่งผลให้เกิดชัยชนะหรือพ่ายแพ้) ผลลัพธ์สุดท้ายจะถูกนำมาใช้เพื่อเพิ่มหรือลดน้ำหนักของตัวเลือกก่อนหน้า ด้วยการทำซ้ำขั้นตอนนี้หลายครั้งติดต่อกัน อัลกอริธึมจะให้การประมาณที่ดีว่าการเคลื่อนไหวครั้งต่อไปที่ดีที่สุดคืออะไร แม้ว่าสถานการณ์จะเปลี่ยนไป (หากศัตรูดำเนินการเพื่อรบกวนผู้เล่น)
เรื่องราวเกี่ยวกับการวางแผนในเกมจะไม่สมบูรณ์หากไม่มีการวางแผนปฏิบัติการที่มุ่งเน้นเป้าหมายหรือ GOAP (การวางแผนการดำเนินการที่มุ่งเน้นเป้าหมาย) นี่เป็นวิธีการที่ใช้กันอย่างแพร่หลายและมีการพูดคุยกัน แต่นอกเหนือจากรายละเอียดที่แตกต่างบางประการแล้ว มันยังเป็นวิธีการเชื่อมโยงแบบย้อนกลับที่เราพูดถึงก่อนหน้านี้อีกด้วย หากวัตถุประสงค์คือการ "ทำลายผู้เล่น" และผู้เล่นอยู่หลังที่กำบัง แผนอาจเป็นดังนี้: ทำลายด้วยระเบิด → รับมัน → ขว้างมัน
โดยปกติแล้วจะมีหลายเป้าหมาย โดยแต่ละเป้าหมายจะมีลำดับความสำคัญของตัวเอง หากไม่สามารถบรรลุวัตถุประสงค์ที่มีลำดับความสำคัญสูงสุดได้ (ไม่มีการรวมกันของการกระทำใดที่สร้างแผน "ฆ่าผู้เล่น" เนื่องจากมองไม่เห็นผู้เล่น) AI จะถอยกลับไปยังวัตถุประสงค์ที่มีลำดับความสำคัญต่ำกว่า
การฝึกอบรมและการปรับตัว
เราได้กล่าวไปแล้วว่าเกม AI มักจะไม่ใช้การเรียนรู้ของเครื่องเพราะไม่เหมาะกับการจัดการตัวแทนแบบเรียลไทม์ แต่ไม่ได้หมายความว่าคุณไม่สามารถยืมบางสิ่งบางอย่างจากบริเวณนี้ได้ เราต้องการคู่ต่อสู้ที่เป็นมือปืนที่เราสามารถเรียนรู้บางอย่างได้ ตัวอย่างเช่น ค้นหาตำแหน่งที่ดีที่สุดบนแผนที่ หรือคู่ต่อสู้ในเกมต่อสู้ที่จะบล็อกท่าคอมโบที่ผู้เล่นใช้บ่อยกระตุ้นให้เขาใช้ท่าอื่น ดังนั้นแมชชีนเลิร์นนิงจึงค่อนข้างมีประโยชน์ในสถานการณ์เช่นนี้
สถิติและความน่าจะเป็น
ก่อนที่เราจะพูดถึงตัวอย่างที่ซับซ้อน เรามาดูกันว่าเราจะไปได้ไกลแค่ไหนโดยการวัดง่ายๆ เพียงไม่กี่อย่างแล้วนำไปใช้ในการตัดสินใจ ตัวอย่างเช่น กลยุทธ์แบบเรียลไทม์ - เราจะทราบได้อย่างไรว่าผู้เล่นสามารถโจมตีในช่วงสองสามนาทีแรกของเกมได้หรือไม่ และต้องเตรียมการป้องกันอะไรบ้าง เราสามารถศึกษาประสบการณ์ในอดีตของผู้เล่นเพื่อทำความเข้าใจว่าปฏิกิริยาในอนาคตจะเป็นอย่างไร ประการแรกเราไม่มีข้อมูลดิบดังกล่าว แต่เราสามารถรวบรวมได้ - ทุกครั้งที่ AI เล่นกับมนุษย์จะสามารถบันทึกเวลาของการโจมตีครั้งแรกได้ หลังจากผ่านไป XNUMX-XNUMX เซสชัน เราจะทราบเวลาโดยเฉลี่ยที่ผู้เล่นใช้ในการโจมตีในอนาคต
นอกจากนี้ยังมีปัญหากับค่าเฉลี่ย: หากผู้เล่นวิ่ง 20 ครั้งและเล่นช้า 20 ครั้ง ค่าที่ต้องการจะอยู่ตรงกลางและสิ่งนี้จะไม่ให้ประโยชน์อะไรแก่เรา วิธีแก้ปัญหาหนึ่งคือการจำกัดข้อมูลที่ป้อนเข้า - สามารถพิจารณา 20 ชิ้นสุดท้ายได้
วิธีการที่คล้ายกันนี้ใช้ในการประมาณความน่าจะเป็นของการกระทำบางอย่างโดยสมมติว่าการตั้งค่าในอดีตของผู้เล่นจะเหมือนเดิมในอนาคต หากผู้เล่นโจมตีเราห้าครั้งด้วยลูกไฟ สองครั้งด้วยสายฟ้า และอีกครั้งด้วยการโจมตีระยะประชิด เห็นได้ชัดว่าเขาชอบลูกไฟมากกว่า ลองคาดการณ์และดูความน่าจะเป็นของการใช้อาวุธที่แตกต่างกัน: ลูกไฟ=62,5%, สายฟ้า=25% และระยะประชิด=12,5% เกม AI ของเราต้องเตรียมการป้องกันตัวเองจากไฟ
อีกวิธีที่น่าสนใจคือการใช้ Naive Bayes Classifier เพื่อศึกษาข้อมูลอินพุตจำนวนมากและจำแนกสถานการณ์เพื่อให้ AI ตอบสนองในลักษณะที่ต้องการ ตัวแยกประเภทแบบเบย์เป็นที่รู้จักกันดีที่สุดสำหรับการใช้งานในตัวกรองสแปมอีเมล พวกเขาตรวจสอบคำเหล่านั้นที่นั่น เปรียบเทียบกับตำแหน่งที่คำเหล่านั้นเคยปรากฏมาก่อน (เป็นสแปมหรือไม่ก็ได้) และสรุปเกี่ยวกับอีเมลที่เข้ามา เราสามารถทำสิ่งเดียวกันได้แม้จะมีอินพุตน้อยลงก็ตาม จากข้อมูลที่เป็นประโยชน์ทั้งหมดที่ AI เห็น (เช่น หน่วยศัตรูถูกสร้างขึ้น หรือคาถาใดที่พวกเขาใช้ หรือเทคโนโลยีใดที่พวกเขาค้นคว้า) และผลลัพธ์สุดท้าย (สงครามหรือสันติภาพ การเร่งรีบหรือการป้องกัน ฯลฯ) - เราจะเลือกพฤติกรรม AI ที่ต้องการ
วิธีการฝึกอบรมทั้งหมดนี้เพียงพอแล้ว แต่ขอแนะนำให้ใช้ตามข้อมูลการทดสอบ AI จะเรียนรู้ที่จะปรับให้เข้ากับกลยุทธ์ต่างๆ ที่ผู้ทดสอบของคุณใช้ AI ที่ปรับให้เข้ากับผู้เล่นหลังการเปิดตัวอาจคาดเดาได้ยากเกินไปหรือยากเกินไปที่จะเอาชนะ
การปรับตัวตามมูลค่า
ด้วยเนื้อหาของโลกเกมของเราและกฎเกณฑ์ต่างๆ เราสามารถเปลี่ยนชุดค่าที่มีอิทธิพลต่อการตัดสินใจ แทนที่จะใช้เพียงข้อมูลอินพุต เราทำสิ่งนี้:
- ให้ AI รวบรวมข้อมูลสถานะของโลกและเหตุการณ์สำคัญระหว่างเกม (ดังที่กล่าวข้างต้น)
- มาเปลี่ยนค่าสำคัญสองสามค่าตามข้อมูลนี้กัน
- เราใช้การตัดสินใจของเราตามการประมวลผลหรือการประเมินค่าเหล่านี้
ตัวอย่างเช่น เจ้าหน้าที่มีหลายห้องให้เลือกบนแผนที่เกมยิงมุมมองบุคคลที่หนึ่ง แต่ละห้องมีคุณค่าในตัวเอง ซึ่งเป็นตัวกำหนดว่าน่าไปเยี่ยมชมเพียงใด AI จะสุ่มเลือกห้องที่จะเข้าตามค่า เจ้าหน้าที่จะจำได้ว่าห้องไหนที่เขาถูกฆ่าและลดมูลค่าลง (ความน่าจะเป็นที่เขาจะกลับมาที่นั่น) ในทำนองเดียวกันสำหรับสถานการณ์ย้อนกลับ - หากตัวแทนทำลายคู่ต่อสู้จำนวนมาก มูลค่าของห้องจะเพิ่มขึ้น
แบบจำลองมาร์คอฟ
จะเกิดอะไรขึ้นถ้าเราใช้ข้อมูลที่รวบรวมมาเพื่อคาดการณ์? หากเราจำทุกห้องที่เราเห็นผู้เล่นเข้ามาในช่วงระยะเวลาหนึ่ง เราจะคาดเดาได้ว่าผู้เล่นจะไปเข้าห้องไหน ด้วยการติดตามและบันทึกการเคลื่อนไหวของผู้เล่นในห้องต่างๆ (ค่า) เราสามารถคาดการณ์ได้
มาดูสามห้องกัน: แดง เขียว และน้ำเงิน และข้อสังเกตที่เราบันทึกไว้ขณะดูเซสชั่นเกม:
จำนวนการสังเกตในแต่ละห้องเกือบจะเท่ากัน - เรายังไม่รู้ว่าจะสร้างสถานที่ที่ดีสำหรับการซุ่มโจมตีได้ที่ไหน การรวบรวมสถิติก็มีความซับซ้อนเช่นกันโดยการเกิดใหม่ของผู้เล่นซึ่งปรากฏอย่างเท่าเทียมกันทั่วทั้งแผนที่ แต่ข้อมูลเกี่ยวกับห้องถัดไปที่พวกเขาเข้าไปหลังจากปรากฏบนแผนที่ก็มีประโยชน์อยู่แล้ว
จะเห็นได้ว่าห้องสีเขียวเหมาะกับผู้เล่น คนส่วนใหญ่ย้ายจากห้องสีแดงไปที่ห้องนั้น โดย 50% ยังคงอยู่ที่นั่นต่อไป ตรงกันข้ามห้องสีฟ้าไม่เป็นที่นิยมเลยแทบจะไม่มีใครไปและถ้าไปก็อยู่ได้ไม่นาน
แต่ข้อมูลบอกเราถึงบางสิ่งที่สำคัญกว่า เมื่อผู้เล่นอยู่ในห้องสีน้ำเงิน ห้องถัดไปที่เราเห็นเขาอยู่จะเป็นสีแดง ไม่ใช่สีเขียว แม้ว่าห้องสีเขียวจะได้รับความนิยมมากกว่าห้องสีแดง แต่สถานการณ์จะเปลี่ยนไปหากผู้เล่นอยู่ในห้องสีน้ำเงิน สถานะถัดไป (เช่น ห้องที่ผู้เล่นจะไป) ขึ้นอยู่กับสถานะก่อนหน้า (เช่น ห้องที่ผู้เล่นอยู่ในปัจจุบัน) เนื่องจากเราสำรวจการขึ้นต่อกัน เราจึงคาดการณ์ได้แม่นยำมากกว่าการนับการสังเกตอย่างอิสระ
การทำนายสถานะในอนาคตโดยอาศัยข้อมูลจากสถานะในอดีตเรียกว่าแบบจำลองมาร์คอฟ และตัวอย่างดังกล่าว (พร้อมห้อง) เรียกว่าโซ่มาร์คอฟ เนื่องจากรูปแบบแสดงถึงความน่าจะเป็นของการเปลี่ยนแปลงระหว่างสถานะที่ต่อเนื่องกัน จึงแสดงเป็นภาพเป็น FSM ที่มีความน่าจะเป็นในแต่ละช่วงการเปลี่ยนภาพ ก่อนหน้านี้ เราใช้ FSM เพื่อแสดงสถานะพฤติกรรมที่ตัวแทนอยู่ แต่แนวคิดนี้ขยายไปสู่สถานะใดๆ ไม่ว่าจะเกี่ยวข้องกับตัวแทนหรือไม่ก็ตาม ในกรณีนี้ รัฐจะเป็นตัวแทนของห้องที่ตัวแทนครอบครอง:
นี่เป็นวิธีง่ายๆ ในการแสดงความน่าจะเป็นสัมพัทธ์ของการเปลี่ยนแปลงสถานะ ทำให้ AI สามารถคาดการณ์สถานะต่อไปได้ คุณสามารถคาดหวังล่วงหน้าได้หลายขั้นตอน
หากผู้เล่นอยู่ในห้องสีเขียว มีโอกาส 50% ที่เขาจะยังคงอยู่ที่นั่นในครั้งต่อไปที่เขาถูกพบเห็น แต่โอกาสที่เขาจะยังคงอยู่ที่นั่นหลังจากนั้นมีอะไรบ้าง? ไม่เพียงแต่มีโอกาสที่ผู้เล่นยังคงอยู่ในห้องสีเขียวหลังจากการสังเกตสองครั้ง แต่ยังมีโอกาสที่เขาจากไปและกลับมาอีกด้วย นี่คือตารางใหม่โดยคำนึงถึงข้อมูลใหม่:
แสดงให้เห็นว่าโอกาสที่จะเห็นผู้เล่นในห้องสีเขียวหลังจากการสังเกตสองครั้งจะเท่ากับ 51% - 21% เขาจะมาจากห้องสีแดง 5% ของพวกเขาที่ผู้เล่นจะไปเยี่ยมชมห้องสีน้ำเงินระหว่างพวกเขา และ 25% ที่ผู้เล่นจะไม่ออกจากห้องสีเขียว
ตารางเป็นเพียงเครื่องมือแสดงภาพ ขั้นตอนนี้ต้องการเพียงการคูณความน่าจะเป็นในแต่ละขั้นตอนเท่านั้น ซึ่งหมายความว่าคุณสามารถมองไปไกลถึงอนาคตได้ด้วยข้อแม้ประการหนึ่ง นั่นคือ เราถือว่าโอกาสในการเข้าห้องนั้นขึ้นอยู่กับห้องปัจจุบันทั้งหมด สิ่งนี้เรียกว่าทรัพย์สินมาร์คอฟ - สถานะในอนาคตขึ้นอยู่กับปัจจุบันเท่านั้น แต่นี่ไม่ถูกต้องร้อยเปอร์เซ็นต์ ผู้เล่นสามารถเปลี่ยนการตัดสินใจขึ้นอยู่กับปัจจัยอื่น ๆ เช่น ระดับสุขภาพหรือจำนวนกระสุน เนื่องจากเราไม่บันทึกค่าเหล่านี้ การคาดการณ์ของเราจึงแม่นยำน้อยลง
N-กรัม
แล้วตัวอย่างของเกมต่อสู้และการทำนายท่าคอมโบของผู้เล่นล่ะ? เหมือน! แต่แทนที่จะเป็นสถานะหรือเหตุการณ์เดียว เราจะตรวจสอบลำดับทั้งหมดที่ประกอบเป็นการโจมตีแบบคอมโบ
วิธีหนึ่งในการทำเช่นนี้คือจัดเก็บแต่ละอินพุต (เช่น Kick, Punch หรือ Block) ไว้ในบัฟเฟอร์และเขียนบัฟเฟอร์ทั้งหมดเป็นเหตุการณ์ ดังนั้นผู้เล่นจึงกด Kick, Kick, Punch ซ้ำๆ เพื่อใช้การโจมตีแบบ SuperDeathFist โดยระบบ AI จะเก็บอินพุตทั้งหมดไว้ในบัฟเฟอร์และจดจำ XNUMX ตัวสุดท้ายที่ใช้ในแต่ละขั้นตอน
(เส้นที่เป็นตัวหนาคือตอนที่ผู้เล่นเริ่มการโจมตี SuperDeathFist)
AI จะเห็นตัวเลือกทั้งหมดเมื่อผู้เล่นเลือก Kick ตามด้วย Kick อื่น จากนั้นสังเกตว่าอินพุตถัดไปจะเป็น Punch เสมอ ซึ่งจะทำให้เจ้าหน้าที่คาดการณ์การเคลื่อนที่ของคอมโบของ SuperDeathFist และบล็อกได้หากเป็นไปได้
ลำดับเหตุการณ์เหล่านี้เรียกว่า N-grams โดยที่ N คือจำนวนองค์ประกอบที่เก็บไว้ ในตัวอย่างก่อนหน้านี้ มันคือ 3 กรัม (ไตรแกรม) ซึ่งหมายความว่า: สองรายการแรกใช้ในการทำนายค่าที่สาม ดังนั้น ใน 5 กรัม สี่รายการแรกจะทำนายรายการที่ห้าและต่อๆ ไป
ผู้ออกแบบจะต้องเลือกขนาดของ N-gram อย่างระมัดระวัง 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 chains เพื่อทำนายอินพุตถัดไปและเดาว่าการย้ายคอมโบจะเป็นครั้งต่อไป
ข้อสรุป
เราได้พูดคุยเกี่ยวกับเครื่องมือและแนวทางทั่วไปในการพัฒนาปัญญาประดิษฐ์ นอกจากนี้เรายังพิจารณาถึงสถานการณ์ที่จำเป็นต้องใช้และจุดที่เป็นประโยชน์อย่างยิ่ง
นี่น่าจะเพียงพอที่จะเข้าใจพื้นฐานของเกม AI แต่แน่นอนว่านี่ไม่ใช่ทุกวิธี เป็นที่นิยมน้อยกว่าแต่มีประสิทธิภาพไม่น้อย ได้แก่:
- อัลกอริธึมการหาค่าเหมาะที่สุดรวมถึงการปีนเขา การลงเขาแบบไล่ระดับ และอัลกอริธึมทางพันธุกรรม
- อัลกอริธึมการค้นหา / การตั้งเวลาของฝ่ายตรงข้าม (การตัดแต่งขั้นต่ำและอัลฟ่าเบต้า)
- วิธีการจำแนกประเภท (การรับรู้ โครงข่ายประสาทเทียม และเครื่องสนับสนุนเวกเตอร์)
- ระบบประมวลผลการรับรู้และความจำของตัวแทน
- แนวทางทางสถาปัตยกรรมสำหรับ AI (ระบบไฮบริด สถาปัตยกรรมชุดย่อย และวิธีการอื่นๆ ของการซ้อนทับระบบ AI)
- เครื่องมือแอนิเมชั่น (การวางแผนและประสานงานการเคลื่อนไหว)
- ปัจจัยด้านประสิทธิภาพ (ระดับรายละเอียด เวลาใดก็ได้ และอัลกอริธึมการแบ่งเวลา)
แหล่งข้อมูลออนไลน์ในหัวข้อ:
1.GameDev.net มี และ .
2. มีการนำเสนอและบทความมากมายในหัวข้อต่างๆ ที่เกี่ยวข้องกับการพัฒนา AI ของเกม
3. รวมหัวข้อจากการประชุมสุดยอด GDC AI ซึ่งหลายหัวข้อมีให้บริการฟรี
4. สามารถดูเอกสารที่เป็นประโยชน์ได้จากเว็บไซต์ .
5. Tommy Thompson นักวิจัยด้าน AI และผู้พัฒนาเกม สร้างวิดีโอบน YouTube พร้อมคำอธิบายและการศึกษา AI ในเกมเชิงพาณิชย์
หนังสือในหัวข้อ:
1. หนังสือชุด Game AI Pro คือชุดบทความสั้น ๆ ที่อธิบายวิธีการใช้คุณสมบัติเฉพาะหรือวิธีแก้ปัญหาเฉพาะ
2. ซีรีส์ AI Game Programming Wisdom เป็นซีรีส์รุ่นก่อนของซีรีส์ Game AI Pro มันมีวิธีการแบบเก่า แต่เกือบทั้งหมดมีความเกี่ยวข้องแม้กระทั่งทุกวันนี้
3. เป็นหนึ่งในตำราพื้นฐานสำหรับทุกคนที่ต้องการทำความเข้าใจสาขาปัญญาประดิษฐ์ทั่วไป นี่ไม่ใช่หนังสือเกี่ยวกับการพัฒนาเกม แต่สอนพื้นฐานของ AI
ที่มา: will.com