Using Nav-Mesh Flood Fill to Speed Up Environment Querying

In almost every game, you need to query the environment for positions and objects for your agents. The most common attribute for these queries is distance. In complex environments, pathfinding data from nav-mesh are more accurate than basic distance checks. They can help you to filter out unreachable positions or give distances through obstacles. However, calculating paths for every possible position is slow, especially when multiple agents are requesting at the same time. To face this problem, we decided to run the Flood Fill algorithm through nav-mesh faces. It allows us to pre-calculate pathfinding data for selected areas and reuse it for multiple queries. This technique allows to increase the number of positions taken into consideration, leading to more optimal results.