David Partouche
The Multiplayer Group
David started to work for Eden Games (Atari) as an AI Programmer on Test Drive Unlimited 2, then went to Frontier Development, working also as AI Programmer, specialising in navigation and locomotion. He spent a few years working as a freelancer, doing indie games, TV show apps, and trying his hands on different projects. He joined MPG in 2020, working on Fall Guys (Mediatonic) and on Tomorrow Falls by DPS Games. He is currently working on a project by Zenimax Online.
David Partouche is speaking at the following session/s
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
