Navigation AI: Overview, and Practical Examples

Navigation AI Overview, and Practical Examples We will begin our presentation, "Navigation AI: Overview, and Practical Examples.“ -------RecastNavigation Copyright (c) 2009 Mikko Mononen [email protected] Microsoft, Windows, and Microsoft Teams are trademarks or registered trademarks of Microsoft Corporation in the United States and other countries. Screenshots of Microsoft products are used with permission from Microsoft. ©CAPCOM 1

Navigation AI System Overview Please note that this presentation includes the following content: • Violence, gore, and horror scenes • Spoilers for important scenes and strategies Viewer discretion is advised The first half of this presentation will provide an overview of the navigation AI system. Before we begin, there will be a section in this session where in-game video will be used as an example. 1 Therefore, this session will include violent scenes, horror scenes, and elements that may spoil the game. Please keep this in mind as we proceed. ©CAPCOM 2

Table of Contents • What is Navigation AI? • AIMap Creation Workflow • Development Support Functions This is the flow for RE ENGINE's navigation AI system. First of all, we would like to briefly introduce what Navigation AI is in the first place. 2 Next, we will discuss how to create maps for character navigation and introduce each system along with its workflow. Finally, we will introduce the development support functions that are useful when actually developing and using the navigation system. ©CAPCOM 3

What is Navigation AI? First, I'll talk about navigation AI. 3 ©CAPCOM 4

Navigation AI in RE ENGINE A mechanism for characters to move arbitrarily in the game world Taking walls and other obstacles into account, it finds a route to the character's destination Characters moving via Navigation The navigation AI in RE ENGINE is a mechanism that allows characters to move arbitrarily in the game world. It's probably similar in other game engines, but it allows the character to find a path to reach a destination while avoiding 4 obstacles such as walls in the field. The video shows many characters on the field moving to thered goal point through the best path for each character. Navigation is the function that guides the characters to the goal. ©CAPCOM 5

Elements Required for Navigation What's needed to get to the destination? Map → AIMap GPS → Agent So what are the elements necessary for navigation? The same elements we need to get somewhere in the real world. First, we need a map. Without a map, we do not know where we are or where our destination is. 5 Next is a navigation system. Today, most are familiar with in-car or smartphone GPS systems. With such a navigation system, you can go anywhere. Our Navigation has two elements: AIMap and Agent. These correspond to real world maps and GPS navigation systems respectively. ©CAPCOM 6

AIMap The game world's equivalent of a map In RE ENGINE, there are three varieties of AIMap: NavMesh VolumeSpace Waypoint AIMap is like a map of the game world. RE ENGINE has three types of map: NavMesh, VolumeSpace, and Waypoint. The appropriate map is chosen for each character. ©CAPCOM 6 7

Characteristics of each AIMap NavMesh VolumeSpace Waypoint NavMesh VolumeSpace Waypoint Use Moving on the ground Moving through the air Moving between fixed points Generation method Automatic generation from collision map Automatic generation from collision map Manual placement of points Number of nodes ≈Processing load Many Many Few Here are the features of each AIMap. NavMesh is a map often used for characters moving on the ground, and is automatically generated from environment collision map data. 7 The ground is represented as a mesh, allowing the user to calculate which edges are needed to reach the destination. The polygonal coverage of the ground surface results in a large number of nodes, and the processing load is consequently high. ©CAPCOM 8

Characteristics of each AIMap NavMesh VolumeSpace Waypoint NavMesh VolumeSpace Waypoint Use Moving on the ground Moving through the air Moving between fixed points Generation method Automatic generation from collision map Automatic generation from collision map Manual placement of points Number of nodes ≈Processing load Many Many Few VolumeSpace is a map used for characters that move through the air. It is a graph of voxels automatically generated from collision meshes. It is like an aerial version of NavMesh, with the same drawback of having many nodes. ©CAPCOM 8 9

Characteristics of each AIMap NavMesh VolumeSpace Waypoint NavMesh VolumeSpace Waypoint Use Moving on the ground Moving through the air Moving between fixed points Generation method Automatic generation from collision map Automatic generation from collision map Manual placement of points Number of nodes ≈Processing load Many Many Few In the Waypoint AIMap, points are placed manually in locations you want the character to pass. It is a simple method. The number of points can be easily controlled, reducing processing load, but it requires manually placement and does not take into account terrain information such as walls. 9 Each has its own advantages and disadvantages. We have the user choose the appropriate map depending on the character. ©CAPCOM 10

Agent The "GPS navigation system" that guides the character to their destination Attached to game objects as a component NavigationSurface component 1. Attach to game object 2. Set AIMap and destination 3. Guide to the destination (It is up to the character to decide how to actually get there.) The Agent is like a car's GPS navigation system that guides the character to its destination. The Agent is attached to the character you want to move, and once you set which AIMap you want to use and where you 10 want it to go, the Agent will guide it to the destination. The agent only shows the direction you should head, as shown by the red arrow in the video. It doesn't physically move the character. Just as it is up to the driver to decide how the car will move when the car navigation system tells them "turn right,“ we leave it up to the character to decide how to move. ©CAPCOM 11

AIMap (NavMesh) Usage Workflow Next, we will show you the workflow for actually using navigation in a game. The subject here is a NavMesh used by a character moving on the ground. 11 ©CAPCOM 12

NavMesh Usage Workflow Automatic generation of base NavMesh Automatic generation of base NavMesh from terrain data Here is an overview of the workflow. There are three main phases of the NavMesh usage flow. First, a base NavMesh is automatically generated from the game terrain information. 12 The NavMesh is generated at locations where the character can walk, avoiding places where there is no ground or where there are walls. ©CAPCOM 13

NavMesh Usage Workflow Automatic generation of base NavMesh Static processing of NavMesh We want to jump between nodes that are not connected by the ground Next, we process the NavMesh statically. This consists of manually adjusting the NavMesh that was automatically generated earlier. For example, look at the position of the red arrow in the image. 13 They are not connected by the automatically generated NavMesh because they are not connected by the ground, but it may be possible to jump over it depending on the game. In order to satisfy such a requirement, RE ENGINE provides the ability to modify the automatically generated NavMesh. ©CAPCOM 14

NavMesh Usage Workflow Automatic generation of base NavMesh Static processing of NavMesh Dynamic processing of NavMesh We want to change pathing mid-game Lastly, dynamic processing of the NavMesh. For example, "Normally you can go here, but after a rockfall event, I want to close it to traffic." 14 To satisfy such requirements, RE ENGINE has functions to process the NavMesh dynamically in-game. We will introduce these functions in order. ©CAPCOM 15

1. Automatic Generation of Walkable Areas Automatic generation of NavMesh in walkable areas based on collision mesh information in the game world In-game collision mesh Generated NavMesh (RecastNavigation) What counts as 'walkable' can be adjusted per-character via parameters This function automatically generates a NavMesh of walkable areas based on collision meshes. The NavMesh is the graph structure represented by green nodes and white links. What kind of mesh is generated can be controlled according to the character using the map. Parameters like the character's size and the height of the steps it can climb can be set. 15 This uses RecastNavigation, which is also used by many other game engines. ©CAPCOM 16

2. Modifying the Generated Mesh For example... • We want to connect nodes that can be reached by jumping • We want the character to jump down from ledges • There is a node on the NavMesh that we don't want the character to go through Jumps over gaps Can jump down but not climb up We want to make a poison swamp that the character will detour around We will modify the NavMesh that we have just generated. For example, we want to connect nodes that can be reached by jumping. Or we want to make a step unclimbable, but we want the character to jump down from it. Or here are nodes on the NavMesh that we do not want the character to traverse. The following features help realize the above. ©CAPCOM 16 17

2-1. ExtraLink Ability to create links between placed boundaries Can be placed as one-way or two-way links For jumping down, Downward link Bidirectional link for jumping Moving through links The first feature is called ExtraLink. This is a function that allows you to place a Boundary at an arbitrary location and then create links between the Boundaries 17 afterwards. Both one-way and two-way links are supported, and you can create links that match what you want to do, such as downward-only links or two-way links. In the video, the character descending from a high plateau uses an ExtraLink to jump down, but the character climbing up to the plateau moves all the way up the hill. This is because the link for jumping off is one-way and cannot be used for climbing. ©CAPCOM 18

2-2. MapBoundary Attributes are assigned to nodes that come in contact with a specified area Agents can be made to avoid certain nodes with certain attributes Specify an area to attach the attribute with Boundary Attributes are assigned to the nodes with which the boundary is in contact Avoiding the poisonous swamp Next, we introduce the MapBoundary function. This also places a Boundary at an arbitrary location, but allows attributes to be assigned to nodes that come into contact with the Boundary. 18 The character can move to avoid certain attributes, so in the video, the character doesn’t pass through the attribute that has become a poison swamp, but instead goes around it. ©CAPCOM 19

2-3. MapBoundary + Map Division Section off nodes according to the specified area and assign attributes within the area ◎ Benefits of map division • Can specify the range of influence according to the shape of the set piece, etc., without being limited by node shape ▲ Disadvantages • Increased number of nodes increases processing load Proceed by the shortest route, just barely avoiding the poisonous swamp MapBoundary provides the ability to divide the map into sections. I mentioned earlier that MapBoundary assigns attributes to the nodes it contacts, but the shape of the poison swamp does not necessarily match the shape of the nodes. 19 However, with the division function, it's possible to specify the area of influence to match the shape of the set piece, etc., without being limited by the shape of the nodes. The video shows the character taking the shortest path forward, just barely avoiding the poisonous swamp. However, it has the disadvantage of increasing the node count, and in turn the cost ofcalculation. Whether to use the division function is up to person designing the set piece. ©CAPCOM 20

3. Dynamic Manipulation of NavMesh at Runtime At certain times during runtime execution • We want to change attributes • We want to create a link between specific nodes ◎ Benefits • Operation can be turned on/off according to game state • NavMesh can be manipulated to match moving objects ▲ Disadvantages (Advantages of static processing) • High processing load, can cause game slowdown Ladder in RE:4 In some games, the location of the poison swamp changes over time, and some games have a mechanic that allows ladder movement only while a ladder is in place. 20 In RE:4, for example, there is a set piece that allows enemies to climb up a ladder once the ladder is in place. In such cases, we provide the ability to modify the NavMesh even during the game. By turning a link on or off depending on the game mechanic, it is possible to change the area of influence according to moving objects. However, doing this at runtime is costly, and it is not possible to avoid extra load that may make the game become sluggish. ©CAPCOM 21

3-1. Adding Attributes with AIMapEffector Dynamic attribute assignment Dynamic map partitioning Rotating turrets in RE:4 • • • Assumes 4 patterns in advance vertically, horizontally, and diagonally Dynamic attribute assignment by AIMapEffector Pre-partitioning by MapBoundary (processing load reduction) As attributes change, the Agent changes paths AIMapEffector is a dynamic MapBoundary-like function. It can dynamically assign attributes to the nodes it contacts. It can also dynamically divide the map. In the video on the left, you can see that even when the poisonous swamp is moved, the character correctly avoids it. 21 It can also help when bottlenecked by processing load. Divide the map in advance with MapBoundary, AIMapEffector can be used to add attributes to the map. In RE:4, there is a rotating turret setpiece that uses this method. This turret can be moved 360 degrees in any direction by the player. The enemy must move to avoid running into the turret. ©CAPCOM 22

3-1. Adding Attributes with AIMapEffector Dynamic attribute assignment Dynamic map partitioning Rotating turrets in RE:4 • • • Assumes 4 patterns in advance vertically, horizontally, and diagonally Dynamic attribute assignment by AIMapEffector Pre-partitioning by MapBoundary (processing load reduction) As attributes change, the Agent changes paths The area is divided by MapBoundary in advance, assuming four vertical, horizontal,and diagonal configurations. Four Effectors of the same size are also prepared. When the game is running, only the Effector closest to the current angle is enabled. The NavMesh around the turret can be clipped at an approximate position. 21 The video on the right shows a simple reproduction of this mechanic. As shown in the top half, you can use AIMapEffector's dynamic division to change the mesh at any time, but this is a very processing-intensive implementation. By pre-cropping as per the bottom half, while achieving a behavior similarto the dynamic division above, the processing load can be greatly reduced. ©CAPCOM 23

3-2. ExtraLink with AIMapEffector AIMapEffector dynamically makes ExtraLink between touching nodes ExtraLink is dynamically generated between effectors (light blue boundary) Dynamic linking Agent behavior before and after link Next is the dynamic ExtraLink. This is also provided by using AIMapEffector. This function allows you to place two AIMapEffectors and link between them. In the video, when a ladder appears, the link is connected to the top and bottom of the steps. 22 The first character to move will go up the slope, since there is no ladder. However, after the ladder appears, the character takes a shortcut using the ladder. ©CAPCOM 24

Development Support Functions The following are three development support functions that help developing and using navigation systems. 23 ©CAPCOM 25

AIMapDebugger Tool to visualize AIMap information Features • Rendering nodes and links • Filtering of draw elements • Drawing range filtering • Display of detailed information for each node • Pathfinding tests Monster Hunter Rise: AIMap drawing of the Shrine Ruins Note: The scene is for testing navigation and differs from the released game First, here is the AIMapDebugger. In the images used in the previous explanations, the NavMesh was drawn in green. The AIMapDebugger is the tool that draws it. 24 The AIMapDebugger is a tool that draws the nodes and links of the AIMap. You can see how the AIMap is laid out in the game. When developing and using navigation, you can check if the NavMesh is generated correctly, and confirm ExtraLinks and attributes are set as intended. If a problem occurs during the game, such as a character bypassing somewhere, AIMapDebugger can be used to check for unnatural breaks in nodes, etc. The AIMapDebugger has functions such as drawing filtering and pathfinding testing. Let's take a look at the AIMapDebugger while actually running it. ©CAPCOM 26

AIMapDebugger Demo Note: This is a demo scene and differs from the actual game screen. The defects in this demo are fictitious for demonstration purposes. I would like to take a look at an AIMap from "Monster Hunter Rise" using AIMapDebugger. This time, as a demonstration of bug investigation, we have prepared a scene in which the Palico makes a detour at a certain point. 25 This is a bug created for demonstration purposes, so it will not happen in the actual game. No need to panic. First, go to the location where the glitch occurred. The yellow and blue balls are placed as landmarks. If you try to go from the yellow point to the blue point, your Palico will take a detour. ©CAPCOM 27

AIMapDebugger Demo Note: This is a demo scene and differs from the actual game screen. The defects in this demo are fictitious for demonstration purposes. AIMapDebugger has the ability to do a pathfinding, Let's look at a route using it. Indeed, a detour has been created at a place that could have been reached by going straight ahead. ©CAPCOM 26 28

AIMapDebugger Demo Note: This is a demo scene and differs from the actual game screen. The defects in this demo are fictitious for demonstration purposes. To see what is happening, let's actually look at the Palico's AIMap. I tried to display the AIMap, but it's just a large stage, I ended up displaying way too much NavMesh. 27 It's difficult to investigate when extra meshes are drawn, so let's narrow down the display area. This way, you can display only nodes in the area specified by the boundary. ©CAPCOM 29

AIMapDebugger Demo Note: This is a demo scene and differs from the actual game screen. The defects in this demo are fictitious for demonstration purposes. Now let's take a look at the detour. The debug drawing shows that the NavMesh has been split between the start and the goal. This means that the Palico can't reach the goal by going ahead, so it goes around. ©CAPCOM 28 30

AIMapDebugger Demo Note: This is a demo scene and differs from the actual game screen. The defects in this demo are fictitious for demonstration purposes. The reason why the NavMesh is divided this time, Is because I had placed the AIMapEffector described earlier. Once this was removed, the NavMesh was successfully connected. 29 When we check the route again with the path finding function, we can see that we have successfully created a straight path to the goal. Investigation complete. In this way, using AIMap's drawing, filtering, and path finding functions are used to implement and debug navigation. ©CAPCOM 31

NavigationProfiler Navigation routing problems • Path finding (A* algorithm) is intensive • The farther away from the goal, the greater the load • Increased load if multiple characters search at the same time --> How much margin do we have? We need some visualization Desired information • Start/goal position and calculation time for each character • Number of pathfinding requested by multiple characters at the same time • Total computation time spent in one frame Next is the introduction of NavigationProfiler. The reason for the creation of the Profiler is that the A* algorithm used for path finding has a large processing load and 30should not be executed indiscriminately. The processing load increases with the distance to the goal and when multiple characters search for a route at the same time. So, NavigationProfiler was created as a tool to visualize how much processing is required to perform navigation. It collects the start and goal positions and computation time of the characters that performed the pathfinding, the number of requests, execution time, etc., for each frame. ©CAPCOM 32

NavigationProfiler A tool that can profile the information needed to investigate the processing load of pathfinding Information that can be profiled • Total • Frame average of computation time and number of requests • Maximum frame of computation time and number of requests • Total number of requests during the profile period The NavigationProfiler screen looks like this. You can profile the information needed to investigate the processing load of pathfinding. The maximum and average values for the number of requests and computation time can be obtained. ©CAPCOM 31 33

NavigationProfiler A tool that can profile the information needed to investigate the processing load of pathfinding Information that can be profiled • Total • Frame average of computation time and number of requests • Maximum frame of computation time and number of requests • Total number of requests during the profile period • Per frame • Computation time, number of requests Next is information on each frame. You can view information for each frame you specify. You can get the computation time and number of requests for that 32 frame. ©CAPCOM 34

NavigationProfiler A tool that can profile the information needed to investigate the processing load of pathfinding Information that can be profiled • Total • Frame average of computation time and number of requests • Maximum frame of computation time and number of requests • Total number of requests during the profile period • Per frame • Computation time, number of requests • Per pathfind request • Computation time • Start/goal position • Various setting items such as Map type Detailed information for each request can also be viewed. Which GameObject the request is from, the type of AIMap being looked at, time spent, start and goal coordinates, and33 more. ©CAPCOM 35

RE:4 Practical Example Here's a look at the NavigationProfiler being used on the navigation in RE:4. The scene we will profile is Leon visiting a village early in the game, where he has to survive an attack by villagers. 34 The event is an attack by a large number of villagers all at once, and since each villager is navigating their way around, there are a lot of pathfinding requests. ©CAPCOM 36

RE:4 Practical Example Overall profile information Villagers pouring in Demo Video We picked up some of the results of measuring about 5,000 frames of the event. This time it is only for profile results measured in a PC environment. If you change the platform, such as PS5, you will get different results. 35 During 5,000 frames, there were 6021 pathfinding requests, which is about 1.2 per frame. ©CAPCOM 37

RE:4 Practical Example Overall profile information Villagers pouring in Demo Video As far as we could profile this time, the maximum number of requests in a frame was 5. Next, we will examine in detail the frames in which these maximum requests were made. 36 ©CAPCOM 38

RE:4 Practical Example Frame with most requests made information Overall profile information Villagers pouring in Demo Video Looking at the information for the frames with 5 requests, the total computation time appears to be 0.512 ms. 37 This is longer than the average value of 0.348 ms, but shorter than the maximum value of 0.797 ms. This frame has a large number of simultaneous requests, but the computation time for each request seems to have been short. ©CAPCOM 39

RE:4 Practical Example Frame with most requests made information Details of those 5 requests Villagers pouring in Demo Video Let‘s take a look at the details of the five requests made. Which GameObject each route calculation request is from, which AIMap was looked at, time taken, start and goal coordinates, etc. are listed. 38 Based on this, the title can decide "There are too many requests in one frame, so let’s limit them", or "requests are taking a long time, so let's shorten the search distance." An appropriate plan of attack for processing load countermeasures can be considered. ©CAPCOM 40

NavigationChecker When adding functionality, bugs that unintentionally change the route can be introduced Title There are places where it used to go straight but now it's going around. Until a month ago, it was going straight. But I ran it for the first time in a while, and it took a detour. That's not supposed to happen... Engine We will investigate. Feature addition A Feature addition B Bug fix C ・ ・ ・ • Huge amount of changes made in the last month • Can't tell which one is to blame • Only in certain pathways • Wasn't caught in testing when the feature was added --> We want to know as soon as possible if a bug has been introduced Finally, there is NavigationChecker. Although navigation has many features, such as those just described, when a feature is added or modified, it may accidentally change the route. 39 It is easy to notice if the change is obvious to the eye, but in many cases, the path may have shifted by only 1 cm, or when it is changed only on a certain map in a certain game. If no one notices for a while, and you finally encounter a case where the pathway has shifted a month later, you will have to dig through all the changes for that month. NavigationChecker is a tool to check for unintentional route changes in navigation, to prevent such cases from occurring. ©CAPCOM 41

CI Checks with NavigationChecker A mechanism to check daily that unintended rerouting has not occurred Registers each coordinate of the route and notifies when there is a difference in the engine's calculation results Comparison Reference path Today's engine's path Post to Microsoft Teams when route differences are detected NavigationChecker has two functions. A function to store the coordinates of the start/goal and the coordinates of the route from the start to the finish line. 40 And a function where, when the current engine calculates the route coordinates, it checks if there is any difference compared to the saved coordinates from the first function. With this, the correct coordinates calculated by the engine are registered and checked against every day to see if the engine's calculated values have changed. Since it would be tedious to manually check the coordinates every day, the check is automated by CI. When there is a difference in the route, it is posted to Microsoft Teams. ©CAPCOM 42

NavigationChecker Test Path Check with real game maps to pick up problems specific to complex terrain • Using a map from the previously released Monster Hunter Rise • • Massive routes that can cover a wide area of the map ・For each of the 13 areas, there are 156 routes to move from one area to another (=13 x 12) Unusual paths where problems have been reported in the past 3 maps Large Monster Small Monster Palico 3 stages Shrine Ruins Sandy Plains Lava Caverns Large number of test routes and coordinates Glitches that don't appear in simple stages like the one I showed you in the feature introduction often crop up in complex terrains used in actual games. 41 Therefore, in order to detect problems specific to complex terrain, we have been testing this feature using maps from Monster Hunter Rise, which has already been released. How do we create the pathways to be tested? First, we created a large number of paths that could cover a large area of the map. Specifically, because there are 13 areas in the Shrine Ruins, 156 pathways can be created to travel from one area to another. Then, we have added some special pathways that have caused issues in the past. Pathways that include climbing up and down walls, long-distance pathways, etc. ©CAPCOM 43

NavigationChecker Test Path Check with real game maps to pick up problems specific to complex terrain • Using a map from the previously released Monster Hunter Rise • • Massive routes that can cover a wide area of the map ・For each of the 13 areas, there are 156 routes to move from one area to another (=13 x 12) Unusual paths where problems have been reported in the past 3 maps Large Monster Small Monster Palico 3 stages Shrine Ruins Sandy Plains Lava Caverns Large number of test routes and coordinates This title has separate AIMaps for large monsters, small monsters, and Palicoes. The pathway coordinates are saved for each AIMap. 41 Also, aside from the Shrine Ruins, we also used the Sandy Plains and Lava Caverns locales to create test routes and run similar tests. By performing checks on a large number of routes created in this way, unintended behavior can be prevented. ©CAPCOM 44

Navigation AI System Overview Summary Elements Required for Navigation • Game World Map: AIMap • Game World GPS Navigator: Agent NavMesh Usage Workflow • Automatic generation of NavMesh from ground surface collision mesh • Static processing of NavMesh (ExtraLink generation, attribute assignment) • Dynamic ExtraLink generation and attribute assignment in game Development Support Functions • AIMapDebugger to visualize AIMap information • NavigationProfiler to visualize the status of navigation requests • NavigationChecker to detect unintended route changes That's all for the navigation AI system overview of RE ENGINE. Here is a brief summary. First of all, the elements required for Navigation AI. AIMap as a map and an Agent as a navigation system. 42 Next, we introduced the workflow for creating an AIMap. The NavMesh is automatically generated from environment collision, followed by static and in-game dynamic processing at appropriate times. ©CAPCOM 45

Navigation AI System Overview Summary Elements Required for Navigation • Game World Map: AIMap • Game World GPS Navigator: Agent NavMesh Usage Workflow • Automatic generation of NavMesh from ground surface collision mesh • Static processing of NavMesh (ExtraLink generation, attribute assignment) • Dynamic ExtraLink generation and attribute assignment in game Development Support Functions • AIMapDebugger to visualize AIMap information • NavigationProfiler to visualize the status of navigation requests • NavigationChecker to detect unintended route changes Finally, three development support functions were introduced. First there's the AIMapDebugger, which allows you to draw AIMaps and perform various debugging tasks. 42 Then there's the NavigationProfiler, which visualizes navigation requests and gathers information to reduce processing load. And, finally, the NavigationChecker, which detects unintended route changes during daily development. The game characters created with RE ENGINE use these functions to run around the game world. ©CAPCOM 46

Examples of Use in Titles Here is how these Navigation features are used in the titles: I will use RE:4 and EXOPRIMAL, which have already been released, to give some examples. 43 ©CAPCOM 47

Table of Contents • Enemy Character Movement (RE:4) • Ally Character Movement (RE:4) • Processing and Memory Load Reduction Measures (RE:4) • Development Support (RE:4 / EXOPRIMAL) This is the content of the next part. Movement of enemy characters, movement of ally characters, processing and memory load reduction measures, and development support. ©CAPCOM 44 48

Enemy Character Movement (RE:4) I will start with a case study of enemy character movement in RE:4. 45 ©CAPCOM 49

Enemy Character Movement Ganado (Villagers) • Attack in groups • Still have some intelligence What kind of navigation is required? • They're supposed to be easy to handle one-on-one, but as their numbers increase, they gradually drive you into a corner; their movement should get that terror across. The most representative enemy characters that symbolize this title are the villagers called "Ganado" who appeared in the video mentioned earlier. 46 They are characterized by the fact that they still have the intelligence they had when they were human, and they hunt you down in groups. In order to express this characteristic in the navigation, it is not enough to move independently; we needed to focus on how they work together. ©CAPCOM 50

Ganado Pursuit As a test, for all Ganado, we set the player coordinates as the destination and all agents use the shortest path. This creates a Ganado traffic jam on narrow streets, making it easy to run away or beat them. But this is not good enough... P E E E First, let us consider the case where everyone is ordered to follow the player uniformly, without being aware of the other individuals. If Navigation is executed with no information other than the destination, all agents will search for the shortest path. 47 It is like a traffic jam on a highway. With some variation depending on the starting point, the Ganados will crowd into a single corridor. This makes for monotonous, unintelligent movement, which does not play its part in the horror story. ©CAPCOM 51

Ganado Pursuit How to determine destinations during group pursuit Set roles for each Ganado A) Attacker unit B) Flanker unit C) Ambush unit (Zone Defense) What did we do to relieve this traffic jam? In this title, we decided to give each Ganado a role to play during the group pursuit. Those are these three roles. I will explain them in order. ©CAPCOM 48 52

A) Attacker unit Pursue players on the best, shortest path Move toward a position that surrounds the player, not the player's position itself P P E E E E E E E When you focus on one point, you get push and shove, and we lose the impression of intelligence. E Putting pressure on them by surrounding with a group and block from retreating The first is a pursuit unit called "Attacker." They simply and clearly track the player along the best and shortest path. As in tag, the player must first deal with their pursuit. 49 When approaching the player, if we set the objective coordinates to the player’s position, then the Ganado will head straight for the target. This results in jostling between enemies, and their movement will be like animals with no higher intelligence. By setting the objective coordinates for each enemy to surround the player, the player can feel their will to "kill the target without fail." And if the attack is more spread out, it makes for a more rewarding challenge to defeat it. ©CAPCOM 53

B) Flanker unit Tracking a player using a different path than the pursuit unit • The shortest route is used by the attackers and should be avoided • We need to use the "not-so-shortest route" P • With the usual A* algorithm, only the shortest path can be searched for... What do we do? E E E Next is the "Flanker," a detouring unit. When a player is fighting back against or running away from the attackers, the "Flanker" is the one who makes the player 50 think, "Are they coming from that way?" In other words, this unit plays an important role in making the Ganado seem "collectively intelligent." The pursuit unit follows the player along the shortest path, so this unit requires "other" paths. As mentioned earlier, the navigation system is a mechanism for obtaining the "shortest" path. We need to think of a way to get the "not-so-short" path. ©CAPCOM 54

B) Flanker unit Waypoints placed along rough paths and NavMesh generated based on detailed terrain First, search by Waypoint to determine the paths that can be taken, then, detailed path between Waypoints is determined by NavMesh search • Allows us to get to the same destination from various routes To explain that story, the AIMap used by Ganado, i.e., its spatial information, needs to be explained. Two types of AIMap are used together in the stages of this title. 51 The first being the manually placed Waypoints with connection information between them, that we went into detail on earlier in the presentation. And the second being, the NavMesh that is automatically generated from the collision mesh. Imagine the former as points placed at each intersection of a road, and the latter as a mesh of polygons covering the entire road. When searching for a route, first determine the road to be taken roughly by waypoints. ©CAPCOM 55

B) Flanker unit Waypoints placed along rough paths and NavMesh generated based on detailed terrain First, search by Waypoint to determine the paths that can be taken, then, detailed path between Waypoints is determined by NavMesh search • Allows us to get to the same destination from various routes NavMesh is used to find the path in units of coordinates to move along between the manually placed Waypoint map. We will now explain how to use both to generate variations in the paths. ©CAPCOM 51 56

B) Flanker unit Pursue player using "non-shortest paths" P E E P Ignore any waypoints placed on the path taken by the player Since that makes it impossible to pursue directly behind the player, it selects a detour Back to the topic of "non-shortest paths." In order to search for a non-shortest path, we have to think of it in the opposite way. 52 In standard horror game gameplay structure, players will try to fight while keeping distance from the enemy. Therefore, the attacker type mentioned earlier often follows the player's path from behind. So, make it so the player marks the waypoints on the path that the player has taken, and set those waypoints to be treated as roadblocks by the Flanker units. By blocking the paths that are easiest to follow, detour routes will be explored for the same objective. In this way, the enemy will use various paths to get to the player, creating the flanking movement of going around them. ©CAPCOM 57

C) Ambush unit Move to a specified position and ambush • If all enemies pursue the player, the player can keep running away by kiting them • Create a sense of tension that "even if you run, there are more waiting" P E P E E E Finally, let's talk about the ambush unit called "Zone Defense." This one is simple: "Go to a specified position where the player isn't." 53 The "specified position" is set in advance to a location where the player is likely to flee to during the battle. The visual aspect of the game is also designed to induce the players to run for cover. The enemy will appear just as you think you're safe, creating a tense situation. ©CAPCOM 58

Switching units As the distance and position of the player and the enemy changes, the enemies periodically change roles • Assigns the following groups in order of proximity to the player: (A)ttacker < (F)lanker < (Z)one (D)efense P A ZD P A ZD F F These roles are updated periodically based on distance and location to the player. Since the player is always on the move, the role of the enemy changes as the situation changes. 54 In this way, the enemies seem to work together, and it gives the player a sense that they are being pursued by intelligent creatures. ©CAPCOM 59

Ally Character Movement (RE:4) That's the end of the description of enemy characters. Next, using RE:4 again, I would like to introduce an example of ally character movement. ©CAPCOM 55 60

Ally Character Movement Ashley (an ally you're supposed to protect) • Can recognize and avoid danger, but cannot attack • Can be targeted by the enemy and abducted What kind of navigation is required? • Should not unreasonably interfere with the player, but should have movement behavior such that the player has to pay proper attention This game includes a companion named Ashley. Ashley is not a "companion to fight with" but rather a "companion to protect." She accompanies the player character, Leon, who has to escort her. 56 She is unarmed and cannot engage in combat, but she is aware of and able to avoid danger. However, she has no experience in training for extreme conditions. If you are not careful, she can be taken out by the enemy in a matter of seconds. To express these characteristics in the navigation, we sought to provide a certain degree of safety while at the same time keeping the player on their toes. ©CAPCOM 61

Ally Character Movement Ashley can be given two commands • Tight (stay close) • When fleeing from enemies, etc. • Loose (keep your distance) • When waiting in a safe place during a battle, etc Ashley switches between two states at the player's direction. The first is "Tight," in which Ashley stays close to the player when fleeing from enemies, The other is "Loose," in which Ashley stays in a safe space when fighting an enemy. 57 Her movement behavior changes based on these two states. ©CAPCOM 62

Tight Tight - Follow the player closely • Select the most recent location from the list of possible destinations around the player and move along the shortest route • However, avoid the front so as not to interfere with player movement or attacks A P First, let's talk about "Tight." This one is simple: She heads straight for the player’s location as a destination. However, the area in front of the player may be an obstacle to movement or attack. The character should avoid that direction and aim for a position around the player. ©CAPCOM 58 63

Loose
Loose moves to the safest location possible and along the
safest route possible
• What is a "safe location?"
• Don't get too close to the player; you'll get caught in the crossfire
• Don't be too far from the player; help won't arrive in time
• Also, stay away from enemies; the risk of being abducted is great if you are
too close to them

• What is a "safe route?"
• Do not get closer to enemies: Move while avoiding enemies as much as
possible

• Needs to be finely tuned for safe positioning under constantly
changing conditions

E
E

P
A
E

Next, let's talk about "Loose."
Staying close to the player is simple, but keeping some distance opens up a myriad of options in terms of how much distance
and what
59
direction, so judgment is required.
The player is thinking "go to a safe position."
"A safe position" here means, "a position that is neither too close nor too far from the player, and at a distance from the enemy."
It is a low-risk position where Ashley doesn't interfere with the battle, but can expect help to arrive quickly if needed.
Even if such a position is determined, it is not safe if you have to go through the midst of enemies to get there.

©CAPCOM

64

Loose Loose moves to the safest location possible and along the safest route possible • What is a "safe location?" • Don't get too close to the player; you'll get caught in the crossfire • Don't be too far from the player; help won't arrive in time • Also, stay away from enemies; the risk of being abducted is great if you are too close to them • What is a "safe route?" • Do not get closer to enemies: Move while avoiding enemies as much as possible • Needs to be finely tuned for safe positioning under constantly changing conditions E E P A E You need a route that makes it seem as if Ashley is avoiding danger of her own volition. The positions of both players and enemies are constantly changing. Ashley must take their positions into account and 59 constantly make such decisions as she moves. ©CAPCOM 65

Loose Statically built AIMap makes fine movement adjustment difficult • The more nodes are needed to have detailed spatial information, the more processing load and memory... • Need to have dynamically changing information Ashley only moves within a short distance (around the player)* • Stage-wide information not required So... (* Except during specific scenes in some stages) To find a "safe position," detailed spatial information at the one-meter level is required. Creating this as a static AIMap for the entire stage would require a non-negligible level of processing load and memory 60usage. In addition, the situation is constantly changing depending on the player and enemies’ position, so dynamic information is required in addition to static terrain information. In considering how to solve this problem, we came to focus on the fact that Ashley's movement is limited to a very small area around the player. ©CAPCOM 66

Grid Location Information Exclusively for Ashley To dynamically generate grid-like spatial information around Ashley • Denser and finer points rather than automatically generated static NavMesh • Implement this on the title side and use it in combination with static NavMesh information Note: The game screen has been processed to improve visibility. The measure we took was to dynamically generate a grid of finely arranged points around Ashley. The points are placed densely, but in a limited area, reducing processing load and memory consumption. Dynamic generation eliminates the cost of manual placement. 61 This is implemented on the title side and used in combination with static NavMesh information placed on the stage. ©CAPCOM 67

Safe Positioning Step 1: Trimming branches of the grid • Overlay the grid on top of the NavMesh and remove points where the mesh does not exist or cannot be entered (i.e., unreachable points) Step 2: Select destination • Each point has a "safety level" calculated from the distance from the player and the distance from the enemy Step 3: Pathfinding • The cost of movement is set high around enemies, so pathfinding bypasses them • A* algorithm is used for search Based on this, Ashley's movement action follows this procedure. First, overlay the grid and the NavMesh in the area. Remove any points that are outside of the NavMesh and any points that overlap with inaccessible nodes. The grid is now placed along the shape of the NavMesh. 62 Next, we look for destinations to proceed to. For each point, we set a "safety level" calculated from the distance from the player and the distance from the enemy, and set the highest point as the destination. ©CAPCOM 68

Safe Positioning Step 1: Trimming branches of the grid • Overlay the grid on top of the NavMesh and remove points where the mesh does not exist or cannot be entered (i.e., unreachable points) Step 2: Select destination • Each point has a "safety level" calculated from the distance from the player and the distance from the enemy Step 3: Pathfinding • The cost of movement is set high around enemies, so pathfinding bypasses them • A* algorithm is used for search Finally, the path to the destination is searched. We use A* for the search algorithm. This algorithm lets you set a cost to each node and reduces the selection priority of high cost nodes. 62 By increasing the cost of points in the vicinity of enemies, we can find a path to the destination that keeps as much distance from the enemy as possible. ©CAPCOM 69

Safe Positioning Now, let's see it in action on video. As the player moves, the grid area follows accordingly. The grid is not generated in areas that are inaccessible. 63 There is an enemy. Let's pass in front of the enemy. The enemy has noticed us. Some debugging information is displayed on the screen. The safety score is quantified based on the distance from Ashley herself to the player. ©CAPCOM 70

Safe Positioning The candidate for movement is selected from here. As the player approaches, she searches for a new candidate location to gain distance. 63 The colored triangles shown above on the grid are attributes set as points to be avoided as much as possible. When the player aims the gun, the attribute information changes. The character is trying to leave the area immediately because it is dangerous to be in the line of fire. In this way, the player feels that their allies is making their own decisions and moving on their own accord. ©CAPCOM 71

Processing and Memory Load Reduction Measures (RE:4) That is the end of the description of ally characters. Next, we will discuss measures for reducing processing load and memory load. We'll use RE:4 as example here as well. ©CAPCOM 64 72

Main Factors of Processing Load and Memory Load The main factor that makes the process of path finding intensive is the number of nodes to be searched • If the destination is farther away, the number of nodes to be explored will inevitably increase • The more complex the terrain, the greater the density of nodes Memory usage increases as the number of nodes increases • We want to reduce the number of nodes as much as possible, even from the original AIMap data This premise is not limited to RE ENGINE's Navigation system. In general, the processing load of pathfinding is greatly affected by the number of nodes to be explored. The farther away the destination, the longer the route to be explored, and the more nodes that need to be explored. 65 Also, if the terrain is flat, such as inside man-made structures, AIMaps with a simple shape can be used. But for complex terrain such as natural terrain, the AIMap will be dense, and the number of nodes will increase even for a short route. Since the number of nodes also affects memory usage, it is important to reduce the number of nodes in the AIMap data itself, not just how many are used in each search. ©CAPCOM 73

Hierarchical AIMap to Suppress the Number of Search Nodes Separate granularity between AIMap for long-distance search and AIMap for short-distance search • Search for distant locations with relatively coarse-grained AIMap to obtain intermediate transit points • Search with fine-grained AIMap for travel between transit points (short distance) Actual examples in RE:4 • Waypoint for long distance and NavMesh for short distance • In addition to the purpose of selecting detour routes, it also has the effect of reducing the processing load In the earlier description of the enemy character we mentioned that two AIMaps, Waypoint and NavMesh, were used in a hierarchical manner. When searching over long distances, we use a coarse AIMap. The rough transit points are determined, and then a detailed search is performed for each point. 66 Not only does this method let us express route variations, it also has the effect of reducing the number of nodes searched. ©CAPCOM 74

Automatic Removal of Useless Nodes Due to the automatic generation of the NavMesh from the collision mesh, nodes may be unintentionally created where characters cannot enter Main Causes • Forgot to delete collision meshes • Assets with collision meshes get placed to create the distant view Detailed collision mesh shaping can reduce it, but it takes time... Is there any way we can batch remove them...? Also, as a factor that directly increases the number of nodes in AIMap, there was a problem with unused nodes being generated. At the time the system was implemented, it was assumed that collisions related to Navigation would be refined in advance 67 and then AIMaps would be generated. However, with the recent increase in the size of stages and changes in faster workflows, it has become more difficult to manually sculpt collision meshes. As a result, the development of this title required a method to automatically reduce nodes in post-processing. ©CAPCOM 75

Automatic Removal of Useless Nodes Implemented a function in RE ENGINE to detect isolated nodes and remove them all at once • A node is considered "isolated" if it cannot be reached by any path from the specified coordinates as a reference point • Isolated nodes are not reachable and should not be needed...so remove them • Specify at AIMap build time so that they are automatically removed In one stage in RE:4, this netted a node count reduction of about 50% The proposed method was to delete isolated nodes that cannot be entered from anywhere, as they are presumed unnecessary. The nodes have connection information, so unreachable nodes can be detected by walking them. 68 AIMap's generation flow now includes the ability to automatically delete nodes that are isolated from the starting point, spawn point, etc. When applied to this title, the reduction was as great as 50% in some stages. This functionality is now provided to other titles as a standard feature of RE ENGINE. ©CAPCOM 76

Development Support (RE:4 / EXOPRIMAL) Finally, here is a case study on development support. 69 ©CAPCOM 77

NavMesh Imaging (MapVisualizer) RE ENGINE function to visualize the area that can be entered based on the NavMesh • Although the mesh is also displayed on the editor, it is surprisingly time-consuming to view the terrain information alone, as there are a lot of other things drawn • Can show only the outline to ensure visibility First, we would like to introduce you to an imaging of the NavMesh called MapVisualizer. When you want to know the pathable areas of a scene, you can display the Navmesh data. But there is a lot of extra information and it takes a lot of time to see what you want. 70 Therefore, by directly converting the NavMesh data into an image of the pathable areas, it is possible to obtain simple outline information. ©CAPCOM 78

NavMesh Imaging (MapVisualizer) Major examples of use in RE:4 • Detection of unintentionally created nodes • Nodes may be created in unexpected places due to forgetting to erase collision meshes, etc. • Check updated parts levels • By periodically outputting the same range and resolution, the difference between images can be confirmed (see image) • Map UI creation assistance • Significantly less labor intensive than building from scratch by hand Difference comparison result (example) In RE:4, this feature produced the following results. First, the detection of unintended nodes. 71 We found that there were considerably more nodes left than expected, which led to the proposal for automatic node removal mentioned earlier. Next, checking updated portions levels. It's difficult to explain in words where a level has been updated, and it's not always easy to notice changes. An image comparison can show exactly where changes are. This is possible because the tool allows for fixed image output settings. Finally, this function assists in the creation of the in-game map UI. Map creation tended to be a process of eyeballing and copying scenes. Having accurate data has led to labor savings and improved accuracy. ©CAPCOM 79

Pathfinding History Telemetry Failure of pathfinding (not being able to reach the destination) can cause processing load, so we want to reduce it as much as possible • Explores various nodes until a reachable path is found P E Next, two examples of telemetry from "EXOPRIMAL" will be presented. The first is pathfinding history telemetry. 72 When searching for an unreachable destination, it tries to search every possible route. This is very expensive, so it is necessary to eliminate failures as much as possible. ©CAPCOM 80

Pathfinding History Telemetry EXOPRIMAL stores the entire history of pathfinding performed by characters • When, by whom, from where, and to where was the pathfinding performed? Heatmap history of failures • Detect and correct forgotten traffic attribute settings, forgotten ExtraLink installations, etc. In this game, the history of all pathfinding results executed by characters is saved and visualized as a heat map. Areas with many failures indicate that something is wrong with the AIMap, or that the destination may have been incorrectly set. 73 Therefore, it is easier to find the problem by focusing on these points. ©CAPCOM 81

Footprint History Telemetry The route obtained by pathfinding is not always correct Trying to go through a narrow passageway that the character can't fit in Stepping off the edge of the road and falling down Choosing an unfortunate detour Next is the telemetry of the travel route history, or footprint history. Even though the pathfinding itself was completed successfully, problems may occur when the character travels along the 74 returned route. For example, a pathway that is narrower than the character's collision mesh may have been selected, or cases where a character falls off the road en route. Or cases in which what seems like a shortcut is taken but it turns out to be a long detour. These cases can be avoided if the settings for AIMap generation are properly configured, but, it is possible for them to be mixed in without being noticed. ©CAPCOM 82

Footprint History Telemetry EXOPRIMAL saves a history of the coordinates of characters' movement • Lets us see when a character is stuck or following an unintended path, and investigate the issue • Widen paths that are too narrow • Add walls to keep characters from falling These issues can be noticed if they happen to be caught by the player's camera. But that isn't guaranteed, so this title saves and visualizes the history of travel paths. 75 By looking at the footprints, it is easy to notice problems such as a character not going to a place they are supposed to go, or stagnating in the same place for a long time, We have fixed these problems by widening narrow paths and putting up walls where characters cannot turn and fall. This telemetry information was accumulated daily by CI, and was instrumental in resolving navigation issues. ©CAPCOM 83

Summary Character movement is achieved by using a combination of RE ENGINE's standard Navigation functionality and each title's own systems, enabling movement behavior that fulfills various requirements By adding detour-taking and waiting behavior to the standard shortest-path-finding behavior, gameplay variety can be expanded for a richer experience Reduce processing and memory load, automating data reduction and reviewing the execution process, allows more advanced game expression to be realized with the resources available Automatic error detection to catch mistakes early helps to improve product quality Finally, to summarize. Character movement is achieved by combining RE ENGINE's standard Navigation functions and a title's systems to provide 76 movement behavior that meets the title's requirements. If used as is, navigation will only utilize the shortest path. However, with ingenuity, other actions can also be realized, enriching the range of gameplay. By paying attention to processing and memory load, and by reducing data size and reviewing runtime processing, resources can be better used for other essential parts of the game. As development scale increases. mistakes will naturally occur, but with automated systems we can detect them early and improve the quality of our products. This is the end of this presentation.We hope this has further sparked your interest in character navigation. ©CAPCOM 84