Physics: Havok integration

How the engine embeds Havok 2016.2: the new-pipeline (hknp) world with legacy-pipeline ragdolls, the engine's handle to the world, the world's layout and gravity, the material palette and its half-precision fields, what is live and what ships unused, the Havok heap, the tagfiles that carry navigation meshes and collision shapes, and the surface types that decide footsteps, climbing, shooting through and impacts.

Which Havok

Physics is Havok Physics 2016.2 (hk2016_2_0_r1) in its new pipeline: the hknp* classes, which replaced the older hkp* API. The build is a hybrid: rigid bodies are hknp, but ragdoll constraints are still the legacy hkpRagdollConstraintData and hkpLimitedHingeConstraintData. Havok AI (hkai*) provides navigation meshes, avoidance and silhouettes, and Havok Cloth deforms cloth with hkaSkeleton; Havok Animation and Behavior are not used (see Animation). HavokScript runs the game's scripts (see Scripting).

Havok work runs on three HavokWorkerThreads (shared routine 0x11AFE58) and on the main thread's task queue: in play the main thread spends about 5% of its time in the physics step (TtPhysics, 0x6528B8) and about 3% in the Havok task queue, where hkaiAvoidanceSolverTask shows up.

The engine's handle

The world has exactly one construction path (its constructor 0x15464FC has one caller, 0x11B1504, whose only caller is 0x1187004), and the engine publishes its owner in a static slot:

[base+0x2A86760]   the physics owner (0x6860 bytes), published by 0x1186FB0
                   (1 write, 66 reads in 60 functions)
[base+0x2A86768]   u32 generation, incremented at each publish
  owner+0x20 -> hknpWorld (allocated from the Havok heap, 0xAA0 bytes)

The world is rebuilt on every world load.

The world

hknpWorld (vt_0x22EEA90). Sub-objects, named by their own run-time type information:

Arrays are Havok hkArrays ({T* data, u32 size, u32 capacity and flags}). The body arrays at +0x040, +0x050, +0x0C8 and +0x0D8 / +0x0F8 hold 15,360 entries each: the body capacity is 15,360, kept as parallel structure-of-arrays lanes. +0x0B8 is the active-body id list (254 of 15,364 in a combat scene); a body id packs index | generation << 24. +0x108 has capacity 1,024, matching the material palette.

This gravity drives the rigid-body solver only. Characters move through the engine's character controller, which the behaviour graph owns (see Animation).

Materials

Both libraries keep their entries in an hkArray at +0x30. The material palette is one contiguous array of 1,024 hknpMaterial entries (vt_0x1DAC040, stride 0x80):

hkHalf is not IEEE half precision: it stores the top 16 bits of a float32 (decode with float_from_bits(h << 16)). Only a handful of entries are configured - they carry a maximum contact impulse of FLT_MAX instead of the sentinel - and the number grows during play as surfaces register on demand: 13 and then 18 configured entries were seen in one world about an hour apart. Entries 0-7 are nearly uniform (friction 0.5, restitution 0, with one bouncier entry at 0.199 and one at friction 0.547 / restitution 0.05), so a handful of shared materials surfaces the whole world.

What is live, and what ships unused

A census of the live heap in a desert scene (169 live Havok classes; controls passing):

The default modifier set (hknpDefaultModifierSet) instantiates the six per-contact modifiers: trigger, mass changer, restitution, soft contact, surface velocity and animated-shape surface velocity.

Shipped in the executable with their vtables but never instantiated: the complete Havok vehicle suite (hknpVehicleInstance with its engine, transmission, steering, suspension, brake, aerodynamics, velocity damper, tyre marks and ray-cast wheels), Havok's demo guns (hknpBallGun, hknpGravityGun, hknpProjectileGun, hknpMountedBallGun, hknpFirstPersonGun, hknpFirstPersonCharacter), the spring / unary / binary actions, and the linear and circular surface velocity objects.

The Havok heap

Havok allocates its whole heap in one call (0x11870E4); its size is the u32 at 0x262AC80. The world, both libraries, the material palette and the motion array all live in that single region, which is the largest single allocation in the process (512 MB with a raised setting).

Tagfiles: navigation meshes and collision shapes

Havok data ships as tagfiles (root hkRootLevelContainer) that carry their own type table, so every class layout is read from the file itself. Every carrier parses exactly: 923 standalone .hkai files (185 types), 1,176 HKAI sections inside bundles, and 5,148 physics files in world-object entries plus 4,808 inside bundles (196 types).

• Navigation meshes: hkaiNavMesh version 16 (208 bytes): faces, edges and vertices in world space (cm). worlds\retail\mtnpass\mtnpass.hkai (37.5 MB) holds 713 navigation meshes, all structurally exact; its main mesh has 205,467 vertices, 273,917 edges and 49,774 faces (3-14 edges each); every edge's opposite is symmetric (227,694 of 227,694). The smaller meshes are the dynamic navigation pieces of props (Resou_09.W.dnmp, Store_34.NMPtop).
• Collision shapes: roots are hknpCompoundShapes holding hknpCompressedMeshShape, hknpConvexPolytopeShape (boxes and capsules), hknpSphereShape, hknpHeightFieldShape and hknpConvexShape, in metres; an instance places a shape as p' = R (p * scale) + t.

Surfaces

What a character, a projectile or a sound does when it meets geometry is decided by the surface it touched: one of the 78 Surfaces/Surfaces records (type Surface.Surface).

Every field but two has an accessor read by game code; CanSpiderCrawl and CanMeleeThrough are registered in the schema and filled in the data, but no code reads them. The sets are telling: wall-climbing is allowed only on Air, AxeClimb, Can_Scramble, PlayerBlocker_Dust and the three No_WallRunPlusSlip* surfaces; the 14 slippery surfaces are the *_No_WallRun* family, the player blockers, Perimeter, Wood_Tree and Slippery; the 12 fire props are the wood and cloth surfaces; warg jumps are refused on 18 surfaces, the five Drake_* collision surfaces among them, which are also the only five that refuse spider crawling.

Surface ids. Collision data does not name a surface by index but by a 16-bit id folded from the P919 hash of its record name: id = (h + (h >> 16)) & 0xFFFF (78 of 78 surfaces, no two sharing an id). A table of 16-byte entries {u16 id, ..., +0x08 the record} between [base+0x277C9E0] and [base+0x277C9E8] (78 entries, in the category's record order) maps an id back to its record: 0x2748F8 compares the id with the "no surface" value at 0x2A868F8 (0) and searches the table. A query result carries a surface reference {u16 id, u8 valid}, resolved by 0x2748E4 (null when the valid byte is 0). A world object can also carry its own surface: the u16 at +0xCE (0x274B5C; 0x274B68 returns the u32 at +0xCC, whose high half it is). In one loaded world 107 of 105,842 placed objects set it (106 metal_cage, one water_shallow); every other object holds 0, no surface.

Impacts and collision properties. Surfaces/Impacts has 65 records, one per material and size (Small, Medium, Large, Ambient, Explosion, with _OlogHai variants, Fist_*, Nazgul_Projectile); Surfaces/SurfaceFXType names the eight impact kinds. Collisions/CollisionProperty has 52 records, of which the surfaces use nine (Wood 16 times, Metal 6, water 5, Cloth 4, Stone 3, Footstep 2, Sand 2, Flesh 2, Orc_head 1); the table also carries props of a contemporary setting that nothing in this game's surfaces refers to (Office_Chair, Keyboard, ComputerCase, Radio, Deli_SignChains, CeilingTile, Duct, PropaneTank ...).

Open questions

• What registers a new material slot during play.
• The meaning of the unnamed floats of a material (+0x3C, +0x44, +0x48) and of the solver values near the gravity vector.
• How collision geometry carries a surface per triangle or per shape: the query result's {u16 id, u8 valid} reference is filled from somewhere in the collision data.
• What CanWallClimb permits, given that it is set on the No_WallRunPlusSlip* surfaces and clear on WallRun.

Shadow of War (Steam), game version 1.21. An unofficial fan research project, not affiliated with or endorsed by Warner Bros. Games, Monolith Productions or Middle-earth Enterprises. Middle-earth: Shadow of War belongs to its owners.