Death Stranding's Biggest Design Challenge

Getting AI Characters to Walk Across an Open World

AI and Games is a YouTube series made possible thanks to crowdfunding on Patreon. Support the show to have your name in video credits, vote for future episode topics, watch content in early access and receive exclusive patron-only videos and merchandise.

---

Death Stranding is, on the face of it, a game about walking. As Sam Porter Bridges, players work their way across the post-apocalyptic United States, delivering packages to way stations and reestablishing connections between them, all in an effort to pull humanity from the brink of total collapse. What makes Death Stranding stand out is that the primary focus of the game is simply trying to navigate the terrain. The beautiful but often brutal landscapes introduce a myriad of navigation challenges, as players need to decide on the safest route to traverse, whether to use items such as ropes or ladders for crossing the most perilous of hazards, and whether it's worth risking taking a vehicle on a particular route, all the while trying maintain your balance such that you don't fall and damage the precious cargo in your care.

But it's not just the hazardous terrain that can prevent you from a successful delivery. There are enemy factions awaiting you as you attempt to make your journey, to hunt you down and steal that which is not theirs. Not to mention the ethereal and supernatural BTs that haunt the landscape. But just like the player, all of these AI-controlled characters must know how to navigate the world in a way that is realistic. While ensuring their decisions reflect the very same challenges the player does.

So let's take a look at some of the gameplay systems required to enable the enemy factions of Death Stranding to do something you might have thought is painfully simple: walking through a videogame world.

AI for Navigation

As detailed in my AI 101 episode on the subject, in video games, we typically use a data structure known as a navigation mesh in order to allow characters to move around the world. A navigation mesh is computed by looking at all of the geometry in the game world, such as the ground, nearby objects that sit atop it and everything connected to it. This results in a mesh that represents the area within which a non-player character can then move around based on the game's internal understanding of the character's size. From there, a pathfinding algorithm can compute the valid path that a character can take to get from one point on the navmesh surface to another.

Navigation meshes are relatively easy to compute, they look for boundaries and edges on the surface that could justify the navigable area breaking apart into individual quads. It's a standard in game development you can expect to find in any modern game engine. But, just because you can compute it, doesn't guarantee that you get a useful and working mesh, nor any useful pathfinding. The process requires us to identify individual areas that are separate from one another. So one large area could be cut up into multiple quads within a single navmesh. This can include distinct rooms, stairways, ramps and more. Plus, it requires us to understand what areas are blocked off, which are less desirable and ultimately areas we'd prefer to traverse versus others. And quite often this means the navigation mesh parameters need to be carefully balanced so that smaller obstacles can be stepped over, while larger obstacles must be walked around. Adapting to different terrain types is something a human can do quite readily. You can simply look at the terrain in the game as you go, and make decisions on how to navigate it. But it's not as straightforward as that for an AI character.

You'll notice in most video games, even when you're caught in the likes of post-apocalyptic landscapes, the area in which you walk around is often quite flat and straightforward. Somehow all these open warzones and demolished buildings are conveniently still quite easy to walk around in. This is because it's easier for both the player character and the enemy AI to walk across it smoothly. But also it's because the more complex the floorspace is, the more broken, incomplete and fractured a navigation mesh will become. So making the ground open, clear and free of clutter is quite often the easiest approach to solving this problem.

Death Stranding Navigation

Now you might be wondering what all the fuss is about. What makes Death Stranding's AI merit this discussion? I mean, it's a game about walking, Sam goes for a walk and so do the enemies too. Just use a navmesh. The trick with Death Stranding is that Kojima Productions sought to ensure the AI has to face the same navigational challenges as the player. And it's this aspect of the game's design that adds a lot of complexity to both the navigation meshes, and the pathfinding algorithms, in a way that we seldom see in other games.

Early efforts by Kojima Productions to build their navigation meshes in the rocky and more natural terrain of Death Stranding were largely fruitless, given the rocks, cliff faces and slopes would be considered unnavigable - because in most games, they wouldn't be. Meaning that an AI character would simply be standing still and have no idea what to do because it would be impossible to compute a path on the navmesh more than a few feet in any direction.

But this is just the first of a number of issues brought on by the game. There are rivers and other surfaces that slow the player down and eat up your stamina. This is important given a character should only attempt to cross a river at particular points given the added complexities it introduces. But quite often the most efficient path to your destination might mean running through a lot of these less desirable areas. So there's a need to ensure the game can calculate optimal paths that - in practice - don't look stupid or require unlimited stamina to navigate.

The third issue is the volatility of navmeshes. A navigation mesh is computed one time based on what is in the world at that moment. However, anytime the world space changes in such a way that it will change where a character can walk, such as an object falling onto the ground, or a vehicle driving through the space, it will be forced to recalculate. Now a key mechanic of Death Stranding, is that the player can leave ladders or ropes to help themselves and other players navigate the environment. So whenever one of those is dropped down, it needs to re-evaluate.

Plus there is the even more extreme example brought about by the BTs. Players will enter environments during 'timefall' (or when it's raining) known as Beached Things, these make it harder to navigate the game world given they are effectively hunting you and rely on sound to spot you. But, in the event they spot you, it can trigger a mini-boss battle with a Catcher, in which the area is flooded with tar and fundamentally changes the navigable space. In some cases, this can be quite extreme, with Dolphin Catchers swimming around in the tar, while the Lion Catcher jumps around after you in the hunt. But in either case, it can also lead to entire buildings and other structures emerging from the tar and they need to know how to move atop or around them. Hence the navmesh needs to adapt to this.

Now as I said, calculating a navmesh is relatively straightforward, but it's often a calculation that is done offline during development. You can rebuild it at runtime if you want, but that leads to the fourth and final issue which is cost.

The denser the environment is, the more time it will take to calculate the navmesh. But also, it's worth asking just how much of the game world needs to be calculated at any given time. If the action is only occurring within a short range of the player, then you generate the navigation mesh in a fixed range, even if that fixed range is within a radius of the player. But also, you need to know just how much of the navmesh needs to be loaded in memory at any given time. Death Stranding's map is absolutely massive in scale, with hundreds of square miles of the game world that need to be calculated. Typically, a game will only store the nav mesh it needs in the area the player is in, but many of the Mules and Demens will detect and chase Sam down across great distances if their sensors detect him. Meaning you need to have all of that navmesh data loaded for every character to move around, and recalculate it when needed, all while ensuring it doesn't create any CPU or memory overhead that will cause the game to break or lag.

So now that we've explained the challenges faced by the development team, let's see how all of this is addressed in Death Stranding.

Achieving Traversal Parity

As detailed by Eric Johnson in the 2021 GDC post-mortem of Death Stranding, to keep in line with the game's primary design goals, the enemy characters could not rely on a simpler navigation mesh or cheat their way around all the issues raised. Enemies were designed to have what was referred to as 'traversal parity' with the player, meaning wherever the player can go, the enemy must always be able to follow. Most interactions with enemy AI are built around a simple game of cat and mouse. If the player enters a region of the world where Mules are active, they will ping the environment and can detect the cargo you're carrying. Once pinged, they enter a hunting behaviour as they seek to find you and in theory, they should be able to hunt you down and attack you wherever you are in the world. So in order to make that work, they had to take tried and tested tools and techniques for AI navigation and revise them to better fit the game they were trying to create.

Death Stranding is built in the Decima engine, a tool developed by Guerilla Games originally for Killzone: Shadow Fall, but has since been used in the likes of Horizon Zero Dawn and its sequel Forbidden West. But with the exception of Supermassive Games' Until Dawn, it wasn't used outside of the studio itself. In fact, according to Guerilla's studio director Angie Smets, the engine didn't even have an internal name. However, when Kojima Productions opted to use it courtesy of their partnership with Sony Interactive Entertainment, it needed a name given it would be referenced in the marketing of Death Stranding. Guerilla took inspiration from the Dutch trading post of Dejima based in Nagasaki in the 17th century. In an interview with the Dutch newspaper Algemeen Dagblad, Smet said:

"When it turned out that he [Hideo Kojima] wanted to work with our tech, we had to come up with a name very quickly. With us, it was always just called 'the engine', but now it is officially the Decima Engine. A nice reference to the age-old trade relationship between the Netherlands and Japan."

The environments of Death Stranding itself are largely inspired by the hauntingly beautiful landscapes of Iceland. And while the navigation tools were already well equipped to handle more rugged landscapes, as discussed in my episodes on the AI of Horizon Zero Dawn. There were still a lot of changes and smart design decisions needed to get it all to work as intended.

To ensure that the navigation mesh could at least hold together. One of the first issues to address was all of the 'islands' that would emerge in the navmesh, these are gaps that appear because the rocks were considered impossible to traverse for the AI. But given that the player can cross and step over some of these obstacles, the goal was to enable the AI to do that as well.

This is pretty easy to do, given you configure what is known as the step height of the mesh (essentially saying how big a step up can a character walk, like say you're walking up a flight of stairs). But the additional check is it runs raycast checks in line with the feet. This does two things, first, it ensures appropriate foot placement animations run to make sure it looks realistic. But also that with a probability, they could periodically trip and stumble as they cross them, because it's quite plausible that they should do that in the heat of the moment as the player does.

But of course just because you can walk over a rock, you don't want to do it all the time. Paths on navigation meshes are designed to simply state this is the best valid path you can take, but the probability of tripping on a rock isn't embedded in the navigation mesh data. So ideally, you want the character to recognise some areas you'd prefer to avoid if possible as a human does. Typically this is achieved with area costs, so you say that rockier regions or the rivers are less desirable. But given all of the rock placements are largely achieved through procedural tools built-in Decima, going in and manually assigning a cost to the rocks would be a horrible amount of work for anyone to do.

To resolve this the development team built a technique known as placement painting, whereas environmental features like rocks and water are added, the navigation mesh costs are painted onto them, which means that now a mule will run across rocks or cross rivers if it seems like the best thing to do in the moment.

Finding the Path

By making all of the changes mentioned thus far, it enables the navigation mesh to generate something that is actually useful, allowing AI characters to use the terrain in the open world much like the player would. And this brings us to the next big challenge, ensuring the non-player characters can then pathfinder in a way that keeps performance costs down and gets the desired behaviour.

The pathfinding runs on the A* search algorithm. A standard in artificial intelligence that will start in one part of the navigation mesh, and on each iteration will find the nearby connecting areas and prioritise their exploration based on the overall costs and perceived distance to the goal and the distance traversed to reach it. To keep the performance stable, the algorithm is capped at 500 iterations for any NPC trying to find a path to the goal. This cap works well within certain circumstances. As shown by Johnson in the GDC presentation, locations such as the Timefall Farm in the southern part of the Central Region of the game can easily find a path within that limit, given that the area itself is quite flat and undisturbed, meaning that navigation mesh is quite clean.

However, as we know, Death Stranding's environments are typically a lot more rocky, meaning the navmesh is fractured into more and more distinct areas which in turn will increase the number of iterations that the A* search will require in order to find a path. So depending on the area, those 500 iterations could mean it can find a path to traverse 200m, or only path 25m given the area is complex and still not reach the goal. So how can the developers ensure that the paths it generates are useful within the 500 iteration cap, even if it doesn't calculate the full path to the goal? But also, ensure it only stores just enough of the navigation data at any given time so it doesn't cause any performance issues.

Rebuilding the World

First let's take a look at how Death Stranding only generates the navigation mesh data that it needs at any given time. The solution is that it only builds the navigation mesh in the proximity of the characters themselves. NavMesh Bubbles are built around the player and other non-player characters, meaning that the navmesh only exists within their immediate proximity. If you consider the entire game world as a grid of squares, then the tile in that grid that the character is standing in will have its navmesh generated. Plus having this all broken up into tiles is very useful for the pathfinding part, which we'll look at more in a second.

The tiles are rebuilt dynamically as characters move through the world and respond to changes as they happen. So when a change occurs courtesy of a ladder or bridge being spawned in by the player, the unlocking of the chiral network, or even strand objects rising from tar, then NPCs characters will now be able to use it, given their navmesh settings update - for all you Unreal Engine fans out there, this is markedly similar to the navmesh invokers concept available in that engine.

However, this changes the pathfinding. Given only the navmesh in the bubble is generated, it now means the navigation is only pathing inside the bubble, and as the character begins to follow the generated path, it will repath as it goes. This sounds like a sensible solution, given it's much like a human would navigate: heading in the general direction and only resolving the path you need to take that's directly in front of you.

But, this creates an entirely new problem. Because the navmesh is only for the current tile, in theory, a character could calculate a path that doesn't work, because there could be obstacles, dead ends and other issues in the area between the current tile, and the destination. A human would be able to see that up ahead and begin to fix it as they go. But for these characters, they can only see what's on the navmesh of the current tile.

Refining the Path

So to resolve the issues of long-distance pathfinding, non-player characters in Death Stranding adopt a process known as event-based pathfinding. Each NPC when moving through the world establishes what is known as a corridor between their current location and the destination. The corridor establishes the general path to the goal, and if it's a short distance, it establishes the corridor of navmesh across the immediate tile, whereas if it's long-distance, the corridor to find the tiles it would go through in order to get to the destination, but the navigation mesh of each tile is only generated when needed. And to refine the behaviour and make it realistic, it only paths on the navmesh area that's available at that time within the corridor.

Ironically, this is slightly similar to the approach seen in my second video on Horizon Zero Dawn which enabled the flying machines to path across large distances successfully. Given it creates an abstract path and then refines it as it goes.

However, as the character continues to explore the world and move towards the destination, there's a good chance that the path devised by the corridor is invalid. So the NPCs follow a specific set of rules that dictate when and why the system will force a repath, these include:

• That the character leaves the corridor, typically because as it pathed through the space it had to walk around some rocks, which meant it left the corridor.

• Secondly, if the destination moved, which is particularly relevant if they're chasing the player, and you move out of the original corridor it created.

• Thirdly, if a corridor tile becomes invalid, because an obstacle appeared or something changed in the world that merits re-evaluating it.

• The fourth is when an edge clamp changes. Edge clamps are how it devises the corridor, given it looks at the available chunks of the game world and looks at their edges to see how it should leave that tile to enter the next one. If that edge changes, then so will the corridor.

• And lastly, the corridor itself is limited by the A* iteration cap. So if the corridor itself is incomplete and the NPC reaches the end of it, then it will re-run the pathfinding again.

Taking the corridor and event-driven repath approach, it ensures that these characters can gradually find the path as they go. They detect the issues as they go, and will then accommodate by repathing automatically.

However, this was still insufficient in some cases. Particularly when the characters have to travel distances that are several hundreds of meters in length in the more complex terrain. Even the corridor couldn't be generated within the A* iteration cap, so it couldn't find even an abstract path to the destination. While you might not trigger this kind of behaviour yourselves by kiting the enemies towards you a few meters at a time, the bigger issue often arose when you escaped them and they tried to turn back to areas of interest such as home bases or patrol paths. Or conversely, if there's a height differential, meaning they needed to climb up or down a complex environment to reach you.

The dev team actually fell back on a system called the AI Road Network. This already existed in the Decima engine and it allowed for AI characters to move along long-distance routes as devised by designers. So the corridor system was expanded to operate in a hybrid structure. A number of abstract paths would be put into the world by designers, and the pathfinding could then use this as a high-level guide if it discovered that the road network could help get it closer to the goal. It's still using the navmesh system to pathfind, but it means it could once again figure out the high-level path, then worry about how to actually navigate the terrain as it comes across it.

While researching this episode, I found some situations where even this solution doesn't work. Notably, if you travel from the Distribution Centre south of Lake Knot City, to then visit the Film Director or Junk Dealer you have to cross an area full of deep ravines. I suspect that the road network doesn't extend into this part of the game map. Hence I discovered Mules would get a little flustered as they tried to figure out how to reach me. And it's important I highlight this now. Not to speak ill of the game or the development team at Kojima Productions, but rather to point out that still, after all of this work and the interesting solutions devised, there are still limitations given the complexity of Death Stranding's environments when compared to many other games.

Closing

Death Stranding could certainly be argued as a fairly unique game in the library not just of PlayStation console exclusives, but also that of the game's director Hideo Kojima. And to achieve that level of novelty, it also had to take existing concepts we used all the time in AI for games, and tweak them so that it made sense for the game’s design and ultimately achieve the overall design vision.

For further reading:

• Eric Johnson, Death Stranding AI Postmortem, GDC 2021