Source Engine NAV file format redesign in KaitaiStruct.

source_engine_nav_redesign.ksy

# My ideal implementation of the Source Engine NAV file format in kaitai struct.
meta:
  id: nav_file
  title: NAV
  file-extension: nav
  tags:
  - valve
  - source_engine
  - nav_mesh
  - navigation_mesh
  - improvement
  endian: le
# Docs
doc: |
  My idea of the NAV file format used by the Source Engine to store nav mesh data for maps.

# NAV Format.
# Stores all metadata at the beginning.
seq:
  - id: magic_number
    contents: [0xce, 0xfa, 0xed, 0xfe] # 0xFEEDFACE is outputed in reverse.
    doc: Magic Number of the NAV file. NAV files are always generated with 0xFEEDFACE in little-endian.
  # Originally there were two 32-bit values that determined the version.
  # My improved version uses a null-terminated string. This is to
  - id: version
    type: strz
    encoding: UTF-8
  # The original NAV file format stores a 32-bit value of the NAV file's BSP Map's size.
  # My improved version uses a 64-bit hash value of the BSP Map.
  - id: map_hash
    type: u8
    doc: Hash value of the BSP Map the NAV file was generated/saved on.
  # The original NAV file format stores the 'is nav mesh analyzed' boolean as a byte
  - id: analyzed
    type: b1
    doc: |
      Value that stores if the nav mesh has been analyzed (usually through `nav_analyze`).

      True: The nav mesh has been analyzed.
      False: The nav mesh is not been analyzed.
  # Unnamed areas boolean.
  # Changes:
  # * Store value as bit instead of a byte.
  - id: has_unnamed_areas
    type: b1
    doc: Determines if NAV file has unnamed areas.

  # The original NAV format stores the place name, area, and ladder sequence after their respective element counts.
  # My version instead stores the sequences' counts sequentially first, and then stores the elements sequentially.
  - id: place_name_count
    type: u4
    doc: Amount of place names stored.
  - id: area_count
    type: u4
    doc: Amount of areas stored in the nav mesh.
  - id: ladder_count
    type: u4
    doc: Amount of ladders stored in the nav mesh.
  # This section is where navigation data is stored.

  # Changes:
  # * Place name count is stored before 'has unnamed areas' boolean, instead of before place names.
  # * Store place names as null-terminated strings instead of length-string pairs.
  # * Encode place name strings as UTF-8 instead of ASCII.
  - id: place_name_sequence
    type: strz
    encoding: UTF-8
    repeat: expr
    repeat-expr: place_name_count
    doc: Sequence of place names.

  # Original NAV format stores area count before area data.
  - id: area_sequence
    type: nav_area
    repeat: expr
    repeat-expr: area_count
    doc: Container for stored navigation areas.
  - id: ladder_sequence
    type: nav_ladder
    repeat: expr
    repeat-expr: ladder_count
    doc: Container for ladder areas stored in the nav mesh.
  - id: custom_data
    size-eos: true
    doc: Optional custom data appended by a implementation of the NAV format.

types:
  # Connection Pair
  area_id_array:
    seq:
      - id: count
        type: u4
      - id: area_ids
        type: u4
        repeat: expr
        repeat-expr: count
  # NavApproachSpot
  approach_spot:
    seq:
      - id: target_area_id
        type: u4
        doc: ID of area to approach to.
      - id: approach_prev
        type: u4
      - id: type
        type: u1
      - id: next
        type: u4
      - id: method
        type: u1
    doc: Datum point that determines the type of movement between areas. Removed in NAV version 15.
  # NavHidingSpot
  hiding_spot:
    seq:
      - id: hide_spot_id
        type: u4
        doc: ID of the hide spot. Added in NAV version 2.
      - id: hide_spot_position
        type: f4
        repeat: expr
        repeat-expr: 3
        doc: Hide spot position (vector). Added in NAV version 1.
      - id: attribute_flag
        type: u1
        doc: Hide spot attribute flags. Added in NAV version 2.
    enums:
      # Attributes.
      hide_spot_attribute:
        1: in_cover
        2: good_sniper_spot
        4: ideal_sniper_spot
        8: exposed
  # Class: AreaBindInfo
  area_bind:
    seq:
      - id: bound_area_id
        type: u4
        doc: Identifier of the targeted area.
      - id: vis_attribute_flag
        type: u1
        enum: visibility_type
        doc: "brief Determines type of visibility to the bound area."
    doc: |
      Holds relationship data to an area. Added in NAV version 16.

      Reference Class: AreaBindInfo
    enums:
      # VisibilityType enum.
      visibility_type:
        0: not_visible
        1: potentially_visible
        2: completely_visible

  # NavEncounterSpot
  encounter_spot:
    seq:
      - id: order_id
        type: u4
        doc: The ID of the area to go to.
      - id: parametric_distance
        type: u1
        doc: Parametric distance as byte.
    doc: Spots of the encounter path that determine the area  ID to travel to.
  # NavEncounterPath
  encounter_path:
    seq:
      - id: entry_area_id
        type: u4
        doc: The area ID to come from.
      - id: entry_direction
        type: u1
        enum: nav_direction
      - id: destination_area_id
        type: u4
      - id: destination_direction
        type: u1
        enum: nav_direction
      # Encounter spots
      - id: encounter_spot_count
        type: u1
        doc: Amount of encounter spots.
      - id: encounter_spot_data
        type: encounter_spot
        repeat: expr
        repeat-expr: encounter_spot_count
        doc: Sequence of encounter spots.
    doc: |
      A sequence of encounter spots which are used by NextBots to determine how to traverse an area.
  # NavArea
  nav_area:
    enums:
     # NavAttributeType
     nav_attribute_type:
      0: nav_mesh_id
      0x00000001: nav_mesh_crouch # Must crouch to use this node/area.
      0x00000002: nav_mesh_jump # Must jump to traverse this area (only used during generation).
      0x00000004: nav_mesh_precise # Do not adjust for obstacles, just move along area.
      0x00000008: nav_mesh_no_jump # Inhibit discontinuity jumping.
      0x00000010: nav_mesh_stop # Must stop when entering this area.
      0x00000020: nav_mesh_run # Must run to traverse this area.
      0x00000040: nav_mesh_walk # Must walk to traverse this area.
      0x00000080: nav_mesh_avoid # Avoid this area unless alternatives are too dangerous.
      0x00000100: nav_mesh_transient # Area may become blocked, and should be periodically checked.
      0x00000200: nav_mesh_dont_hide # Area should not be considered for hiding spot generation.
      0x00000400: nav_mesh_stand # Bots hiding in this area should stand.
      0x00000800: nav_mesh_no_hostages # Hostages shouldn't use this area.
      0x00001000: nav_mesh_stairs # This area represents stairs, do not attempt to climb or jump them - just walk up.
      0x00002000: nav_mesh_no_merge # Don't merge this area with adjacent areas.
      0x00004000: nav_mesh_obstacle_top # This nav area is the climb point on the tip of an obstacle.
      0x00008000: nav_mesh_cliff # This nav area is adjacent to a drop of at least CliffHeight.

      0x00010000: nav_mesh_first_custom # Apps may define custom app-specific bits starting with this value.
      0x04000000: nav_mesh_last_custom # Apps must not define custom app-specific bits higher than with this value.
      0x20000000: nav_mesh_func_cost # The navigation area is in a nav_func_cost entity.
      0x40000000: nav_mesh_has_elevator # Area is in an elevator's path.
      0x80000000: nav_mesh_nav_blocker # Area is blocked by nav blocker ( Alas, needed to hijack a bit in the attributes to get within a cache line [7/24/2008 tom]).
    seq:
      - id: area_id
        type: u4
        doc: Identifier of an area.
      - id: attribute_flag
        type: u4
        doc: Area attribute flag. Size varies across NAV versions.
      - id: north_west_corner
        type: f4
        repeat: expr
        repeat-expr: 3
        doc: The north-west corner position of an area.
      - id: south_east_corner
        type: f4
        repeat: expr
        repeat-expr: 3
        doc: The south-east corner position of an area.
      - id: north_east_corner_height
        type: f4
        doc: The height (Z coordinate) of the area's north-east corner.
      - id: south_west_corner_height
        type: f4
        doc: The height (Z coordinate) of the area's south-west corner.
      # Connection data.
      - id: connection_data
        type: area_id_array
        repeat: expr
        repeat-expr: 4
        doc: Container for connections.
      # Hide spots
      - id: hiding_spot_count
        type: u1
        doc: Amount of hiding spots.
      - id: hiding_spot_data
        type: hiding_spot
        repeat: expr
        repeat-expr: hiding_spot_count
      # Encounter Path sequence.
      # Encounter paths are only used by the Counter-Strike games, so they should be stored in custom data, not as part of the base nav mesh.
      - id: encounter_path_count
        type: u4
        doc: Amount of encounter paths.
      - id: encounter_path_data
        type: encounter_path
        repeat: expr
        repeat-expr: encounter_path_count
      # Place ID
      - id: place_id
        type: u2
        doc: Reference place index.
      # Ladders
      - id: ladder_data
        type: area_id_array
        repeat: expr
        repeat-expr: 2
      # Occupy times
      - id: earliest_occupation_time
        type: f4
        repeat: expr
        repeat-expr: 2
        doc: Earliest occupation times possible for each team. Added in NAV version 8.
      # Light Intensity
      - id: light_intensity
        type: f4
        repeat: expr
        repeat-expr: 4
        doc: Light Intensities for each corner. Added in NAV version 11.
      # Vis areas
      - id: area_bind_count
        type: u4
        doc: Amount of area-binds stored in area data. Added in NAV version 16.
      - id: area_bind_array
        type: area_bind
        repeat: expr
        repeat-expr: area_bind_count
      # Inheritance
      - id: area_id_visibility_inheritance
        type: u4
        doc: ID of area to inherit visibility bind information from.

      # Original NAV format does not safeguard for custom data.
      # My version adds a byte count (16 bytes / 1828 bits, which feels too large ik, but gotta think about that forward compatibility!) for the amount of custom data stored in bytes.
      # * As a result it is possible to skip past custom data.
      # * Custom data can be safely parsed without the need for specific implementations.
      - id: custom_data_byte_count
        type: u8
        doc: Length of the custom area data in bytes.

      - id: custom_data
        size: custom_data_byte_count
        doc: Custom area data as a byte array.

  # NavLadder
  nav_ladder:
    seq:
      - id: ladder_id
        type: u4
        doc: Area ID of the ladder.
      - id: width
        type: f4
        doc: Width of the ladder area.
      - id: top_corner
        type: f4
        repeat: expr
        repeat-expr: 3
        doc: Top corner (vector) of the ladder.
      - id: bottom_corner
        type: f4
        repeat: expr
        repeat-expr: 3
        doc: Bottom corner (vector) of the ladder.
      - id: length
        type: f4
        doc: Length of the ladder area.
      - id: direction
        type: u4
        enum: nav_ladder_direction
        doc: Direction of the navigation area.
      - id: top_forward_area_id
        type: u4
        doc: Connects area ID to the front of the top rung.
      - id: top_left_area_id
        type: u4
      - id: top_right_area_id
        type: u4
      - id: top_behind_area_id
        type: u4
      - id: bottom_area_id
        type: u4
    enums:
      nav_ladder_direction:
        0: up
        1: down
        2: count
    doc: A subtype of a navigation area that allows NextBots to walk up it.

enums:
  # The originial NAV file format stores directions in NESW.
  # My version stores directions as radians in doubles.
  nav_direction:
    0: north
    1: east
    2: south
    3: west
    # Amount of directions
    4: count