[AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI

Nayru 09-14-2013, 04:05 PM

บทความนี้เป็นบทความแรกของผมนะครับ ผิดพลาดประการใดขออภัยไว้ ณ ที่นี้
Credit : Dr. Tanasanee Phienthrakul

หลายท่านอาจจะเคยสงสัยว่า
"เอ๊ะ! ตัวละคร/ศัตรูในหลายๆเกม ทำไมมันถึงฉลาดจัง" ไม่ว่าเราจะเดินหนีเลี้ยวเข้าซอยนู้น หลบซอยนี้ มันก็ยังเดินตามมาได้ ในขณะที่เราๆพอทำเกมเอง "ศัตรูทำไมมันไม่ฉลาดเลย เดินอ้อมเข้าประตูมาหาเราก็ทำไม่ได้" ได้แต่ยืนจ้องหน้าเราผ่านกระจกบางๆที่กั้นอยู่

วันนี้ผมเลยมาสอนเป็นคอนเซ็ปต์ในเห็นภาพกันว่าการทำงานของ AI ในหลายๆเกมเขาทำงานกันประมาณไหน (ส่วนแต่ละเอ็นจิ้นทำยังไงต้องไปปรับใช้เอาเองนะครับ)

A* Search
A* Search เป็นอัลกอริทึมการค้นหาสำหรับ AI ที่มักนำมาใช้กันในการทำ pathfinding เนื่องจากจะได้เส้นทางที่สูญเสีย cost น้อยที่สุด (ถ้าว่ากันแบบบ้านๆก็เส้นทางที่สั้นที่สุดนั่นแหล่ะ)

สามารถศึกษาและดูภาพประกอบเพิ่มเติมได้ที่
http://en.wikipedia.org/wiki/A*_search_algorithm

มาดูสมการการคำนวณ cost ของแต่ละจุดกัน

Quote:f´(S) = h´(S) + g(S)

โดยที่

h´ คือ ฟังก์ชันที่ประมาณ cost จาก stateปัจจุบัน ถึง stateเป้าหมาย
g คือ ฟังก์ชันที่คำนวณ cost จาก stateเริ่มต้น ถึง stateปัจจุบัน
f´ จึงเป็นฟังก์ชันที่ประมาณ cost จาก stateเริ่มต้น ถึง stateเป้าหมาย

(state ที่ดี f´ จะมีค่าน้อย)

จากที่เห็นข้างต้นก็จะเอามายกตัวอย่างด้วย RM (เพราะมันเป็นตารางช่องๆเข้าใจง่ายดี) โดยมีโจทย์คือ

Quote:เราจะให้หมาน้อยของเราเดินมาหาเราให้ได้ และใช้ระยะทางในการเดินน้อยที่สุด

- จากรูปแรกเลย แน่นอนว่าท่านเดาไม่ผิด เวลาตั้งในRM ให้หมาน้อยของเรา"เดินตามผู้เล่น" มันจะวิ่งมาทางซ้ายโดยไม่สนใจอะไรทั้งสิ้น ไม่ว่าจะมีภูเขาหรือแม่น้ำกั้น มันก็จะดันทุรังเดินมาทางซ้าย ซ้าย และ ซ้าย ซึ่งบ่งบอกถึงความฉลาดของ AI เป็นอย่างมาก/chan ซึ่งเราไม่ต้องการแบบนี้ ดังนี้เราจึงต้องใช้อัลกอริทึม A* มาช่วย
[Image: path0_zpsc0764754.png]

-ในรูปนี้ แต่ละช่องที่มีตัวเลขจะบ่งบอกถึง h´(S) + g(S) ของช่องนั้นว่าดีแค่ไหน (อย่างที่บอกไป ยิ่งน้อยยิ่งดี)
*ตัวอย่าง cost 1+3 ก็คือ ห่างจากจุดเรื่มต้น1ช่อง และห่างจากจุดเป้าหมาย3ช่อง
**จริงๆA*จะไม่ได้คำนวณ cost ทั้งหมดทุกช่องในทีเดียว จะค่อยๆแตกแขนงไปเรื่อยๆ แต่ในรูปใส่ไปหมดเลยจะได้เห็นภาพหน่อย
[Image: path1_zps6fdffc1e.png]

-หลังจากนั้นก็จะเริ่มการค้นหาเส้นทางโดยจากจุดเริ่มต้น โดยไปทางที่ cost น้อยที่สุดก่อน หากไปแล้วตันหรือไม่พบว่าเป็น stateเ้ป้าหมาย ก็จะเปลี่ยนไปในทางที่ cost สูงกว่าเดิม ทำไปเรื่อยๆจนกว่าจะพบ stateเป้าหมาย หากไม่มีการพบstateเป้าหมายเลย นั่นหมายถึงไม่มีเส้นทางให้เราไปเป้าหมายนั้นได้นั่นเอง
[Image: path2_zpsab7911f6.png]

ตัวอย่างการทำงานของ A* ในรูปแบบภาพเคลื่อนไหว(จากwikipedia)
-อย่างรูปนี้A*จะพบว่าระหว่างจุดaกับจุดdนั้น ไปทางจุดaจะดีกว่าเพราะcostน้อยกว่า แต่พอไปถึงจุดb พบว่าการไปจุดcต่อนั้นไม่ได้ดีกว่าการไปจุดdแล้ว จึงเปลี่ยนมาค้นหาเส้นทางทางจุดdแทน
[Image: AstarExample.gif]

-รูปที่2นี้แบบรูปการทำงานของ pathfinding สังเกตุว่าช่วงต้นจะพยายามไปทางที่สั้นที่สุด(นั่นคือตรงไปยังเป้าหมายเลย)แต่ติดกำแพง จึงต้องเปลี่ยนเส้นทางมาใช้เส้นที่ cost เพิ่มขึ้นเล็กน้อย(ค่อยๆอ้อมไปทีละนิด) จนกระทั่งเจอเส้นที่อ้อมน้อยที่สุด
[Image: Astar_progress_animation.gif]

ตัวอย่างการนำไปปรับใช้กับ Engineต่างๆ
-Game Maker
http://irpg.in.th/thread-1392.html (โดยท่านนิราจ)
-Rpgmaker
http://forums.rpgmakerweb.com/index.php?...er-vx-ace/

**มีข้อเสนอแนะหรือคำถามอะไร โพสต์ไว้ได้เลยนะครับ

This post was last modified: 09-15-2013, 10:57 PM by Nayru.