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

+- 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เป้าหมาย
(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?/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: สุดยอดเลยครับ สูตรครบเลย
มีคำอธิบายบางอันที่ผมไม่ได้เรียนด้วยครับ
ขอบคุณคับ
ถ้าท่านนิราจอยากเสริมส่วนไหน ลงได้เลยเน้อ Derp


(09-15-2013, 05:28 PM)arkman Wrote: ขออภัย ผมดูแล้วผมงงครับ แบบว่าตกเลข(จริงๆครับ ได้0กับ1)
เข้าใจคอนเซ็ปต์ของมันก็พอครับ อิอิ ส่วนมากหลายๆเอ็นจิ้นเขาก็มีพวกนี้มาให้อยู่แ้ล้วล่ะ ทำหน้าเหยาหมิง


RE: [AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI - Mysticphoenix - 09-16-2013

ใช้สคริป pathfinding โดยพลัน