Geometric and Discrete Path Planning for Interactive Virtual Worlds (Synthesis Lectures on Visual Computing: Computer Graphics, Animation, Computational Photography and Imaging)

Path planning and navigation are indispensable components for controlling autonomous agents in interactive virtual worlds. Given the growing demands on the size and complexity of modern virtual worlds, a number of new techniques have been developed for achieving intelligent navigation for the next generation of interactive multi-agent simulations. This book reviews the evolution of several related techniques, starting from classical planning and computational geometry techniques and then gradually moving toward more advanced topics with focus on recent developments from the work of the authors. The covered topics range from discrete search and geometric representations to planning under different types of constraints and harnessing the power of graphics hardware in order to address Euclidean shortest paths and discrete search for multiple agents under limited time budgets. The use of planning algorithms beyond path planning is also discussed in the areas of crowd animation and whole-body motion planning for virtual characters.

路徑規劃和導航是控制互動虛擬世界中自主代理的不可或缺的組件。鑑於現代虛擬世界的規模和複雜性不斷增長，已經開發出一些新技術，以實現下一代互動多代理模擬的智能導航。本書回顧了幾種相關技術的演變，從傳統規劃和計算幾何技術開始，逐漸轉向更高級的主題，重點關注作者的最新研究成果。涵蓋的主題範圍從離散搜索和幾何表示到在不同類型約束下的規劃，並利用圖形硬件的能力來解決歐幾里得最短路徑和在有限時間預算下的多代理離散搜索。還討論了在人群動畫和虛擬角色的整體運動規劃領域中使用規劃算法的情況。