Efficient Visibility Approximation for Game AI using Neural Omnidirectional Distance Fields

In NPC behavior design, visibility refers to knowing whether one position in a game scene can be ”seen” by an object at another position. In order to design complex and believable behaviors, various parts of the NPC decision making logic rely heavily on visibility information. This includes higher-level systems such as NPC visual perception (Walsh, 2019; Welsh, 2013; McIntosh, 2019) and tactical position selection (Jack, 2019), as well as more moment-to-moment logic, such as checking whether an agent should pull the trigger, change stance, or take some other immediate actions (McIntosh, 2019). For example, when evaluating NPC movement destinations during combat, visibility information between candidate positions and the player’s current position is critical.

While z-buffer scanning and raycasting (Bittner and Wonka, 2003) are common algorithms for visibility tests in graphics, NPC visibility queries require testing pairs of positions scattered throughout the game scene. Therefore, raycasting-based methods are often more efficient. However, as game scenes become more complex, raycasting algorithms face performance challenges. (Smits, 2005) highlights the complexity and considerations required to optimize raycasting. Although more efficient raycasting algorithms (Möller and Trumbore, 2005), acceleration structures (Klimaszewski, 1994; Klosowski et al., 1998; Foley and Sugerman, 2005), and hardware-accelerated libraries (Wald et al., 2014) have been developed, the cost of intensive visibility computation is still significant in many modern video games.

The probe-based irradiance field with visibility representation, as introduced in (McGuire et al., 2017; Majercik et al., 2019), is a promising advancement in real-time global illumination. By storing and constantly updating visibility information in GPU-resident probes, this technique effectively mitigates rendering problems such as light leaks. Accessing low-detail dynamic visibility results from these probes and estimating them by interpolation can be efficient (Majercik et al., 2019). However, the transition to game AI applications presents notable challenges. First, the probes are designed for rendering tasks, so they are often placed around the camera or cover only part of the scene. For game AI applications, however, the probes need to be placed and active for a larger area, which can significantly increase its GPU memory usage. Second, game AI applications operate primarily on the CPU, requiring low throughput visibility tests with minimal latency response. This makes probe-based methods less optimal.

In our approach, we leverage neural representations to approximate visibility and execute in the CPU. This is because achieving 100% accuracy for each visibility test is often unnecessary in game AI applications. For example, the visibility from a position to an object is often evaluated by sampling multiple visibility tests against the volume of that object, so the sampling errors can be handled by statistical techniques.

Neural implicit representations have emerged as a powerful tool for encoding high-dimensional data as a continuous, implicit function defined by a neural network, enabling various applications such as novel view synthesis (NVS), 3D shape reconstruction, and physical simulation. For example, NVS seeks to render a scene from unseen viewpoints using a dataset of images and camera poses. In particular, Neural Radiance Fields (NeRF) (Mildenhall et al., 2020) learns a representation of the scene using a continuous volumetric function of color density and relies on ray marching to render view-dependent images. In our task, we are more interested in distance fields that can be used to evaluate visibility.

Previous studies have explored the use of neural distance functions primarily for 3D shape reconstruction, such as predicting unsigned distance fields from sparse point clouds (Chibane et al., 2020) or learning consistent distance and density fields for improved localization (Ueda et al., 2022). However, these distance functions only model distance with respect to the surface normal and rely on algorithms such as sphere tracing to reconstruct shape, making them unsuitable for fast visibility evaluation between positions.

Classical implicit neural representations suffer from slow training and inference due to the computational complexity. To improve efficiency, previous research falls broadly into two categories: accelerating volumetric representations and non-volumetric representations.

Accelerating volumetric representations. With the introduction of auxiliary acceleration data structures, NeRFs can efficiently evaluate samples with a shallow MLP or no MLP at all. Plenoctrees (Yu et al., 2021), plenoxels (Fridovich-Keil and Yu et al., 2022) and multiresolution hash encoding (Müller et al., 2022) use voxel grids or hash table data structures as position features, along with low degree truncated spherical harmonics (SH) as direction features. A typical setting is SH truncated at degree 2 ($SH_{2}$). Sparse Neural Radiance Grid (SNeRG) (Hedman et al., 2021) bakes NeRF’s continuous neural volumetric scene representation into a discrete data structure at training time, and uses a small MLP with view direction at evaluation time for efficient rendering. These methods still rely on ray marching for evaluation and thus require multiple MLP inferences for a single sample. Another notable effort to accelerate volumetric representations is through point-based radiance fields. 3D Gaussian Splatting (Kerbl et al., 2023) represents the scene using point-based 3D Gaussians and optimizes them using differentiable rendering. This allows the representation evaluation to skip unnecessary computations in empty space, resulting in real-time rendering speed.

Non-volumetric representations. Various works represent the scene using other representations to be more efficient. MobileNeRF (Chen et al., 2023), represents the scene as a triangle mesh textured by learned deep features. This method leverages a classical rasterization pipeline, incorporating a compact MLP implemented as a GLSL fragment shader. The rendering process for each sample involves a single MLP inference. As a result, they achieve interactive frame rates on mobile phones. It shows that the volumetric representations can be baked onto a proxy surface geometry for efficient rendering. The ray-based implicit 3D shape representations (Feng et al., 2022; Liu and Yang, 2023) are another type of non-volumetric representation. They have a similar concept to our work, modeling distance fields based on rays. However, their ray parameterizations are tailored for 3D shape reconstruction, which limits their application to single objects or small scenes. In contrast, our focus is on rays that originate from selected sparse source positions and can be easily scaled to cover the entire game world. Our approach models the omnidirectional distance originating from these positions, allowing us to efficiently test occluders between them and arbitrary target positions. In particular, previous work has introduced the concept of neural ODF for 3D reconstruction using recursive inference (Houchens et al., 2022), the computation time of which is impractical for our task.

Although some NeRFs can handle scenes the size of a single room or building, they are generally still limited and do not scale to large environments such as the game world. Researchers in the field have proposed to extend NeRF using architectures that align multiple NeRFs in a distributed manner, as shown in (Tancik et al., 2022; Turki et al., 2022). Our approach follows a similar concept of partitioning the entire scene. However, unlike previous methods that use an end-to-end architecture to dynamically select NeRFs for rendering tasks, we exploit the fact that the evaluation of visibility depends only on the local ODF representation. This insight allows us to partition the game scene through a simple grouping of source positions, paving the way for a scalable and adaptable application.

For positions of interest in the game scene, the input variables of ODF can be expressed as rays $r=(p_{r},\,d_{r})$, where $p_{r}\in\mathbb{R}^{3}$ represents the position, and $d_{r}\in\mathbb{S}^{2}$ represents the normalized direction. The ODF distance value associated with each ray can be collected in the game scene through raycasting.

In practice, we can only generate a finite number of rays for data collection. To distribute the rays evenly across the surface of the unit sphere, we employ Fibonacci lattice (Swinbank and James Purser, 2006; González, 2010) as a basic approximation. Let $N$ be any natural number, integer $i\in[-N,\,+N]$. The $i$th direction in radians are

where

The number of directions is

After collecting data at all positions of interest, partitioning can be implemented as a post-processing step. This involves virtually grouping rays based on position $p_{r}$, for example, grouping them by the voxels to which $p_{r}$ belongs.

Standard MLPs are known to have a learning bias toward smooth functions, making them poorly suited for low-dimensional coordinate-based vision and graphics tasks (Rahaman et al., 2019). To overcome this limitation, neural representations employ encoding methods that map inputs to higher dimensions, improving the expressiveness for high-frequency signals. Unlike other representations designed for volumetric rendering or 3D shape reconstruction (Yu et al., 2021; Fridovich-Keil and Yu et al., 2022; Müller et al., 2022), whose common practice is to use lower degree truncated SH to encode directions, e.g. $SH_{2}$, our neural ODF representation requires capturing high frequency details for directions. This is demonstrated by an experiment of ODF reconstruction at a single position. In the experiment, we set several truncated SH degrees to encode directions, the greater the truncated SH degree, the more SH coefficients are used, the more high-frequency details the trained neural network can capture, as shown in Fig. 3.

However, high-degree SH encoding is computationally expensive. The direct computation scales $\mathcal{O}(N^{3})$ (Müller, 2006). Although there are some methods to reduce the computational cost (Suda and Takami, 2002; Dutordoir et al., 2020), we decided to develop a more efficient approach.

To address the encoding challenge while aiming for fast evaluation, we consider the onmidirectional distance data as a 2D spherical surface, so that it can be mapped onto the UV plane for 2D reconstruction. Inspired by the trade-off between memory and evaluation time made by discretized volumetric representations (Hedman et al., 2021; Müller et al., 2022), we employ a multi-resolution grid data structure to store our parametric direction features. Each grid is rectangular in shape and has a ratio of approximately $2:1$ for the longitude and latitude axes to match their value ranges. The grid settings we used in our offline experiments are the coarsest resolution of $16\times 8$ and the finest resolution of $256\times 128$, with the number of levels $L=16$ and the length of the feature stored in each texel $F=5$. For each ray direction $d_{r}$, the direction features are bilinearly interpolated from the four nearest texels of the UV plane and concatenated across multiple resolutions of the grid. We illustrate a two-level resolution grid example in Fig. 4.

In addition to the multi-resolution grid used for direction encoding, we map the position $p_{r}$ to higher dimensional space using hash encoding (Müller et al., 2022) or positional encoding (PE) (Mildenhall et al., 2020), these features are then concatenated and finally fed into a compact MLP. To optimize the neural network, we perform direct regression of the ground truth distance, minimizing the mean squared error. During the optimization, we use the Adam optimizer. To prevent divergence, we apply weak weight decay regularization (coefficient $10^{-5}$) to the MLP.

To mitigate ray aliasing in performance evaluation, we construct our testing dataset in the game scene separately by simulating visibility tests between candidate NPC movement destination positions and player positions. Each candidate position corresponds to one of the source positions where we collected omnidirectional distance data, while each target position is chosen randomly from the entire game scene. Additionally, we collect the results of raycasting-based visibility tests as the ground truth labels, denoted as $y$. The testing dataset is represented as:

where $\mathcal{P}$ represents positions of interest and $\mathcal{Q}$ represents all positions within the game scene.

To establish an offline environment for convenient performance comparison with baselines, we first collect training and testing data in a game scene using the methods described in Section 3.1 and Section 3.3. The data is exported as binary files for convenient integration with machine learning frameworks such as PyTorch. We then post-process the training data by partitioning the 6227 source positions using a simple 2D grid scheme, as shown in Fig. 5(b). Based on this $8\times 8$ partitioning scheme, we create 64 independently initialized small models for each method under evaluation. During both the training and testing phases, each sample infers only one of these models, determined by the local partition index associated with the given source position.

The evaluation results are presented in Table 1. All these experiments are performed offline with PyTorch. The prediction accuracy is evaluated through classification metrics (Powers, 2008). The inference time is benchmarked on a Xeon W-2135 CPU and is constrained to single-threaded execution without batching, simulating the typical execution of visibility tests in game AI applications.

In the positional encoding (Mildenhall et al., 2020) experiment, we use 6 exponential growth frequencies ($n_{\text{freq}}=6$) for both position and direction inputs. In the hash encoding (Müller et al., 2022) experiment, we use the setting $(F=2,\,L=16)$ with $2^{16}$ as the hash table size. For its direction encoding we employ SH truncated at degree 2 and degree 12. In the Fourier Feature Mapping (FFM) (Tancik et al., 2020) experiment, we use a standard deviation $\sigma=1.0$ for the Gaussian distribution to encode positions and SH truncated at degree 12 to encode directions. In our method, for directions, we experimented with longitude-latitude projection and the Mercator projection for spherical mapping, the multi-resolution grid setting is described in Section 3.2, which is $(F=5,\,L=16)$. For positions, we use hash encoding and PE of $n_{\text{freq}}=6$. The hidden size of the MLPs is 128 neurons and 4 layers for all methods.

For all methods, there is a trade-off between prediction performance, memory, and computational cost. From the result, our method with PE shows promising metrics in both prediction performance and computational cost, at a reasonable memory cost. With hash encoding, our method achieves slightly better prediction performance but slower speed. We don’t see much difference between the two projection methods with the experimented grid settings. Due to the smoothness in reconstructing omnidirectional distance data, hash encoding with SH truncated at degree 2 has a similar prediction performance to the no mapping baseline. In our experiments, we observed that while positional encoding can yield commendable results with appropriate frequency configurations, its effectiveness is highly sensitive, requiring hyperparameter tuning across different scenes. Hash encoding and FFM with SH truncated at degree 12 are much slower due to their SH computations. Among different versions of our methods, we choose the PE with longitude-latitude projection for further in-game experiments due to its simplicity, faster speed, and lower memory cost.

Certain applications require the use of multi-threaded CPU or GPU batching operations to perform high-throughput visibility testing. Our approach benefits from the integration of parallel and vectorized computation with batching. The scalability of the inference throughput of our method for both CPU and GPU is illustrated in Fig. 6. The throughput depends on the hardware and inference framework used; we present the measurements tested using PyTorch, a Xeon W-2135 CPU, and a RTX A5000 GPU.

Our method involves compressing omnidirectional depth maps for all source positions within the local partition into a single neural ODF representation. Fig. 7 illustrates a comparison of the memory composition. To analyze the difference in memory usage, we conduct an experiment using the offline environment with the partitioning and settings of our method described in Section 4.1. Each partition in the experiment contained an average of 100 source positions. For PNG DEFLATE lossless compression, we used ZLIB compression level 6.

As shown in Table.2, for each partition, our neural representation has a significantly reduced memory size compared to the size of uncompressed depth maps, although it remains larger than PNG compressed memory size. Traditional image compression methods have their own drawbacks when applied to game AI applications, such as additional computation time, inconvenience in evaluating individual pixels, and lack of generalization ability. To further optimize the memory size of our neural representation, future considerations may include actions such as reducing weight precision to 16-bit float, applying quantization, or using smaller feature vectors. For the scope of this study, our primary focus is on prediction accuracy and inference time in a real game environment, which will be discussed in the following section.

To evaluate our method in a real game environment, we perform a side-by-side comparison with raycasting using an AAA game engine. The raycasting implementation is based on a commonly used commercial product called Havok Physics. The maximum raycasting distance for both data collection and baseline comparison is set to 100 meters. Three types of scenes are selected as our evaluation environment, as shown in Fig. 8. These scenes are partitioned into $16\text{\,}\mathrm{m}$ $\times$ $16\text{\,}\mathrm{m}$ $\times$ $16\text{\,}\mathrm{m}$ voxels, and each partition contains a different number of source positions of interest, ranging from 30 to 200. The evaluation results for execution time and visibility prediction accuracy are presented in Table.3. Due to the significant impact of CPU caching on execution time, we collect both cold start and warm start average execution times for all tasks. The execution time and accuracy of our method are measured based on a C++ implementation and executed on a single-threaded CPU process without batching. We use (PE, Long-Lat) version of our method. In addition, various sizes of MLPs are evaluated, while keeping the encoding settings the same ($n_{\text{freq}}=6,\,F=2,\,L=16$). So the input size of the MLPs is $2\times 3\times 6+2\times 16=68$.

For each partition, using 32-bit float precision, the memory size of the multi-resolution grid is approximately 1.64 MB, while the memory size of the MLP ranges from 13 KB to 234 KB. The observed memory usage is lower than that of offline experiments due to the utilization of smaller feature vectors and MLP for in-game evaluation. To compare memory usage with raycasting, as shown in Table 4, we estimate raycasting memory usage by assessing the memory size of the collision geometry at the level of detail employed for raycasting. For our methods, we estimate memory usage by multiplying the number of partitions for each environment by the model size for each partition.

Due to the different characteristics such as average collision distance and number of triangles in the three scenes, the execution time of raycasting-based visibility is different. In contrast, our inference time remains the same across the three scenes because we are using exactly the same model architecture. This is potentially a desirable property for game AI applications, as it makes the execution time more predictable.

From the experimental results presented in Table.3, we observe that the most challenging scene for our method is Environment B, which contains many small objects in the open area. We hypothesize that the reason for the lower accuracy is due to the reconstruction error at object edges. As observed in the visualizations shown in Fig. 9, most of the incorrect predictions are around object edges, corresponding to the viewing direction from the source position. In the future, this problem may solved by using a hybrid approach that detects object edges and switches between raycasting-based visibility tests and ours. For Environment C, where most of the target positions are not visible, the prediction accuracy of our method is very high ($>98.5\%$). Under different MLP settings and scenes, our method shows speedups ranging from $1.95\times$ to $26.26\times$.