The navmesh defines the area's an AI entity could traverse. To assist building better navmeshes for the game,
I implemented the navmesh renderers supplied by the Recast & Detour navigation library into this custom engine through our specialized SDK. Recast & Detour is the library used by the engine for AI pathfinding.
I modified the renderers to feature Streaming SIMD Extensions instructions (SSE), and to integrate it into the heavily modified Valve Source engine. I also implemented some optimization vectors to aid with visualizing the navmesh on larger levels without dropping frames.
​
-
The source code for this project can be found in this GitHub link.
-
A blog explaining how I achieved this level of optimization can be found in this link.
INTRODUCTION
PROGRAMMING
Render function for drawing the navmesh BVTree. Some context:
-
OverlayBox_t::Transforms is a structure composed of 3 Vector4D's, declared union with 3 __m128 types. This structure defines the transforms of the render box (position, rotation, scale). Declaring the types as union allows us to use the SSE intrinsics directly without any type casting, while also still being able to use the Vector4D class (both types are equal in size and share the same memory location).
-
We can adjust the render behavior with console variables, such as disabling the depth buffer using r_debug_overlay_zbuffer.
​
Since some of the levels in Apex Legends are huge, we can't render everything due to the engine's debug draw overlay limit. To mitigate this problem, I came up with the idea of rendering tiles and their details within a certain radius from the main camera (the camera used to render the scene and display to the user).
​
Before we can do this, I need to grab the main camera's origin. After some little reverse engineering of certain functions that use the main camera's origin, I found the following assembly:
This simply moves the address of the splitscreen player in the static array to R14. In this modified engine, RDX is always 0, since splitscreen is technically not supported, so the first index of the array is always the local player.
​
Going a bit further down the same function, I found the following with the same pointer stored in R14:
This simply just moves 3 single precision floating point scalars in 3 separate XMM registers. This could had been done in a single instruction, but speed didn't matter much in this particular function. Anyways, after inspecting memory at runtime, I confirmed these were indeed the main camera's origin:
After creating a dynamic solution for resolving pointers to the camera singleton, I created the following inline:
Using this inline, we can do the following:
This statement is in the BVTree render function above, at line 27. What this does: it checks if the distance between the navmesh's tile position and the main camera's origin is within the maximum range defined by the console variable "navmesh_debug_camera_range". If it is, it will render the tile and all its details (polygons, portals, bv nodes, offmesh connections, etc...) This allows for rendering relevant areas only.
​
I set the Z in xMinBound and xMaxBound to that of the camera itself, so we can render and view the
navmesh from above, since we don't need to cull on the Z axis. This combined proofs quite helpful:
From the ground:
Only relevant areas are rendered, and we can quickly skim over the entire level to inspect the navmesh!
​
All the other render functions (DrawNavMeshPortals, DrawNavMeshPolys, DrawNavMeshPolyBoundaries, etc...)
have been taken from the Recast & Detour library, with the same Streaming SIMD and camera optimizations shown above, I left these out of the page to maintain overview. The full source code can be seen in this link.
Remark:
-
In the future, I want to learn more about DirectX, and create my own render solution instead of relying on the game's "v_RenderLine", v_RenderBox", etc... I was initially planning on implementing a DirectX render solution to the SDK, but since we have to use the game's DirectX device and context (we are an imported DLL), it was unfortunately not something I could do at the time due to time constraints.
-
I also want to change the culling behavior to feature frustum culling instead. Due to the lack of time I decided to use radius culling for now, which has proven to be good enough.
-
This implementation has proofed useful to developers using the SDK. They were able to debug navmesh problems on dynamic entities and solve them easily using the external navmesh editor.
The polygons of the navmesh being drawn over the level with enemy AI entities traversing the navmesh area.
SHOWCASE
The polygons of the navmesh being drawn over a platform. The dark blue edges define the poly bounds.
The navmesh being drawn in a corridor with one of the walls culled away. The portals are being rendered here as well (the vertical squares).
The BVTree of the navmesh being drawn over a complicated area, here we also draw the portals and poly boundaries. Notice how we only draw relevant areas.