Navmesh disk cache

Everything about development and the OpenMW source code.
Post Reply
elsid
Posts: 20
Joined: 01 Aug 2017, 08:20

Navmesh disk cache

Post by elsid »

There has to be a way to reuse generated navmesh between different game sessions. It allows to reduce openmw CPU usage and decrease location load latency. The cache can be pre generated by a separate tool (executed from the launcher) for all current game data based on current user settings (settings.cfg + openmw.cfg). It also can be updated while the engine is running in a similar way as memory cache is updated if required.

Current memory stores a set of tiles without difference what cell they belong to, using a following structure:
  • Key:
    • agent half extents
    • tile position
    • tile collision geometry data as a single mesh
    • off mesh connections
    • water levels
  • Value - recastnavigation navmesh data (array of bytes)
Some important facts:
  • Key size takes 70% of cache size.
  • Total cache size is about 1.8 GiB for default Morrowind including only all official expansions and mods, default agent half extents and initial objects transformations.
There are requirements for disk cache comparing to in-memory:
  • Format can't be changed without keeping compatibility. Users should not be forced to regenerate cache each time we decide to change things because it's a fast operation.
  • Separate in-memory index has. This allows to avoid reading from disk if tile is not present in the cache.
  • Index should not bloat memory usage. In-memory cache key can't be used as is.
  • Cache access should be asynchronous. It should not block threads for realtime navmesh generation.
  • It can be pregenerated from .esm/.esp files without openmw application involvement. Standalone tool and component that can be used from launcher and editor.
The proposed algorithm for requesting navmesh tile:
1. Find tile by full key in-memory cache, use tile if found.
2. Find tile by short key in disk cache index, schedule (3) reading from disk if found or fallback to generation (4).
3. Find tile by full key in disk cache, use tile if found or fallback to generation (4).
4. Generate a navmesh tile from a given full key.
5. Store tile to in-memory cache.
6. Schedule tile writing to disk cache.
7. Update disk cache index.

There are open questions:
1. What is a short key?
  • Cell id (name for interior and position for exterior) and tile position.
    Pros:
    • Small size.
    Cons:
    • False positives for index hit.
2. What disk storage to use? Most important criteria here is performance to read and write a single navmesh tile.
  • Loose binary files.
  • ESM extension.
  • SQLite database.
  • Custom single binary file storage.
User avatar
akortunov
Posts: 899
Joined: 13 Mar 2017, 13:49
Location: Samara, Russian Federation

Re: Navmesh disk cache

Post by akortunov »

elsid wrote: 03 Jul 2021, 17:52 Total cache size is about 1.8 GiB for default Morrowind including only all official expansions and mods, default agent half extents and initial objects transformations.
It is too much, IMO - it is more than default Morrowind with official expansions occupies. I do not even mention TR + SHOTN, which have a much larger landmass.

Also I do not see how you want to validate that cache (when player added, updated or removed any mod or an object was moved, enabled or disabled via script). In this case cache can be present, but it will be invalid, so OpenMW will need to detect such cases an fallback to runtime generation for such chunks (but probably without rewriting the cache).
Post Reply