Go to top

Pathfinding

Mercuna 3D Navigation 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 3D Navigation’s advanced pathfinding features include:

  • Asynchronous pathfinding – 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, Mercuna first builds the octree at low resolution to allow basic AI navigation almost immediately. Then, in the background, Mercuna progressively upgrades the octree to full resolution to allow unrestricted movement.
  • Runtime regeneration – regenerate sections of the navigation octree during gameplay when the world changes and ensure that your agents’ paths are always up-to-date and reflect the changing game world around them.
  • Level streaming – as sublevels are streamed in, Mercuna integrates the new sections of the octree to create a single unified octree, allowing seamless navigation across the whole world.
  • Modifier volumes – mark volumes within the map as being more expensive to traverse, and/or only traversable by certain agent types. Use these to make certain routes less desirable or to block routes and areas so that only certain agents can enter them.
  • Level of Detail volumes – generate the octree at lower resolution in volumes where detailed navigation is not required in order to reduce memory usage.