Python In Short: Tower Defense I

Most of us have played, have heard or have seen somebody play a Tower Defense style game. 
The list of such games is very large: Bloons Tower Defense, Plants vs Zombies, Kingdom Rush, PixelJunk Monsters, Defense Grid, geoDefense, Jelly Defense, Dungeons Defenders and on and on.
Hopefully you’ve spent some quality time setting up your defenses, killing enemies and advancing through several rounds/waves.

The basic idea of these strategy/turn based games is simple: The game progresses in rounds/waves. In each round your opponent (usually the computer) has a certain number of "soldiers" that traverse a maze along which you sprinkle, in strategic locations, one or more "towers" (how many towers you place depends typically on how many you can afford, since each tower will have its own price).
The towers will fire at the approaching soldiers; it might take one or several hits to kill a soldier (you earn "money" with each successful hit).
The goal of the towers is to prevent any of the soldiers to reach the exit of the maze. Each soldier that leaves the maze will cause you to lose one life.

In this post we will consider a simple version/variant of the game.

Lets suppose the game starts with gameTowers towers, and gameSoldiers soldiers.

Each tower can kill numKills soldiers per round (one hit one kill) and can sustain numHits before the tower crumbles.

Each soldier in turn can hit one random tower per round causing that tower to lose one of its numHits. More than one soldier can hit the same tower in the same round.

The game proceeds in the following manner: for a given wave/round each soldier will hit a tower. When all soldiers have done so, each tower will then hit numKills soldiers. If there are any soldiers and towers left, the game moves to the next wave. Otherwise if there are only soldiers/towers left, the soldiers/towers win.

One last important detail: At the start of each new round the surviving towers will get reloaded with numKills. Those are fully spent within the round when it is the towers turn (if there are enough soldiers; the towers can only shoot one of their numKills per soldier; if there are not enough soldiers to shoot at, that will be the last round and the towers win the game). The damage they suffer however carries over from round to round. I.e. all towers start the game with numHits but those will decrease from round to round (and within the same round) for those towers hit by the soldiers.

Given these rules and the 4 constants gameSoldiers, numHits, numKills, gameTowers we would like to know how fast can the soldiers destroy the towers or if that is not possible (i.e. if the towers will win).

In which round all the soldiers/towers will be destroyed and how many soldiers/towers are left in that round? If only towers are left we would also like to know how many hits and kills each of them has left. (It is not possible for the game to end with a tie.)

We can go one step further and ask how many towers and soldiers are left after each wave/round. We can gather this information in a dictionary where the keys are the wave number and the values are a list of the values we are interested in tracking after the end of each round. We will call this dictionary waveStats.

An Algorithm to Maximize the number of Towers destroyed

A simple algorithm that maximizes the number of towers destroyed is the following

 def attack(self, gameSoldiers, numHits, numKills, gameTowers):
        totalHits = numHits * gameTowers
        gTowers = gameTowers
        gSoldiers = gameSoldiers
        waveStats = {}
        wave=0
        waveStats[wave] = {'gameSoldiers':gameSoldiers,
                           'gameTowers':gameTowers,
                           'numHitsLeft':numHits*gameTowers,
                           'numKillsLeft':numKills*gameTowers}
        
        # keep iterating as long as there are towers and soldiers
        while totalHits>0 and gSoldiers>0:
            wave += 1
            # first the soldiers fire
            totalHits -= gSoldiers 
            # break if no tower is left
            if totalHits <=0:
                waveStats[wave] = {'gameSoldiers':gSoldiers,
                           'gameTowers': 0,
                           'numHitsLeft': 0,
                           'numKillsLeft': 0}
                break   
            # then the towers fire
            gTowers = (totalHits + numHits-1)/numHits
            
            if gSoldiers > numKills * gTowers:
                gSoldiers -= numKills * gTowers
                waveStats[wave] = {'gameSoldiers':gSoldiers,
                           'gameTowers':gTowers,
                           'numHitsLeft':totalHits,
                           'numKillsLeft':0}
            else:
                waveStats[wave] = {'gameSoldiers':0,
                           'gameTowers':gTowers,
                           'numHitsLeft':totalHits,
                           'numKillsLeft': numKills* gTowers - gSoldiers}
                gSoldiers = 0
                                   
        return waveStats

The idea of the algorithm is simple:
We compute the number of total hits the towers can take. That number is initially the product of each tower's hits by the number of towers.
Then as long as the number of total hits is greater than zero and the number of soldiers is also greater than zero (if one of these is zero or smaller than zero the game is over) we perform round after round of the game (each iteration of the while loop is one wave/round of the game).

In each round, first the soldiers still alive (gSoldiers) fire removing $gSoldiers$ hit points from the total of hits available.
Then the towers still available (gTowers) shoot back killing $ numKills * gTowers$ and leaving $gSoldiers - numKills * gTowers$ soldiers for the next round.

If however $numKills * gTowers$ is greater than $gSoldiers$, then the towers will only shoot $gSoldiers$ and keep the remaining $numKills * gTowers - gSoldiers$ (this will only happen in the last round of a game won by the towers).

A final note on how we compute the number of towers (gTowers) available after the soldiers shoot on each round. Intuitively we would divide the number of hits available by the number of hits per tower
$$gTowers = \frac{totalHits}{numHits}$$.

This works if totalHits is a multiple of numHits. If it is not a multiple it will give us a smaller number of towers. For example consider $totalHits=11$ and $numHits=5$. Doing $totalHits/numHits=2$ but obviously there are 3 towers (2 that can take 5 hits each and 1 tower that can only take 1 hit) not 2. Similarly if $totalHits=4$ and $numHits=5$ we get $totalHits/numHits=0$ but again there is 1 tower (that can take 4 hits points) instead of 0 towers. We see that this division always under-counts the number of towers by one when the two numbers are not divisible.

If we instead add $numHits -1$ to $totalHits$ before dividing the whole thing by $numHits$ we will be guaranteed to round the division by one. For the example above $totalHits=11$ and $numHits=5$ we get $(totalHits + numHits -1)/numHits=(11+4)/5=3$. And if $totalHits=4$ and $numHits=5$ we get $(totalHits + numHits -1)/numHits=(4+4)/5=1$.

It is important to notice that the number of towers destroyed can vary enormously.
For example imagine we have 2 towers with 4 hits each and 3 kills each and we have 5 soldiers. The 5 soldiers could shoot one of the towers twice and the other three times. Both towers would stay alive and would then kill the 5 soldiers in the first round.
In the approach we just presented, the soldiers will shoot one of the towers 4 times thus destroying it and shoot the second tower once (from our discussion above $gTowers = (3+3)/4=1$ is the number of towers at the end of the first round). That tower will go on to kill 3 of the soldiers and the game would go on to a second round where the remaining tower would still kill the remaining soldier.
In other words in the algorithm we presented the soldiers will always destroy (in each round) the maximum number of towers they can. Take some time convincing yourself that this is the case.

Below is the code. Press the Run button to execute the examples. It might take 3 or 4 minutes to run all 19 examples. Be patient and you will be rewarded (you can also delete/comment out a few of the tests in the all_tests list of the run_tests method and thus shorten the runtime quite a bit).

Lets look at the first test result

Executing test 0
Starting numbers
----------------
Number of Soldiers: 13
Number of Towers: 8
Total hits left: 16 (2 and 0 per tower)
Total kills Left: 24 (3 and 0 per tower)
                                            
End of Wave 1
Number of Soldiers: 7
Number of Towers: 2
Total hits left: 3 (2 and 1 per tower)
                                            
End of Wave 2
Number of Soldiers: 7
Number of Towers: 0
Total hits left: 0 (0 and 0 per tower)
                                            
Soldiers win in 2 rounds

We start with 13 soldiers and 8 towers. Each tower can take 2 hits (16 total) and can kill 3 soldiers per round (24 total). In the first wave, the 13 soldiers destroy 6 of the towers and leave 2 towers one with 2 hits left and another with 1 hit left. These two towers then kill 6 soldiers leaving 7.
In the second wave those 7 soldiers destroy easily the remaining two towers winning the game in two rounds.

You can also run some of the tests graphically using the game below. We will come back to this game in a future post.
One thing that you might notice (in particular in test 11) is that for some tests the result of the game is not the same!
If you run the last test a few times, the towers will win most of the times. There will be however a few times in which the soldiers will win.
This happens because the towers are placed randomly. Thus although most of the times the soldiers shoot at the closest tower sometimes two or more towers are within the same range of closeness to the soldier and therefore the soldiers shooting does not result in the maximum number of towers being destroyed in one wave. Instead the soldiers will spread their bullets evenly over two or three close towers leading to an extra tower to survive to the next round. In that case enough towers might survive each round that the towers have enough firepower to finally win.
Wins by the soldiers will happen when the towers are placed such that the soldiers shooting results in maximal number of towers destroyed.

An Algorithm to Minimize the number of Towers destroyed

It is interesting to consider the opposite case in which the soldiers try to destroy the least number of towers in a given round. Of course that is not in their interest but it is very much in the towers interest. Because the towers can only shoot after the soldiers they are at a disadvantage and will be happy to accept any give away.

Intuitively, to achieve this, the soldiers should spread their shots through all the towers (or as many towers as possible) instead of focusing their aim in as few towers as possible to destroy those few towers.
Lets consider the three different cases:

a) $gameSoldiers = gameTowers$

Soldiers should shoot each tower equally in the first round. If $numHits=1$ then all towers are killed. Otherwise since $numKills>0$ the towers will then kill all soldiers in the first round (because $numKills * gameTowers = numKills * gameSoldiers \geq gameSoldiers$).
So this strategy guarantees the soldiers defeat every time in the first round if $numHits>1$!
In fact in this case there is no way the soldiers can ever win even if they destroy the highest number of towers they can in each round. All they can do is prolong the game a few extra rounds: consider 2 towers, 2 soldiers, 2 numHits per tower and 1 numKills per tower. If the 2 soldiers destroy one of the towers then the remaining tower will leave one soldier and the game goes an extra round before that soldier is also killed.
Here it is a "proof" that the towers always win if $numHits>1$ no matter the soldiers strategy:

The number of towers destroyed in the first round is $gameSoldiers/numHits=gameTowers/numHits$. The number of towers that remain is then $gameTowers-gameTowers/numHits=gameTowers(numHits-1)/numHits=gameSoldiers(numHits-1)/numHits$. These remaining towers will then kill $numKills*gameSoldiers(numHits-1)/numHits$ soldiers. This is smallest when $numKills=1$. Lets assume that is true in the following.
At the start of the second round $gameSoldiers/numHits$ soldiers are left and $gameSoldiers(numHits-1)/numHits$ are left. If $numHits>1$ this is half or less of the soldiers. Lets assume then $numHits=2$ in order to maximize the number of soldiers. This will minimize the number of towers as well. So we have in the second round $gameSoldiers/2$ soldiers and towers (each tower with 2 numHits and 1 numKills). We are then in the same situation we started with (i.e. the same number of soldiers and towers) so we repeat the reasoning. The towers and soldiers are halved to $gameSoldiers/4$ entering the third round.
In general entering the $nth$ round there will be $gameSoldiers/2^{n-1}$ soldiers and towers.
Eventually there will be a round where only 1 soldier and 1 tower are left (assume for simplicity that $gameSoldiers=2^{n-1}$ so this will happen in round $n$). The soldier can shoot off one of the 2 numHits left and the tower will then kill the soldier. Game over!

b) $gameSoldiers < gameTowers$

In this case the $gameSoldiers$ should shoot $gameSoldiers$ towers. Assuming that $numHits>1$, all towers survive and given that $numKills>0$ they kill all soldiers in the first round.
If $numHits=1$ on the other hand it is possible that even with this bad strategy the soldiers will win sometimes: Suppose the game starts with 4 towers each with $numHits=numKills=1$ and there are 3 soldiers. The soldiers kill 3 towers. The remaining tower kills one soldier and it is then killed in the second round by one of the remaining two soldiers.

c) $gameSoldiers > gameTowers$

It is harder to find a strategy that minimizes tower destruction consistently. If $numHits=1$ then the soldiers win right away.
Otherwise if $gameSoldiers/gameTowers = n$ ($n$ being an integer) we can consider two cases:

If $n>=numHits$ the soldiers win right away.
If $n<numHits$ lets suppose n=2. Then at least half the soldiers are killed in the first round (if $numKills=1$; if $numKills>1$ more than half of the soldiers will be killed in the first round). The second round starts then with at least an equal number of soldiers and towers or more towers than soldiers and we fall in one of the previous two cases. If n=3 at least one third of the soldiers are killed in the first round (if $numKills=1$). The start of the second round is the same as the case n=2. Similarly for $n=4,5,...$ we can always reduce the problem to $n-1$ but starting at a later round. Thus if $n=10$ we know that the start of the second round can be reduced to the case $n=9$, the start of the third round can be reduced to the case $n=8$ and so on until the start of the ninth round can be reduced to the $n=2$ case.

We will leave to the reader to analyze the case were $gameSoldiers/gameTowers$ is not an integer.

This last section was intended to make us think a bit beyond the initial problem posed (how fast can the soldiers destroy the towers). Our analysis was not completely rigorous but it did provide a way to understand what the game outcome is depending on the relation between $gameSoldiers$ and $gameTowers$. The important takeaway is that it is useful to break a problem in steps and sometimes reduce some of those steps to previous steps that we are able to solve/reason about.

Tuesday, July 7, 2015

Tower Defense I

An Algorithm to Maximize the number of Towers destroyed

An Algorithm to Minimize the number of Towers destroyed

No comments:

Post a Comment