top of page
ain_simd_draw_we_tt.png

The AI Network is a type of navigation system used for larger AI entities. This particular version of the modified Valve Source engine only uses script nodes. Script nodes are location points an AI entity could be moved to programmatically, which are directly accessible from the engine's Squirrel scripting interface, through several functions binding native engine code to the scripting interface (similar to Unity's scripting API and Unreal Engine's Blueprint system).

​

To assist the programmer working with the engine's script API, I created an AI script network renderer.

Due to the scale of some of these levels, I decided to use Streaming SIMD Extensions (SSE) to help boost the performance.

​

  • The source code for this project can be found in this GitHub link.

  • A blog explaining how I achieved this level of optimizations can be found in this link.

INTRODUCTION

PROGRAMMING

Render function for drawing AI script network. 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 or setting a specific range of indices to be rendered using ai_script_nodes_draw_range. We can also change how we want to render links, by default it will render links in the order the network was build, but if ai_script_nodes_draw_nearest is set, we draw links from node to its nearest node.

  • We can also render within a specific range from the main view camera, using the console variable 'navmesh_debug_camera_range'. More details regarding camera range culling can be found in my NavMesh renderer portfolio page available in this link.

This boilerplate packs 4 node indices into a single XMM register. Currently, the lower half of the XMM register

(c and d) are unused. Before we pack a and b together, we check if a is lower than b. If this condition evaluates to true, we swap them using the _mm_shuffle_epi32 intrinsic. This is so we always end up with one possible combination of node indices. Without this, we will draw duplicate links when:

  • Parameter a happens to be node 100, and b 104 (b is the nearest to a).

  • Parameter b happens to be node 100, and a 104 (a is the nearest to b).

Node 100 will be near 104 and vice versa, but packing the nodes 100-104 in reverse order (104-100),

will yield a different hash during lookup in the unordered map, even though these render the same link.

This small optimization can save thousands of clock cycles during a single render frame.

ain_simd_draw_mu1_night.png

SHOWCASE

The AI Network being drawn.

  • The green boxes represent the script node positions.

  • The red lines represent links to the nodes, which in the above image, represent the order the AI Network has been build. But it can also render links to the nearest node:

Here we draw links between the nearest script nodes. The algorithm behind this logic is the same as the one used for the script function NavMeshNode_GetNearestNodeToPos (provided by the engine), which gets the nearest node to a world space Vector3 position. By using the same algorithm, we can visually assist the AI programmer by rendering the paths the AI entity might take. 

We can cover larger areas in huge levels as well, using index shifting and a range limit that can be set from the developer console using the variables we created and registered:

bottom of page