Differences

This shows you the differences between two versions of the page.

--- trs:npc_behaviour [2017/01/25 10:32]
stohrendorf removed
+++ trs:npc_behaviour [2017/11/17 12:19] (current)
stohrendorf
@@ Line 1: / Line 1: @@
+{{indexmenu_n>6}}
+====== Non-Player Character Behaviour ======
+===== Overview =====
+All the Tomb Raider game physics and entity behaviour is hardcoded, with each type ID being associated with some specific sort of behaviour (as Lara, as a boat, as a tiger, as a door, as a boulder, as a lock, etc.). That is, each model refer two internal engine routines — //collisional// one and //control// one. For static entities (like flame emitters), //collisional// routine may contain no functional code, while //control// routine is present. On contrary, “decorative” entities (usually called //animatings// in TRLE) may lack //control// code, while retaining //collisional// code.
+Several entity types may share the same collisional and/or control routines — for example, there is one generic collisional routine for almost all enemies, another generic routine for doors, and another one for //standable// entities, like bridge or platform objects.
+Lara is unique player character, so she has a large set of both //control// and //collisional// routines, which are switched depending on her current //state//.
+<note>
+In original Tomb Raider source code, notation for collisional and state routines follows two different schemes. For Lara, collisional and control routines are called ''%%lara_col_STATE%%'' and ''%%lara_as_STATE%%'', where ''%%STATE%%'' is the name of the state, like //walk, run, reach//, and so on.
+For other entity types, there is more generic scheme: collisional routines are called ''%%NAMECollision%%'', where ''%%NAME%%'' is entity type name, like //CreatureCollision//, and control routines are called ''%%NAMEControl%%'', where ''%%NAME%%'' is entity type name. E.g., bear will have a pair of routines linked to it, named //CreatureCollision// and //BearControl//.
+</note>
+===== Entity Scripting =====
+Despite the existence of //script files//, here is no any scripting for entity behaviour, like in most contemporary games. This hardcoding makes it difficult to port the earlier Tomb Raider scenarios to the engines of the later games, which could be desirable with their improved hardware support. While textures, models, and animations can be ported, behaviour cannot be.
+However, there is a small change in TR4 and TR5 which indicates that specific entity behaviour can be altered — it’s called //OCB//. It was briefly described in [[trs:meshes_models#object-code-bit|this section]]. OCB is a special value defined for each entity instance, based on which entity can switch the way it acts (most prominent examples are flame emitters, which change their size and emit direction based on OCB, and teeth spikes, which change their orientation in space).
+Sometimes OCB is interpreted as a “packed” field with several values incorporated — like teeth spike OCB contain information about their horizontal and vertical orientation, and also about their “physical” behaviour (stick out constantly, pop-retract in looped manner, or pop-retract just once).
+<note tip>
+For list of valid entity OCBs in TR4, you may refer to TRLE User’s Manual, although it was written in a big rush, and thus it lacks many existing OCBs for many entities. There are also fan-made OCB lists which are much more comprehensive.
+As for TR5, no proper OCB list exists for its entity types, so it may be considered a big unknown.
+</note>
+However, OCB can’t be seriously called “scripting”, as it also operates with pre-defined hardcoded behaviour.
+<note>
+Recent patches for TR4 game engine (used to play custom levels), like //TREP// and //TRNG//, feature some kind of basic scripting functionality. However, there’s still no sign of //real scripting language// in them, and such scripting is basically specifying pre-defined variables to alter entity behaviour, just like OCB does.
+</note>
+===== Pathfinding =====
+Despite the lack of scripting, the Tomb Raider series does have navigation hints for the Non-Player Characters; those entities that move freely across the maps under the command of the game AI. NPCs find their way in a level by checking “FloorData” collisional functions in the same way Lara does, and also with the help of special data structures which are used for proper pathfinding.
+==== Data Structures ====
+TR engines use three different structures to assist pathfinding. These are //boxes, overlaps, and zones//. Most sectors point to some //box//, the main exceptions being horizontal-portal sectors. Several neighbour sectors may point to the same box. A box is a horizontal rectangle, with corners and height specified; each box also has a pointer into the list of //overlaps//. Each segment in that list is the list of accessible neighbouring boxes for some box; the NPCs apparently select from this list to decide where to go next.
+Several neighbour sectors may point to the same box. Each box also has a pointer into the list of //overlaps//. Each segment in that list is the list of accessible neighbouring boxes for some box; the NPCs apparently select from this list to decide where to go next.
+This selection is done with the help of the //zones//. These structures of 6 (TR1) or 10 (TR2-TR5) ''%%int16_t%%''s that act as zone IDs; their overall indexing is the same as the boxes, meaning that each box will have an associated set of zone IDs. An NPC will select one of this set to use, and will prefer to go only into the overlaps-list boxes that have the same zone value as the box it is currently in. For example, one can create guard paths by making chains of zone-ID-sharing boxes, with their overlaps pointing to the next boxes in those chains.
+{{anchor:Boxes}}
+=== Boxes ===
+A box is a horizontal rectangle, with corners and height specified.
+This is presumably the way //TRLE// creates boxes for each level:
+  * For each sector, extend one axis until a height difference is reached.
+  * Then extend this row (or column) perpendicular until another height difference is reached. This is a rectangle with the same height and it //defines a box//.
+  * Do the same with the other axis first, and you get another box.
+  * Repeat this process for every sector, maybe extending into neighbor rooms through the portals.
+  * Make sure that there are no any duplicate boxes.
+There are two variations of box structure — one for TR1 and another for TR2 and any other game version.
+{{anchor:tr_box}}
+<code cpp>
+struct tr_box   // 20 bytes
+{
+    uint32_t Zmin;          // Horizontal dimensions in global units
+    uint32_t Zmax;
+    uint32_t Xmin;
+    uint32_t Xmax;
+     int16_t TrueFloor;     // Height value in global units
+    uint16_t OverlapIndex;  // Bits 0-13 is the index into Overlaps[].
+};
+</code>
+{{anchor:tr2_box}}
+<code cpp>
+struct tr2_box   // 8 bytes
+{
+    uint8_t Zmin;          // Horizontal dimensions in sectors
+    uint8_t Zmax;
+    uint8_t Xmin;
+    uint8_t Xmax;
+    int16_t TrueFloor;     // Height value in global units
+    int16_t OverlapIndex;  // Bits 0-13 is the index into Overlaps[]
+};
+</code>
+The ''%%OverlapIndex%%'' contains a block mask for path finding by enemies in two highest bits: Bit 15 (blockable) and bit 14 (blocked). The first one marks it as unpassable by large enemies, like the [[:items:details:tr1:trex|T-Rex (ID 18)]], the [[:items:details:tr1:mutant|Mutant (ID 20)]] or the [[:items:details:tr1:centaur|Centaur (ID 23)]] and is always set behind doors. The second one marks it unpassable for other enemies and is set for movable blocks (if blockable bit is set), for closed doors and for some flip maps (set at start).
+=== Overlaps ===
+This is a set of lists of neighbouring boxes for each box, each member being a ''%%uint16_t%%''. NPCs apparently use this list to decide where to go next.
+Overlaps must be parsed in serial manner, as with //FloorData// functions: the highest bit (''%%0x8000%%'') is used to terminate overlap list iteration for a single box.
+=== Zones ===
+This is a set of ''%%int16_t%%''s, 6 for TR1 and 10 for TR2-5. NPCs prefer to travel to a box with the same zone ID as the one they are currently at. Which of these zone IDs it uses depends on the kind of the NPC and its current state. The first half of the Zones structure is for the //normal// room state, and the second half is for the //alternate// (flipped) room state. TR1 has 2 sets of ground zones and 1 set of fly zones:
+{{anchor:tr_zone}}
+<code cpp>
+struct tr_zone   // 12 bytes
+{
+    uint16_t GroundZone1_Normal;
+    uint16_t GroundZone2_Normal;
+    uint16_t FlyZone_Normal;
+    uint16_t GroundZone1_Alternate;
+    uint16_t GroundZone2_Alternate;
+    uint16_t FlyZone_Alternate;
+};
+</code>
+TR2-5 have similar breakdowns, though they have 4 ground zones:
+{{anchor:tr2_zone}}
+<code cpp>
+struct tr2_zone   // 20 bytes
+{
+    uint16_t GroundZone1_Normal;
+    uint16_t GroundZone2_Normal;
+    uint16_t GroundZone3_Normal;
+    uint16_t GroundZone4_Normal;
+    uint16_t FlyZone_Normal;
+    uint16_t GroundZone1_Alternate;
+    uint16_t GroundZone2_Alternate;
+    uint16_t GroundZone3_Alternate;
+    uint16_t GroundZone4_Alternate;
+    uint16_t FlyZone_Alternate;
+};
+</code>
+The ground zones are for NPCs that travel on the ground, while the fly zones are for flying or swimming NPCs.
+==== Moods ====
+Each mobile NPC in TR may be in a certain //mood//. A mood defines the way creature behaves. The way NPCs change their mood is based on several conditions, mainly on certain enemy implementation.
+Most obvious example of mood change is wolf, which can sleep, walk slowly, chase Lara and flee. This change of mood is based on Lara’s position — if Lara is found in any of the box that NPC can reach, mood is changed to //chase//, which means that //pathfinding algorithm// is in effect (see further).
+There are another examples of mood changes. In TR3, monkeys are calm unless Lara shoots them. However, this is not the case for level 2 (Temple Ruins), where monkeys are hardcoded to chase Lara on start-up.
+{{anchor:pathfinding-algorithm}}
+==== Pathfinding algorithm ====
+For most of TR NPCs, when they are in //chase// mood, pathfinding (and eventual attack) may be broken down to several steps:
+  * Collect all boxes that are in the same zone as the NPC.
+  * Find a path using //[[https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm|Dijkstra algorithm]]// with respect to the NPC abilities and a //maximum depth of 5 boxes//.
+  * Calculate a random point in the intersection of the current box and the next box on the waypoint.
+  * If NPC is finally shortly at arriving at Lara, try to predict the direction in which Lara is running (with different lookahead distances for different types of NPCs).
+  * Perform an attack based on aforementioned calculations.
+{{anchor:ai-objects}}
+===== AI Objects =====
+Since TR3, in addition to pathfinding data structures, there are now special //AI objects//, which are used in a node-like manner, defining specific action, like wandering between two points, guarding specific point or running to specific place in case Lara is around. For example, MP Guards in TR3’s “Area 51” may patrol specific area when they are limited by special //AI_PATROL// object.
+<note>
+Not every NPC is “taught” to work with AI objects — usually, only “smart” human enemies or friends can take advantage of them. Analyzing level files with utilities like //FexInspect// may help understanding particular AI object setup and learn which NPCs can actually work with them.
+</note>
+Specific set of AI objects and their respective entity type IDs are different across game versions, but types themselves largely remained unchanged from TR3 to TR5. Here are they:
+  * **AI_GUARD** — Makes the enemy stay on his current position and turn his head, looking left and right, with a 180 degree field of view — so his “viewing cone” is continuously changed, based on current look direction. When Lara gets into his “viewing cone”, default entity behaviour is engaged — for example, MP guards will chase Lara and try to beat her.
+  * **AI_AMBUSH** — Makes the enemy run to a designated square by dropping an AI_AMBUSH object on the same sector with him, and another AI_AMBUSH on the sector where he should run to. He will do that only if he spots Lara (hence the name). After reaching second AI_AMBUSH point, enemy will switch to default behaviour. Best example is MP Guard in “Area 51” who locks out first secret, if you won’t manage to kill him in time after he noticed you.
+  * **AI_PATROL1** and **AI_PATROL2** — Makes the enemy patrol specific path between AI_PATROL1 and AI_PATROL2 locations. To make it work, AI_PATROL1 object must be in the same sector with enemy, and AI_PATROL2 must be in the point to which enemy must go. After reaching AI_PATROL2 point, enemy will return to AI_PATROL1 point, and vice versa. It’s also possible to specify another “starting point” for enemy by dropping extra AI_PATROL1 object — then enemy will go to this secondary AI_PATROL1 object just after activation. If enemy spots Lara, he will switch to default behaviour.
+  * **AI_MODIFY** — When placed in the same sector with //AI_GUARD//, it makes the enemy look straight ahead, instead of turning his head left and right.
+  * **AI_FOLLOW** — Used primarily with friendly NPCs, and makes them wait for Lara and then “lead” her to specific point. For such behaviour, one AI_FOLLOW object must be placed in the same sector as NPC, and second AI_FOLLOW object must be placed on target point. If Lara shoots NPC affected with AI_FOLLOW behaviour, he will abandon it and become hostile.
+<note>
+If there is a HEAVYTRIGGER under an AI_AMBUSH or AI_PATROL object, the enemy will activate it only when he gets there.
+</note>
+{{:icons:tr4.png?nolink|TR4 only}}{{:icons:tr5.png?nolink|TR5 only}} TR4 introduced three additional AI objects, **AI_X1**, **AI_X2** and **LARA_START_POS**. First two are used, for example, with SAS Guards in //Cairo// story arc. When AI_X1 object is placed in the same sector with SAS Guard, he will prefer to shoot grenades instead of bullets. If another SAS Guard with AI_X2 is activated nearby, then first one will stop shooting grenades, and second one will shoot them instead.
+As for **LARA_START_POS** AI object, it is used to modify Lara’s level starting position, according to prior //end level trigger action// configuration. That is, at start Lara will be teleported to any existing **LARA_START_POS** AI object with same OCB value as in ''%%Timer%%'' field of //end level// trigger in previous level.
+==== AI Object IDs ====
+Here are all AI Object type IDs in each TR version which has them:
+^              ^TR3       ^TR4        ^TR5        ^
+|AI_GUARD      |''%%74%%''|''%%398%%''|''%%378%%''|
+|AI_AMBUSH     |''%%75%%''|''%%399%%''|''%%379%%''|
+|AI_PATROL1    |''%%76%%''|''%%400%%''|''%%380%%''|
+|AI_PATROL2    |''%%79%%''|''%%403%%''|''%%383%%''|
+|AI_MODIFY     |''%%77%%''|''%%401%%''|''%%381%%''|
+|AI_FOLLOW     |''%%78%%''|''%%402%%''|''%%382%%''|
+|AI_X1         |          |''%%404%%''|''%%384%%''|
+|AI_X2         |          |''%%405%%''|''%%385%%''|
+|LARA_START_POS|          |''%%406%%''|''%%386%%''|
+==== AI Data Block in TR4-5 ====
+Beginning with TR4, AI objects are //not kept along with other entities//. Instead, they have their own structure, which is basically simplified [[trs:meshes_models#tr4_entity|[tr4_entity]]] structure, and moved to separate data block. This seems reasonable, as the only purpose of AI objects is to serve as “waypoints”, and they have neither //collisional// nor //control// code attached to them.
+The format of AI object structure as follows:
+{{anchor:tr4_ai_object}}
+<code cpp>
+struct tr4_ai_object   // 24 bytes
+{
+    uint16_t TypeID     // Object type ID (same meaning as with tr4_entity)
+    uint16_t Room;      // Room where AI object is placed
+     int32_t x, y, z;   // Coordinates
+     int16_t OCB;       // Same meaning as with tr4_entity
+    uint16_t Flags;     // Activation mask, bitwise-shifted left by 1
+     int32_t Angle;
+};
+</code>

trs/npc_behaviour.1485336766.txt.gz · Last modified: 2017/01/25 10:32 by stohrendorf

Back to top