'Death Stranding': An AI Postmortem

[Music] hello my name is eric johnson i'm an ai programmer at kojima productions and today i want to share with you some of the ai features we built challenges we faced and things we learned during the development of death stranding this is primarily a navigation talk to that end i want to begin by discussing the game environment and why it was such a challenge for us to work with game design's goals for npcs and how they affected our approach to dealing with the environment how we reflected the complexity of the terrain on the nav mesh the impact this complexity had on navigation support for different types of dynamic terrain a quick look at a trick we used to improve position selection in our environments and a peek into a few of the other ai systems we built for the game first i want to give special thanks to gorilla for providing us with the decimal engine on which death training is built as well as the ongoing support they've given us throughout development i also want to thank the rest of the mpc

team at kojima productions whose work i'll be sharing with you today without them this talk would not be possible so as most of you are probably familiar death stranding is a game with a heavy focus on environmental traversal deciding your route what equipment to bring and how to approach the landscape overcoming environmental obstacles using a variety of tools at your disposal such as ropes ladders and bridges all in order to ultimately reach your destination but it's not just these large-scale obstacles you need to worry about even flat terrain is difficult to traverse you can lose your balance and stumble slip in the mud when it rains or lose your footing on steep slopes or get swept away by the current of rivers every step has the potential to be hazardous

so to create an environment where even walking would be a challenge in the early days of the company the team went location hunting in iceland to gather reference material while they were there they toured volcanic rock fields rivers valleys and gorges crevices caves and geysers which they referenced to create environments like these take a look

so these were the types of beautiful but unforgiving landscapes the environment team had created to challenge the player but if this terrain was meant to be difficult for the player to traverse this meant it was going to be even harder for the ai because while the central challenge is overcoming the environment it's not the player's only obstacle there are of course enemy encounters and the ones i want to talk about today are mules melee enemies that chase after the player and steal their cargo terrorists ranged attackers whose target is the player who can use cover and catchers giant bts who need to be able to navigate around climb on top of and even destroy dynamic terrain during the concept phase the core gameplay loop revolved around the cat and mouse game of mules searching for and stealing the player's cargo as the player attempted to make it through hostile territory to complete their delivery because they'd need to steal packages directly from the player as much as possible we would need to

provide traversal parity wherever the player could move mules would need to be able to follow similarly if cargo was dropped onto the terrain npcs would need to be able to reach it to pick it up wherever it lands finally a lot of effort was placed on making the player interact realistically with the terrain to feel grounded we wanted npcs to have a similar level of fidelity here's where we started this is our first ai prototype you can see here the mules are searching the area for cargo the player can subdue them with a non-lethal takedown and while still undetected they are able to escape and make their way towards the cargo destination a year later we had added more non-lethal weapons like the bola gun npcs could now respond to noise and perform investigation behaviors perception had been iterated on enabling the player to evade the enemy in tall

grass but npcs now have the ability to ping the cargo's player's cargo to track them down still the gameplay loop remain focused on evading and escaping rather than fighting and here's the final version that we shipped when the player enters mule territory their cargo is pinged a search party is formed and a group of enemies move to the ping location to try and find the cargo that was detected this gives the player an opportunity to escape while they're searching for the package if the player successfully evades the enemy long enough they will reping the area and the cat and mouse game begins again but if the player is spotted all mules in the encampment will immediately begin chasing the player to steal their cargo switching gameplay from evasion to escape this is the core loop the npc team was responsible for delivering and one of the major components in doing so was

developing reliable navigation over the terrain so why is this terrain such an issue and what kinds of problems does it create for the navmesh to explain let's start by looking at some nab mesh that represents what we were used to seeing in a typical production here is a man-made environment with flat level ground open spaces clearly defined walls and corridors there are challenges in navigation over an app mesh like this positioning finding cover flanking but these are ones that we were generally familiar with and knew how to handle likewise in natural environments navmesh was often just a continuous sheet with the occasional hole where rocks trees and other obstacles have been placed to decorate the terrain however because the environment in death training was designed first as an obstacle for the player our nav match now looked like this everywhere we looked there were jagged shapes with sharp turns

thin strips and nav mesh and tiny disconnected navmesh islands covering the landscape normally we would either make these areas off limits to the ai or work with level design to make them easier to traverse but in order to chase the player in the world of death stranding this time neither of those was an option to illustrate just how much more complex things had become for us seen from above the difference between the two looks like this both of these areas are the same scale and show a single navmish tile but for every navmesh polygon on the left there are a dozen on the right this was much more complex than anything we dealt with before but let's take a step back because you may have noticed even if the terrain in the complex example has collision like this at worst the navma should look something like this so what is this mess to explain let's take a look at some sample terrain uh here we have some grassy hills on the left rocky terrain

on the right and a river that cuts through the middle in the beginning this is what a nab mesh looked like for humanoid npcs it was configured so that they would stay out of the water and step around rocks too big to climb over however the player's movement controller could automatically detect and step over obstacles that are roughly knee-high so npcs needed to be able to as well if they were going to follow the player so we first raised the nap mesh step height covering most of the areas where these small rocks were then we added raycast checks in front of the npc to detect these small ledges and then play special step up and step down animations to get over them however if the player runs over those same rocks there is a chance they'll trip and lose their balance and we wanted npcs to do this as well to show that it's just as hard for them to traverse the terrain as it is for the player so we implemented ground material checks

that could trigger specific animations when stepping onto a rocky material we added a random chance for an npc to slip or stumble of course knowing this the player learns to avoid running over rocks to prevent tripping so npcs should have enough understanding of the terrain to do so as well but how are we going to add that the answer is something we call placement painting most of the rocks grass and other decoration on the terrain are added via decimal's procedural placement system for rock spawn in this way we painted the navmesh with a high cost area that surrounded each one this encourages the navigation system to produce paths that go around obstacles without removing the navmesh on top of them this means that npcs can can still walk through rocky areas but they'll only do so if there are no better options and the player is also able to wade through deep water so in order to give chase npcs need to be able to follow them into and through these areas too

so we ensure that there is nap mesh generated over the water as well this works but as you can see wading through water is very slow and it's easy for a player on land to get away from a mule in order in addition because it can drain stamina players learn that in general it's better to avoid moving through water when possible to handle this we applied the same strategy as placement painting we paint a high cost area onto the nav mesh wherever water is present allowing navigation through it but discouraging npcs from entering unless it's the fastest way to the destination and we actually shrink this a little bit only painting areas with at least 30 centimeters of water as this is the threshold for the waiting animation as a result npcs would now skirt right along the edges of the shore taking as optimal a route as possible when going around bodies of water and that is how we got from this rough

but still reasonable navmesh on the left to this multi-colored missile right but in doing so we created a huge amount of new problems for ourselves the first being the cost of pathfinding itself due to the size of the environment the search area can be very large so to manage performance we cap a star search to 500 iterations often this is not an issue take for example the scene from the time fall far if we take a look at a nav mesh we can see some fences and small structures over basically flat terrain nothing too complicated we then try to find a path from the left side to the right the result looks something like this the green polygons are a path corridor and the nodes explored during a-star are shaded from yellow to red depending on when they were opened in this example we were able to successfully generate a complete path over a distance of about 200 meters without any issue however if we move to another area with more complex terrain like the cliffs by this

mule cam we can see that the nav mesh is much more fragmented and if we then try to perform the same path binding request navigating from the left to the right we're only able to generate a partial path and don't even make it 25 meters before hitting our 500 node iteration cap compared to the time fall farm which produced a 200 meter path without hitting this limit so depending on the location the farthest range at which we could reliably produce a complete path would change dramatically on top of this the now mesh and death stranding is generated at run time using nav mesh bubbles placed on npcs and the player this means that it's common for navmesh to not even exist that the destination would begin moving so because navmesh polygons are much smaller it is now much more expensive to run pathfinding as more nodes need to be explored than when we started as well there's no guarantee that we'll get a complete path to a reachable destination either even for very short distances

so at some point while following one of these incomplete paths we knew we'd need to repath to continue making progress but how could we determine when this is well to start how do we normally decide when to repath when we're following a complete path and we want to detect when something has gone wrong common methods include ray casting ahead to a point further along the path if we hit anything it means we've deviated too far from our path or detected a change in the nav mesh or we can automatically repath at regular intervals avoiding the issue by ensuring that a path is only ever going to be invalid for a limited time however both of these techniques have their own issues raycasting only detects problems immediately in front of us even if we can see a change in the environment further away we won't respond to it until we get close for time free pathing it isn't clear how frequent is frequent enough too slow when we run into things too fast and we waste performance performing pathfinding when nothing is wrong on top of that it introduces another

problem so it turns out that in early development this was actually the method we were using rebounding twice a second and simply heading towards the next waypoint in the past around this time we received reports that npcs were occasionally looking around when patrolling which was strange because we hadn't actually added any behavior to do that and we thought it might be an aim or look at bug but on closer investigation we discovered that at specific points along the patrol route the path could change completely for just a moment and then revert back now you can see that here when the mule reaches the yellow arrow this would actually be expected uh when pathfinding depending on your starting location in a navmesh polygon there may be completely different optimal routes to the target and then by chance we were repathing after crossing one of these thresholds which resulted in the npc turning momentarily towards the new path and then back again on the next free path

it was clear we needed a better system because our search range was limited we knew we might need to perform multiple path binding requests to reach targets even ones as close as 25 meters away and we also wanted to repath automatically as soon as an issue was detected but no sooner both to improve performance and to avoid the instability we were experiencing so we first identified five conditions that could require a repath in order to reach our destination to illustrate them here we have an agent on the left following a path to a target on the right and the white squares represent the navmesh polygons of the path corridor the first situation is if the agent moves outside of the path corridor entirely this could happen if the npc misses a turn or is pushed out by an external force similarly we could also require a path if the destination moves outside its polygon at the end of the path or if a polygon in the coordinator becomes invalid that indicates that the

nav mesh at that location is changed this can happen if an obstacle is added or removed or if that mesh no longer exists there a tricky one is that in the event that nav mesh tiles have not been generated at our destination to serve as a temporary stand-in we clamp the destination to the boundary of the closest navmish tile in the direction of the agent and navigate to that point instead then if this clamp location moves that indicates that nav mesh tiles between the agent and the target have either been added or removed or that the destination itself is moved if this occurs a better path may now be available now finally if none of the above situations occur and we successfully navigate to the end of the path but the path itself is incomplete due to hitting the a-star iteration cap we can try re-padding again on arrival to see if we can make any further progress from a new location in order to support this we needed to

move away from simple waypoint following and monitor both the path and the path cobra tomorrow so we added a validator that would run every frame during navigation checking all repath conditions that we had identified if any condition failed it would automatically trigger a repath request then this new path would replace the current one and navigation will continue uninterrupted here's our event based pre-padding system in action so long as no validation errors occur we continue following our initial path avoiding any unnecessary path binding calls however if a qualifying event occurs such as a change in the nav mesh uh recorder passes through validation will trigger a repath which replaces the original wall we are moving you can see that this happens both when an obstacle appears in our path and when it's removed and here's an example of the validation check for tile clamped locations as the npc moves new tiles are generated

around its navmesh bubble when this happens it causes the clamp destination to move triggering a repath that lets the agent make incremental progress toward the destination now agents were navigating but they weren't navigating well uh we started getting reports that npcs on patrol were taking weird detours even when they should have had a clear path to their destination when we investigated we saw the path in the port or the npcs were following look like this but why would this happen why would a-style return this is the core this is what we were expecting if there is nothing between us and the destination we should be getting a simple two-point path passing straight through the car however this is what we were actually getting the problem is that the path corridor is generated by searching between the midpoints of nav mesh polygon edges which is only an approximation of the shortest path to the destination

when we then string pull a path through this corridor kinks will appear wherever there's a large difference between the approximation and the optimal paths i should add that you don't need a tiled map mesh for this to happen either in this example if i search for a path from the blue point on the left to the red target on the right because the edge midpoints used during pathfinding look like this and it's the shortest path that passes path that passes through these midpoints that determines the pat corridor a situation like this results in a path like this but by chance while we were working on how to deal with this i was rereading the author of recast mikkomanon's old blog post about its development here he is describing the funnel algorithm in a post from over 10 years ago on march 8 2010 in the comments section someone posted that they were having the exact same issue kinks in what should have been a

straight path over a tiled lab mesh mikko's recommendation was to use nav mesh raycast to find waypoints in the path that could be skipped then replace the section of the path corridor between those two points with the corridor returned by the nav pass or by the mesh radius so this is exactly what we did starting at the first wave point in the path we skip over the second waypoint and perform anatomist raycast to each remaining point in the path and remember the last successful result we continue until we reach the end or the raycast hits something once either happens we stop remove the portion of the path corridor from the start to the last successful result and replace it with the corridor returned by the raycast now this part of the corridor has been straightened and we repeat the process from the next uncorrected node in this case the original corridor is already optimal so we keep it and return the merged result

in the version in the version we shipped we actually perform this straightening operation a second time from the end of the path to the start which is usually enough to find all potential shortcuts in most situations in addition even if the raycast is successful it may pass through a high cost area of navage so we only replace the corridor section if the straightened version has a lower traversal cost now our corridor has been straightened but there's still one more step we need to perform string pulling again through the straightened corridor to generate the final path like this and here's the final result uh path quality had been greatly improved and npcs were now navigating directly to their destination at this point things were looking good npcs could handle different types of terrain repath on their own and navigation looked natural until they started to run

because we had stopped repathing on timed intervals npcs could deviate significantly from the original path as long as they stayed in their path corridor and because we simply steered directly towards the next waypoint on the path it was possible for them to get into a situation where that waypoint was no longer reachable here you can see that after an npc passes the first two waypoints it attempts to move directly towards the player but falls out of the path chord or triggering a re-path because of its large turn radius while running it then misses those waypoints exits the corridor again causing another re-path creating a situation where it's never able to reach its goal it turns out that this problem had also been solved over 10 years ago and the solution was in the exact same blog entry we referenced to straighten path corridors at the end of mikko's post about the funnel algorithm he noted that it's so fast you could perform string pulling over the path corridor every frame to find the next chord or this corner to steer towards

which is also exactly what we did now when the npc makes its wide turn a new corner appears in the path it turns towards that instead of the player and is able to reach its destination on the first try note that we aren't repathing when this happens we're only re-running string pulling over the original corridor well this was looking good in the test environment but around this time we also started getting bug reports that npcs were randomly making 360 degree turns while walking here you can see an npc approaching the player but when the agent gets close to the pink high cost area it turns around moment momentarily before moving forward again what was happening is that when an npc deviated from its path and stepped into a high cost nav mesh area leaving the corridor would immediately trigger every path but the new path would almost always prefer to back out of the high cost area we just entered instead of going through it which caused agents to turn around in order to get back to low cost terrain

we did want enemies to avoid high cost areas but if they entered one by accident it would usually only be for a moment so they might as well keep going so to discourage agents from entering high cost areas but commit to walking through one if they stepped into one we extended namash areas to support not only traversal costs but an entry cost as well a path would receive a one-time cost penalty for moving into a navmesh area but this could be adjusted independently from the cost of moving through it for rocks we reduced the traversal cost to the default and added a large one-time entry cost instead this meant that once inside rocky areas would be treated like ordinary navmesh but while outside npcs would still prefer to avoid them staying on flat terrain as much as possible and here's the result you can see that the npc's path tries to avoid passing through high cost areas but if if it misses its turn and steps into one it commits to traversing through it and

continues moving forward once it gets back to low-cost terrain it continues to avoid entering other high-cost areas but no longer backtracks if it injures them so after all this work we finally had natural reliable navigation over all types of terrain and with pass that would update automatically and only when needed almost even after adding entry costs we're still getting reports of npcs backtracking and turning in circles it turns out that there was still one more issue we had to solve using the event-based repatting system when an agent's nav mesh bubble moves and generates or destroys navish tiles the destination's tile clamp position moves as well triggering a re-path but depending on the terrain this can trap us in an area where the partial path to the clamp destination oscillates between opposite directions causing the agent to pace back and forth forever initially we just expanded the bubble

size to fix the specific case shown here in the video but that solution wouldn't work everywhere consider the following scenario now this mule has spotted the player in its territory at the bottom of a deep chasm and wants to move into attack range the crevice is far too deep for it to jump down so in order to pursue the player it has to find another way or not looking at the area from above we can see that there is an opening in the crevice near the top we can enter so we might expect the mule to tick around like this moving up to the crevice entrance and then back down again to approach the player one problem the size of the landscape features here are too large to pathfind around even if we extend the radius of an agent's navmesh bubble up to 100 meters we still hit our a-star iteration cap without even discovering the entrance in this situation the closest position to the player that we can find is our current location at the top of the cliff in early testing it was trivially easy

for players to escape mules in these areas worse if the mule did manage to make its way into the crevice it was almost never able to make its way back out again the size of the namish polygons inside the crevice are much smaller so our search radius would shrink to just a few dozen meters which meant that there was also no way that it was going to make its way back to base after an encounter had ended so we needed a way to navigate around these large scale terrain features and it was clear that the navmesh alone wouldn't be sufficient our solution was to take advantage of another feature in decimal the ai road network initially this existed as a self-contained graph with its own pathfinding functionality we extended it so that the npc's path following component could use it as a general-purpose high-level navigation layer merging the results of road paths and navmesh passing to a hybrid navigation system once ai roads had been placed by game

design npcs could seamlessly get on and off the road network to reach their destination if they were unable to find the complete path using only the nav image here's what our navigation behavior originally looked like the npc at the bottom is trying to reach the player at the top but as it approaches the cliff in the middle it's unable to find a way around it and get stuck even with this with a 500 node iteration cap the terrain features here are just too big for it to navigate around however with the hybrid path following component as the npc approaches it discovers a high level path on the road network and because it was only following a partial navmish path it switches to use the road network to ensure it reaches its destination the npc now uses the nav mesh to follow the road path and navigating towards an intermediate position a few meters further along the road we will then continue to follow this moving target until it exits the road network after which point it will revert back to navigating using only the nav machine

and now finally movement behavior was not only stable across all types of terrain but agents could also navigate reliably across the entire map even for complex routes spanning several kilometers but up to this point all the work that we had been doing was only to support navigation over static environments we also had several types of dynamic terrain to deal with each with its own challenges for example when a catcher encounter begins we spawn in a number of strand objects buildings vehicles chunks of concrete that rise up from the tar the catcher needed to be able to not only navigate around these objects but jump up on top of them as well in order to chase the player you can see here that as soon as strand objects begin to appear we generate nav mesh over their location along with jump links connecting them to the ground below the catcher is then able to use these links to jump up onto the buildings and once it does the building will begin to sink back into the tar when this happens that strand object's nav mesh is removed

this allows the ketchup to follow the player anywhere across the encounter area as it changes and here's how we did it each strand object actually has two sets of collision one for the object itself and another that only responds to the nav mesh because strand objects are in constant motion using their actual collision to regenerate the navmesh wasn't a feasible option instead on spawn the navmesh collision is activated at the object's final position and then off mesh links are added around its perimeter to connect it to the ground when a strand strand object is scheduled to sink and despawn the navmesh collision and surrounding links are removed and the area reverts to its original shape outside of catcher encounters most dynamic terrain in the game takes the form of navmesh obstacles attached to props like these retractable barriers at the entrance to distribution centers or destructible physics objects like barrels and fences as well as vehicles when they're pumped

or on player built structures like this timefall shelter but they aren't used simply to prevent movement uh to chase the player effectively we wanted npcs to take advantage of the player's own traversal structures during navigation for example by attaching navmesh obstacles to bridges we were able to allow npcs to use them too here you can see the player constructing a bridge once it begins printing the navmesh responds to the change in collision and automatically generates navmesh across its span then once printing is finished npcs are able to use it just like the player once this was working a game design came to us with a question if they can use bridges can we also let them use ladders

and at first we weren't sure in most games ladders are statically placed perfectly vertical every variable is controlled even then supporting them is a significant amount of work but in our case the player can place them anywhere and at any angle ladders placed at more than 45 degrees like this one need to be climbed with both hands but ladders placed at less than 45 degrees would be walked across like bridges but because these provide avenues of escape for the player it was important for npcs to be able to traverse them as well if they couldn't use them it would be trivial for the player to move somewhere that they couldn't follow so we accepted the challenge and started by enumerating all possible ways an npc could get on and off a ladder for vertical ladders there were four ways to get on grabbing on from the top or bottom or from the sides at two different angles there are five ways to get off depending on whether we dismounted by stepping off

at the end of a ladder or by jumping similarly for horizontal ladders there are two ways to step on from the ends or the sides and four ways to step off or jump off depending on how close we were to the ground the next step was to identify where an npc could get on to determine entry points for the ladder we started by defining sampling points at 50 centimeter intervals and then at each sample point checked for navmesh at all possible boarding spots all the locations here in white represent the possible position where we could get on the ladder from the nav mesh the next step would be to find all possible exits and connect pairs of entrances and exits with off-mesh links but testing all possible pairs isn't practical this would generate hundreds of links most of which would be redundant so to reduce the number of tests and connections we form groups from runs of matching navmesh entrances

then from left to right we perform a collision a collision check for validation from the entrance to the ladder but only for the last entrance in a group because ladder traversal is slow this minimizes the time we spend on it by ensuring we get on at the last possible moment then we do the same for the first entrance of subsequent groups for step off connections this ensures that we get off the ladder as soon as possible also i should mention that to walk off a ladder from the center without turning we had a hidden dismount exit during this step for groups without entrances we can only jump off here we perform both a collision check off the ladder down to the ground as well as test for navmesh at the bottom jump off points that either don't have an amish below them or fail the collision test are discarded leaving the final set of exit points for the first entrance group we then add an off-match link connecting

each entrance to exit pair in this set and continue the process for subsequent entrance groups finally we perform the entire operation again in the opposite direction at runtime the process of analyzing the terrain and adding off mesh links happens in a time slice job that checks one pair per tick and looks like this and here's what it looks like in game here we have an npc commanded to approach the player's position if we place a ladder the moment it hits the ground a terrain analysis job is kicked off and link generation is already complete by the time the player grabs onto it after we jump off we can see the npc is already approaching the ladder entrance in order to follow us to the top of the shelter because terrain analysis failed to find

any valid step-off positions on top of the shelter the npc dismounts by jumping and continues to our location if we then place a horizontal ladder the process repeats connecting damage at the top of the shelter to the far side of the ladder and the ground below likewise as soon as we jump off the mpc continues to approach us using our own ladder to jump down from above spatial queries and position picking also played a large part in navigation and behavior development and there's a lot on this topic that i'd love to talk about but today i want to focus on one specific problem we faced and the trick we came to handle it let's imagine we are the blue mpc on the left and we want to find an attack position near the yellow player on the right in between us is a high cost nav mesh area representing a large body of deep water we want to get close let's stay out of the water as it's

going to slow us down if we generate a grid of sample points over the terrain we can give positions inside high cost areas a low score to avoid entering them and if we then rank the rest based on distance to the target we'll get something near the player and outside the water great and because it is a high cost nab mesh area the path to our attack position will go around the water as well this type of query actually worked well for us in early development but if the player was not near a lake but a river we would encounter a problem we could test for positions in high cost navish areas and give them a low score but at the end of our position peaking query our target position could be on the far side of the river and the npc would spend ages waiting across just to stand on the other side when some place on the near side would have been just as effective but because both sides looked equally attractive from our spatial queries perspective and combat npcs would cross and re-cross the same river over and over as they

repositioned around the player what we needed was not just a way to avoid choosing positions in high cost areas but also positions that npcs would have to pass through high cost areas to get to so we came up with an idea our spatial query system could already use a dijkstra search over the nav mesh from the agent's position to calculate a rough approximation of path cost letting us rank points based on their estimated navigation cost here you can see that areas on our side of the river have a low path cost shown in blue while areas that enter or pass through the river on the right have a high cost shown in red this was close to what we wanted but places that were simply far away like the area on the far left would also have a high path cost even though they didn't pass through a river or other high cost area we wanted a test that would rank positions based on how much unfavorable terrain they would have to pass through to get there regardless of distance

but the same test could also return the raw path length to areas around it if we subtracted this length from the cost places where the path length and cost differed would indicate areas that would require the mpc to pass through a high cost area at some point conversely places where the length and cost were the same represented areas that could be reached without walking through difficult terrain this is what we were after so we added a third setting to our pathfinding test in the spatial query system the delta path a delta cost the delta between path cost and pass length however there was one issue while this worked as we had imagined when the npc was outside of a high cost area avoiding both entering and passing through the river if an mpc was already in the river it would stop moving entirely the reason is because from inside a high cost area moving anywhere would force us to pass through more unfail unfavorable terrain

than just standing still we would need a different heuristic if we wanted to discourage agents from staying in high cost areas and instead move back into easily traversable terrain the trick we came up with was to manipulate the reported path length and cost so that the total distance to all locations looked the same what this means is that we would first find the highest path length among all sample locations in the query and then for the rest of the locations virtually extend the length at the end of their path to match we then adjust the path cost to match this added length at the destination another way of putting it is that the test now compared how much time an agent was spending in high cost areas even if it wasn't moving if it could reach our location quickly it would stay there and accumulate the traversal cost at that location until it had traveled a virtual distance equal to that of the longest path in the query now we have the heuristic we were after

our special query could identify all locations that required us to pass through a high cost area to reach and if we were already inside of one we would know which locations could get us out the fastest and here's the final result here we have an npc moving from right to left across the river initially both points in the river and on the other side of it have a high path cost delta and receive a low score once we enter the river still has the lowest ranking but the far side is now a bit higher and gradually increases as we get closer finally once we leave with the water the river and the area beyond it both received low scores again as before this is actually a really simple technique and very easy to implement but we hadn't encountered it before and the added spatial awareness this test gave to npcs made a real difference in the quality of behaviors we were able to achieve so hopefully some of you will find it useful as well

lastly i want to talk briefly about a few other features we've spent time on and what they allowed us to accomplish first among them is the approach we use to support cover and terrorist camps we built our solution on top of decimal's dynamic cover system which provided a way for npcs to generate cover on demand when a cover point was requested a frame budgeted job would analyze a subset of nearby nav mesh edges performing collision tests on any edge long enough for an npc to hide behind creating crouching or standing cover points wherever an npc was both protected by cover and could peek out to shoot once generated npcs could use the spatial query system to test for line of fire from these cover points to a target which would check as many points as it could fit into its frame budget and return a list of all valid cover locations finally these results were cached so over time the entire area would incrementally become populated with cover points and their status would be revalidated during the encounter as npcs

continued to make additional cover requests this was great for performance but because the encounter area in terrorist camps was so large it could take several minutes before enough cover points had been generated for an npc to find a usable one consistently even after the arios was populated since only a small number of cover points are ever in the right position to actually provide cover from the target at a given time testing only a handful of them on demand usually resulted in failure as a result terrorists weren't able to take advantage of the system as well as they should have and sometimes they never use cover at all what we needed was a way to prepare and analyze cover in advance before it was requested so it would be ready to go when an npc eventually did need it we could have accomplished this by just placing static cover by hand instead but we didn't want to lose the ability to respond to changes in the nav mesh so our approach was to transition cover generation and analysis from an on-demand service to a persistent

background job when combat begins agents register themselves with the cover manager and specify a target and as long as at least one agent is registered the cover manager will incrementally analyze the that mesh around them in its own thread as well as check the line of fire from generated cover points to the target here you can see the status of cover generation as nav mesh tiles are analyzed red tiles have generated partial cover results while blue tiles have finished analysis and those that contain at least one cover point are highlighted in light blue later when an agent finally does request a cover point we simply return these cache results to the cover manager that is that it's been preparing for us here's another example of you from ground level you can see that as terrorists approach the player cover is gradually generated generated around them and once a valid cover point becomes available an npc moves into it immediately

and this is what the line of fire check looks like from the debug view the cover points around each registered npc are batched together and the resulting set is sent to a background job to check for both exposure and line of fire to the target as soon as one job finishes a new one is started here an agent has moved into a green cover point which has both cover and line of fire to the player and if we crouch on the other side of the barrier it turns red as it loses line of fire and the npc immediately responds by repositioning and this is what we were after by keeping the cover state updated asynchronously in the background finally we were able to produce consistent cover behavior over large encounter areas like these another feature we added was ai for low lod entities most npcs are actually persistent when the player is far away they don't despawn but instead switch to a low lod mode without a physical representation until the player comes back when this happens they also switch to a simple lightweight version of their ai so that they can continue to perform the same activities activities that they do

in high lod this includes enemies making patrols around camps inspecting vehicles stopping for breaks reporters following delivery routes dropping off packages picking up new orders and so on and while we do completely suspend some npcs when they're extremely far away in general the whole world is alive and in motion even when it's out of view and adding this mode also allowed us to do one other neat thing when the player triggers an event that causes time to pass we could now fast forward the ai by the same amount by temporarily switching them to low lod and running their update tick with a large delta time so when the player passes time in the time fall shelter 10 minutes will pass not only for them but for npcs as well this is what lets us do things like advanced porters along the delivery routes like you can see here finally it wouldn't be a postmortem if i didn't talk about some things we tried

that didn't work uh first is bidirectional pathfinding at the 2018 ai summit nathan's third prevent presented a great talk on bi-directional search uh our environment met all the criteria it should be suited for a weighted terrain problem asymmetry map asymmetry and local minim and it just so happened that this was right around the time that we were struggling with regularly hitting our a-star iteration limit so we were very curious to see how bi-directional search might perform and after a bit of work we actually did manage to get to port nbs to recast and had it running inside the game and it was performing great uh early tests showed promise in areas that in the game that were difficult for forward starts to handle unfortunately we ran into two issues after adding one-way jump links the nav mesh was no longer an undirected graph a jump down link had no connection in the opposite direction for the reverse search to explore breaking

search symmetry likewise after adding nav mesh area entry costs the reverse search would incur the entry costs as well creating a situation where we'd pay the cost both on entry and exit to be clear both these are solvable problems with some modifications to how off-mesh links and entry costs are handled nbs can absolutely be made to work in this environment but in our case even though the results were promising we had to put it aside and were unable to return to it later we also tried a number of methods to improve path smoothing if an agent was running simply heading directly towards the next waypoint often resulted in them missing following turn which made it difficult for them to reliably hit the start of jump links or the entrance to a ladder the method we ended up shipping with in the end was actually just a bezier spline that the agent could follow constructed so that the curb would already be turning in the direction of

the next segment before hitting the waypoint additionally to avoid triggering a re-path each apex was constrained so that the smooth path would never leave the core door to a degree this actually worked agents will depending on the situation make wide turns and do hit more waypoints but the checks we used to constrain the spline to the corridor were overly strict and even path corridors and flat terrain could be very narrow which means that often the spline shape is not significantly different than the original straight path so there's still a lot of work we'd like to do in this area to improve path quality further finally while we were able to generate jump links for ladders and strand objects procedurally every other jump link in the game was placed by hand by game designers which became a painstaking process because links would break and need to be adjusted repeatedly as changes were made both to animation

and the environment during development now we wanted to develop a procedural placement system for these links as well but weren't able to fit it in the development schedule so we had to use brute force to make sure that every encounter area every ledge rooftop and navmesh island that the player could access was connected by jump links so that npcs could follow in the end we had about 2 000 of these links placed across all areas which was more than enough that by the end we regretted not being able to automate this task so to wrap everything up in this post-mortem we took a look at the environment of death training and why it was such a challenge to work with for ai i discussed game design's goals for npcs and how that drove our need for robust animation how we went about creating a nav mesh so we could use to satisfy those goals and the problems this created for navigation techniques techniques we use to support dynamic obstacles that npcs could use to follow the player one trick that served us well for

believable repositioning over natural terrain and a brief overview of a few other features we developed for the game including some that didn't work out so i hope you've enjoyed taking this look at some of the challenges our team faced over the course of developing the ai for death stranding thanks for attending [Music] you