+- irpg Community (https://irpg.in.th)
+-- Forum: Imperial School of Art, Literature and Design (https://irpg.in.th/forum-41.html)
+--- Forum: Literature & Design Library (https://irpg.in.th/forum-14.html)
+--- Thread: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI (/thread-1396.html)
[AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - Nayru - 09-14-2013
บทความนี้เป็นบทความแรกของผมนะครับ ผิดพลาดประการใดขออภัยไว้ ณ ที่นี้
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เป้าหมาย
จากที่เห็นข้างต้นก็จะเอามายกตัวอย่างด้วย RM (เพราะมันเป็นตารางช่องๆเข้าใจง่ายดี) โดยมีโจทย์คือ
Quote:เราจะให้หมาน้อยของเราเดินมาหาเราให้ได้ และใช้ระยะทางในการเดินน้อยที่สุด
- จากรูปแรกเลย แน่นอนว่าท่านเดาไม่ผิด เวลาตั้งในRM ให้หมาน้อยของเรา"เดินตามผู้เล่น" มันจะวิ่งมาทางซ้ายโดยไม่สนใจอะไรทั้งสิ้น ไม่ว่าจะมีภูเขาหรือแม่น้ำกั้น มันก็จะดันทุรังเดินมาทางซ้าย ซ้าย และ ซ้าย ซึ่งบ่งบอกถึงความฉลาดของ AI เป็นอย่างมาก/chan ซึ่งเราไม่ต้องการแบบนี้ ดังนี้เราจึงต้องใช้อัลกอริทึม A* มาช่วย
![[Image: path0_zpsc0764754.png]](http://i1343.photobucket.com/albums/o783/Abel_Caelius/path0_zpsc0764754.png)
-ในรูปนี้ แต่ละช่องที่มีตัวเลขจะบ่งบอกถึง h´(S) + g(S) ของช่องนั้นว่าดีแค่ไหน (อย่างที่บอกไป ยิ่งน้อยยิ่งดี)
*ตัวอย่าง cost 1+3 ก็คือ ห่างจากจุดเรื่มต้น1ช่อง และห่างจากจุดเป้าหมาย3ช่อง
**จริงๆA*จะไม่ได้คำนวณ cost ทั้งหมดทุกช่องในทีเดียว จะค่อยๆแตกแขนงไปเรื่อยๆ แต่ในรูปใส่ไปหมดเลยจะได้เห็นภาพหน่อย
![[Image: path1_zps6fdffc1e.png]](http://i1343.photobucket.com/albums/o783/Abel_Caelius/path1_zps6fdffc1e.png)
-หลังจากนั้นก็จะเริ่มการค้นหาเส้นทางโดยจากจุดเริ่มต้น โดยไปทางที่ cost น้อยที่สุดก่อน หากไปแล้วตันหรือไม่พบว่าเป็น stateเ้ป้าหมาย ก็จะเปลี่ยนไปในทางที่ cost สูงกว่าเดิม ทำไปเรื่อยๆจนกว่าจะพบ stateเป้าหมาย หากไม่มีการพบstateเป้าหมายเลย นั่นหมายถึงไม่มีเส้นทางให้เราไปเป้าหมายนั้นได้นั่นเอง
![[Image: path2_zpsab7911f6.png]](http://i1343.photobucket.com/albums/o783/Abel_Caelius/path2_zpsab7911f6.png)
ตัวอย่างการทำงานของ A* ในรูปแบบภาพเคลื่อนไหว(จากwikipedia)
-อย่างรูปนี้A*จะพบว่าระหว่างจุดaกับจุดdนั้น ไปทางจุดaจะดีกว่าเพราะcostน้อยกว่า แต่พอไปถึงจุดb พบว่าการไปจุดcต่อนั้นไม่ได้ดีกว่าการไปจุดdแล้ว จึงเปลี่ยนมาค้นหาเส้นทางทางจุดdแทน
![[Image: AstarExample.gif]](http://upload.wikimedia.org/wikipedia/commons/5/5d/AstarExample.gif)
-รูปที่2นี้แบบรูปการทำงานของ pathfinding สังเกตุว่าช่วงต้นจะพยายามไปทางที่สั้นที่สุด(นั่นคือตรงไปยังเป้าหมายเลย)แต่ติดกำแพง จึงต้องเปลี่ยนเส้นทางมาใช้เส้นที่ cost เพิ่มขึ้นเล็กน้อย(ค่อยๆอ้อมไปทีละนิด) จนกระทั่งเจอเส้นที่อ้อมน้อยที่สุด
![[Image: Astar_progress_animation.gif]](http://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif)
ตัวอย่างการนำไปปรับใช้กับ Engineต่างๆ
-Game Maker
http://irpg.in.th/thread-1392.html (โดยท่านนิราจ)
-Rpgmaker
http://forums.rpgmakerweb.com/index.php?/topic/1640-near-fantasticas-path-finder-v1-for-rpg-maker-vx-ace/
**มีข้อเสนอแนะหรือคำถามอะไร โพสต์ไว้ได้เลยนะครับ
RE: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - Nazuth - 09-14-2013
พอจะเข้าใจสมการแต่จะงงตอนไปเขียน Ruby นี่แหละ
RE: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - นิราจ - 09-14-2013
สุดยอดเลยครับ สูตรครบเลย
มีคำอธิบายบางอันที่ผมไม่ได้เรียนด้วยครับ
ขอบคุณคับ
RE: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - arkman - 09-15-2013
ขออภัย ผมดูแล้วผมงงครับ แบบว่าตกเลข(จริงๆครับ ได้0กับ1)
RE: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - Nayru - 09-15-2013
(09-14-2013, 04:28 PM)natsukikung Wrote: พอจะเข้าใจสมการแต่จะงงตอนไปเขียน Ruby นี่แหละมีตัวอย่างให้ลองแกะๆดูนะครับ ^^
(09-14-2013, 04:34 PM)นิราจ Wrote: สุดยอดเลยครับ สูตรครบเลยถ้าท่านนิราจอยากเสริมส่วนไหน ลงได้เลยเน้อ
มีคำอธิบายบางอันที่ผมไม่ได้เรียนด้วยครับ
ขอบคุณคับ
(09-15-2013, 05:28 PM)arkman Wrote: ขออภัย ผมดูแล้วผมงงครับ แบบว่าตกเลข(จริงๆครับ ได้0กับ1)เข้าใจคอนเซ็ปต์ของมันก็พอครับ อิอิ ส่วนมากหลายๆเอ็นจิ้นเขาก็มีพวกนี้มาให้อยู่แ้ล้วล่ะ
RE: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - Mysticphoenix - 09-16-2013
ใช้สคริป pathfinding โดยพลัน