Individualized Pathfinding in Rugged Open Terrains Using Semantic Navigation Meshes

Traditional navigation meshes split the terrain into convex walkable regions, which work well for nearly flat environments with clearly defined obstacles. However, in complex outdoor terrains with variable slopes and heights, these approaches fail to capture areas with consistent characteristics. Moreover, human preferences vary per individual: some may favour smooth paths with gentle slopes, while others prefer shorter routes even if steeper. We present a semantic navigation mesh that generates cells with coherent, low‐variance values for chosen semantics, such as slope or vegetation density. Cells are constructed via a region‐growing partitioning algorithm, optionally refined for compactness, and can incorporate multiple semantic dimensions simultaneously. This approach preserves terrain complexity without relying on a binary walkable/non‐walkable classification. From this partition, we propose different alternatives for generating a navigation graph and perform semantically‐aware pathfinding for agent‐specific cost functions, which prevents the use of precomputed hierarchical paths. Our evaluation demonstrates that semantic meshes accelerate pathfinding on complex open terrains while producing trajectories close to those obtained by a brute‐force search over the entire domain. This provides a flexible, generic framework that balances graph size, subdomain homogeneity, search efficiency, and path quality.