Difference between revisions of "Paths (GTA SA)"

From GTAMods Wiki
Jump to navigation Jump to search
m (→‎Description)
(huge update)
Line 1: Line 1:
−
The 64 <code>nodes*.dat</code> files in <code>gta3.img</code> (or any other archive) contain the paths and some other path-related information. There's a file for every 750&times;750 unit square, starting at the south-west corner (-3000, -3000).
+
The 64 <code>nodes*.dat</code> files in <code>gta3.img</code> (or any other [[archive]]) contain the vehicle and ped paths and related information for [[:Category:GTA SA|GTA SA]]. There's a file for every 750&times;750 [[unit]] square, starting at the south-west corner (-3000, -3000) in [[Wikipedia:row-major order|row-major order]].
  
−
==Header==
+
==Purpose==
−
Contains information for locating the various sections in the file.
 
  
−
Total 20 bytes:
+
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 <code>[[Item_Placement#PATH|paths.ipl]]</code> and related. These files are still present in SA, but unused.
−
[DWord, 4b] Number of entries in section 1
 
−
[DWord, 4b] Number of entries in section 1a
 
−
[DWord, 4b] Number of entries in section 1b
 
−
[DWord, 4b] Number of entries in section 2
 
−
[DWord, 4b] Number of entries in section 3/5/6
 
  
−
==Section 1==
+
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.
−
Contains node data for pedestrians and vehicles.  Section 1a contains the nodes for vehicles and section 1b contains the nodes for pedestrians.
 
  
−
Total 28 bytes per entry:
+
Node files are streamed by the game &mdash; 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.
−
[Signed Word, 2b] Unknown
 
−
[Word, 2b]        Unknown
 
−
[DWord, 4b]      Unknown (always zero)
 
−
[Signed Word, 2b] X-position (must be divided by 8)
 
−
[Signed Word, 2b] Y-position (must be divided by 8)
 
−
[Signed Word, 2b] Z-position (must be divided by 8)
 
−
[Signed Word, 2b] Unknown
 
−
[Word, 2b]        Link ID
 
−
[Word, 2b]        Area ID
 
−
[Word, 2b]        Node ID
 
−
[Byte, 1b]        Path Width
 
−
[Byte, 1b]        Node Type
 
−
[DWord, 4b]      Flags
 
  
−
Explanations for some of these values:-
+
The separate <code>nodes*.dat</code> files in the <code>data\paths\</code> directory are ignored by the game.
−
* Link ID is an index to entries in section 3,5 and 6.
 
−
* Area ID is the area of the node, the same as in the filename.
 
−
* Node ID is used to refer to nodes in the other sections.
 
  
−
Node Type is some kind of group for the nodes.  In section 1a, a Note Type value of 1 is for cars, 2 is for boats and higher values are for race tracks and other mission applications.  For peds, there is a node type per village/city.
+
==File Format==
  
−
[[Category:Map_Formats]]
+
Each file starts with a header, followed by 7 distinct sections.
 +
 
 +
Paths are stored as double-linked (thus undirected) [[Wikipedia:graph theory|graphs]] in [[Wikipedia:adjacency list|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 1a)
 +
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    - unknown, always 0x7FFE
 +
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    - Node Type
 +
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 128.
 +
;Link ID: Index into sections 3, 5 and 6; used to find adjacent nodes.
 +
;Area ID and Node ID: Informational data, probably only used by the path generator. 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)''.
 +
;Node Type: Defines some kind of group for the nodes. For vehicle nodes a value of 1 is for cars, 2 is for boats and higher values are for race tracks and other mission applications. For ped nodes there seems to be a distinct ID per village/city/area.
 +
;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.
 +
 
 +
''Node flag bits, from low to high:''
 +
 
 +
  0-3 - link count
 +
T 4,5 - traffic reduction (0 = full, 1 = medium, 2 = low, 3 = none)
 +
A  6 - road blocks?
 +
B  7 - boats
 +
C  8 - no traffic (emergency vehicles only)
 +
D  9 - zero
 +
E  10 - unknown, grove house entrance paths ?
 +
F  11 - zero
 +
G  12 - is not highway ?
 +
H  13 - is highway ? - these two are 00 for peds and never 11 for cars (so G = !H)
 +
I  14 - zero
 +
J  15 - zero
 +
K  16 - unknown, usually 1, except for 9 nodes
 +
L  17 - unknown, usually 1, except for those without K and several more
 +
M  18 - unknown, usually 1, similar to K and L, seems to exclude both
 +
N  19 - unknown, usually 1, similar to M
 +
O  20 - sort of road block, rarely used
 +
P  21 - parking
 +
Q  22 - zero
 +
R  23 - similar to O
 +
24-31 - zero
 +
 
 +
The following ''statistics on flag usage'', grouped by path type, might be useful for further research:
 +
 
 +
    Peds  Cars  Boats Tracks
 +
#  37650  27083  1507  1997
 +
A  none  1.44%  none  none
 +
B  none  none    all  4.46%
 +
C 15.99% 22.95% 15.79% 60.89%
 +
D  none  none  none  none
 +
E  0.05%  none  none  none
 +
F  none  none  none  none
 +
G  none 90.63%    all 94.39%
 +
H  none  9.37%  none  none
 +
I  none  none  none  none
 +
J  none  none  none  none
 +
K 99.99% 99.98%    all    all
 +
L 97.41% 98.35%    all    all
 +
M 97.41% 98.33%    all    all
 +
N 97.23%    98%    all    all
 +
O  none  0.03%  none  none
 +
P  none  0.79%  none  0.05%
 +
Q  none  none  none  none
 +
R  none  0.06%  none  none
 +
 
 +
===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.
 +
 
 +
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 128.
 +
;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 <nowiki>[-100, 100]</nowiki>, which corresponds to floating point values <nowiki>[-1.0, 1.0]</nowiki>.
 +
;Flags: These are used to characterize path segment behavior, for more information see the table below.
 +
 
 +
  0- 7 - unknown
 +
  8-10 - number of left lanes
 +
11-13 - number of right lanes
 +
    14 - unknown/intersection behavior
 +
    15 - zero/unused
 +
16,17 - traffic light behavior
 +
18-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 ''intersection behavior'' flag is somewhat related to this; it is only used if the target node is in the center of the intersection, but this has not been tested yet.
 +
 
 +
===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 <code>0xFF,0xFF,0x00,0x00</code> (192x), but this can be filled with zeros as well.
 +
 
 +
===Section 5 - Navi Links===
 +
 
 +
These are links to adjacent navi nodes, '''2 bytes''' per entry. For indices from ped nodes (in section 1b) these are zero (unused).
 +
 
 +
2b - UINT16 - lower 10 bit are the Node ID, upper 6 bit the Area ID
 +
 
 +
===Section 6 - Link Lengths===
 +
 
 +
These are the distances between linked nodes in full [[unit]]s, '''1 byte''' per entry. They are essential for path finding algorithms.
 +
 
 +
1b - UINT8 - Length
 +
 
 +
===Section 7 - unknown===
 +
 
 +
Unknown length, unknown content. This section is filled mainly with zeros, but there are exceptions of bytes with very low values greater than zero. It is assumed that this section is actually unused and might just be garbage.
 +
 
 +
==Tools &amp; Scripts==
 +
 
 +
* [http://www.gtagarage.com/mods/show.php?id=1093 SA Path Editor] (WIP) by [[User:<nowiki>JGuntherS@NL</nowiki>|<nowiki>JGuntherS@NL</nowiki>]] &ndash; Only useful for editing existing path data.
 +
* [http://www.gtaforums.com/index.php?showtopic=214901&view=findpost&p=3841297 Path Compiler] (WIP) by [[User:ocram88|ocram88]] &ndash; Allows to create linear ped paths by generating waypoints from inside the game.
 +
* [http://www.gtaforums.com/index.php?showtopic=214901&view=findpost&p=3936074 Path Tool] (WIP) by [[User:steve-m|steve-m]] &ndash; Comes bundled with a MaxScript to export ped and vehicle paths from Max (by using spline shapes).
 +
 
 +
==See Also==
 +
 
 +
* [http://www.gtaforums.com/index.php?showtopic=214901 Compiled Path Nodes] &ndash; original discussion thread on GTAForums
 +
 
 +
 
 +
[[Category:Map Formats]][[Category:GTA SA]]

Revision as of 22:02, 14 November 2006

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.

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

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 1a)
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    - unknown, always 0x7FFE
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    - Node Type
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 128.
Link ID
Index into sections 3, 5 and 6; used to find adjacent nodes.
Area ID and Node ID
Informational data, probably only used by the path generator. 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).
Node Type
Defines some kind of group for the nodes. For vehicle nodes a value of 1 is for cars, 2 is for boats and higher values are for race tracks and other mission applications. For ped nodes there seems to be a distinct ID per village/city/area.
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.

Node flag bits, from low to high: 

  0-3 - link count
T 4,5 - traffic reduction (0 = full, 1 = medium, 2 = low, 3 = none)
A   6 - road blocks?
B   7 - boats
C   8 - no traffic (emergency vehicles only)
D   9 - zero
E  10 - unknown, grove house entrance paths ?
F  11 - zero
G  12 - is not highway ?
H  13 - is highway ? - these two are 00 for peds and never 11 for cars (so G = !H)
I  14 - zero
J  15 - zero
K  16 - unknown, usually 1, except for 9 nodes
L  17 - unknown, usually 1, except for those without K and several more
M  18 - unknown, usually 1, similar to K and L, seems to exclude both
N  19 - unknown, usually 1, similar to M
O  20 - sort of road block, rarely used
P  21 - parking
Q  22 - zero
R  23 - similar to O
24-31 - zero

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

    Peds   Cars  Boats Tracks
#  37650  27083   1507   1997
A   none  1.44%   none   none
B   none   none    all  4.46%
C 15.99% 22.95% 15.79% 60.89%
D   none   none   none   none
E  0.05%   none   none   none
F   none   none   none   none
G   none 90.63%    all 94.39%
H   none  9.37%   none   none
I   none   none   none   none
J   none   none   none   none
K 99.99% 99.98%    all    all
L 97.41% 98.35%    all    all
M 97.41% 98.33%    all    all
N 97.23%    98%    all    all
O   none  0.03%   none   none
P   none  0.79%   none  0.05%
Q   none   none   none   none
R   none  0.06%   none   none

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. 

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 128.
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].
Flags
These are used to characterize path segment behavior, for more information see the table below.
 0- 7 - unknown
 8-10 - number of left lanes
11-13 - number of right lanes
   14 - unknown/intersection behavior
   15 - zero/unused
16,17 - traffic light behavior
18-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 intersection behavior flag is somewhat related to this; it is only used if the target node is in the center of the intersection, but this has not been tested yet.

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, 2 bytes per entry. For indices from ped nodes (in section 1b) these are zero (unused). 

2b - UINT16 - lower 10 bit are the Node ID, upper 6 bit the 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 - unknown

Unknown length, unknown content. This section is filled mainly with zeros, but there are exceptions of bytes with very low values greater than zero. It is assumed that this section is actually unused and might just be garbage.

Tools & Scripts

  • SA Path Editor (WIP) by [[User:JGuntherS@NL|JGuntherS@NL]] – Only useful for editing existing path data.
  • Path Compiler (WIP) by ocram88 – Allows to create linear ped paths by generating waypoints from inside the game.
  • Path Tool (WIP) by steve-m – Comes bundled with a MaxScript to export ped and vehicle paths from Max (by using spline shapes).

See Also

Retrieved from "https://gtamods.com/mediawiki/index.php?title=Paths_(GTA_SA)&oldid=793"