Paths (GTA SA) - Revision history

GrandTheftAutoSanAndreas: /* Section 2 - Navi Nodes */

2010-12-19T08:44:27Z

Section 2 - Navi Nodes

← Older revision		Revision as of 08:44, 19 December 2010
Line 138:		Line 138:

	Note: There is no Z coordinate for Navi Nodes. Instead, the vehicle relies on collision data from the road model.		Note: There is no Z coordinate for Navi Nodes. Instead, the vehicle relies on collision data from the road model.

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

GrandTheftAutoSanAndreas: /* Section 2 - Navi Nodes */

2010-12-19T08:43:56Z

Section 2 - Navi Nodes

← Older revision		Revision as of 08:43, 19 December 2010
Line 136:		Line 136:
	;Area ID and Node ID: These identify the target node a navi node is attached to.		;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>.		;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>.

			Note: There is no Z coordinate for Navi Nodes. Instead, the vehicle relies on collision data from the road model.
	====Navi Node Flags====		====Navi Node Flags====
	These are used to characterize path segment behavior, for more information see the table below.		These are used to characterize path segment behavior, for more information see the table below.

A-Dust at 01:28, 21 September 2010

2010-09-21T01:28:06Z

← Older revision		Revision as of 01:28, 21 September 2010
Line 1:		Line 1:
	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 [[GTA SA]]. There's a file for every 750×750 [[unit]] square, starting at the south-west corner (-3000, -3000) in [[Wikipedia:row-major order\|row-major order]].		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 [[Grand Theft Auto: San Andreas\|GTA SA]]. There's a file for every 750×750 [[unit]] square, starting at the south-west corner (-3000, -3000) in [[Wikipedia:row-major order\|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]].		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]].

Gtabot: /* File Format */clean up, replaced: {{SA-navi}} → {{gtasa}}

2010-01-23T20:30:22Z

File Format: clean up, replaced: {{SA-navi}} → {{gtasa}}

← Older revision		Revision as of 20:30, 23 January 2010
Line 182:		Line 182:

	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.		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.
	{{~~SA-navi~~}}		{{gtasa}}

	[[Category:Map Formats]][[Category:GTA SA]]{{fdl}}		[[Category:Map Formats]][[Category:GTA San Andreas]]{{fdl}}

Gtabot: clean up,

2010-01-23T20:18:22Z

clean up,

@@ Line 182: / Line 182: @@
 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.
 {{SA-navi}}
 [[Category:Map Formats]][[Category:GTA SA]]{{fdl}}

Gtabot: clean up,

2010-01-23T20:13:55Z

clean up,

← Older revision		Revision as of 20:13, 23 January 2010
Line 1:		Line 1:
	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 [[GTA SA]]. There's a file for every 750×750 [[unit]] square, starting at the south-west corner (-3000, -3000) in [[Wikipedia:row-major order\|row-major order]].		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 [[GTA SA]]. There's a file for every 750×750 [[unit]] square, starting at the south-west corner (-3000, -3000) in [[Wikipedia:row-major order\|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\|~~01EB]] and [[~~03DE\|~~03DE]].		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 <code>[[Carrec\|carrec's]]</code>.		Trains are using paths in the tracks(1-4).dat and there are also paths for several missions and concrete cars. These paths are <code>[[Carrec\|carrec's]]</code>.

Line 188:		Line 188:
	* {{GTAF\|post\|214901\|3841297\|Path Compiler (WIP)}} by {{U\|ocram88}} – Allows to create linear ped paths by generating waypoints from inside the game.		* {{GTAF\|post\|214901\|3841297\|Path Compiler (WIP)}} by {{U\|ocram88}} – Allows to create linear ped paths by generating waypoints from inside the game.
	* {{GTAF\|post\|214901\|3936074\|Path Tool (WIP)}} by {{U\|steve-m}} – Comes bundled with a MaxScript to export ped and vehicle paths from Max (by using spline shapes).		* {{GTAF\|post\|214901\|3936074\|Path Tool (WIP)}} by {{U\|steve-m}} – Comes bundled with a MaxScript to export ped and vehicle paths from Max (by using spline shapes).
	* ~~{{GTAF\|295628\|APE v1.1}}~~ by {{U\|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!		* by {{U\|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!
	* ~~{{GTAF\|283684\|Path Script}}~~ – a script by {{U\|Deniska}} for 3DSMax that creates path files directly.		* – a script by {{U\|Deniska}} for 3DSMax that creates path files directly.
	* ~~{{GTAF\|392955\|PathViewer}}~~ – a tool by {{U\|Aschratt}} which allows to view paths and highlight nodes with special flags in 3D.		* – a tool by {{U\|Aschratt}} which allows to view paths and highlight nodes with special flags in 3D.

	==See ~~Also~~==		==See also==

	* {{GTAF\|214901\|Compiled Path Nodes}} – original discussion thread
	* {{note\|1}} {{GTAF\|post\|93990\|3813170\|Paths Documentation for SA, VC and GTA3}}

	{{SA-navi}}		{{SA-navi}}

	[[Category:Map Formats]][[Category:GTA SA]]{{fdl}}		[[Category:Map Formats]][[Category:GTA SA]]{{fdl}}

Gboyers: 1 revision: Imported from gtamodding.com - under GNU FDL

2010-01-11T23:55:42Z

1 revision: Imported from gtamodding.com - under GNU FDL

← Older revision	Revision as of 23:55, 11 January 2010
(No difference)

gtw>Aschratt@GTAM: Template usage ;-)

2009-10-16T11:31:52Z

Template usage ;-)

New page

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 [[GTA SA]]. There's a file for every 750×750 [[unit]] square, starting at the south-west corner (-3000, -3000) in [[Wikipedia:row-major order|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|01EB]] and [[03DE|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 <code>[[Carrec|carrec's]]</code>.

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 <code>[[Item_Placement#PATH|paths.ipl]]</code> 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 <code>nodes*.dat</code> files in the <code>data\paths\</code> 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) [[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 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 - 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 8.
;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.

====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){{ref|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 <nowiki>[-100, 100]</nowiki>, which corresponds to floating point values <nowiki>[-1.0, 1.0]</nowiki>.
====Navi Node 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 - traffic light direction 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 ''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 <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 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'''!

===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 & Scripts==

* {{GTAG|1093|SA Path Editor (WIP)}} by {{U|JGuntherS@NL}} – Only useful for editing existing path data.
* {{GTAF|post|214901|3841297|Path Compiler (WIP)}} by {{U|ocram88}} – Allows to create linear ped paths by generating waypoints from inside the game.
* {{GTAF|post|214901|3936074|Path Tool (WIP)}} by {{U|steve-m}} – Comes bundled with a MaxScript to export ped and vehicle paths from Max (by using spline shapes).
* {{GTAF|295628|APE v1.1}} by {{U|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!
* {{GTAF|283684|Path Script}} – a script by {{U|Deniska}} for 3DSMax that creates path files directly.
* {{GTAF|392955|PathViewer}} – a tool by {{U|Aschratt}} which allows to view paths and highlight nodes with special flags in 3D.

==See Also==

* {{GTAF|214901|Compiled Path Nodes}} – original discussion thread
* {{note|1}} {{GTAF|post|93990|3813170|Paths Documentation for SA, VC and GTA3}}

{{SA-navi}}

[[Category:Map Formats]][[Category:GTA SA]]{{fdl}}