[2021 Re-Release] Bot navigation .nav file format

Describes the file format of the bot navigation files .nav used by the Quake 2021 Re-Release version.

Introduction

This guide will describe and explain the .nav files. These are the files that save all the bot navigation data (eg: waypoints). This guide is intended for programmers.

It's a binary format but it's relatively simple. I've written the format into Kaitai[kaitai.io]. Download the KSY file here[pastebin.com] and you can try it at their online IDE[ide.kaitai.io]. From there you're able to upload .nav files and see the contents or generate file readers for multiple programming languages.

Version

The current .nav (as of Sep 24 2021 version) is version 15.

Some important info

All offsets are relative to the beginning of the structure or sub-structure, not the file. The file is variable length so it's not possible to do that anyway.

Here's the types and their length in case there's any confusion:

Type	Size (bytes)	Comment
int	4
short	2
float	4
vector3	12	XYZ coordinates, 3 floats

Diagram

This is a diagram generated from the Kaitai struct file. It might not correspond 1:1 to what is in this guide but all the fields are there.

File Structure

The file is divided into 6 structures.

Rel. Off.	Name	Type	Description
0	Header	Header	Header of the file. Contains some important info.
20	Nodes	Node[]	Info about the nodes
...	Node origins	NodeOrigin[]	3D coordinates where nodes are placed
...	Links	Link[]	Info about the links between nodes
...	Traversals	Traversal[]	Info that helps bots on how to traverse big gaps between nodes
...	Edicts	Edicts	Info about connection of links to edicts

Header

The header of the file contains mostly counters that tell you how much data to expect.

Rel. Off.	Name	Type	Description
0	Magic Number	char[4]	Always 'NAV2'
4	Version	int	Indicates the version of this nav file. Currently 15.
8	Node count	int	How many nodes exist in the file
12	Link count	int	How many links exist in the file
16	Traversal count	int	How many traversals exist in the file

After the header comes the Node structure.

Nodes

The node structure contains info related to each node, but surprisingly not the position as that is contained inside a separate structure.

There are as many sequential nodes here as specified in the header.

Rel. Off.	Name	Type	Description
0	Flags	short	The type of node. See table below
2	Connection count	short	How many outgoing connections this node has.
4	Connection start index	short	In which index in the connection array the connections for this node begin.
6	Radius	short	Radius of the node

After this array, the file continues with Node origins structure.

Node flags

This is a bit flag enum.

Bit flag	Description
1	Teleporter
2	Pusher
4	Elevator Top
8	Elevator Bottom
16	Underwater
32	Hazard
64	Check for Floor
128	Check for Solid

Nodes origins

The nodes origin coordinates are stored in a separate array. There is as many as there are Nodes and they correspond by index. So for example, Node[53] will be NodeOrigin[53].

Rel. Off.	Name	Type	Description
0	Origin	vector3	XYZ coordinates

After this, comes the Links structure.

Links

The links connect all nodes together and provide pathing for the bots, however this array is quite bare.

As with Nodes, there are as many Links as defined in the Header.

Rel. Off.	Name	Type	Description
0	Destination	short	Target Node index where this link leads to
2	Type	short	What type of link this is. See table below.
4	Traversal index	short	Index of the traversal info to use for this link. 0xFFFF if not used.

The file continues with the Traversals structure.

Link types

A link can only be 1 type.

Value	Name
0	Walk
1	Long Jump
2	Teleport
3	Walk Off Ledge
4	Pusher
5	Barrier Jump
6	Elevator
7	Train
8	Manual Jump
9	Unknown (literally)

Traversals

This is probably the most surprising thing from the file, as it contains pre-computed helping coordinates to tell the bot how to traverse gaps like long jumps.

There as many Traversals as specified in the Header.

For simplicity sake I'll condense XYZ float coordinates into a 'vector3' type.

Rel. Off.	Name	Type	Description
0	Node exit	vector3	Where the bot should leave the node. Coordinate is at the radius edge.
12	Jump start	vector3	Where the bot should start jumping.
24	Jump end	vector3	Where the jump ends / lands.

The file continues with the Edicts structure.

Edicts

The final structure of the file is the Edicts. It appears to be kind of independent of the other structures as it links Nodes to Edicts.

Header

The structure begins with a small header that indicates how many 'Edict' entries come after.

Rel. Off.	Name	Type	Description
0	Edict count	int	How many edicts are contained in the file.

Edict

There are as many Edict as specified in the Edict header.

Rel. Off.	Name	Type	Description
0	Link id	short	Which link this belongs to, connected via it's index
2	Mins	vector3	The world coordinates for the target edict 'mins'
14	Maxs	vector3	The world coordinates for the target edict 'maxs'
26	entity_id	int	Entity index of target edict, in negative numbers.

Entity Index

The entity index is

-entity_index - 1

of the actual index.
In-game you'll see like, "func_door_16". This means the number that is written to this field would be -17.

Versioning

List of .nav versions:

Version 18

• Higher bytes of link types are now used as team masks

Version 17

• Added heuristic

Version 15

Kaitai[pastebin.com]

• Edict now contains an entity_id instead of targetname and classname.
  
• New node flags: Check for Floor, Check for Solid.

Version 14

Kaitai[pastebin.com]