Nayru

Administrator

Nayru's Signature
[Image: Signature-Alex.png]
Nayru's Forum Info
Total Posts:
266 (0.06 posts per day | 0.96 percent of total posts)
Total Threads:
7 (0 threads per day | 0.23 percent of total threads)
Total Thanks Received: 443 (0.1 per day | 1.15 percent of total 38489)
(Find All Threads Thanked ForFind All Posts Thanked For) Total Thanks Given: 997 (0.23 per day | 2.59 percent of total 38489)
(Find All Thanked ThreadsFind All Thanked Posts)
Reputation:
0
Status:
(Hidden)
Time Spent Online:
(Hidden)
Additional Info About Nayru
Sex
Male
Primarily Uses
Others
Additional Info About Nayru
Joined: 10-11-2012
Last Visit: (Hidden)
Date of Birth: 09-27-1989 (34 years old)
Local Time: 05-30-2024 at 04:49 PM
Nayru's Most Thanked Post
Post Subject Post Date/Time Numbers of Thanks
[AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI 09-14-2013, 04:05 PM 15
Thread Subject Forum Name
[AI เบื้องต้น] ศึกษาการทำงานของ Searching Algorithm ใน AI Imperial School of Art, Literature and Design
Literature & Design Library
Post Message
บทความนี้เป็นบทความแรกของผมนะครับ ผิดพลาดประการใดขออภัยไว้ ณ ที่นี้ 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* มาช่วย http://i1343.photobucket.com/albums/o783/Abel_Caelius/path0_zpsc0764754.png -ในรูปนี้ แต่ละช่องที่มีตัวเลขจะบ่งบอกถึง h´(S) + g(S) ของช่องนั้นว่าดีแค่ไหน (อย่างที่บอกไป ยิ่งน้อยยิ่งดี) *ตัวอย่าง cost 1+3 ก็คือ ห่างจากจุดเรื่มต้น1ช่อง และห่างจากจุดเป้าหมาย3ช่อง **จริงๆA*จะไม่ได้คำนวณ cost ทั้งหมดทุกช่องในทีเดียว จะค่อยๆแตกแขนงไปเรื่อยๆ แต่ในรูปใส่ไปหมดเลยจะได้เห็นภาพหน่อย http://i1343.photobucket.com/albums/o783/Abel_Caelius/path1_zps6fdffc1e.png -หลังจากนั้นก็จะเริ่มการค้นหาเส้นทางโดยจากจุดเริ่มต้น โดยไปทางที่ cost น้อยที่สุดก่อน หากไปแล้วตันหรือไม่พบว่าเป็น stateเ้ป้าหมาย ก็จะเปลี่ยนไปในทางที่ cost สูงกว่าเดิม ทำไปเรื่อยๆจนกว่าจะพบ stateเป้าหมาย หากไม่มีการพบstateเป้าหมายเลย นั่นหมายถึงไม่มีเส้นทางให้เราไปเป้าหมายนั้นได้นั่นเอง http://i1343.photobucket.com/albums/o783/Abel_Caelius/path2_zpsab7911f6.png ตัวอย่างการทำงานของ A* ในรูปแบบภาพเคลื่อนไหว(จากwikipedia) -อย่างรูปนี้A*จะพบว่าระหว่างจุดaกับจุดdนั้น ไปทางจุดaจะดีกว่าเพราะcostน้อยกว่า แต่พอไปถึงจุดb พบว่าการไปจุดcต่อนั้นไม่ได้ดีกว่าการไปจุดdแล้ว จึงเปลี่ยนมาค้นหาเส้นทางทางจุดdแทน http://upload.wikimedia.org/wikipedia/commons/5/5d/AstarExample.gif -รูปที่2นี้แบบรูปการทำงานของ pathfinding สังเกตุว่าช่วงต้นจะพยายามไปทางที่สั้นที่สุด(นั่นคือตรงไปยังเป้าหมายเลย)แต่ติดกำแพง จึงต้องเปลี่ยนเส้นทางมาใช้เส้นที่ cost เพิ่มขึ้นเล็กน้อย(ค่อยๆอ้อมไปทีละนิด) จนกระทั่งเจอเส้นที่อ้อมน้อยที่สุด 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/ **มีข้อเสนอแนะหรือคำถามอะไร โพสต์ไว้ได้เลยนะครับ

Nayru's Received and Given Thanks
  Thanks Received Thanks Given
Last week 0 0
Last month 0 0
Last 3 months 0 0
Last 6 months 0 0
Last 12 months 0 0
All Time 443 997
 
Most thanked by
[IRPG] Kuntana 41 9%
LuZi 38 9%
Pummy 36 8%
arkman 33 7%
[IRPG] bassza123 31 7%
 
Most thanked
LuZi 89 9%
arkman 81 8%
Nazuth 72 7%
Neoz Kaho 45 5%
[IRPG] Kuntana 39 4%

Powered By MyBB, © 2002-2024 MyBB Group.
Made with by Curves UI.