Simulations can provide curious insights; in this case a distinct advantage to winning a game. I recently encountered a perfect opportunity to run a simulation on the game “Bloons TD Battles”. There is a “money” aspect and I wanted to know what strategy would be best. Since the rules are quite simple, at least part of them, it shouldn’t be too hard to code.
The full code can be found here. It’s written in C++ using a few C++11 features. I’ve also put it up at ideone for quick experimentation.
The Game
This tower defense game has a two-player “defensive” mode. You and another player attempt to hold off an onslaught of balloons. The person who lasts longer wins. You can either buy towers (monkeys in this game) or invest the money to increase your income. It’s a somewhat tricky balance: lots of things to buy, four investment plans to choose from.
Each investment plan has an upfront cost and a revenue increase amount: spend money now to gain back more over time. The lowest plan is $50 for $2 income: spend $50 and at each income interval you get an additional $2. The next plan is $300 for $15. At first it looks better: buying 6 of the lower plan would cost the same, but get you less return ($12 as opposed to $15). The trick is that you normally don’t have enough money to buy the higher plan and would be forced to wait. During that waiting time you could be compounding more money with the lower plans.
The Plans
That was my basic question: is it worth it to wait for the higher plans? This is what I addressed first in my simulation. My initial results seemed a bit off due to a missing variable. Each time a plan is purchased it has a cool-off time before it can be purchased again. Watching the game I noted the numbers and created a plan data structure.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
struct plan { //plan acquisition cost int cost; //resulting increase in revenue int increase; //timeout before repeat purchase int regen; }; std::vector<plan> plans({ { 50, 2, 4 }, { 300, 15, 13 }, { 1000, 70, 60 }, }); |
Money in the game is an integral value therefore all monetary values are using int. There is also a fourth plan, which costs a lot more, that I’ve omitted. In practice you never have enough money to buy it: I was unable to determine it’s regen timeout.
Game State
A simulation requires a state. This state is modified on each iteration of the game. Here I use a 1-second interval as it matches the precision needed for this game. My state structure looks like below, plus several member functions to manipulate it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
struct game_state { // how much money we have now int money; //income on each income interval int income; //total money we had/have int total; //money spent on upgrades int spent; //money invested for income int invested; //block purchase of the plan for regen time std::vector<int> plan_timeout; //total elapsed time int time; |
A step function does the one-step iteration. It adds the income to the money and updates the tracking stats. Additionally it iterates over the plan_timeout to model the plan purchase lockout time. My state object thus also models the core mechanics of the game. Often one finds the state as independent data and a separate driver class modifies it. If the rules of the simulation are complex that would be required, but here the rules are simple enough, and static, to be situated in the state class.
Strategy
With the basic modelling complete a strategy is now required. A strategy models the player’s behaviour in the game. At each step in the simulation the strategy is called and allowed to perform its actions. This is the perfect scenario for polymorphism with inheritance and a virtual function.
1 2 3 4 5 6 7 8 9 10 11 12 |
struct strategy { void step(int spend) { /*common behaviour*/ . . . state->step(); step_impl(); } virtual void step_impl() = 0; }; |
The approach I’ve taken is to implete a step function as well as a virtual step_impl. This allows me to implement common behaviour across all strategies in the base class and specialized behaviour in derived classes. I’ve also also chosen to store the state directly in each strategy; the strategy step function is responsible for calling step on the state. I don’t believe in overdoing the design and this setup is sufficient for this simulation.
Baseline Strategy
A couple of basic strategies establish the baseline for our simulation. The first is the buy_none strategy which never invests in any plan. It sticks with the starting income level for the duration of the game. The second is buy_all which buys every plan it can whenever it can.
Before I show any results I must explain the stats I track first. The total money in the game is the total amount of money the player ever had (starting money plus all income). It’s actually not an interesting number. The spent money is more interesting. It tracks how much money was actually spent on building defenses — without these you lose quite quickly. In my initial version no money was “spent” though, so this number is just how much money was left over at the end. It is essentially the disposable income, and it is the interesting number.
For the first round the buy_none strategy ends up with only 3950 spent, and the buy_all has 9060. Clearly investing looks better.
Spending
Investment is obviously not the goal of the game. You need to build defense to block those pesky balloons from getting past. This means a strategy that doesn’t consider spending may not be valid. The ideal way to spend the money is not easy to simulate as there are a lot of factors involved. However, I can estimate roughly what the rate of spending must be.
I created a very simple formula of multiplying the elapsed time by a constant factor. At each interval the baseline strategy ensures it has spent at least this much money. If not enough money is available it will check again next interval.
Adjusting the value does change the results. Lower values tend to improve the value of investing. That is of course at the expense of possibly letting balloons through and loosing.
Fixed plans and stopping
I added a few other simple strategies that purchase only one particular plan. Here it came out that buy_all and buy_plan_1 looked to be quite comparable in spent money. I realized though that it doesn’t make sense to invest right up to the end of the game: a certain period of time is needed to recoup the investment. I needed a strategy that stopped investing after some point.
This is a modification to all existing strategies. Rather than complicate the hiearchy I just added a stop_when variable to the base strategy and introduced a should_buy_plan function.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
struct strategy { //stop investing at this time, if -1 then never stop int when; . . . virtual bool should_buy_plan( int i ) { if( stop_invest_when >= 0 && state->time >= stop_invest_when ) { return false; } return state->can_buy_plan(i); } }; |
When to stop depends highly on how long the game actually lasts. So far my games have been topping out at seven minutes. I run the simulation with a variety of stopping times. Stopping at 240s is roughly ideal for the buy_all strategy, and at 300s for the buy_play_1 strategy. They both have roughly the same spent money. Interesting though is that stopping at 180s for buy_all is only 2% less money. Since the game is hectic it is helpful to stop earlier and focus on other things.
Conclusion
The results are somewhat unfortunate. Investing is clearly meant to play a significant role in the game, but the influence is quite limited. A good strategy is to buy whatever plan you can, whenever you can, and stopping around half-time. Changing many of the constants in the simulation change the total money spent, but the same strategy is usually one of the best. It is also has the great advantage of being very flexible: you are never waiting to accumulate money to invest.
Finding this desired strategy is of course the purpose of the simulation. I also just enjoy writing simulations; they are somewhat different from my typical daily programming tasks.
