อัลกอริทึมการวางวิถีเรบกราฟสำหรับการจำลองฝูงชน

Abstract

งานวิจัยนี้เสนออัลกอริทึมการวางวิถีสำหรับการจำลองฝูงชนโดยอัลกอริทึมในการวางวิถีแบบต่างๆที่ผ่านมาเมื่อนำมาประยุกต์ใช้กับการสร้างภาพเคลื่อนไหวฝูงชนนั้น จะพบว่านอกเหนือจากข้อจำกัดต่าง ๆ เช่นการใช้ตารางกริด(Grid-Based search) นั้นวิถีที่ได้จะขึ้นกับความเหมาะสมของการกำหนดขนาดตารางซึ่งไม่มีหลักการตายตัว ส่วนวิถีการเคลื่อนที่ตามวิธีพลังงานสนามศักย์ (Potential field) จะมีข้อจำกัดในเรื่องจุดต่ำสุดเฉพาะที่ (Local minima) ทำให้อาจจะได้วิถีทางตัน ส่วนวิธีเรขาคณิต (Geometric algorithms) หรือวิธีเชิงสุ่ม(Sampling-based algorithm)ก็อาจจะได้วิถีที่ไม่เป็นแนวกลางและซับซ้อนซึ่งทำให้การเคลื่อนที่ของฝูงชนมีการชนมากขึ้น งานวิจัยนี้จึงมุ่งเน้นที่การออกแบบอัลกอริทึมวางวิถีสำหรับการจำลองฝูงชนที่ใช้เวลาในการคำนวณน้อยและวิถีที่ได้ครอบคลุมสภาพแวดล้อมทั้งหมด เหมาะกับการจำลองการเคลื่อนที่ของฝูงชนคือวางตัวในแนวกลางของพื้นที่ว่างและไม่มีวิถีที่แตกกิ่งซับซ้อน โดยเริ่มจากประยุกต์ต้นไม้อัฐภาค (Octree) ช่วยในการแบ่งพื้นที่ว่างและสิ่งกีดขวางออกเป็นตารางกริดแปดส่วนจนกว่าในพื้นที่จะว่างหรือมีแต่สิ่งกีดขวางอยู่ ส่วนในการสร้างเรบกราฟ (Reeb graph) สร้าง เรบกราฟขึ้น โดยกำหนดเซตระดับให้กับพื้นที่ว่างแบ่งออกเป็นเซต และกำหนดให้แต่ละเซตระดับสมนัยกับปมของเรบ กราฟ (Reeb node) ซึ่งอยู่กลางปริมาตรของพื้นที่ว่าง แล้วเชื่อมต่อด้วยเส้นเชื่อมของเรบกราฟ (Reeb edges) โดยจะกำหนดปมของเรบ กราฟ ท้ายสุดจะได้วิถีการเคลื่อนที่ ผลจากการทดลองพบว่าวิถีการเคลื่อนที่ที่ได้จากอัลกอริทึมการวางวิถีสำหรับการจำลองฝูงชน แสดงการเชื่อมต่อของพื้นที่ว่างที่เคลื่อนที่ได้และวางตัวในแนวกลางห่างจากสิ่งกีดขวางโดยวิถีที่ได้จะเรียบง่ายเหมาะกับการเคลื่อนที่ฝูงชนและใช้เวลาในการคำนวณน้อย