Level Design Process of Warrior Defense

I put out a poll on Facebook asking people whether I should write about the level design process; or optimizations done for Warrior Defense. Level design process won. I think it won because I mentioned that I used a genetic algorithm in making levels. Maybe it sounded cool to them, but really, genetic algorithms are just glorified brute force. So don’t be impressed when someone brags that they can code a genetic algorithm. Here goes:

Let me begin by describing the level data model. A level is simply a collection of wave sets. Each wave set is a collection of spawn sessions. Here’s a level with 3 waves represented in XML:

<Level initialResource="400">
  <Waves>
    <WaveSet notification="">
      <Spawn unit="Critter" time="0" number="22" rate="1.1" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Critter" time="10" number="22" rate="1.1" startGroup="START_2" goalGroup="GOAL_2" />
    </WaveSet>
    <WaveSet notification="">
      <Spawn unit="Runner" time="10" number="1" rate="1" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Critter" time="0" number="25" rate="1.2" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Runner" time="25" number="1" rate="1" startGroup="START_2" goalGroup="GOAL_2" />
      <Spawn unit="Critter" time="15" number="25" rate="1.2" startGroup="START_2" goalGroup="GOAL_2" />
    </WaveSet>
    <WaveSet notification="">
      <Spawn unit="Critter" time="0" number="27" rate="1.2" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Runner" time="11" number="1" rate="1" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Critter" time="13" number="27" rate="1.2" startGroup="START_2" goalGroup="GOAL_2" />
      <Spawn unit="Runner" time="24" number="1" rate="1" startGroup="START_2" goalGroup="GOAL_2" />
    </WaveSet>
  </Waves>
</Level>

Note that this is only a simplified version. The actual level XML contains a lot more tags. I just left what’s relevant for this article.

A spawn session describes how a series of a number of a certain enemy units are spawned into the level. Think of it as a specification of a magical portal where enemies come in. It has the following properties:

  • unit – What enemy unit to spawn
  • time – The time to start spawning the enemies from the starting time of the wave
  • number – Number of units to spawn
  • rate – Spawn rate of the units. It’s in spawn/second. It determines how fast the enemies are spawned. Higher number means faster spawn.
  • startGroup – The area where the spawned units start. It is named as ‘group’ here because it is a tile group.
  • goalGroup – The area where the spawned units are headed.

This is how a single level in Warrior Defense is described, at least the meat of it. We now head to the actual level designing. One important question that need to be answered was “How do we make waves that are ensured to have increasing difficulty?” Digging deeper, putting it in another way is “How do we quantitatively measure how difficult a wave is?” If we have the answer to this question, then it’s just a matter of increasing this value.

How do we quantitatively measure how difficult a wave is?

What I did is I assigned a hypothetical value measuring how tough a single enemy unit is. It’s the same as setting a difficulty level for each unit. The following are XML element description of three enemy units in the game:

<Unit name="Critter" type="Crawler" value="1" size="Small">
    ...
</Unit>

<Unit name="Runner" type="Crawler" value="2" size="Small">
    ...
</Unit>
    
<Unit name="Roach" type="Crawler" value="3" size="Small">
    ...
</Unit>

The value attribute represents the difficulty value of the unit. The higher the value, the more difficult it is.

With this, calculating for a wave’s difficulty is just a matter of addition and multiplication. For example, for this wave set:

<WaveSet notification="">
    <Spawn unit="Critter" time="0" number="22" rate="1.1" startGroup="START_1" goalGroup="GOAL_1" />
    <Spawn unit="Runner" time="10" number="15" rate="1.1" startGroup="START_2" goalGroup="GOAL_2" />
</WaveSet>

The difficulty value of this wave set can be calculated as:

difficultyValue = Sum of all spawn session difficulty
difficultyValue = (numberOfCritter * difficultyValueOfCritter) + (numberOfRunner * difficultyValueOfRunner)
difficultyValue = (22 * 1) + (15 * 2)
difficultyValue = 52

It’s a rather simple quantitative measure and probably not representative enough of the actual difficulty, but it works enough for my purposes for level designing. Choosing how to increase the difficulty value is easy. I could use linear, logarithmic, quadratic increase, etc… anything to my liking.

Combinations of enemies

The next hurdle I encountered is where I used some programming. “How do I make combinations of enemies that total to a certain difficulty value?” For example, I want to make a wave set that has a DV of 100. What combination of units and how many of them should I include to make this wave set? What if I don’t want Critters to be in this wave? I want Tanks and Runners in this wave. How many of them should I use?

I turned to computer science. This particular problem can be best solved by a simple genetic algorithm. The idea is to generate random spawn session combinations and breed them to find better ones until the one with the exact difficulty value emerges. The code is also not that hard to make as I imagined it. So I decided to put a little time to make this little tool I call Wave Set Generator.

Forgive the UI. It's long.
Forgive the UI. It’s vertically long.

Continuation from previous image
Continuation from previous image

This tool generates a set of spawn sessions that matches a number of criteria:

  • Spawn Data Count – Number of spawn sessions
  • Target Unique Count – The number of unique units. Spawn sessions may or may not have the same enemy types.
  • Target Total Value – The difficulty value of the whole set in a certain range
  • Target Unit Count – Overall number of units in a certain range
  • Exception Set – Units that should not be included in the set. In later waves, easier enemy types might no longer be necessary. Or I would want waves with no flying units.
  • Required Set – Units that should be included in the set. In some waves, I may want only flying units, or only heavy units.

When the Start button is clicked, the tool generates random combinations at first then interbreeds them until the combination that meets all criteria has been generated. The tool stops as soon as one combination is found. There are more than one possible combination. If I don’t like the generated one, I can just press Start again to look for another combination. How cool is that? This is the most time saving tool I’ve ever made. After a good combination is generated, I’ll just have to put them to the level xml.

Just imagine what I was doing without a tool for this. I choose some units, then I would assigned an arbitrary number to one unit and calculate for the rest. If I didn’t like the resulting combination, I’d have to recompute for other units, or worse, start all over again. In short, it takes a lot of time just to compose waves.

The genetic algorithm I used goes like this:

  1. Represent the spawn session set as a list of bytes (also known as ‘chromosome’).
  2. Provide a fitness calculator that checks if a chromosome meets all the criteria. If not, it assigns a fitness score to a single chromosome.
  3. Generate a fixed number of random chromosomes. Say this is N.
  4. Using the fitness calculator, check each chromosome if it is already the fittest candidate. If one is found, stop the process. Else, assign the fitness score to each chromosome.
  5. Generate a new generation of N chromosomes by mating the current ones. Ensure that the fitter chromosome have more chances of mating.
  6. Repeat step 4 until the fittest chromosome is found.

Implementation details is already out of scope for this post. I’ll write about that in another one. The concept of the algorithm is it looks for the best solution by culling the unfit solutions to generate better solutions in every generation. It’s kind of like how evolution works. I say it’s a glorified brute force because there’s not even an actual solution. It looks for it blindly.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s