Alternative Title
3D Multi-Threaded AI Navigation with Pathfinding and Obstacle Avoidance
Subject Area
Computer Science
Abstract
In this thesis, I developed a 3D multi-threaded AI navigation system using my own custom-built C++ game engine. The system combines triangle-based A* pathfinding with real-time obstacle avoidance using a set of velocity-obstacle algorithms. It is designed to support large numbers of agents navigating complex environments while avoiding collisions. I created two main simulation modes: Navigation Mode, which integrates A* with ORCA to handle large-scale pathfinding and movement, and Obstacle Avoidance Mode, which allows direct comparison between VO, RVO, HRVO, and ORCA in a controlled test setting.
The terrain is procedurally generated using Perlin noise, and this terrain data is then used to generate a NavMesh composed of walkable triangles. Each triangle connects to its neighbors through shared edges, allowing agents to move fluidly across the mesh. My A* algorithm operates directly on this triangle structure and includes a pruning step that removes unnecessary waypoints to produce cleaner, more efficient paths. Pathfinding is fully multi-threaded, with each request running as an independent job using a custom job system, enabling fast and scalable computation.
For obstacle avoidance, I implemented several velocity-obstacle-based algorithms that allow agents to dynamically adjust their movement based on nearby agents. ORCA provides the most advanced solution, calculating half-plane constraints to ensure smooth and collision-free navigation. To support debugging and evaluation, I implemented visualizations for velocity cones, direction adjustments, and constraint regions.
Agents use physics-based movement with smooth acceleration, turning, and terrain-aware positioning. In Obstacle Avoidance Mode, agents are placed in a sandbox environment loaded from an OBJ model, which creates a closed space for consistent behavior testing. This project gave me the opportunity to explore how pathfinding, real-time avoidance, and multi-threaded systems can be combined to create scalable and intelligent 3D AI navigation. It demonstrates how custom-built solutions can meet the demands of modern simulation and game environments.
Degree Date
Spring 5-17-2025
Document Type
Thesis
Degree Name
M.I.T.
Department
Programming
Advisor
Dr. Corey Clark
Format
Recommended Citation
Belgrave, Jabari, "3D Multi-Threaded AI Navigation with Pathfinding and Obstacle Avoidance" (2025). Programming Theses and Dissertations. 4.
https://scholar.smu.edu/guildhall_programming_etds/4
