irpg Community - Profile of Nayru

Nayru

Administrator

Nayru's Signature

Nayru's Forum Info

Total Posts:
266 (0.06 posts per day | 0.96 percent of total posts)

Find All Posts

Total Threads:
7 (0 threads per day | 0.23 percent of total threads)

Find All Threads

Total Thanks Received: 443 (0.1 per day | 1.15 percent of total 38497)
(Find All Threads Thanked For — Find All Posts Thanked For) Total Thanks Given: 997 (0.23 per day | 2.59 percent of total 38497)
(Find All Thanked Threads — Find All Thanked Posts)

Reputation:
0

Details

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 (35 years old)

Local Time: 11-14-2024 at 01:33 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%