Speaker: Leonid Darovskikh
Abstract
Pathfinding on square grids is a typical problem in game development, commonly solved using the A* algorithm and navmeshes(navigation meshes). However, traditional navmeshes decompose the traversable area into triangles, which may be suboptimal for grid-based maps. Therefore this thesis proposes an approach utilizing navigation meshes which decompose the area into axis-aligned rectangles, resulting in fewer nodes and therefore (theoretically) better performance. This technique will be implemented from the ground up, including the decomposition, local navmesh repair and actual pathfinding, which will support any-angle paths and maps with non-uniform movement costs. Finally, its performance will be evaluated by comparing it to state-of-the-art methods such as aforementioned traditional navmeshes, JPS, REA*, etc. on maps of different sizes and archetypes(such as caves, mazes and dungeons).