Optimal Path Maps on the GPU.

Area of Science:

• Computer Graphics
• Computational Geometry
• Artificial Intelligence

Background:

• Pathfinding algorithms are crucial for navigation in virtual environments.
• Existing methods often lack efficiency or fail to account for dynamic traversal speeds.
• Real-time path computation for multiple agents remains a challenge.

Purpose of the Study:

• To develop a GPU-accelerated method for computing optimal path maps.
• To introduce a novel path map concept incorporating vertex weights for traversal speed variations.
• To enable efficient real-time path queries in complex 2D environments.

Main Methods:

• Utilizing GPU rasterization via OpenGL shaders for cost propagation.
• Implementing the method entirely on the GPU without pre-computation.
• Handling multiple source points (points and line segments) and vertex-based speed changes.

Main Results:

• Generated optimal path maps efficiently queryable at run-time.
• Successfully incorporated vertex weights to represent variable traversal speeds.
• Demonstrated suitability for animating multiple agents in virtual environments.

Conclusions:

• The proposed GPU-based method offers a novel and efficient approach to optimal path map computation.
• The inclusion of vertex weights enhances pathfinding realism by accounting for speed variations.
• This technique provides advanced navigation capabilities for animated virtual environments.