Go to top

Pathfinding

Mercuna offers full 3D pathfinding using a highly optimized A* search through a sparse octree. Mercuna creates a voxelised representation of your game geometry, and stores it in the efficient octree structure – allowing both fast pathfinding and responsive reachability queries. For longer range path queries, Mercuna offers hierarchical pathfinding to improve performance.

You can also use the octree to shape your agents’ objectives. Thanks to Mercuna’s optimised reachability tests, you can check whether a given agent can reach hundreds of target points using just a single query. And because reachability information is baked into the octree, these queries are answered extremely quickly.

Mercuna’s advanced features include:

  • Asynchronous pathfinding – by default all pathfinds are performed as background asynchronous jobs, so even long and complex paths can be found without visibly impacting your game’s performance.
  • Hierarchical pathfinding – for longer range path queries, Mercuna uses hierarchical pathfinding. An approximate route across the map is found using an automatically generated coarse navigation graph, before the octree is consulted to refine the path.
  • Advanced spatial queries – quickly find points in navigable space and test which are reachable. Fast navigation raycasts allow you to check for clear, unobstructed routes through complex geometry.
  • Multiple agent sizes – Mercuna’s navigation octree supports multiple agent sizes, giving you flexibility to mix large and small agents in a single game world without requiring multiple octrees.
  • Runtime generation – for procedural levels, generate the navigation octree at level start. Mercuna will first build the navigation octree at low resolution in order to allow AI to do basic navigation and start moving almost immediately. Then, in the background, Mercuna goes through progressively upgrading the octree to full resolution to allow unrestricted navigation.
  • Runtime regeneration – regenerate sections of the navigation octree during gameplay when the world changes and ensure that your agent’s path are always up-to-date and reflect the changing game world around them.
  • Per Nav Volume resolution – specify, on a per nav volume basis, the level of detail at which to generate the octree within that volume. Generate the octree at lower resolution in regions where you don’t need detailed navigation in order to reduce memory usage.