Handling Sector Overlaps

When you have multiple sectors in a terrain they are likely to overlap, at least around their edges. This overlap may affect the navigable areas in one or both of the sectors.

The NavData generation system identifies these areas of overlap and gives them special treatment in order to ensure that the NavData correctly reflects the geometry that is loaded into memory.

  1. First, each sector has NavData generated for it on its own, without considering the geometry in adjacent sectors.

    Each sector needs to be configured with a globally unique ID represented by an instance of the KyGuid class, which you provide when you create the sector.

  2. Next, the areas of overlap are identified between all adjacent sectors. An alternative chunk of NavData is then generated that reflects the combination of the overlapping terrain geometries. This alternative chunk is tagged with a KyGuid that is a combination of the unique IDs assigned to all of the sectors involved in the overlap.
  3. The alternative chunk is saved into the .NavData file for one or the other of the overlapping sectors.
  4. When you stream the NavData for your sectors in and out of memory at runtime, the Database automatically swaps the overlap data in and out depending on what sectors are currently loaded.

For example, consider a sector that contains a relatively flat plain, and an adjacent sector that contains a hill. The geometry in the two sectors overlaps slightly, so that a little of the hill projects below the level of the plain, and a little of the plain extends below the hill.

When only the NavData for the plain is loaded, its NavData reflects the flat terrain. When only the hill is loaded, its NavData reflects only the hillside. When both sectors are loaded at the same time, the parts of the plain and the hill that overlap are automatically replaced by the alternative chunk that represents the overlap area, allowing a bot to pass from one sector to the next.

This process is entirely transparent. All you have to do is provide all your different sectors in the same run of the NavData generation system; the generation and runtime stitching of the overlap data will be handled automatically.

Controlling the generation of overlap data

The automatic overlap detection and stitching system is designed to seamlessly handle every combination of sectors to ensure that the NavMesh is always consistent with the geometry of whatever set of sectors are currently loaded into the game, even along the borders between sectors.

However, in some scenarios, you may want to prevent the generation of overlap data in order to decrease the memory footprint of the NavData for your sectors. The scenarios that typically allow for disabling the generation of overlap data without compromising the accuracy of the NavMesh are described below.

Using swappable sectors

Sometimes, when major changes can occur in a terrain geometry during the course of a game, you may want to generate NavData for that sector in two different states, and swap them at runtime when the state of the terrain changes. The classic example of a swappable sector is an area with a large building that can be destroyed at runtime. While the building is in place, you want characters on the ground to walk around it, and you may even want characters to be able to move around inside the building, on the roof, etc. However, when the building gets destroyed, the characters should be free to move along the ground through the area formerly occupied by the building.

You can create the NavData for these swappable sectors transparently by setting up a different sector for each state of the geometry, and generating both sectors at the same time along with the rest of the sectors in your world. For example, you would create one sector that contains the geometry of the terrain with the building intact, and another sector that contains the geometry of the terrain after the destruction of the building. The Generator will transparently take care of creating NavData for both versions of the swappable sector, and creating overlap data that link both versions to the surrounding sectors.

However, by default the NavData generation system will consider it possible for the two versions of the swappable sector to be streamed into memory at the same time. It will detect that the two sectors overlap in space, so in addition to creating a NavMesh for each sector on its own, it will also create overlap data that covers the whole area of the swappable sector for the combination of the geometry. This is not a problem, in that the system will still work smoothly at runtime: whichever sector you have loaded at any time will always have a NavMesh that correctly represents the terrain. However, in the case of swappable sectors, you know that the overlap data will never be needed, since the two versions of the swappable sector will never be loaded at the same time. You can therefore save memory by preventing the NavData generation system from creating the overlap data in the first place.

Using the Navigation Lab

To set up exclusive sectors in the Navigation Lab:

  1. Set up multiple sectors by adding multiple .obj files to the scene in the Navigation Lab.
  2. In the Scene View window, click Add Excl. Sectors. A new element called "ExclusiveSectors" is added to the ExclusiveGuids tree in the Scene View.
  3. Click the new "ExclusiveSectors" element.
  4. Open the Attribute Editor window to the right of the 3D view. The window lists all of the sectors currently present in the scene.
  5. Check all sectors that are exclusive with each other.

    Each time you check the box for a sector, an Activate button appears. Click this button if desired in order to show only that sector in the 3D view.

    Note that the name of your "ExclusiveSectors" element in the Scene View has been updated to indicate which sectors it manages.

You can set up as many different sets of exclusive sectors as you need.

Using the Generator in C++

You can inform the Generator which sectors will never be loaded at the same time by providing the KyGuids of those sectors in a call to GeneratorInputOutput::AddExclusiveGuids(). The Generator will not generate any overlap data for that combination of sectors. You can call this method as many times as necessary to set up different sets of exclusive sectors.

Using fixed-step or grid-based partitioning

Some game projects use streaming sub-levels whose extents adhere to a regular axis-aligned grid with a consistent length and width for each cell. If your project uses such a grid to lay out the divisions between adjacent sub-levels, you can avoid the generation of unnecessary overlap data by using cell boxes to define the extents of your sectors.

In this approach, you align the cell size used internally by the NavData generation framework with the size of your grid cells. For each sector, you provide the extents of a box that defines which cells will be assigned to that sector.

  • NavData for each cell in the grid is saved only in the sector whose cell box contains that cell.
  • The NavData for each cell reflects the combination of all triangles in the terrain that intersect that cell, regardless of which sector your GeneratorInputProducer class assigned those triangles to.
  • No overlap data is generated at all for any overlapping sectors that have cell boxes configured for them. If you need to force overlap data for a particular combination of sectors, you can do so by calling GeneratorInputOutput::AddExplicitOverlapSectors().

Note that because each NavData cell always reflects the combination of all overlapping geometries, but each cell is stored in only one of the sectors, you may see localized inconsistencies between the NavData and the geometry within areas of overlap if you load the terrain mesh for only one of the overlapping sectors into the game.

To determine the extents of the cell box to use for each sector, you can:

  • Calculate the values yourself. The origin of the 3D cell box is always at the same origin as the 3D world space, and the width and length of each cell in the cell box is determined by the value of GeneratorInputOutput.m_params.m_cellSize. The cell box is always axis-aligned.
  • Do a first generation pass for your sector, open the NavData in the Navigation Lab, and view the layout of the cells in the generated NavData for the sector.

For a code example, see the Tutorial_Generation_cellbox.cpp file.

Using the Navigation Lab

  • To set the size of the internal cell partitioning grid, set the value of the Cell size (m) control in the Parameters group in the Generation panel.
  • Select each sector in turn in the Scene View panel, and open the Attribute Editor. In the Cell box area, check the Active control, and set the extents of the cell box for the selected sector along the horizontal X and Y axes.

    You can toggle the rendering of the cell boxes in the 3D view by toggling the CellBoxes button in the Generation Inputs toolbox.

Using the Generator in C++

  • To set the size of the internal cell partitioning grid, set the value of the GeneratorInputOutput.m_params.m_cellSize class member.
  • For each sector, set the extents of the cell box along the horizontal X and Y axes by calling GeneratorSectorConfig::SetInputCellBox().
Please send us your comment about this page

Creative Commons License Except where otherwise noted, this work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Please see the Autodesk Creative Commons FAQ for more information.