David Partouche

Hierarchical Kinematic Path Planning for Vehicles in Open Terrain

Existing solutions for navigation in game engines are mostly aimed at biped characters, and can’t be applied for vehicle navigation, as it fails to take into consideration the kinematics constraints of the vehicle. Most games use navigation paths for vehicles, which are precomputed and already optimised for the vehicle’s turning rate at a given speed. But it means that the vehicle needs to stay on these paths. We provide a solution, adapted from Stanford’s Hybrid A* to allow vehicles in game to navigate anywhere on an open map.

The Hybrid A* allows for a realistic representation of the path a vehicle can take by calculating its different positions based on its turning angles, instead of having fixed points on a map like a traditional A*.

The original Hybrid A* algorithm is adapted for a vehicle driving at a constant speed, and calculates its future position on the fly, which restricts its functionality for video-games. Our solution was to calculate the turning radius of each vehicle for different speeds, and add the results to a datatable that is used to calculate the path points on the grid.

We also adapted the algorithm to use a double-layered hierarchical map, where the highest layer would do a traditional A* to check first if a goal can be accessed, and the lower layer would use the hybrid A* algorithm. Once we have the result of the A*, we can compute the the hybrid A* in parallels for each subpath, optimising the cost of the algorithm.

Session Takeaway

• Vehicle Navigation
• Hierarchical Hybrid A*
• Kinematic Pathfinding

Session speakers