Automated path and route finding through arbitrary complex 3D polygonal worlds

A complete system for path and route finding through arbitrary complex three-dimensional (3D) polygonal worlds is presented. The system is fully automated and can quickly map a complete digital environment without the need for human intervention. Arbitrary complex polygonal worlds can be processed within a few minutes on today’s computers. The processed information allows a robot with a limited number of degrees of freedom to efficiently navigate around obstacles and find routes through the environment. The system is especially suitable for route finding and navigation through buildings which are typically designed with the use of computers these days. As such, digital polygonal representations of buildings are readily available. Not only can the system be used for robot navigation, it can also be used to guide people through buildings. Being able to quickly compile an arbitrary building into a route and path finding system can be especially useful for firemen and tactical military units to invade buildings and reach specific locations. When a building is partly destroyed or inaccessible for other reasons, the digital representation of the building can easily be adjusted by adding or removing polygons and the system presented here can be used to quickly recalculate routes. The system has been successfully implemented and employed in the popular computer game Quake III Arena. The artificial players in this game use the system for path and route finding through complex 3D polygonal worlds. Many other computer games can also benefit from the system presented here.