Automated generation of waypoints : for pathfinding in a static environment

Sammanfattning: Video game characters must almost always be able to travel from point A to point B and this task can be solved in various ways. There exist grid maps, waypoints, mesh navigation and hierarchical techniques to solve this problem. On randomly generated terrain we make use of automatically generated waypoints to solve pathfinding queries. The waypoints are connected by edges to create a waypoint graph and the graph can be used in real time pathfinding for a single agent in a static environment. This is done by finding the vertices of the blocked triangles from the terrain and place a waypoint on each. We make use of the GPU to create the waypoint graph. The waypoints are connected by utilizing a serialized GPU quad tree to find the relevant blocked geometry to do a line-triangle intersection test. If a line between two waypoints do not intersect any blocked geometry the connection is valid and stored. We found out that it is possible to generate a waypoint graph during the startup of the game with acceptable time results, make use of such a graph for real time pathfinding and that players perceive the paths generated by the algorithm as realistic and responsive. Our conclusion is that our solution is well suited for a deterministic environment with agents of the same size.