Death Stranding: A Playground of Algorithms

Death Stranding was a surreal experience for several reasons. First, the game has a werid story line that’s a little hard to follow at times; exactly what you’d expect from the game’s director Hideo Kojima. Secondly, I’m still not used to seeing recognizable famous people in games. Facial capture isn’t new in the games industry, but it’s still weird to see Conan O’Brien in the middle of your videogame when you aren’t expecting it. Finally, it’s weird to see your area of research used as fodder for game play mechanics.

In Death Stranding, the player controls Sam Porter Bridges. Even after completing the game, I’m not sure if Porter is Sam’s middle name or simply a title. That’s because in Death Stranding Sam is a porter. For those unfamiliar with the term, a porter is someone paid to carry things, typically in an airport or a hotel. In our case, Sam carries cargo between cities.

That’s not just the back story and justification for the character. That’s the core gameplay mechanic: carrying things between places. Loading up Sam with more crates than a human should be able to carry, maintaining balance while navigating difficult terrain, and avoiding hazzards and enemies is most of what you do. To wit, the core gameplay mechanic is route optimization, a common application domain of combinatorial search.

It would be weird to see just one of my research interests reflected in a modern videogame with high production values. True to the director’s form, Death Stranding is supremely weird. It’s not just a game that uses route planning as the core gameplay mechanic. Algorithms play as big of a role in the game as stars like Norman Reedus and Guillermo del Toro. The multiplayer aspects of the game are, in essence, an implementation of ant colony optimization. Additionally, the end game looks a lot like building a minimum spanning tree of locations.

Death Stranding as a Path Planning Problem

Death Stranding is broken up into a series of missions each of which is capped with an evaluation. The evaluation scores the player based on the number and weight of packages they carry between two points. It also scores the player based on how quickly they transport the packages between locations, and the game scores the player based on how much they jostle the packages in transit.

This gives rise to a multi objective optimization problem. Previously when we’ve talked about optimization problems, we’ve restricted ourself to the case where there’s one objective function that needs to be maximized: cost. Here, we care about cost (in time), number of packages carried, how damaged the packages get, and how level we can hold the packages throughout. When you have multiple objectives to optimize that can’t be compared to one another, you don’t produce one plan, you produce many.

Specifically, you produce a pareto frontier of plans. These are an undominated set of plans according to the metrics that you care about. Undominated means that there is some metric, or combination of metrics, for which no other plan is better than the supplied plan. This is easiest to visualize in two dimmensions, as we do in the figure below. Here we consider length of the plan and the number of packages that can be carried (we invert number of packages carried so that we’re trying to minimize both criteria.) Points on the figure represent plans according to their length and number of packages carried.

The figure above shows what it means for a point to be dominant (in two dimmensions): there are no accepted plans which are longer and carry as many or fewer packages. The same concept extends to as many dimmensions as you would care to consider simultaneously. Algorithms for single objective optimization aren’t really appropriate for multi-objective optimization, but thankfully there exist many algorithms specifically envisioned for this setting.

Death Stranding Multiplayer as Ant Colony Optimization

Death Stranding has a really unique approach to multiplayer interaction. You can’t directly interact with any other player of the game. However, other players can see which path you’ve taken and they can interact with structures that you’ve built along the way. Coupled with the fact that structures degrade over time, this closely mimics the operation of ant colony optimization.

Ant Colony optimization is a biologically inspired technique for approximately solving optimization problems that can be modeled as finding paths through a graph. At a high level, the technique works by simulating the behavior of ants on top of the graph. Ants move by traversing edges of the graph, and lay down pheremone trails as they move through the graph. When deciding which edge to take, ants take an edge randomly, with more of the probability being assigned to edges with a large number of pheremones. Pheremones decay from edges over time. By tuning the rate at which ants act randomly and the rate at which pheremones decay, the system can be made to converge on a reasonable solution to the optimization problem.

In Death Stranding, players themselves are the ants. Their structures are the pheremone trails. When deciding how to navigate between locations, players choose to navigate towards existing player structures or to forge their own trails. If they visit a player structure, they may reinforce it with materials or by simply noting that they’re pleased with its existence. As with pheremone trains for ant colony optimization, the structures decay over time.

Building a Zip Line Network as a Minimum Spanning Tree Problem

The last structure you get access to in Death Stranding is the zip line. It’s exactly what it sounds like it is: a zip line between two large poles hundreds of meters apart. If they want to really make an impact on the post-apocalypse world by delivering as many packages as quickly and safely as possible, the savvy porter will build a network of zip lines to support that. That’s because the zip lines are the fastest, safest way to travel between two points.

As much as they might want to build ziplines literring the landscape, players have a finite amount of resources available to them for building structures in the game. As a result, players will want to build a network that spans all of the possible cities in the game while using the minimum number of resources to do so.

This is very close the problem of building a minimum spanning tree for a graph. A minimum spanning tree of a graph is a collection of edges that connects all interesting nodes of the graph together. The spanning tree is minimum in the sense that it uses the fewest number of edges, or in the case of a weighted graph, the smallest sum of edges.

For Death Stranding, the interesting nodes are the locations where the player would like to deliver packages, and the edges represent zip line placements. The routing problem in Death Stranding is simple enough that we can just use edge count, rather than edge weight, when computing the minimum spanning tree for the game.

Conclusion

I really enjoyed my time with Death Stranding. It’s nice to see any game try something radically different from other titles, and that’s even rarer in the AAA video game space. It was a pleasant surprise to see the things which I care so passionately about reflected in my favorite hobby.