RTS Battle simulation with IronPython
I used Python to simulate Age of Empires archer battles. I wanted to be able to answer questions like:
- If 12 archers attack 10 archers, what will the margin of victory be?
- If two armies of the same size attack each other, how do different strategies affect the outcome?
This also led to some practical strategies and some quiz questions about why certain behaviors occur.
Python is good for both quickly modeling systems like this and easily running the queries. Code snippets need to be able to:
- Concisely represent the query. If we can ask the question in 1 sentence of English, we don't want 6 pages of code to write the same query.
- Allow operations like averaging across multiple runs.
- Scale to arbitrary complexity, and potentially include arbitrarily complex algorithms ( Turing machine calculations).
These queries would be painful to express in C# 1.0 (although certainly improved with C# 3.0 and Linq). Many interesting queries can be written in literally a single line of Python code.
I wrote all these snippets using IronPython, a Python implemention on .NET.
This is a relatively large entry because I wanted to deliver an end-to-end view in a single entry. It's broken into the following parts:
- The rules.
- The Python code for emulating them.
- Concise queries and pretty charts.
The Rules
The rules for the simulation:
The rules (as I observe in AOE, Dune 2, and other RTS games) that I'm simulating here are:
- Each unit has a health meter. (In my case, I arbitrarily chose 50 HP.)
- A unit is alive if health > 0.
- Time is broken into discrete turns. (In RTS, these turns operate on a timer, so if you snooze, you lose. )
- At each turn, each live unit can attack any enemy unit. (Imagine the units are short-ranged like archers.) This results in the target unit's HP decreasing by the attack value (in this case, 1 HP per attack).
- All units issue their attacks simultaneously. So 2 units may kill each other at the same time. (This avoids bias in the order units issue attacks).
So if 2 units are attacking each other, they'd both start out with 50 HP, and each turn, they'd both attack the other one and decrease 1 HP. After 50 turns, they'd both kill each other.
Complexity from Simplicity
This is a pretty simple set of rules. Specifically:
- The rules are deterministic. There is no dice-rolling. (Contrast to the battle system in Civilization or Risk.)
- All units are identical. Units don't have a location, so they don't need to maneuver into positions or worry about neighbors.
- A unit's attack power doesn't decrease with damage, so a 1% HP and 100% HP have the same offensive capability.
- If 10 units all attack the same foe in a given turn, and the first one kills him, then the other 9 units are attacking a corpse for that turn and thus wasting their ammo.
A more complex simulation could of course change any of these to try to get a more accurate simulation. In fact, when I first started the simulation, I figured that I'd soon be adding more complexity. However, just applying simple rules on large scales can quickly lead to complex behavior. (see Emergent Properties for more on this) See the graphs below for some examples.
Policy: who do you attack?
A policy issue that arises out of rule #3 is "what enemy unit does each individual unit attack?" For example, say we have a 3 on 3 battle (A,B,C vs. X,Y,Z). Does each unit just attack a random opponent on the other side? Does an entire army gang up on the weakest opponent to try to take him out? Does an army coordinate to avoid wasted ammunition?
The Python Code
Modeling:
This is a pretty simple set of rules to model with Python. I model the unit with a class cleverly named Unit, which just encapsulates health and attack policy. A single turn of attacks is executed by the Attack1 function.
Here's the essential code. Note that it's under 50 lines, and that's even including some asserts and comments:
#--------------------------------- # Inidividual unit. class Unit: def __init__(self, fpAttackPolicy=PickWeakest): self.healthStart = self.health=50 self.fpAttackPolicy = fpAttackPolicy def __str__(self): return "health: %d/%d" % (self.health, self.healthStart) def ApplyDamage(self, d): self.health -= d if (self.health < 0): self.health = 0 # Return true iff is alive. def IsAlive(self): return (self.health > 0) # Pick a target in the opposing army. def PickTarget(self, army): guy = self.fpAttackPolicy(army) assert(guy.IsAlive()) return guy #--------------------------------- # Given 2 arrays of armies, do a single round of attacks. # Return True if both armies are still alive. def Attack1(a1, a2): # 1) calculate targets # each alive unit can attack another unit. t1 = [x.PickTarget(a2) for x in a1 if x.IsAlive()] t2 = [x.PickTarget(a1) for x in a2 if x.IsAlive()] assert(len(t1) > 0) assert(len(t2) > 0) # 2) apply targets. # Apply all attacks at once, to avoid giving bias to order of attack. # This allows 2 units to kill each other. for x in (t1 + t2): x.ApplyDamage(1) # 3) check if armies are still alive if (NumAlive(a1) == 0): return False if (NumAlive(a2) == 0): return False return True # count how many in army are still alive. def NumAlive(army): c = 0 for x in army: if x.IsAlive(): c+= 1 return c
Additional layers
You can layer simple utility functions on top of the essentials. For example, a Make() function creates an army (an array of Unit instances) for a given size that has the attack-weakest policy. MakeR is similar for an attack-random policy. A VictoryMargin() function quantifies how much army #1 defeated army #2 by. The Battle() function takes 2 armies and fights until 1 is destroyed and then returns some statistics about the battle.
# Make an army def Make(size, fpAttackPolicy=PickWeakest): return [Unit(fpAttackPolicy) for i in range(size)]# shorthand for Making army with 'random attack' policy def MakeR(size): return Make(size, PickRandom)# return victory margin between 2 armies. # = (winner current health / winner starting health) * 100 # negative for a1, positive for a2 # 0 if both are dead def VictoryMargin(a1, a2): s1 = Stat(a1) s2 = Stat(a2) if s1.alive: assert(not s2.alive) return - s1.health * 100 / s1.healthStart elif s2.alive: assert(not s1.alive) return s2.health * 100 / s2.healthStart else: return 0 # both dead # Fight the 2 armies until 1 is defeated, printing status at each turn. # Return a rich summary object. def Battle(a1, a2): turn = 0 done = False print '-----------' while(True): # print status print '%2d)' % (turn), for x in a1: print '%2d' % (x.health), print '|', for x in a2: print '%2d' % (x.health), print # end of line if (done): break turn+= 1 done = not Attack1(a1, a2) print '-----------' v = VictoryMargin(a1, a2) print "done. Margin=%d%% (of victor's original health)" % (v) # Create a summary container for results. class Res: def __init__(self): self.turns = turn self.victory = v self.size1=len(a1) # starting size of each army self.size2=len(a2) self.end1 = NumAlive(a1) # ending size of each army self.end2 = NumAlive(a2) return Res()
Concise Queries and Pretty Charts
This section shows some simple queries and executions.
1) Simple 2 on 1 battle:
The following runs a battle of 2 units vs. 1 unit, showing the results after each turn.
Battle(Make(2), Make(1))
Here's the output. Each row is a turn. The 4 columns are: turn #, Unit #1 of Team #1, Unit #2 of Team #1, and Unit #1 of Team #2.
|
All units here are using the "attack weakest opponent" policy. Not surprisingly, the side with 2 clobbers the side with just 1. The bigger army has a 2:1 size advantage, but retains 75% of its original health, and 100% of its units stay alive.
2) If 2 armies of the same size randomly attack each other, is the outcome random?
Intuitively, you'd expect 2 equally-sized armies that randomly attack each other to be a toss-up. After all, there's too much symmetry to have a bias in winner.
We can verify this. This snippet runs a battle for nTimes and returns a vector of the victory margin from each battle. Recall victory margin is between -100 (if army1 has a perfect victory) and +100 (if army2 has a perfect victory). 0 means a tie (i.e., both armies are killed).
def NVictory_Random(size=5, nTimes=10):
return frun(nTimes, lambda: Battle(MakeR(size), MakeR(size)).victory)
So you can run something like:
l = NVictory_Random(5, 100)
to get a list of 100 trials of 5-on-5, and then see how close that is to a tie. A quick sanity check shows avg(l) gave an average of -.42, which is pretty close to zero.
However, to be more formal, you can run queries like:
len([x for x in l if abs(x) <= 7])*100/len(l)
Which returned 95 for me, meaning that 95% of the results were within 7% of a tie (0).
Or, just run the standard deviation for the data set l against an expected target value of 0:
math.sqrt(sum([x*x for x in l])/len(l))
Which gave me 4.35 on my data.
That's pretty much a tie, as we expected.
3) How many turns does a battle take as a function of army size?
If 2 armies of same size battle, do larger battles take longer?
Here are 2 queries to show turns vs. army size (for 1 <= i <= nMax) for 2 different attack policies (attack the weakest opponent, attack a random opponent).
def NTurns_Weakest(nMax): return [Battle(Make(i),Make(i)).turns for i in range(1,nMax+1)]def NTurns_Random(nMax, nTimes=5): return [ favg(nTimes, lambda : Battle(MakeR(i),MakeR(i)).turns) for i in range(1,nMax+1)]
For the attack-random case, we run an average across 5 times.
The graph of the results is:
Some interesting observations here:
- For random attacks, the army size doesn't influence battle duration beyond noise. 20-on-20 takes about as long as 1-on-1.
- For attack-weakest, the battle takes longer with larger armies. (Quiz #1: Why?)
4) How much better is attack-weakest vs. attack-random?
We can simulate a single round of N-on-N via: Battle(MakeR(n), Make(N)). Note that this is MakeR (for attack-random) vs. Make (for attack-weakest).
This query runs the battle across a range of sizes, and then gets a projection including victory margin and number of turns.
def RvsW2(nMax = 4):
# get raw data
b = [Battle(MakeR(i),Make(i)) for i in range(1,nMax+1)]
# run projection to get interesting fields:
w=map(lambda i: (i.size2, i.end2, i.turns, i.victory), b)
return w
Here are the results we get:
If we take number of turns instead:
Observations:
- Notice that Victory Margin is always positive, indicating that attack-weakest policy always wins over attack-random.
- It turns out the graphs are surprisingly deterministic, even though there's randomness from the attack-random policy. Running multiple times appears to gives the same curve. (Quiz #2: Why?)
- Notice that as battle duration (# of turns) goes up, victory margin goes down (and vice-versa). My theory is that the longer the battle lasts, the more time the losing side (attack-random) has to inflict damage on the winning side, thus pulling down the victory margin.
Practical tidbit #1: When you're playing a RTS, it's more efficient to manually have your units target a single enemy then to let the AI employ an essentially attack-random policy.
5) How does size advantage affect victory margin?
We can see that an N-on-N battle is a tie. But how big do extra units help?
Here's a snippet to show a battle between armies of (size) vs. (size+x), for a range on x.
def NMargin_Extra(nMaxDelta = 5, size=10):
return [Battle(Make(size), Make(size+i)).victory for i in range(nMaxDelta)]
Here's the graph of the results, where the base size is 10. This shows the victory margin in the range on 10-on-10 vs 10-on-30.
As we'd expect:
- When the armies are the same size (size-advantage=0), it's a tie (victory margin=0).
- The large the size advantage, the bigger the victory margin approaching the maximum of +100.
- The difference between double (10-on-20) and triple (10-on-30) is insignificant.
Practical tidbit #2: When attacking an enemy army, a 2-1 advantage should clobber. Waiting to build up for a 3-1 advantage may be overkill.