Traversal Problem

A mathematics professor introduced me to an interesting optimization problem in a video game setting. It goes like this:

"You are a warrior defending a region from a monster invasion! The region is represented by a square map, and you can select any starting position on the map. After you select your starting position, monsters will randomly spawn on the map, but you must choose where to start before they spawn. Once they appear, you must travel to each one and defeat them. Where should you start to minimize travel time on average?"

Understanding the Problem

To tackle this problem, we need to make a few assumptions and lay some groundwork:

Monster Spawn: Monsters spawn with uniform random probability. That is, they are equally likely to spawn at any point on the map.
Map Width: The map width is set to one for ease of future calculations.
Travel Time: We assume travel speed is constant and terrain has no impact on travel time. Thus, a straight line is the fastest route between any two points.

Simplification and Approach

This problem is complex and can be approached from several directions. When faced with an open question like this, it’s a good idea to simplify it in stages until reaching the simplest unsolved version you can think of. That done, you can work through the problems from least to most complex, letting findings from each step inform the next. Use the interactive portion of the document below by clicking on highlighted text to see how we can simplify this problem into something approachable.

When you see a word or phrase highlighted, it means you can click on it to make some changes, usually to the map on the left. Let's get started!

Looking at our map again, a number of complexities can be ignored for the time being. First, we can address a (perhaps not obvious) problem with the shape. A square makes the task at hand a little more challenging, as the distance from center to edge varies across the shape's perimeter. What if we had a shape with an equal distance from center to any point on the edge? That would make things easier, so let's do that.

In fact, while we're simplifying the shape, let's get rid of that pesky second dimension making all of our distance calculations so difficult. Now we only have to worry about left and right, not up and down, and we near the simplest case. There is something else we can eliminate, however. Since selecting a point on the right half of the line is the same as selecting its mirrored point on the left half, we can ignore half of the line for hero placement. Then, once we find a solution to the one-dimensional case, we can spin it and see how it works on a circular map.

Thanks for sticking around to see how this problem can be approached! If you want to see how progress is going, head over to the github repository and poke around. It isn't as stylish as this presentation page, but it is kept more up-to-date (since the work happens there).

Optimal Realm Defense

Understanding the Problem

Simplification and Approach

Interactive Exploration