Decision Modeling and Optimization in Game Design, Part 3: Allocation and Facility Location Problems

This article is the third in an ongoing weekly series on the use of decision modeling and optimization techniques for game design.  The full list of articles includes:

• Part 1: Introduction (Blogspot) (Gamasutra)
• Part 2: Optimization Basics and Unrolling a Simulation (Blogspot) (Gamasutra)
• Part 3: Allocation and Facility Location Problems (Blogspot) (Gamasutra)
• Part 4: Competitive Balancing Problems (Blogspot) (Gamasutra)
• Part 5: Class Assignment Problems (Blogspot) (Gamasutra)
• Part 6: Parametric Design Techniques (Blogspot) (Gamasutra)
• Part 7: Production Queues (Blogspot) (Gamasutra)
• Part 8: Graph Search (Blogspot) (Gamasutra)
• Part 9: Modular Level Design (Blogspot) (Gamasutra)

Spreadsheets for this article can be downloaded here: (SuperTank) (Teleporters part 1) (Teleporters part 2)

SuperTank: Solved!

In the first article in this series, we introduced an example problem for a game called SuperTank. In the second article, we introduced the basic concepts of decision modeling and guided you through a simple example using Excel's Solver tool.

Now, it’s time to apply the techniques we learned in Part 2 to the SuperTank problem from Part 1, and prove that we can use them to quickly and easily solve SuperTank.  Just to refresh your memory, SuperTank is a game where you’re able to fight with a customizable tank.  A SuperTank looks something like this:

Each SuperTank can have any number of weapons of five different types, as shown below:

Your SuperTank can hold 50 tons worth of weapons, and you have 100 credits to spend. Your SuperTank also has 3 “critical slots” used by special weapons like MegaRockets and UltraLasers.

You can download the spreadsheet for this example here.

The goal is to pick the weapons that maximize the SuperTank’s damage, while staying within the limits of 50 tons, 100 credits, and 3 critical slots. We also assume that this table properly encapsulates everything we need to know, and that factors such as weapon range, refire rate, and accuracy are either irrelevant or are already properly factored into the “Damage” setting for that weapon.

In order to optimize this, we’ll first enter the table above into a spreadsheet. Then, just below it, we’ll enter a second table that has a set of 5 “quantity” cells to specify the quantity of each of the 5 weapon types.

For now, we’ll enter a value of ‘1’ into these cells just to test that they work properly, but these are our decision cells – we will ask Excel Solver to find the correct values of these cells for us (you can tell that they are decision cells due to the yellow coloring, as we are following the formatting guidelines laid out in the second article). To the right of “quantity” cells, we’ll add calculation cells that multiply the quantity values in these decision cells by the Damage, Weight, Cost, and Critical Slots values from the table above. Thus, each row of this table will properly add up how much damage, weight, cost, and critical slots all the weapons in each weapon category will use up.

Finally, we set up a section below that sums up all the quantity, weight, cost, and critical slots values from the table above, and compares those against the maximum weight, cost, and critical slots settings specified in the problem statement (50, 100, and 3, respectively).

Following our formatting conventions from Part 2 of this series, the blue cells along the top are our criteria from the problem statement. The grey cells are calculation cells representing the total weight, cost, and critical slot values based on the summations from the quantity table above (i.e. the totals of the “Weight x Quantity,” “Cost x Quantity,” and “Critical Slots x Quantity” columns. Finally, the orange cell represents the total damage of our SuperTank, based on the total damage from the “Damage x Quantity” column of the table above.

Before we run ahead and solve this, let’s take the time to make our spreadsheet a bit more user-friendly. We’ll take advantage of Excel’s ability to name each cell to give user-friendly names to these 7 cells in the final calculation table. This isn’t strictly necessary, but in the long run, it will help make our spreadsheet significantly more understandable if we can give cells readable names such as “MaxCriticalSlots” instead of “$F$21.” To do this, we simply select a cell and go to the name entry box above the spreadsheet and just to the left of the formula bar and type in the new name.

Finally, let’s go to Excel Solver and find the solution (go to the right side of the “Data” tab and select “Solver”; if you don’t see it, go to Excel Options, select the Add-Ins category, ensure that the “Manage” drop box is set to “Excel Add-Ins,” hit “Go…” and ensure that “Solver Add-in” is checked.)

Under “Set Objective,” we’ll select the orange objective cell and select the “Max” radio button below it. Under “By Changing Variable Cells,” we’ll select the decision cells (the yellow cells in the “Quantity” column of the second table). Below that, we’ll hit the “Add” button to add constraints as follows:

• The decision cells should be between 0 and some reasonable maximum (we pick 50, even though this is probably a much larger upper limit than we need). It’s also essential to set the “= integer” constraint on each decision cell, since you cannot have a fractional amount of any given weapon, and since Excel Solver assumes any variable is a real number unless you tell it otherwise, it would undoubtedly try to do this if we let it.

• We also set the total cost, total weight, and total critical slots values to less than the maximums specified in the problem statement. You can see from the dialog image below that these now have the nice user-specified names we added in the table below, making this dialog much more readable.

Now we hit the “Solve” button, and after a brief wait, Solver fills in the “Quantity” values for us, giving us:

• 1 Machine Gun
• 3 Rockets
• 2 MegaRockets
• 1 Laser
• 1 UltraLaser

All of this gives us total damage of 83 and uses exactly 50 tons, 100 credits, and 3 critical slots. You can see that the best solution does not change no matter how much time you give Solver to run.  If you reset these values and re-optimize, or if you go to Options and change the random seed, it will still give you these values.  We can't be 100% sure this is the optimal solution, but given that Solver seems to be unable to improve on it after repeated optimization passes, it seems quite likely that this is the real optimum and not just a local maximum.

Problem solved!

Additional Uses

What’s exciting about this is that we've not only solved the problem much more quickly than we could have done by hand, we've also set it up to allow us to test which weapons are most useful with different (weight, cost, critical slots) settings for a SuperTank. This means that we can relatively easily see and measure the effects of various changes to any of these parameters on the SuperTank, and if we wanted to introduce a new alternate model of SuperTank that was lighter, heavier, or had a different number of critical slots, we could do so very easily.

We can also get a sense of the relative utility of all of our five weapon types as we modify all of these parameters, and quickly identify which weapons are too useful, not useful enough, inappropriately priced for their weight and damage characteristics, and so on.

Again, the point is that this kind of tool allows us to search through the design space much more quickly than we could do by hand. For any incremental design decision we might consider, whether it be changing any of the parameters of the weapons or the SuperTank itself, adding new weapons or SuperTank models, or adding new parameters (say, a Size requirement measured in cubic meters), this gives us a very easy way to get visibility into some of the ramifications of that potential change.

To see what I mean, go to the blue “Max Cost” cell and change it from 100 to 99. Then re-run Solver, and you should now get a very different weapon loadout:

• 0 Machine Guns
• 2 Rockets
• 3 MegaRockets
• 3 Lasers
• 0 UltraLasers

This loadout gets a slightly lower damage score (82 instead of 83), but is radically different from the previous loadout.

If you set Max Cost to 101 or 102 and re-run, chances are that you’ll get a configuration similar or identical to the first one; in either case, damage will remain at 83 (actual results may vary since there are several optimal loadouts in these cases). However, if you set Max Cost to 103, you should get:

• 1 Machine Gun
• 4 Rockets
• 2 MegaRockets
• 0 Lasers
• 1 UltraLaser

… which increases our total damage to 84.

This is interesting; this weapon loadout is very different from the first two.

As you can see, we get a surprising result: the optimal choice of weapons in our loadout is highly dependent on the SuperTank's parameters and can change dramatically with even a tiny change in those parameters. This also gives us all kinds of other useful information: all five of the weapon types are useful in at least two of the three SuperTank settings, with Rockets and MegaRockets having clear utility in all three. This seems to indicate that all five weapons are well-balanced in the sense that they are all useful relative to one another, while at the same time remaining unique.

And you can also see, this sort of decision modeling and optimization gives us an excellent way to quickly search the local neighborhood and re-optimize. For some problem types, it can allow us to gain visibility into dominant player strategies and exploits that might be difficult or impossible to find any other way.

Wormhole Teleporters

After looking at the last two examples (the strategy game tax rate example and the SuperTank), you may think these techniques only apply to cases where users have to deal with numbers. Nothing could be further from the truth! As we’ll see, there are countless instances where we can gain benefits from optimizing design elements that either do not appear as numbers to the user, or do not seem to involve any numbers at all!

You might also be inclined to conclude that decision modeling only applies when modeling the decisions that players will make in our games. This is also incorrect: in some cases, you can also use it to model an optimize your own decisions as a designer.

Assume that you are working on a massively multiplayer space-based role-playing game. One day your design lead comes to you with a look of worry on his face. “We've just wrapping up a redesign of the Omega Sector,” he says, “and we’re running into a problem. We're planning to have some wormhole teleporters in that world segment, but we can’t agree on where to put them.”

“How many teleporters?” you ask.

“We’re not sure yet. It will probably be three, but it could be anywhere between 2 and 4. We just don’t know right now.” Then he lays down a map that looks like this:

“What’s that?” you ask.

“It’s a map of the Omega Sector. Or at least, the star systems the player can visit within that quadrant. We need you to figure out which cells should contain wormholes.”

“OK, what are the rules for wormhole placement? And can I have a wormhole in the same quadrant as a star system?”

“We want you to place the wormholes in a way that minimizes the distance between any star system and the nearest wormhole. And yes, you can put them in the same quadrant as a star system; they’re just small teleporters hanging in space, so you can put them anywhere. And don’t forget, we haven’t agreed on how many wormholes this sector should have yet, so try to give me solutions for 2, 3, and 4 wormholes.”

How would you frame this problem, and how would you solve it?

Optimize Me Up, Scotty!

Let’s start by setting up the decision cells. We’ll call the four wormhole teleporters ‘A,’ ‘B,’ ‘C,’ and ‘D.’ We know that each teleporter is essentially nothing more than an (x,y) coordinate on the Omega Sector star map above. We also know that we’ll need some way to specify how many of these four teleporters are actually active, so we’ll add a cell to let us specify the number of teleporters. We will use teleporter ‘D’ only in the case where we are using 4 wormholes, and we’ll use ‘C’ only when we have 3 or more.

Below that, we’ll set up a table to figure out the distance from each star system to the nearest teleporter. That table looks like this:

On the left side, in blue, we have the coordinates of each star system on the map. Each star system is represented in one row. We simply typed this in from the Omega Sector map we were handed above.

To the right of that, we calculate the distance to each of the four teleporters A, B, C, and D. This is simply the Pythagorean theorem, calculated as the square root of the horizontal and vertical distance between the star system and the teleporter:

=SQRT(($B14-Ax)^2+($C14-Ay)^2)

(Don’t worry – I promise that this is as complicated as the math will get in this series!)

We get the X and Y coordinates of each star system from the blue cells in the table above, and we get the X and Y coordinates of each teleporter (the cells named “Ax” and “Ay” for teleporter A in the SQRT() function above) from the yellow decision cells at the top.

Finally, we take the minimum of these four values in the “Dist to Closest” column, which simply uses the MIN() function to determine the minimum of the four values immediately to its left. We then sum that entire column at the bottom; this sum is our objective cell.

You may have also noticed that in the screenshot above, the “Dist to D” cells all have the value 99. The reason for this is that we use the “Number of Teleporters?” cell in the section at the top of the decision model to let us tweak the number of teleporters we are considering. If the number of teleporters is 2, we use the value ’99’ in both the “Dist to C” and “Dist to D” columns, while if it is 3, we use ‘99’ in the “Dist to D” column only. This ensures that each star system will ignore any extraneous teleporters when calculating the distance to the closest teleporter in the case of 2 or 3 teleporters.

Now, we run Solver, as before:

The objective cell is the sum at the bottom of our “Dist to Closest” column. Note that unlike other examples, we want to use “To: Min” in the radio button for this, because we want the minimum distance from all the star systems to our teleporters, not the maximum.

Below that, we specify the decision cells (“By Changing Variable Cells”) as the eight yellow decision cells for the X and Y coordinates of wormholes A, B, C, and D. In the constraints section at the bottom, we constrain each of our coordinates to be an integer between 0 and 12. Note that we are using an integer constraint on these decision cells because we are assuming our design lead simply wants to know which cell each teleporter should be in, but we could just as easily skip this constraint if our design lead wanted to know a real-valued location.

If we set the “Number of Teleporters?” cell to 2, 3, and 4, and re-run Solver at each setting, we get the following configurations:

Armed with this information, you can go back to your design lead and show the optimal locations to place any number of teleporters between 2 and 4. Here is what these optimal wormhole locations look like on the map (shown in green) for 2, 3, and 4 wormholes, respectively.

You can download the spreadsheet for this example here.

Did I Mention There Are Ninjas?

“OK, that’s terrific,” your design lead replies, but you can see a slight look of anguish on his face. “But, uhh … well, I forgot to tell you some of these star systems are inhabited by Space Ninjas. And we actually want the systems with Space Ninjas to be farther away from the wormholes, because we don’t want players to feel too threatened.”

“Oh. Well, that kind of throws a monkey wrench into things.”

“Yeah. Also, some star systems have 2 colonies in them instead of one, so it makes it twice as important for them to be closer to the wormhole teleporters. Or twice as important for them to be farther, in the case of that one star system that has 2 Space Ninja colonies. Here’s what the map looks like now:”

He continues: “Every negative number is a Space Ninja colony. The system with a ‘2’ has two human colonies, while the ‘-2’ has two Space Ninja Colonies. So, can you tell us where to put the teleporters in this case?”

“Tell me you've at least decided whether there will be 2, 3, or 4 teleporters by now,” you reply snarkily.

“No such luck, I’m afraid.”

Solving For Ninjas

In order to solve this, we need to add a new column to our table to represent the weightings in the table above. We will call this the “multiplier.” We will then multiply this value by the value in the “Dist to Closest” column

When we do this, though, “Dist to Closest” changes its meaning slightly. It’s not really the distance to the closest star system, since for Space Ninja star systems, it’s -1 times that. It’s more of a generalized “score,” so let’s call it that instead.

In this way, the score now represents an aggregate value. By minimizing it, we ensure that Solver attempts to be as close as possible to human-colonized star systems and as far as possible from Space Ninja-occupied systems simultaneously.

Now we get the following results:

As you can see, this gives us a significantly different wormhole configuration in each case from the simpler, pre-Space-Ninja version.

The spreadsheet for this extended version of the teleporter example can be downloaded here.

As you can see, our decision model was able to very quickly solve this non-trivial problem, and we could adapt it to changing requirements remarkably quickly.

This problem is from a class of problems called "facility location problems," which are very well-studied in the operations management field.  But as you can see, it has potential applications in game design and level design as well, and is easy (to the point of being trivial) to set up in Excel.

Tune in next time, when we'll apply decision modeling and optimization to a challenging game balancing problem for multiple classes in player-vs-player (PvP) combat for a simplified role-playing game.


-Paul Tozour


Part 4 in this series is now available here.

This article was edited by Professor Christopher Thomas Ryan, Assistant Professor of Operations Management at the University of Chicago Booth School of Business.