เทคนิคแพรวพราวของอัลกอริทึม A* สำหรับการหาเส้นทางในวิดีโอเกม
(timmastny.com)- ในเกมสไตล์ Zelda มุมมองจากด้านบนแบบ 8 บิต การทำให้ มอนสเตอร์ไล่ล่า ผู้เล่นได้ต้องการมากกว่าการเคลื่อนที่เป็นเส้นตรง จึงเปรียบเทียบ Dijkstra กับ A* เพื่อหาจุดสมดุลของการหาเส้นทางสำหรับเกม
- การเคลื่อนที่เป็นเส้นตรงจะหยุดทันทีเมื่อชนกำแพง แต่ถ้าใส่ wall-sliding เข้าไป ก็จะเคลื่อนที่เลียบกำแพงได้ ทำให้การควบคุมลื่นขึ้น และยังสร้างองค์ประกอบเชิงกลยุทธ์ที่ผู้เล่นใช้ภูมิประเทศขังมอนสเตอร์ได้
- อัลกอริทึม Dijkstra รับประกันเส้นทางที่สั้นที่สุด แต่เพราะมันสำรวจบริเวณรอบโหนดเริ่มต้นอย่างกว้างขวาง ในเกมที่จุดหมายเปลี่ยนทุกเฟรมจึงคำนวณเกินความจำเป็นเมื่อเทียบกับแค่การหา ทิศทางถัดไป
- A* กำหนดลำดับความสำคัญของการค้นหาจากระยะถึงจุดหมาย จึงมองไปทาง ทิศของเป้าหมาย ก่อน และเมื่อเจอกำแพงก็ตรวจโหนดรอบข้างโดยไม่กลับไปเยี่ยมโหนดเดิม ทำให้หาเส้นทางอ้อมได้
- บนแผนที่เกม สามารถใช้ กราฟแบบปริยาย ที่ไม่ต้องสร้าง adjacency list ล่วงหน้า การค้นหาระดับไทล์ และ ฮิวริสติกตามเรขาคณิต อย่างการจำกัดความลึกของรอบค้นหา เพื่อปรับสมดุลทั้งความเร็วและความยากง่ายในการพัฒนา
บริบทของเกมและความต้องการพื้นฐาน
- ในเกมสไตล์ Zelda มุมมองจากด้านบนแบบ 8 บิตที่ใช้ PPU466 มอนสเตอร์ต้องสามารถไล่ตามผู้เล่นได้
- PPU466 มีข้อจำกัดคล้ายแฟนตาซีคอนโซลอย่าง PICO-8 คือกราฟิก 8 บิต, 4 สีต่อไทล์, พื้นหลังคงที่ และจำนวนสไปรต์ที่มีจำกัด
- เป้าหมายคือให้มอนสเตอร์ตามผู้เล่นได้ โดยไม่หยุดเมื่อชนกำแพงแบบทื่อ ๆ หรือไปติดค้างในรูปแบบที่ไม่ต้องการ
การเคลื่อนที่เป็นเส้นตรงและ wall-sliding
- วิธีที่ง่ายที่สุดคือวาดเส้นตรงระหว่างมอนสเตอร์กับผู้เล่น แล้วเคลื่อนที่ไปตามทิศนั้น
- ถ้าใช้แค่วิธีนี้ มอนสเตอร์จะ หยุดทันทีที่แตะกำแพง
- เมื่อนำ wall-sliding มาใช้ มันจะไม่หยุดเมื่อชนกำแพง แต่จะเลื่อนไปตามแนวกำแพงแทน
- สำหรับการเคลื่อนที่ของผู้เล่น นี่เป็นเทคนิคที่ช่วยให้การควบคุมบริเวณกำแพงและมุมตอบสนองได้ดีขึ้น และแทบทุกเกมก็ใช้กัน
- มันถูกใช้มาตั้งแต่ Pac-Man และใน Pac-Man Championship Edition DX+ ยังเพิ่มเอฟเฟกต์ประกายไฟเมื่อผู้เล่น wall-slide
- ถ้าเอา wall-sliding ไปใช้กับการเคลื่อนที่เป็นเส้นตรง ก็จะทำให้สามารถขังมอนสเตอร์ไว้ในภูมิประเทศบางแบบได้
- บางเกมใช้สิ่งนี้เป็นองค์ประกอบเชิงกลยุทธ์ เช่น safespotting ใน Runescape
- แต่สำหรับเกมนี้ นั่นไม่ใช่พฤติกรรมที่ต้องการ จึงหันไปพิจารณาอัลกอริทึมการหาเส้นทางจริงจัง
ข้อจำกัดของอัลกอริทึม Dijkstra
- อัลกอริทึม Dijkstra ติดตั้งใช้งานได้ตรงไปตรงมาและ รับประกันเส้นทางที่สั้นที่สุด
- ปัญหาคือมันทำงานมากเกินกว่าที่จำเป็น
- มันหาเส้นทางสั้นที่สุดจากโหนดเริ่มต้นไปยังทุกโหนดอื่นในกราฟ
- แม้จะหยุดได้เมื่อเจอโหนดปลายทาง แต่ก็ไม่มีวิธีชี้นำการค้นหาให้มุ่งไปทางจุดหมายเฉพาะ
- ในวิดีโอเกม ผู้เล่นเคลื่อนที่ตลอดเวลา ดังนั้นจุดหมายของมอนสเตอร์จึง เปลี่ยนทุกเฟรม
- สิ่งที่มอนสเตอร์ต้องการจริง ๆ ไม่ใช่เส้นทางทั้งหมด แต่ใกล้เคียงกับการรู้ว่าตอนนี้ควรขยับไปทางไหน
- จะคำนวณเส้นทางสั้นที่สุดล่วงหน้าสำหรับทุกพิกเซลหรือทุกไทล์บนแผนที่ก็ได้ แต่จะกินหน่วยความจำมาก
- บนแพลตฟอร์มรุ่นเก่าหรือแพลตฟอร์มที่ทรัพยากรจำกัด Dijkstra จึงไม่เหมาะนัก
ทำไม A* จึงเหมาะกับการหาเส้นทางในเกม
- A* Search Algorithm ใช้ข้อมูลระยะจากโหนดเริ่มต้นไปยังจุดหมายเพื่อกำหนดลำดับความสำคัญของการค้นหา
- ในขั้นแรก มันจะลองไปในทิศที่พุ่งตรงสู่เป้าหมายก่อน
- ต่างจาก Dijkstra ตรงที่ถ้าไม่จำเป็น มันจะไม่เสียเวลาไปสำรวจทิศตรงข้ามมากนัก
- ถ้ามีกำแพงขวางทาง มันจะตรวจโหนดรอบข้างเพื่อหาทางอ้อมกำแพง
- เช่นเดียวกับ Dijkstra มันจะไม่กลับไปเยี่ยมโหนดที่เคยเห็นแล้ว ดังนั้นถึงต้องถอยหรืออ้อมมากแค่ไหน สุดท้ายก็ยังหาเส้นทางอ้อมได้
- ในตัวอย่าง มอนสเตอร์ที่ใช้ A* จะไม่ติดอยู่หลังแนวกำแพง
โครงสร้างข้อมูลกราฟแบบปริยาย
- กราฟตามตำรามักแทนด้วยรายการโหนดและ adjacency matrix หรือ adjacency list แต่ในเกมสามารถทำให้โหนดข้างเคียงยืดหยุ่นได้มากกว่า
- ตัวอย่างเช่น บนหน้าจอขนาด 256×240 พิกเซล สามารถมองพิกัดพิกเซลแต่ละจุดเป็นหนึ่งโหนดได้
- พิกเซลข้างเคียงมี 8 ทิศทาง คือ บน ล่าง ซ้าย ขวา และแนวทแยงทั้ง 4 ทิศ
- น้ำหนักการเคลื่อนที่แนวตั้งและแนวนอนเป็น 1 ส่วนน้ำหนักแนวทแยงเป็น √2 หรือประมาณ 1.4
- แทนที่จะสร้าง adjacency list ขนาดมหึมาล่วงหน้า สามารถสร้างขึ้นสด ๆ เฉพาะโหนดที่มีการเข้าถึงจริงได้
- พิกเซลที่อยู่บนกำแพงหรือถูกสไปรต์อื่นยึดอยู่ไม่ใช่ตำแหน่งที่มอนสเตอร์ไปยืนได้ จึงตัดออกจาก adjacency list แบบไดนามิกได้
- วิธีนี้ทำให้ไม่ต้องไปไล่ตัดโหนดที่เชื่อมต่อกันไม่ได้ด้วยมือใน map editor
ฮิวริสติกที่สะท้อนเรขาคณิตของแผนที่
- องค์ประกอบบางส่วนของ A* สามารถปรับแต่งเองให้เข้ากับ โครงสร้างเชิงเรขาคณิต ของแผนที่ได้
-
ขนาดก้าว
- แทนที่จะใช้พิกเซลเป็นโหนด ในเกม 2D แบบใช้ไทล์สามารถใช้ ไทล์เป็นโหนด ได้
- การค้นหาระดับไทล์ช่วยลดจำนวนรอบที่ต้องใช้ในการหาเส้นทางไปหาผู้เล่นลงอย่างมาก ทำให้ค้นหาได้เร็วขึ้น
- ในกรณีนี้ เส้นทางจะไม่ใช่รายการการเคลื่อนที่ละเอียดระดับหนึ่งเฟรมอย่างเป๊ะ ๆ แต่ใกล้เคียงกับ ลำดับของทิศทาง ที่มอนสเตอร์ควรไปมากกว่า
- โดยปกติมอนสเตอร์ไม่ได้เคลื่อนที่เร็วระดับ 1 ไทล์ต่อเฟรมอยู่แล้ว ดังนั้นแม้ใช้เส้นทางระดับไทล์ ข้อมูลที่ต้องการจริงก็ยังเป็นทิศทางที่พาไปถึงผู้เล่นได้
- แม้เป็นเส้นทางระดับพิกเซลก็มีลักษณะเดียวกัน เพราะมอนสเตอร์อาจไม่ได้ขยับทีละ 1 พิกเซลต่อเฟรม หรือขยับเป็นจำนวนพิกเซลเต็มเสมอไป
-
ความลึกของการวนซ้ำ
- ใน A* เมื่อโหนดถูกดึงออกจาก priority queue โหนดนั้นคือขั้นสุดท้ายของเส้นทางที่ดีที่สุดเท่าที่พบจนถึงตอนนั้น
- ถ้าหยุดอัลกอริทึมหลังจำนวนรอบคงที่ ก็จะได้ เส้นทางประมาณที่ดีที่สุดในตอนนั้น สำหรับเส้นทางสั้นที่สุดไปยังจุดหมาย
- จึงสามารถได้ทิศทางการเดินหน้าที่สมเหตุสมผลโดยไม่จำเป็นต้องรันอัลกอริทึมจนจบ
- ค่าความลึกสูงสุดควรปรับให้เข้ากับเรขาคณิตของเลเวล
- ถ้าความลึกน้อยเกินไป มอนสเตอร์ก็ยังอาจติดอยู่หลังกำแพงได้
- ในตัวอย่าง เมื่อใช้ความลึกคงที่ 30 ไทล์ มอนสเตอร์จะติดค้างและไปต่อไม่ได้ขึ้นอยู่กับตำแหน่งของผู้เล่น
- เพราะ A* ถูกคำนวณใหม่ทุกเฟรม จึงอาจเกิดลูปได้
- ในเฟรมแรกที่ไปถึงกำแพง มันคำนวณว่าควรลงล่าง
- ในเฟรมถัดมา มันคำนวณว่าควรขึ้นบน
- การสลับแบบนี้ทำให้มอนสเตอร์ติดอยู่ในลูป
- ถ้าผู้เล่นเข้ามาอยู่ในขอบเขตที่มอนสเตอร์ค้นหาได้ มันก็จะหาเส้นทางที่ถูกต้องได้
- เมื่อใช้ความลึกคงที่
1ปรากฏการณ์นี้จะยิ่งรุนแรงกว่าเดิม โดยมอนสเตอร์จะย้อนกลับไปยังพิกเซลที่มีระยะยูคลิดถึงผู้เล่นสั้นที่สุดอยู่ตลอด
ทางสายกลางของการคำนวณล่วงหน้า
- หากต้องการให้ประณีตขึ้น สามารถคำนวณล่วงหน้าได้ว่าไม่ว่าตำแหน่งใดบนแผนที่ A* ต้องใช้ ความลึกสูงสุด เท่าไรจึงจะหาเส้นทางเจอ
- ต่างจากการคำนวณเส้นทางทั้งหมดล่วงหน้าแบบ Dijkstra สิ่งที่ต้องเก็บไว้มีเพียงค่าสูงสุดนี้ค่าเดียว
- เมื่อมีค่าความลึกสูงสุดดังกล่าว A* ก็จะหาเส้นทางที่ใช้ได้จริงแบบเรียลไทม์ได้
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
เทคนิคที่เคยใช้กับ A* ใน MMO ระดับโปรดักชัน: 1) ถ้าวาง กราฟแบบลำดับชั้น เช่น ระดับเมือง ระหว่างห้องภายในอาคาร และภายในห้อง ก็จะค้นหาเส้นทางจากจุดในเมืองไหน อาคารไหน ห้องไหน ไปยังอีกจุดหนึ่งได้ภายในเวลาเพียงเศษเสี้ยวของมิลลิวินาที
2) ถ้าเก็บเมทาดาทาของการค้นหา A* ปัจจุบันไว้ในโหนดของกราฟโดยตรง ก็ไม่ต้องดูแล associative array แยกต่างหาก
3) อย่าเดินตามเส้นทางผลลัพธ์ตรง ๆ แต่ควรใช้เป็นอินพุตให้พฤติกรรมการบังคับทิศทางที่พยายามตัดมุมไปยังโหนดเส้นทางถัดไปเมื่อทำได้ ถ้าเป็นเส้นทางไปยังตัวละครอื่น ให้ตัวละครเป้าหมายทิ้ง “เศษขนมปัง” ไว้ แล้วเพิ่มตำแหน่งใหม่เข้าเส้นทางเมื่อไม่สามารถเดินเป็นเส้นตรงจากโหนดสุดท้ายของเส้นทางไปยังตำแหน่งนั้นได้
2b) บีบอัดสิ่งนี้เป็นบิตมาสก์ 16 บิต คือชิ้นส่วน 2 บิต 8 ชิ้น หรือก็คือ 8 ทิศทาง แล้วเก็บไว้ใน hash table
2c) แต่ละชิ้นส่วนบิตมี 4 สถานะ: FULL_BLOCK(กำแพง), HARD_BLOCK(วัตถุขนาดใหญ่ที่ทำให้ผ่านไทล์ไม่ได้จากทุกทิศทาง), SOFT_BLOCK(วัตถุขนาดเล็กที่บล็อกการผ่านมุมด้านหนึ่ง), NO_BLOCK(ไทล์ว่างหรือไทล์ที่มีวัตถุเล็กมาก)
แบบนี้เมื่อยูนิตในอาคารหาเส้นทาง ก็ไม่ต้องตรวจสิ่งกีดขวางทุกไทล์ วัตถุที่อยู่บนไทล์ก็ยังสามารถผ่านได้ หากวัตถุนั้นไม่ใหญ่โตและตามทิศทางการหมุนแล้วไม่ได้บังมุมทางเข้าและทางออก สุดท้ายยังทำให้เอเจนต์เดินทะลุกำแพงได้ด้วย เพื่อไม่ให้ซิมูเลชันพัง เช่น ตอนผู้เล่นลืมวางประตู
https://store.steampowered.com/app/2287430/Metropolis_1998/
ตราบใดที่ตัวละครยังอยู่ใน “ฟอง” แบบนี้ ก็สามารถข้ามการตรวจชนกับโลกทั้งใบไปได้เลย
ตอนเรียนมหาวิทยาลัย ผมไม่เข้าใจว่าทำไม A* ใน RTS ถึงยากขนาดนั้น แต่พอเห็นคำอธิบายว่าถ้าจะไม่ให้ยูนิตเดินทะลุกัน สิ่งที่เคลื่อนที่ทุกอย่างต้องคอยหลบยูนิตอื่นทั้งหมดและหาเส้นทางใหม่ตลอด ก็ทำให้ยิ่งนับถือ Command & Conquer ขึ้นมาใหม่
ถ้าไม่มีเหตุผลที่หนักแน่นมาก โดยส่วนตัวจะหลีกเลี่ยง
เคยคิดเยอะมากเรื่อง การหาเส้นทางอย่างรวดเร็ว เพื่อเร่งความเร็ว Quoridor AI ที่เขียนด้วย Scala และเทคนิคที่ได้เรียนรู้มีดังนี้
MPAA (Multi-Path Adaptive A*) เหมาะเมื่อมีการเพิ่มสิ่งกีดขวาง และต้องค้นหาพื้นที่เดิมซ้ำหลายครั้ง สามารถใส่ผลลัพธ์การค้นหาก่อนหน้าเข้าไปเพื่อทำให้การหาเส้นทางเร็วขึ้นได้
JPS (Jump Point Search) น่าสนใจในเชิงทฤษฎีเพราะลดจำนวน “โหนด” ที่ต้องพิจารณาได้มาก แต่โอเวอร์เฮดในการหา jump point สูงขึ้น จึงไม่ได้ทำให้เร็วขึ้นจริง อาจมีวิธีผสมแนวคิดของ MPAA กับ JPS ได้ แต่พอเริ่มปรับแต่งอัลกอริทึมอย่างสร้างสรรค์ รายละเอียดเชิงแนวคิดเล็ก ๆ ก็ทำให้พลาดได้ง่าย เช่น ถ้าใช้
>ตอนที่ต้องใช้>=ก็อาจรับประกันเส้นทางที่สั้นที่สุดจริง ๆ ไม่ได้ในบางสถานการณ์สำหรับการเก็บโหนดเปิด ถ้าค่าลำดับความสำคัญสูงสุดเป็นจำนวนเต็มที่ค่อนข้างเล็ก ก็อาจพิจารณา bucket priority queue แทน heap ที่ถูกต้องเต็มรูปแบบได้ เพราะใช้อาร์เรย์ภายในโดย index ตามลำดับความสำคัญ การเพิ่มและดึงออกจึงค่อนข้างเร็ว
Quoridor เล่นบนกริด 9x9 และการหาเส้นทางซ้ำ ๆ เป็นสิ่งจำเป็นเพื่อ判断ว่าผู้เล่นอยู่ใกล้เป้าหมายแค่ไหน และยังไปถึงเป้าหมายได้หรือไม่ หากจะ判断การเดินที่เป็นไปได้จากตำแหน่งหนึ่ง ต้องตรวจว่าการเดินทั้งหมดไม่ทำให้การไปถึงเป้าหมายเป็นไปไม่ได้ วางแผนจะเปิดเผยต่อสาธารณะภายในไม่กี่เดือน และจะมี “เอนจิน” ตัดสินใจอย่างน้อย 3 ตัว: mtdf(ตัวแปรของ minimax), MCTS(เวอร์ชันขนานที่ใส่เทคนิคบางอย่าง), และไฮบริดที่ผสม catboost
จุดที่ดีคือสามารถใช้สิ่งนี้เป็นตาราง lookup สำหรับฟังก์ชัน heuristic แทนระยะทางเส้นตรงตามปกติได้ เช่น ตอนเริ่มแต่ละเทิร์น อาจใช้ Floyd-Warshall algorithm เพื่อเริ่มต้นตารางนี้โดยสะท้อนกำแพงที่วางไว้แล้ว ในปัญหาคล้าย ๆ กัน เทคนิคนี้ทำให้ A* เร็วขึ้นค่อนข้างมาก และเรียบง่ายมากด้วย แต่เป็น A* ล้วน ๆ โดยไม่มี MPAA หรือ JPS
หลายปีก่อน เคยเพิ่มฟีเจอร์แสดงภาพการค้นหาแบบ recursive ที่ใช้หา jump node ใน implementation ของ JPS ใน PathFinding.js เดโมออนไลน์อยู่ที่นี่: https://qiao.github.io/PathFinding.js/visual/
ถ้ามีศัตรูมากกว่าหนึ่งตัว อาจคุ้มกว่าที่จะรัน Dijkstra เพียงครั้งเดียวจากมุมมองของผู้เล่น แล้วให้มอนสเตอร์แต่ละตัว lookup เส้นทางที่ดีที่สุดไปยังผู้เล่น
ค่าใช้จ่ายในการคำนวณจะคาดการณ์ได้มากขึ้นเมื่อจำนวนมอนสเตอร์เปลี่ยนไป
ปัญหา ความลึกน้อยเกินไป ในแอนิเมชันสุดท้ายนั้นดูเหมือนพฤติกรรมที่น่าสนใจ ดูราวกับมอนสเตอร์ “รอดูอยู่ว่าคุณจะไปทางไหน”
ถ้าแกล้งทำเป็นไปทางหนึ่งแล้วเปลี่ยนทิศ จะหลอกมันได้ไหมนะ? โชคดีที่มนุษย์ค่อนข้างยืดหยุ่นกับเรื่องแบบนี้ และดูเหมือนจะตีความอะไรก็ได้ให้เหมือนมีสติปัญญา
โดยพื้นฐานแล้ว แค่ให้ศัตรูอัปเดตเส้นทางหลังจากดีเลย์สั้น ๆ เท่านั้น ไม่ใช่ทุกเฟรม แบบนั้นมันจะตามเส้นทางเดิมไปเพราะ “แรงเฉื่อย” และผู้เล่นก็จะหลอกมันได้
ตัวอย่างการใช้ A* ที่น่าสนใจในบริบทของเกมคือ มีโปรแกรมเมอร์คนหนึ่งในช่วงต้นทศวรรษ 2000 ที่ต้องสร้างคู่ต่อสู้คอมพิวเตอร์ให้กับเกม
เขาทำ abstraction ตัวเลือกที่ AI มีในเกม แล้วให้ใช้ A* หาเส้นทางระยะใกล้ที่สุดบนกราฟนั้น สิ่งที่เจ๋งคือมันไม่ได้ใช้ในแบบดั้งเดิมอย่างการหาเส้นทางในโลกเกม แต่เป็นการหาเส้นทางบนการแทนตัวเลือกที่คอมพิวเตอร์ทำได้ และให้เส้นทางสั้นที่สุดแทนกลยุทธ์ที่ดีที่สุดเท่าที่เป็นไปได้
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
มีแหล่งอ้างอิงด้วย (ไม่ใช่ของผม): https://github.com/agoose77/goap-resources
ดูเหมือนมนุษย์จะมองว่าตัวเองและมนุษย์คนอื่นใช้รูปแบบการคิดที่คล้ายกันและความลึกของการคิดที่ใกล้เคียงกัน แม้กับกิจกรรมที่ต่างกันโดยสิ้นเชิง เช่น การวางแผนเส้นทาง การประเมินความเสี่ยง/ผลตอบแทน หรือการวางแผนอีเวนต์อีก 6 เดือนข้างหน้า ถ้าสามารถเข้ารหัส “พื้นที่ค้นหา” ที่หลากหลายให้เป็นกราฟที่เข้ากับอัลกอริทึมร่วมกันได้ ก็ทำให้ระหว่างเล่นมีความเป็นไปได้ที่ AI จะดูรอบคอบและแทบจะเหมือนมีบุคลิกเป็นตัวตน
ตอนที่เรียน A* ในมหาวิทยาลัย ผมก็เจอปัญหาแปลก ๆ นั้นบน เซิร์ฟเวอร์ Minecraft สาธารณะ พร้อมกันพอดี
เซิร์ฟเวอร์กระตุกหนักมาก พอลอง trace ดูก็พบว่าพวกซอมบี้ติดอยู่ในลูปหาเส้นทางเพื่อเข้าไปในหมู่บ้านที่ถูกล้อมด้วยรั้วใหญ่จนปิดสนิท นั่นหมายความว่าการติดตั้งตอนนั้นค่อนข้างซื่อ ๆ และไม่เคยยอมแพ้เลย
ผมจำได้ว่ามีบั๊กรีพอร์ตที่เขียนค่อนข้างละเอียดว่าจะควรแก้อย่างไร
โดยเฉพาะเมื่อมีสัตว์หลายตัวพยายามจะผ่านทางเข้าที่ผ่านไม่ได้ทั้งหมด จะส่งผลต่อ fps อย่างเห็นได้ชัดมาก แน่นอน ถ้ามองเป็นพฤติกรรมแมวที่เรียกร้องอย่างดื้อดึงมากว่าจะผ่านประตูที่ปิดอยู่ ก็อาจบอกได้ว่าสมจริงสุด ๆ แล้ว แต่จะสมจริงกว่านี้ถ้าทันทีที่เปิดประตูให้ แมวเปลี่ยนใจทันทีและหมดความสนใจที่จะผ่านไป!
คุณอาจสนใจ paper เกี่ยวกับ ระบบหลายเอเจนต์ ที่ใช้ A* ในภูมิประเทศที่ไม่คุ้นเคย: https://www.researchgate.net/publication/333917261_Implement...
บทความนี้และเธรด HN มีเคล็ดลับดี ๆ อยู่ ผมยังไม่ค่อยได้มีโอกาสใช้ A* มากนัก แต่รู้ว่ามี ไลบรารี Haskell ที่ดีอยู่: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...