In the last post we considered a simple version of a tower defense game.There were gameSoldiers, gameTowers and each tower had numHits it could take before crumbling and numKills soldiers it could kill in each round. Soldiers would start each round by shooting at a random tower removing one of its numHits. After all soldiers had fired, the remaining towers would shoot with each tower killing numKills soldiers.
In this post we will consider a slightly different variant of the game:
- A castle is attacked at sunrise, by surprise by a group of gameSoldiers soldiers.
- Each soldier carries a canon and a rifle.
- The castle has castleHits strength, i.e. it can take castleHits before it crumbles.
- In the first day, all soldiers fire their canons at the castle decreasing its strength to \(castleHits-gameSoldiers\).
- Assuming the castle still has \(castleHits>0\), it will then send their own defendersPerWave soldiers per day/wave/round.
- In the beginning of each day/round/wave, the soldiers shoot and each soldier can either hit the castle with a canon subtracting one of its castleHits or the soldier can kill one of the castle defenders (if there are any) with its rifle.
- After all soldiers have shot, the total k castle defenders shoot killing k of the soldiers (assuming there are k soldiers, if there are less then the defenders shoot however many soldiers there are and the castle wins the game).
- If at this point the castle is still up and there are still soldiers, the castle will send defendersPerWave which will add up to whatever defenders are still out from previous rounds. I.e. at the end of each round the castle will send a fresh batch of defendersPerWave as long as castleHits>0.
- Notice that since the soldiers attack the castle by surprise, at the beginning of the first round the castle has not sent any of its defenders out (but it will at the end of the first round).
- The game ends with a win for the soldiers if both the castle and all of its defenders are dead and one or more of the soldiers is alive.
- It ends with a win for the castle if no soldiers are left and either \(castleHits>0\) or the number of defenders is > 0 (or both).
- The previous point says that it is possible for the castle to win the game even if it has zero castleHits points as long as there are no soldiers left and there are one or more defenders left (presumably the defenders could then rebuild the castle).
If the soldiers can not win the game we would still like to know in which round will the castle prevail.
And we would like to keep track of the remaining gameSoldiers, castleHits and total number of defenders at the end of a round (which is the same as at the beginning of the next round). This will be, in general, greater than just defendersPerWave since some defenders remain from previous rounds.
REASONABLE SOLUTIONS: Attack the castle first or attack the defenders first
We can try to simulate what happens in each wave like we did in our previous post.
It seems that a possible best strategy to destroy the castle in the minimum number of waves/rounds is the following:
- If the number of soldiers in the wave is greater or equal than the castleHits, we have castleHits of the soldiers shoot at the castle causing it to lose all of its hit points. The remaining soldiers (i.e. \(gameSoldiers - castleHits\)) than shoot at any existing defenders (if \(gameSoldiers-castleHits \geq defenders\) the soldiers win the game in that wave).
- If the number of soldiers in the wave is smaller than the castleHits but greater than the number of defenders, we have the soldiers eliminate all of the defenders and any remaining soldiers shoot then at the castle (that way the castle defenders can not shoot at the soldiers in that round).
- If the number of soldiers in the wave is smaller than both castleHits and the number of defenders, we have the soldiers shoot at the castle.
def attackCastle(self,gameSoldiers,castleHits, defendersPerWave):
totalDefenders = 0
waveStats = {}
wave=0
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
wave = 0
while True:
wave += 1
# case a: castleHits <= gameSoldiers
# gameSoldiers first fire at the castle.
# causing castleHits to go to zero;
# the remaining gameSoldiers - castleHits soldiers
# then fire at any defenders
if castleHits <= gameSoldiers:
totalDefenders -= gameSoldiers - castleHits
castleHits = 0
if totalDefenders < 0:
totalDefenders = 0
# case b: castleHits > gameSoldiers and gameSoldiers>totalDefenders
# the soldiers
# first shoot all the defenders and the remaining
# soldiers then shoot at the castle
elif gameSoldiers > totalDefenders:
castleHits -= gameSoldiers - totalDefenders
totalDefenders = 0
# case c: castleHits> gameSoldiers and gameSoldiers<= totalDefenders
# the soldiers shoot at the castle
else:
castleHits -= gameSoldiers
if castleHits < 0:
castleHits = 0
if castleHits == 0 and totalDefenders == 0:
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
return waveStats
# castle defenders kill as many soldiers
# as there are defenders
gameSoldiers -= totalDefenders
if gameSoldiers <= 0:
gameSoldiers = 0
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
return waveStats
# castle sends another set of defenders out
if castleHits > 0:
totalDefenders += defendersPerWave
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
Although this simulation algorithm seems reasonable and works often it also fails sometimes. In fact following this strategy it will lead sometimes to the soldiers losing the game when they could win it with a different approach.
Consider for example the case where there are initially 10 gameSoldiers, castleHits=43 and the castle sends 8 defendersPerWave.
- In the first wave, the 10 soldiers reduce castleHits by 10.
- The second wave starts therefore with 10 gameSoldiers, castleHits=33 and totalDefenders=8. Since \(gameSoldiers>totalDefenders\) and \(gameSoldiers<castleHits\), 8 of the soldiers kill the 8 defenders and the other 2 soldiers reduce castleHits to 31. The castle sends another 8 defenders.
- In the third round again 8 of the soldiers kill the 8 defenders and reduce castleHits to 29. Another 8 defenders are sent out.
- This pattern repeats itself in the 4th (castleHits=27), 5th (castleHits=25), 6th (castleHits=23), 7th (castleHits=21), 8th (castleHits=19), 9th (castleHits=17), 10th (castleHits=15), 11th (castleHits=13), 12th (castleHits=11) and 13th (castleHits=9).
- In the 14th wave because \(castleHits<gameSoldiers\), the algorithm above makes 9 of the soldiers reduce castleHits to 0 and it makes the remaining soldier kill one of the defenders.
- The 7 defenders then kill 7 of the soldiers. Since the castle is "dead" it will not send any more defenders.
- In the 15th round, the 3 remaining soldiers kill 3 of the 7 defenders and the remaining 4 defenders then kill the 3 soldiers with the win going to the castle.
- Notice how the castle has crumbled in the 14th wave but it still wins the game because 4 of its defenders remain and all soldiers were killed.
- Everything proceeds as described above up to the 13th wave.
- In the 14th wave, again 2 of the soldiers should shoot the castle leaving it with 7 castleHits points and the other 8 soldiers should kill the 8 defenders.
- In the 15th wave, 7 of the soldiers vanish the castleHits points and the remaining 3 soldiers kill 3 of the defenders. The remaining 5 defenders will kill 5 of the soldiers.
- Finally in the 16th wave, the remaining 5 soldiers kill the 5 defenders and win the game.
Another seemingly good algorithm is one that always has the soldiers killing as many defenders as possible, with the remaining soldiers shooting then at the castle. This would not lead to the correct minimum for the example above: the game would go on to a 15th wave (castleHits=5), 16th (castleHits=3), 17th (castleHits=1), 18th (castleHits=0, all 8 defenders killed and all 10 soldiers standing still). So the soldiers would win but in 18 days/rounds/waves instead of the minimum 16 waves.
Intuitively it is clear that while this approach protects the soldiers from the defenders it is not the fastest possible (in fact it will be the slowest possible). If the question we were trying to solve were "which approach/algorithm leads to the least number of soldiers killed" this would indeed be a good candidate.
In code this algorithm looks like this
def attackDefenders(self,gameSoldiers,castleHits, defendersPerWave):
totalDefenders = 0
waveStats = {}
wave=0
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
wave = 0
while True:
wave += 1
# case a: There are (at least) as many totalDefenders
# as gameSoldiers so the gameSoldiers
# all shoot at the defenders, then the
# remaining defenders shoot back
if totalDefenders >= gameSoldiers:
totalDefenders -= gameSoldiers
gameSoldiers -= totalDefenders
# case b:There are more gameSoldiers than defenders
# so the soldiers kill all defenders and the
# remaining soldiers shoot at the castle
elif castleHits >= 0:
castleHits -= gameSoldiers - totalDefenders
totalDefenders = 0
# case c: There are more gameSoldiers than defenders and
# castleHits=0. The soldiers shoot all defenders
# (and win the game)
else:
totalDefenders = 0
if castleHits < 0:
castleHits = 0
# soldiers win
if castleHits == 0 and totalDefenders == 0:
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
return waveStats
# castle wins
if gameSoldiers <= 0:
gameSoldiers = 0
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
return waveStats
# castle sends another set of defenders out
if castleHits > 0:
totalDefenders += defendersPerWave
waveStats[wave] = {'gameSoldiers':gameSoldiers,
'castleHits':castleHits,
'defenders':totalDefenders}
# prevent infinite loops
if wave>50:
return waveStats
As this example shows, the simple algorithms we described above do not work for every initial values of gameSoldiers, castleHits and defendersPerWave. We should keep looking.
Before we move on to look at an algorithm that does solve the problem correctly in all cases, lets write down the code we have so far.
The code is organized in 3 files:
castledefense.py: This is where the 2 algorithms above are (encapsulated in class CastleDefenseI) in two methods called attackCastle and attackDefenders (this one to reflect the fact that the soldiers primarily shoot at the defenders and only then at the castle).
tests.py : This file contains all tests (encapsulated in class CastleDefenseITest). In particular the example discussed above at length is the last one: test_26. Note how tests.py imports CastleDefenseI in order for each test to be able to access both of the methods attackCastle and attackDefenders .
main.py: This file simply creates a CastleDefenseITest object and runs its runTests method.
If you press run you can see which tests fail and which ones are correctly solved by one or both of the above two algorithms (you will need a little patience to run all 26 tests; if your browser freezes let the script keep running for about 1-2 minutes).
I summarize the results in the following table.
The cells highlighted in red indicate the algorithm predicts the wrong side will win (i.e. the castle will win when in fact there is a minimum number of rounds that lead to a win by the soldiers).
The cells highlighted in cyan indicates the algorithm predicts the correct side wins or ties but it takes more moves/rounds than the minimum.
| Test Number | Test Values | Min Rounds | Rounds for attackCastle | Rounds for attackDefenders | |||
|---|---|---|---|---|---|---|---|
| 0 |
|
Soldiers win in 4 | Soldiers win in 4 | Castle Wins in 3 | |||
| 1 |
|
Castle wins in 2 | Castle wins in 2 | Castle Wins in 3 | |||
| 2 |
|
Soldiers win in 9 | Soldiers win in 9 (1 soldier standing) |
Soldiers win in 9 (2 soldiers standing) |
|||
| 3 |
|
Soldiers win in 2 | Soldiers win in 2 (11 soldiers standing) |
Soldiers win in 2 (11 soldiers standing) |
|||
| 4 |
|
Soldiers win in 4 | Soldiers win in 4 (12 soldiers standing) |
Soldiers win in 4 (12 soldiers standing) | |||
| 5 |
|
Soldiers win in 7 | Soldiers win in 7 (10 soldiers standing) | Soldiers win in 7 (12 soldiers standing) | |||
| 6 |
|
Soldiers win in 4 | Soldiers win in 4 | Castle wins in 4 | |||
| 7 |
|
Castle wins in 2 | Castle wins in 2 | Castle wins in 3 | |||
| 8 |
|
Soldiers win in 2 | Soldiers win in 2 (8 soldiers standing) | Soldiers win in 2 (8 soldiers standing) |
|||
| 9 |
|
Soldiers win in 3 | Soldiers win in 3 | Castle wins in 3 | |||
| 10 |
|
Soldiers win in 4 | Soldiers win in 4 | Its a tie! | |||
| 11 |
|
Soldiers win in 37 | Castle wins in 33 | Soldiers win in 41 | |||
| 12 |
|
Soldiers win in 8 | Castle wins in 6 | Soldiers win in 9 | |||
| 13 |
|
Soldiers win in 2 | Soldiers win in 2 | It's a tie! | |||
| 14 |
|
Castle wins in 2 | Castle wins in 2 | Castle wins in 2 | |||
| 15 |
|
Soldiers win in 4 | Soldiers win in 4 | Castle wins in 3 | |||
| 16 |
|
Castle wins in 2 | Castle wins in 2 | It's a tie! | |||
| 17 |
|
Soldiers win in 22 | Castle wins in 18 | Soldiers win in 25 | |||
| 18 |
|
Soldiers win in 11 | Castle win in 8 | Soldiers win in 14 | |||
| 19 |
|
Castle wins in 2 | Castle wins in 2 | Castle wins in 2 | |||
| 20 |
|
Soldiers win in 13 | Soldiers win in 13 (2 soldiers standing) |
Soldiers win in 13 (7 soldiers standing) | |||
| 21 |
|
Soldiers win in 7 | Soldiers win in 7 (5 soldiers standing) | Soldiers win in 8 (19 soldiers standing) | |||
| 22 |
|
Soldiers win in 12 | Castle wins in 8 | Soldiers win in 16 | |||
| 23 |
|
Soldiers win in 15 | Soldiers win in 15 (2 soldiers standing) | Soldiers win in 15 (3 soldiers standing) | |||
| 24 |
|
Soldiers win in 49 | Soldiers win in 49 (1 soldier standing) | Soldiers win in 49 (2 soldiers standing) | |||
| 25 |
|
Soldiers win in 17 | Castle wins in 16 | Soldiers win in 18 | |||
| 26 |
|
Soldiers win in 16 | Castle wins in 15 | Soldiers win in 18 |
Here are some interesting facts we can glance from this table:
- There are a few tests in which both algorithms agree with the minimum number of rounds (soldiers win) but the attackDefenders algorithm always leaves more soldiers alive than the attackCastle approach.
- If the castle wins it wins in 2 rounds always.
- When the castle wins, the attackCastle algorithm always predicts correctly the castle win in 2 rounds.
- The attackDefenders algorithm also predicts correctly that the castle wins but sometimes it takes 3 rounds.
- When the attackCastle algorithm predicts the soldiers win it always takes the minimum number of rounds (and therefore it is always correct in those cases). The attackDefenders algorithm will in several tests require more rounds for the soldiers to win.
- The attackDefenders algorithm will sometimes lead to a tie (in tests 10, 13 and 16) while the attackCastle will never lead to a tie. If you look at the algorithm code you will notice a condition at the very end of the infinite loop
# prevent infinite loops if wave>50: return waveStats
to prevent the loop of never ending in cases where there is a tie.
In our next post we will look at a couple of approaches/algorithms that solve this problem correctly always.
Hi! You know, im trying to explain "for Dummies" Django development, would you give a hand and check my site?
ReplyDeleteAny comment and tip will be appreciated.
Thanks!