Deep Reinforcement Learning for Navigation in AAA Video Games

1 Introduction

Realistic navigation for non-player characters (NPCs) is an important component in most video games to enhance the players' experience. The traditional pipeline for NPC navigation is as follows:

1. A graph representation of the world is pre-generated from the game geometry.

∗Equal contributions, alphabetical order.

1 Hyper Scape was used for experimentation purposes only. Our agent was not shipped in the game. Video in Hyper Scape: youtu.be/DKdQFajLfzk

1. At runtime, a pathfinding algorithm like A* [Hart et al., 1968] is applied on this graph to find the shortest path between any pair of locations in the game.
2. A controller tailored to the character is used to follow this path.

The navigation mesh (NavMesh) [Snook, 2000] is the most used representation of the world geometry [McAnlis, 2008]. This graph, whose nodes represent the traversable surfaces of the 3D environment as convex polygons, is a compact representation of the world, independent of character abilities. Adding character constraints or abilities is traditionally done through other means, such as tweaking the pathfinding algorithm or extending the NavMesh with additional links (more details can be found in Section 2.1). However, these approaches impose limitations on the kind of abilities that NPCs can use to navigate, which detract from its realism.

In this paper, we set out to replace classical graph-based navigation with a system that can learn how to navigate between any two points on a map using all of the navigation options available to the character. Replacing the NavMesh with a learning system in modern AAA video games is challenging for several reasons. First, as the game worlds are increasingly more realistic, they have become both larger and more complex. Second, the maps can be dynamic, as objects and other characters can move in the world. Finally, to replace the existing NavMesh, solutions need to run on a tight budget at runtime and ideally be relatively cheap to train.

To tackle these issues, we opt for a model-free Reinforcement Learning (RL) approach [Sutton and Barto, 2018] to the navigation problem, where an agent learns a policy that maximizes a reward signal through interacting with an environment. Specifically, we train an agent with Deep RL to navigate to locations in the game world using Soft ActorCritic (SAC) [Haarnoja et al., 2018a] as our learning algorithm. We also build off of recent work that augments the agent's state with memory to effectively solve navigation tasks in complex 3D environments [Mirowski et al., 2016; Kapturowski et al., 2018; Wijmans et al., 2019].

We begin by providing the relevant background and related work on navigation in Section 2, followed by a detailed description of our system in Section 3. Then, in Section 4, we demonstrate the performance of our Deep RL system and examine several ablations on two maps created using the Unity game engine [Juliani et al., 2018]. We also train our agent on several map sizes in the engine of a recently released AAA video game to validate its potential as an alternative to the NavMesh. Notably, in contrast to previous RL-based approaches to navigation, we successfully train using continuous actions on 3D maps an order of magnitude bigger than simulators used in the research community [Wydmuch et al., 2018; Manolis Savva et al., 2019].

2 Background and RelatedWork

2.1 Navigation in AAAGames

Waypoint Graph. Prior to the NavMesh, the most popular approach to game navigation was to use a waypoint graph [Lid´en and others, 2002], which consists of a set of points of interest connected to each other. Unfortunately, this approach has several main drawbacks: its manual construction can be cumbersome and prone to human errors, it cannot handle dynamic objects, it is expensive to build since it needs to check all n(n - 1) combinations of paths, and the paths tend to not look realistic since all agents follow the same set of constrained paths [Tozour and Austin, 2002].

NavMesh. The NavMesh solves most of the aforementioned problems with waypoint graphs and is thus currently the main navigation tool used in video games [McAnlis, 2008]. Specifically, the NavMesh divides the game map into a set of convex regions, which can each be trivially navigated within. It can be generated from either the raw geometry of the world using voxel-based approaches, or using pre-processed inputs like planar layers [Van Toll et al., 2016; Oliva and Pelechano, 2011]. It is thus a compact representation of the world's traversable terrains, independent of any character ability. Once the polygons have been placed, a graph is created by using the polygons as nodes and by connecting adjacent polygons with edges. With the built graph, search algorithms such as A* and Dijkstra's algorithm can be leveraged to find the shortest path between two nodes. Then, the path is smoothed to look more realistic [Brand, 2009].

Using Navigation Abilities With a NavMesh. As alluded to in the introduction, it is increasingly common in modern games to offer additional navigation options to the players that enable the full use of the 3D space. For example, by using grappling hooks, jump-pads, jetpacks, teleportation, or other navigation abilities, a player can very quickly navigate a map. These abilities add versatility to the players' gameplay but come at the cost of an increase in the number of feasible paths, making the NavMesh increasingly expensive to search through and labor intensive to create [Van Waveren, 2001; Van Toll et al., 2011]. Specifically, in order to allow NPCs to use navigation abilities, the prevalent solution is to add an edge, called link, connecting the nodes at both ends of the use of the ability. An animation is then played on the character as it goes through the link to give the illusion of using the ability.

Figure 2: NavMesh links (either single or wide) are added to enable navigation between disconnected components of the graph. We added the minimum number of links such that the agent can reach any point on the map, e.g., a link that connects the rooftop to its top floor is added since the rooftops are accessible via double jumps.

A visual illustration of the NavMesh-based approach can be found in Figures 1 and 2. We used Unity [Juliani et al., 2018] to build a minimal map, called Toy Map. We then used Unity's built-in generation tool to create a NavMesh from the map geometry (Figure 1). We added a small set of complex navigation abilities (jumps, jump pads, and double jumps), and added links so that the NavMesh can take these actions into account (see Figure 2).

The search for all possible links that could be added to the graph can sometimes be done automatically. In the case of a jump, for example, possible jump trajectories are simulated and links are added between nodes that can be reached [Axelrod, 2008; Roumimper, 2017; Budde, 2013]. However, as this automatic search relies on connecting all the nodes that can be at the start and end of a movement trajectory, only the simplest trajectories can be used so that the search is tractable and the number of edges added is reasonable.

In practice, having navigation abilities makes the number of links and the graph connectivity increase dramatically and results in extremely long computation time [Axelrod, 2008] with many redundant links [Budde, 2013]. In such cases, adding a limited number of links manually is the favored option. However, not adding enough links can result in unrealistic behaviour, e.g., many NPCs aggregating in navigation bottlenecks around the map to use the specifically hand-designed way-points. As adding more links improves the realism of AI behaviors but increases the labor and runtime costs of the NavMesh, a compromise has to be made.

Another fundamental issue with links is that they do not correspond to a topological reality. For example, if a link to allow NPCs to climb a ladder is added, it is hard to interrupt the character once it starts climbing. Once on the link, the character is no longer moving in a traversable area, as the link does not correspond to a topological reality. Interrupting the character, e.g., by making it fall off the ladder, would require additional work to make it remain on the NavMesh.

Thus, existing solutions to support navigation abilities are far from perfect. Supporting navigation abilities comes at expensive labor and runtime costs, and fundamental flaws limit the realism of the obtained behaviors. In the case of our toy map, we manually placed a small number of additional links 2 to bridge disconnected parts that should be accessible by using the jump, the double jump or the jump pads (Figure 2). While we are definitely not experts, adding links on such a small map still took us a few hours. Even if imperfect, this minimal example helps to illustrate the main limitations of the NavMesh and motivates our use of Deep RL.

2.2 Navigation in Robotics and RL

SLAM. The classical approach to navigation in robotics is called simultaneous localization and mapping (SLAM) [Leonard and Durrant-Whyte, 1991], which builds a highlevel map (usually a top-down view) of the world from experience and locates the agent within this map. The high-level map is generated using data from sensors, such as LIDARs or RGB cameras. Once the map has been built, classical pathfinding algorithms can be used to plan and extract the shortest paths between any two points. Recently, several works have extended the SLAM framework to learn the high-level mapping using differentiable neural networks [Zhang et al., 2017; Beeching et al., 2020] with some approaches even having success in video games [Bhatti et al., 2016]. Similar to the NavMesh, SLAM-based approaches struggle to integrate navigation abilities in the mapping. Moreover, in the case of video games, we already have exact localization and mapping and thus do not need to use an estimate.

Model-Based RL. Alternatively, in model-based RL, a model of the transition dynamics, i.e., a mapping from the current state and action of the agent to its next state, can be used for planning [Sutton, 1991]. The model of the transition dynamics can either be estimated from interacting with the environment [Kaiser et al., 2019], or in some cases be given to the agent beforehand [Silver et al., 2016]. In the case of video games, a model of the world can be used if we can manipulate the underlying game engine, in the sense that actions can be undone and different actions can be tried.

Like SLAM and NavMesh-based approaches, model-based RL approaches could theoretically handle complex navigation actions and potentially be used to plan shortest paths. However, there are two notable drawbacks to using modelbased approaches for planning. Firstly, like SLAM and NavMesh-based approaches, they are expensive to run at inference/mapping time as they need to compute many forward passes of the model to determine the best path using the complex navigation abilities. Secondly, when the model is estimated from data, they tend to suffer from compounding error due to model imperfections, which makes planning challenging [Feinberg et al., 2018].

2 The exact number of additional links is 54.

Model-Free RL. Model-free RL does not use a model to plan but learns which actions to take in the environment through pure trial and error [Sutton and Barto, 2018]. Previous works have used model-free RL for navigation [Mirowski et al., 2016; Wijmans et al., 2019] but have been mostly limited to relatively small 2D environments with simple action spaces. Recent works have circumvented the lack of planning in model-free RL by using a hierarchical architecture, where intermediate goals are given to a controller by a high level planner [Eysenbach et al., 2019]. As navigation in a visually complex environment is usually modeled as a partially observable markov decision process, the importance of using memory has been previously acknowledged [Mirowski et al., 2016]. While unstructured memory such as LSTMs [Hochreiter and Schmidhuber, 1997] can be used, architectures involving spatially structured memory have also been explored [Parisotto and Salakhutdinov, 2017; Beeching et al., 2020]. The use of auxiliary tasks to accelerate the learning of challenging goal-based RL problems has also been studied [Mirowski et al., 2016; Andrychowicz et al., 2017].

3 Approach

The following section describes our approach to solve pointto-point navigation on a fixed 3D map using navigation abilities available to the agent.

States. The state is composed of local perception in the form of a 3D occupancy map and a 2D depth map, as well as scalar information about physical attributes of the agent and its goal (velocity, relative goal position, absolute goal position, and previous action). The 3D occupancy map, referred to as BoxCasts, can be generated and cached offline. This makes it efficient to compute at runtime which is critical when running inside a video game engine. 2D depth maps have been used in several recent works [Manolis Savva et al., 2019; Wijmans et al., 2019]. They can be extracted from a rendering camera, or in our case by casting RayCasts. The absolute positions of the agent and its goal pass through their own network to extract an absolute position embedding similar to [Wijmans et al., 2019].

Actions. The actions are continuous values ∈ [-1, 1], and correspond to jump, forward, strafe, rotate. The jump is treated as a continuous action on the algorithmic side and binarized in the environment, i.e., jump if > 0.

Rewards. To avoid complications associated with long term credit assignment when using a sparse reward, we densify the reward signal to be:

where Dt is the Euclidean distance between the positions of its arguments at time t, α is a penalty given at each step and ϵ is the distance below which the agent is considered to have reached its goal. We note that the first term rewards the agent for getting closer to its goal than it has ever been so far in this episode. While this reward is non-markovian, since it depends on all previous states visited in the episode, we use an LSTM [Hochreiter and Schmidhuber, 1997] to capture a compressed history of the trajectory.

Training Procedure. As running a game engine is costly, we use Soft Actor-Critic (SAC) [Haarnoja et al., 2018a], a sample efficient off-policy RL algorithm. As described in [Haarnoja et al., 2018b], we modify SAC so that the entropy coefficient is learned and there is no state value network. The critic and policy networks share layers that are tasked with extracting an embedding from local perception as well as previous steps by using Convolutional Neural Networks [LeCun et al., 1989] and an LSTM [Hochreiter and Schmidhuber, 1997]. Furthermore, we use a burn-in to initialize the hidden states when sampling from the replay buffer [Kapturowski et al., 2018; Paine et al., 2019].

During training, we spawn the agent and its goal in a cylinder with a variable radius. An episode is considered over when the agent has reached its goal or when the number of steps is over a certain budget. To allow the agent to have informative trajectories at all stages during training, we use a training curriculum [Bengio et al., 2009] and increase the radius of the spawning cylinder until the full map is covered. Specifically, when the agent achieves a success rate of > 80% over the last 200 episodes we increase the spawning radius of the goal. All the networks are trained using the Adam optimizer [Kingma and Ba, 2014]. More details on our hyperparameters can be found in the supplementary material, and Figure 3 describes our architecture.

4 Experiments

To highlight the capabilities of our Deep RL system, we train an agent as described in Section 3 on both a Toy Map (see supplemental) and a Big Map (see Figure 4), which we built using the Unity game engine [Juliani et al., 2018]. Both of these environments have many jump pads scattered across the map and allow for the agent to perform double jumps. In order to determine the factors that lead to its success, we run state-based and algorithmic ablations. For the state-based ablation, we evaluate our agent without BoxCasts, without RayCasts, without BoxCasts and RayCasts, and without absolute positions. For the algorithmic ablation, we test removing the training curriculum, the LSTM, and using Hindsight Experience Replay (HER) [Andrychowicz et al., 2017].

Ablation Results. The results for both ablation studies can be found in Figure 5 and in the supplemental. Concerning the state ablation, we find that, on both the Toy Map and the Big Map, the Base agent is significantly faster (in terms of samples) at reaching the target success rate on the final curriculum level than without BoxCasts, without RayCasts, and without BoxCasts and RayCasts (see supplemental for more details). Furthermore, we find that removing the absolute position from the agent's state does not negatively impact performance. In fact, the agent performs slightly better on average (over 5 seeds) which we find to be statistically significant (p < 0.05) on the Big Map but not on the Toy Map.

Moreover, we find that by removing both BoxCasts and RayCasts, the agent fails to reach the final curriculum level in the training period (see Figure 5) on both the Toy Map and the BigMap. As this agent is training without local perception, it is perhaps unsurprising that it is less sample efficient. However, we do note that since the performance of the agent is still increasing (albeit slowly, see supplemental), given more training samples it may attain the target success rate (100% on the Toy Map and 90% on the Big Map) on the final curriculum level. To verify this, we ran that configuration for 100M steps on the Big Map and confirmed that it could not reach the target success rate of 90% (see supplemental), but plateaus at ∼ 80% success rate on the final curriculum level.

In terms of the algorithmic ablation, none of the algorithmic changes make a significant difference on the Toy Map (see supplemental). On the other hand, on the Big Map we find that removing the LSTM significantly hurts sample efficiency. We hypothesize that the discrepancy between the Toy Map and Big Map with regards to the LSTM can be explained by the simplicity of the Toy map, with the local perception being sufficient to accurately represent the space. We also find that removing the training curriculum improves performance significantly on the Big Map, whereas it does not have a significant impact on the Toy Map. Upon further inspection, we found that we increased the curriculum radius by 5 meters at every iteration on the Big Map and by 10 meters on the Toy Map. A hyperparameter search would need to be done in order to find the optimal setting. However, we note that the strong performance without a curriculum on the Big Map indicates that the dense reward signal that we use is sufficient for the agent to learn efficiently without the need for a curriculum. Finally, we find that performance does not increase significantly with the use of HER on the Toy Map but it does (insignificantly) on the Big Map. Since HER has been shown to be effective in sparse reward regimes, the minimal gains could be attributed to the dense reward signal.

Deep RL vs. NavMesh. To provide a comparison to the NavMesh, we made a video 3 that shows how the two systems behave on the Toy Map. We note that without additional links (which are manually intensive to create), the NavMesh based solution would not be able to navigate to the rooftops. Thus, whereas our Deep RL approach achieves a 100% success rate on this map, the NavMesh based approach without additional links would have a significantly lower success rate. As explained in Section 2.1, such a comparison is imperfect as the NavMesh-based navigation could be made better by spending more time adding links and animating characters on link traversals. Nevertheless, we believe that this visual comparison provides interesting insights to understand how our approach relates to classical solutions for navigation.

3 Video comparison with a NavMesh: youtu.be/WFIf9Wwlq8M

Results in Hyper Scape. To validate that our system can scale beyond toy maps to the needs of AAA video game productions, we integrated our solution in the engine of a recently released game called Hyper Scape. A video of our results in the game is available 4 , in which we can see the agent navigate around the map by moving sticks on a virtual controller. Apparent in the video is that the agent jumps frequently as it navigates. Upon further inspection we discovered that jumping is slightly faster than walking. We found that this can be alleviated by adding a sprinting action (common in games). Nevertheless, the agent is able to navigate successfully on complex maps with a size of 400m× 400m× 90m, reaching a 90% success rate. We also trained the agent on the full map (1000m× 1000m× 90m) on which it reached 74% success rate. Success rates and performance benchmarks are provided in the supplemental.

5 Discussion

The results of our ablation study indicate that local perception (through both RayCasts and BoxCasts) drastically improves the sample efficiency of the Deep RL system. We also found that the LSTM was crucial for optimal sample efficiency on large maps. To further improve sample efficiency, auxiliary tasks [Jaderberg et al., 2016] could be used to train the representation layers more efficiently.

All of the experiments conducted in this paper were concerned with the sample efficiency of the Deep RL agent on a single map. We emphasize that sample efficiency is indeed important when faced with a slow simulator, which is the case with AAA games. This can be alleviated by implementing the game engine into a binary that can be run much faster than real-time, however, this may not be feasible due to engineering complications. Sample efficient solutions, however, often come at the cost of increased inference time. Our results in the AAA game suggest that Reinforcement Learning is a viable alternative to NavMesh-based navigation.

Finally, while not addressed in this paper, generalization is an interesting direction of future work. Typically the agent is tasked with navigation within a game with dynamic components, e.g., players or objects. As for the NavMesh, it is usually prebuilt to optimize for runtime efficiency and thus cannot easily handle dynamic components [McAnlis, 2008]. Instead, NavMeshes are either updated dynamically at runtime [Marden, 2008] or navigate around non-static objects by using heuristics [Brand, 2009]. Thus, a generalizable Deep RL agent may be key to adapt to dynamic components that may not have appeared during training. Generalization could also enable the reusability of the trained system on novel maps. This can have drastic cost saving impacts when the number of maps becomes large, e.g. when procedurally generated, where retraining the agent is not feasible.

In this paper, we showed that Deep RL can be an alternative to the NavMesh for navigation in complicated 3D maps, such as the ones found in AAA video games. In comparison with previous works exploring Deep RL for navigation, our Big Map and AAA Game map are an order of magnitude bigger [Manolis Savva et al., 2019; Wydmuch et al., 2018]. Unlike the NavMesh, the Deep RL system is able to handle navigation actions without manually specifying individual links. We believe that our work can be used as a stepping stone for future Deep RL applications inside modern video games.

4 Hyper Scape video: youtu.be/DKdQFajLfzk

Acknowledgments

We would like to thank Julien L'Heureux, Claudine Combe, Nicolas Landron, B´erenger Bailly, Mike Yurick, Philippe Marcotte and Adrien Logut for many engineering contributions and thorough feedback during the development of this project. We also wish to thank Pierre Falticska, Olivier Pomarez, Paul Barde and Julien Roy for insightful discussions and their feedback on an earlier draft of this paper. Finally, we thank Olivier Delalleau, Batu Aytemiz and Sahand RezaeiShoshtari for contributions to an early iteration of this project.