Graph (.dat) -- AI Navigation Graph

1. What the graph file contains

A graph<taskId>.dat file supplies an AI navigation graph to an AIGraph task. The task id appears in the filename and the graph's node positions are stored in the graph task's local frame. The engine adds the task position to a node position when it needs world coordinates.

The research signatures and method addresses below come from the IGI 1 graph analysis by Dimon Krevedko, Yoejin Light and Artiom Rotari, continued by IGI ResearchDevs@HM. The stream behavior and corpus observations are cross-checked against the OpenIGI graph reader and its retail corpus notes.

2. Two on-disk variants

The field order is consistent in the named retail files, but these are streams rather than fixed-size C records: each field is written as values and node/link records are assembled as their fields arrive. The engine commits a node when its criteria field arrives and a link when its link-type field arrives.

3. Named-field signatures

The field name is not stored as text. The engine hashes its registered name, stores the hash as a typed 32-bit value, then reads the declared value type and payload. The abbreviated signature below is the four-byte prefix shown in the original static research: a type tag followed by the low three bytes of the little-endian field hash. The full hash is included so fields that share a prefix remain distinguishable.

A string value carries a length byte; the count includes the terminating NUL. A blob carries its element type and declared length before its bytes. The route-table reader uses the graph's declared slot count to determine the expected table size.

4. Nodes, links and positional-only data

4.1 Node fields

The static notes call the criteria field Stringx18; the stream reader handles the named form as a length-prefixed string. Treat 18 as the research's field label, not a proven fixed on-disk width.

4.2 Criteria names

These are names resolved to bits in registration order, not a packed multi-bit integer in the file. Retail files contain the empty string or one of these three names.

4.3 Links

A link is assembled from nLinkID1, nLinkID2 and eLinkType. The engine registers it with both endpoint nodes, so links are undirected in the graph API. All 24,433 links observed in the retail corpus have link type 1.

4.4 Positional-only node data

The seven files without the magic use positional records. Each begins with node count, slot count and link count. A node then carries its id, position, gamma and radius, followed by an optional float, an optional material id, a criteria string and two counted lists of integer pairs. The engine's AIGraph hook reads the two lists to advance the stream; the retail parser retains them as positional extras. Links follow the nodes, and the route table follows the links when present.

5. Route table

The precomputed route table has nMaxNodes × nMaxNodes entries, each 8 bytes: a little-endian signed 32-bit next-node id and a 32-bit float cost. Its total size is therefore 8 × nMaxNodes² bytes.

struct RouteEntry {
    int32_t next_node; // -1 means no route
    float   cost;
};

For a route from from to to, the entry index is from + to × nMaxNodes. A no-route entry is { -1, -1.0 }. The engine asks the table for the next node at each step; the file already contains the route choices. This describes the observed lookup and does not assume which shortest-path algorithm produced the table.

6. Runtime extraction methods

The original research identifies these retail IGI.EXE routines as field extractors. Addresses are image-specific and should be read as labels for the analyzed executable:

7. Retail corpus observations

• 300 graph files across the fourteen levels: 293 named-field and 7 positional.
• Declared slot counts: 100 in 274 files, 200 in 19, 300 in 4 and 400 in 3.
• 8,317 nodes; the largest node id is 380. Slot 0 is unused.
• 24,433 links; 203 files contain links and 90 contain none.
• All route tables are square over the declared slot count and are consumed exactly at end of file.
• Criteria counts: empty 7,022; NODECRITERIA_DOOR 465; NODECRITERIA_VIEW 161; NODECRITERIA_STAIR 669.

Evidence note. The corpus counts and parser behavior above describe the OpenIGI retail-data audit. They are implementation cross-checks; the original graph research remains the source for the static signatures, criteria names and runtime addresses credited above.