Paths (GTA SA)

Colour-coded car path nodes for GTA: SA.

The 64 nodes*.dat files in gta3.img (or any other archive) contain the vehicle and ped paths and related information for GTA SA. There's a file for every 750×750 unit square, starting at the south-west corner (-3000, -3000) in row-major order.

However paths for planes and trains are not stored in the node-files. Nodes exist in any of the game's interiors and can only be influenced through SCM using the opcodes 01EB and 03DE. Trains are using paths in the tracks(1-4).dat and there are also paths for several missions and concrete cars. These paths are carrec's.

Usually cars and pedestriants are using nodes if they are not linked to an SCM or an carrec path in any way.

Purpose

It is believed that these files were generated by some sort of path compiler during development of the game, and represent the processing-friendly binary data structures otherwise generated at runtime by previous versions of the game from files like paths.ipl and related. These files are still present in SA, but unused.

Since the built-in path compiler has apparently been removed from the game code or at least made nonfunctional, custom tools and techniques are required to generate new paths for SA.

Node files are streamed by the game — only the active area and those surrounding it are loaded at a time. Thus corrupt files only lead to a game crash when the player enters the specific area.

The separate nodes*.dat files in the data\paths\ directory are ignored by the game.

File format of standard path file

Each file starts with a header, followed by 7 distinct sections.

Paths are stored as double-linked (thus undirected) graphs in adjacency list representation. There can be connections between separate areas.

The following data types and structures are used within this article:

• INT8/UINT8 - signed/unsigned 8 bit integer (1 byte)
• INT16/UINT16 - signed/unsigned 16 bit integer (2 byte)
• INT32/UINT32 - signed/unsigned 32 bit integer (4 byte)
• FLOAT - single precision floating point number (4 byte)

Header

The header contains information about the content of the various sections in the file. It has a size of 20 bytes.

4b - UINT32 - number of nodes (section 1)
4b - UINT32 - number of vehicle nodes (section 1a)
4b - UINT32 - number of ped nodes (section 1b)
4b - UINT32 - number of navi nodes (section 2)
4b - UINT32 - number of links (section 3/5/6)

Note: Sections related to links (3/5/6) have the same number of entries. These entries belong together and can be treated as one record by editors.

Section 1 - Path Nodes

The first section contains the node data for the paths. They are grouped by type: the list of vehicle nodes (cars, boats, race tracks) is followed by the ped nodes. Each node entry has a size of 28 bytes.

4b - UINT32   - Mem Address, unused
4b - UINT32   - always zero, unused
6b - INT16[3] - Position (XYZ), see below
2b - INT16    - heuristic cost, always 0x7FFE, used internally to calculate routes
2b - UINT16   - Link ID
2b - UINT16   - Area ID (same as in filename)
2b - UINT16   - Node ID (increments by 1)
1b - UINT8    - Path Width
1b - UINT8    - Flood Fill, used in route calculations
4b - UINT32   - Flags

Mem Address

These might have been pointers to path segment structures inside R*'s path compiler. Apparently they are ignored by the game and can be set to zero.

Position

This is the position of the node in world coordinates. To convert the signed words to floating point values divide them by 8.

Link ID

Used to find adjacent nodes, the difference to the Node ID is that it counts all the links each node has.

Area ID and Node ID

Informational data, used to connect nodes via Links. Area ID is always the same as the number in the filename, and Node ID is used to identify the node.

Path Width

This is used to modify the width of a path. The default value is 0 (zero). To convert the signed word to a floating point value divide it by 8 (unconfirmed).

Flood Fill

Flood IDs for route calculation for NPCs. For normal NPC vehicle traffic a value of 1 is used, 2 is for boats and higher values are allocated to disconnected path area segment, e.g for race tracks and other mission applications.

Flags

The first 4 bits define the number of links to adjacent nodes. The other bits are used to characterize node behavior, for more information see the table below.

Path Node Flags

Node flag bits, from low to high:

0-3   - Link Count
4-5   - TrafficLevel

The LinkCount defines the number of enties incrementing from the LinkID. The TrafficLevel uses 4 steps: 0 = full 1 = high 2 = medium 3 = low

A    06    - Road-Blocks
B    07    - Boats
C    08    - Emergency Vehicles only
D    09    - zero/unused
E    10    - unknown, grove house entrance paths ?
F    11    - zero/unused
G    12    - Is not Highway
H    13    - Is Highway (ignored for PED-Nodes and never 11 or 00 for Cars!)
I    14    - zero
J    15    - zero
K-M  16-19 - spawn probability (0x00 to 0x0F)[1]
O    20    - RoadBlock?
P    21    - Parking
Q    22    - zero
R    23    - RoadBlock?

 24-31 - zero (unused)

The following statistics on flag usage, grouped by path type, might be useful for further research:

   | Peds           | Cars           | #
#  | 37650          | 30587          | --
A  | 0              | 391 (1.28%)    | 391
B  | 0              | 1596 (5.22%)   | 1596
C  | 6019 (15.99%)  | 7669 (25.08%)  | 13688
D  | 0              | 0              | 0
E  | 17 (0.05%)     | 0              | 17
F  | 0              | 0              | 0
G  | 0              | 27936 (91.33%) | 27936
H  | 0              | 2539 (8.3%)    | 2539
I  | 0              | 0              | 0
J  | 0              | 0              | 0
K  | 37646 (99.98%) | 30582 (99.98%) | 68228
L  | 36676 (97.41%) | 30141 (98.54%) | 66817
M  | 36676 (97.41%) | 30136 (98.52%) | 66812
N  | 36607 (97.22%) | 30046 (98.23%) | 66653
O  | 0              | 8 (0.03%)      | 8
P  | 0              | 215 (0.7%)     | 215
Q  | 0              | 0              | 0
R  | 0              | 16 (0.05%)     | 16

Section 2 - Navi Nodes

The second section contains additional nodes, referred to as navigational nodes (navi nodes) in this article. Each record has a size of 14 bytes.

Navi nodes are used to define additional information for vehicle path segments; they are not used by ped paths. They are usually positioned between two adjacent vehicle nodes on an interpolated curve.

There may be bugs if you don't connect navi nodes correctly. The order to connect them is to check first which of the 2 linked nodes is 'higher'. That means which one has the higher node ID or area ID. The direction of linking is allways from higher to lower node. So the target node of the navi nodes is allways the lower node. (Espacially on area boundaries!)

4b - INT16[2] - Position (XY), see below
2b - UINT16   - Area ID
2b - UINT16   - Node ID
2b - INT8[2]  - Direction (XY), see below
4b - UINT32   - Flags

Position

This is the position of the navi node in world coordinates. To convert the signed words to floating point values divide them by 8.

Area ID and Node ID

These identify the target node a navi node is attached to.

Direction

This is a normalized vector pointing towards above mentioned target node, thus defining the general direction of the path segment. The vector components are represented by signed bytes with values within the interval [-100, 100], which corresponds to floating point values [-1.0, 1.0].

Navi Node Flags

These are used to characterize path segment behavior, for more information see the table below.

 0- 7 - path node width, usually a copy of the linked node's path width (byte)
 8-10 - number of left lanes
11-13 - number of right lanes
   14 - traffic light direction behavior
   15 - zero/unused
16,17 - traffic light behavior
   18 - train crossing
19-31 - zero/unused

• Right (forward) and left (backward) lanes are relative to the direction vector.
• Experience has shown that navi nodes with attachments across area borders don't work too well. A possible solution is to attach them to the last instead of the next node, reverse the direction and exchange the lane numbers (if different) and other direction dependent flags. However, this will never work if previous, navi and next node are located in different areas each. (*)
• Traffic light behavior can be a value from 0 to 2, where 0 means traffic lights is disabled, 1 and 2 are used for the traffic lights and are North-South and West-East cycles for traffic light synchronization respectively.
• The traffic light direction behavior is 1 if the navi node has the same direction as the traffic light and 0 if the navi node points somewhere else.

( (*) Gots clear after knowing how Navis are linked exactly. So you may use this but it is not obligation.)

Section 3 - Links

These are links to adjacent nodes, 4 bytes per entry.

2b - UINT16 - Area ID
2b - UINT16 - Node ID

Section 4 - Filler

This section hold data of constant size and content; its purpose is unknown. These 768 bytes are filled with the repeating data pattern 0xFF,0xFF,0x00,0x00 (192x), but this can be filled with zeros as well.

Section 5 - Navi Links

These are links to adjacent navi nodes, one for each link (in section 3), 2 bytes per entry. For indices from ped nodes (in section 1b) these are zero (unused).

2b - UINT16 - lower 10 bit are the Navi Node ID, upper 6 bit the corresponding Area ID

Please note that this limits the number of Navi Nodes (i.e. vehicle path segments) to 1024 per area file and the number of files/areas to 64! Also, be aware that the Navi Node ID is not the Linked Node ID on Section 2, but rather, the order in which the Navi Node is on the file.

Section 6 - Link Lengths

These are the distances between linked nodes in full units, 1 byte per entry. They are essential for path finding algorithms.

1b - UINT8 - Length

Section 7 - Path Intersection Flags

This section consists of intersection flag values for each node address (i.e. node link).

class CPathIntersectionInfo
{
public:
    unsigned char m_bRoadCross : 1;
    unsigned char m_bPedTrafficLight : 1;
};

The size of section is equal to count of node addresses. The section is followed by 192 bytes of unknown data.

File format of fastman92 path file

This article may need to be rewritten. Please help improve this article. The discussion page may contain suggestions.

Each file starts with a header, followed by 7 distinct sections.

Paths are stored as double-linked (thus undirected) graphs in adjacency list representation. There can be connections between separate areas.

The following data types and structures are used within this article:

• INT8/UINT8 - signed/unsigned 8 bit integer (1 byte)
• INT16/UINT16 - signed/unsigned 16 bit integer (2 byte)
• INT32/UINT32 - signed/unsigned 32 bit integer (4 byte)
• FLOAT - single precision floating point number (4 byte)

Structures

Go here to see the C++ structures used in new format of path file: http://pastebin.com/7hpLZmJJ

Compressed vector

Compressed vector is the way to save some memory in GTA games. It's a structure with __int16 values of x, y, z coordinates. GTA uses accuracy of 8 parts per whole number. To convert __int16 or __int32 value back into float value, you have to cast it into float value, then divide by 8.

#pragma pack(push, 1)
class CompressedVector
{
public:
   signed __int16 x;
   signed __int16 y;
   signed __int16 z;
};
#pragma pack(pop)

Extended version of CompressedVector is used in new format of path files. __int16 values were replaced into __int32 values. __int16 was making a limit of (-2^15/8 = -4096) to ((2^15) - 1) / 8 = 4 095,875

#pragma pack(push, 1)
class CompressedVector_extended
{
public:
   signed __int32 x;
   signed __int32 y;
   signed __int32 z;
};
#pragma pack(pop)

Node address

#pragma pack(push, 1)
struct CNodeAddress
{
  unsigned __int16 areaId;
  unsigned __int16 nodeId;
};
#pragma pack(pop)

Node address structure hold area ID and node ID.

Header

The header contains information about the content of the various sections in the file..

4b - UINT32 - is different format? Should have a value of 0xFFFFFFFF
4b - UINT32 - format, should have a value "FM92"
1b - UINT8 - n, size of nickname
char[n] - nickname, should have a value ( "\x00" "fastman92" "\x00" )
4b - UINT32 - format version, should have a value "VER2" or "VER3"
4b - UINT32 - number of nodes (section 1)
4b - UINT32 - number of vehicle nodes (section 1a)
4b - UINT32 - number of ped nodes (section 1b)
4b - UINT32 - number of navi nodes (section 2)
4b - UINT32 - number of links (section 3/5/6)

Note: Sections related to links (3/5/6) have the same number of entries. These entries belong together and can be treated as one record by editors.

Section 1 - Path Nodes

The first section contains the node data for the paths. They are grouped by type: the list of vehicle nodes (cars, boats, race tracks) is followed by the ped nodes. Size of CPathNode_extended equals to 40 bytes.

	// standard GTA SA
	#pragma pack(push, 1)
	struct CPathNode	
	{
		CPathNode *m_pPrev;
		CPathNode **m_ppNext;
		CompressedVector m_posn;
		int16_t m_wSearchList;
		int16_t m_wConnectedNodesStartId;	// ID into link array
		CNodeAddress m_nodeInfo;

		char m_nPathWidth;
		uint8_t m_nFloodID;		// unused when fastman92 path format VER3 is used
		uint32_t m_dwFlags;

		// Returns number of links
		int GetNumberOfLinks() { return this -> m_dwFlags & 0xF; }
	};
	#pragma pack(pop)

	VALIDATE_SIZE(CPathNode, 0x1C);

	// fastman92 path format VER2
	struct CPathNode_extended : public CPathNode
	{
		CompressedVector_extended m_extended_posn;

		// Sets the position in vector
		void GetExPosition(CVector& out)
		{
			out.x = (float)this->m_extended_posn.x / PATH_COORD_MULTIPLIER;
			out.y = (float)this->m_extended_posn.y / PATH_COORD_MULTIPLIER;
			out.z = (float)this -> m_extended_posn.z / PATH_COORD_MULTIPLIER;
		}
	};

	VALIDATE_SIZE(CPathNode_extended, 0x28);

	// fastman92 path format VER3
	#pragma pack(push, 1)
	struct CPathNode_extended2 : public CPathNode_extended
	{
		int16_t m_nExFloodID;
	};
	#pragma pack(pop)

	VALIDATE_SIZE(CPathNode_extended2, 0x2A);

Section 2 - Navi Nodes

The second section contains additional nodes, referred to as navigational nodes (navi nodes) in this article. Size of CCarPathLink_extended equals to 22 bytes.

Navi nodes are used to define additional information for vehicle path segments; they are not used by ped paths. They are usually positioned between two adjacent vehicle nodes on an interpolated curve.

There may be bugs if you don't connect navi nodes correctly. The order to connect them is to check first which of the 2 linked nodes is 'higher'. That means which one has the higher node ID or area ID. The direction of linking is allways from higher to lower node. So the target node of the navi nodes is allways the lower node. (Especially on area boundaries!)

#pragma pack(push, 1)
struct CCarPathLink
{
  __int16 posX;  // deprecated field
  __int16 posY;  // deprecated field
  CNodeAddress info;
  char dirX;
  char dirY;
  char m_nPathNodeWidth;
  char m_nFlags[2];
  char field_D;
};
#pragma pack(pop)

#pragma pack(push, 1)
struct CCarPathLink_extended : public CCarPathLink
{
 signed __int32 extended_posX;
 signed __int32 extended_posY;
};
#pragma pack(pop)

Area ID and Node ID

These identify the target node a navi node is attached to.

Direction

This is a normalized vector pointing towards above mentioned target node, thus defining the general direction of the path segment. The vector components are represented by signed bytes with values within the interval [-100, 100], which corresponds to floating point values [-1.0, 1.0].

Extended position

This is the position of the navi node in world coordinates. To convert the signed dwords to floating point values divide them by 8.

Navi Node Flags

These are used to characterize path segment behavior, for more information see the table below.

 0- 7 - path node width, usually a copy of the linked node's path width (byte)
 8-10 - number of left lanes
11-13 - number of right lanes
   14 - traffic light direction behavior
   15 - zero/unused
16,17 - traffic light behavior
   18 - train crossing
19-31 - zero/unused

• Right (forward) and left (backward) lanes are relative to the direction vector.
• Experience has shown that navi nodes with attachments across area borders don't work too well. A possible solution is to attach them to the last instead of the next node, reverse the direction and exchange the lane numbers (if different) and other direction dependent flags. However, this will never work if previous, navi and next node are located in different areas each. (*)
• Traffic light behavior can be a value from 0 to 2, where 1 and 2 are related to North-South and West-East cycles for traffic light synchronization.
• The traffic light direction behavior is 1 if the navi node has the same direction as the traffic light and 0 if the navi node points somewhere else.

( (*) Gots clear after knowing how Navis are linked exactly. So you may use this but it is not obligation.)

Section 3 - Links

These are links to adjacent nodes, 4 bytes per entry.

2b - UINT16 - Area ID
2b - UINT16 - Node ID

Section 4 - Filler

This section hold data of constant size and content; its purpose is unknown. These 768 bytes are filled with the repeating data pattern 0xFF,0xFF,0x00,0x00 (192x), but this can be filled with zeros as well.

Section 5 - Navi Links

These are links to adjacent navi nodes, 4 bytes per entry. For indices from ped nodes (in section 1b) these are zero (unused).

4b - UINT32 - lower 16 bit are the Navi Node ID, upper 16 bit the corresponding Area ID

Section 6 - Link Lengths

These are the distances between linked nodes in full units, 1 byte per entry. They are essential for path finding algorithms.

1b - UINT8 - Length

Section 7 - Path Intersection Flags

This section consists of intersection flag values for each node address (i.e. node link).

class CPathIntersectionInfo
{
public:
    unsigned char m_bRoadCross : 1;
    unsigned char m_bPedTrafficLight : 1;
};

The size of section is equal to count of node addresses. The section is followed by 192 bytes of unknown data.

EOF

Path file should be terminated by a DWORD value "EOF". Otherwise, it's considered invalid.

4b - UINT32 - Last value of path file - "EOF"

Tools & Scripts

•  GTAGarage: SA Path Editor (WIP) by JGuntherS@NL – Only useful for editing existing path data.
•  GTAForums: Path Compiler (WIP) by ocram88 – Allows to create linear ped paths by generating waypoints from inside the game.
•  GTAForums: Path Tool (WIP) by steve-m – Comes bundled with a MaxScript to export ped and vehicle paths from Max (by using spline shapes).
•  GTAForums: APE v1.1 by Aschratt – Based on a memhack and including a decompiler it is possible to add path to the existing or to create completely new from ingame!
•  GTAForums: Path Script – a script by Deniska for 3DSMax that creates path files directly.
•  GTAForums: PathViewer – a tool by Aschratt which allows to view paths and highlight nodes with special flags in 3D.
•  GTAForums: fastman92 limit adjuster – Limit adjuster by fastman92 which allows to increase the path limits.

See Also

•  GTAForums: Compiled Path Nodes – original discussion thread
• ^  GTAForums: Paths Documentation for SA, VC and GTA3