Flash Games

[zz1000zz]

I like playing flash games. They can provide good minor distractions. I especially like the variety available in them. However, I have a bad habit when I play them (the same habit I have for any game). This habit is analyzing game strategies. The more time I spend on a game, the more thought I put into "maximizing" my efforts. While this is completely normal, it has led me to wonder. What sort of framework is there in math for this sort of thing?

My current interest lies primarily with "tower defense" games. For those of you who may not have played these, the idea is simple. Enemies enter from one or more points, move across a field and exit at one or more points. The goal of the player is to prevent them from reaching the exits. This is done by creating "towers."

Depending upon the game, enemies may travel along set paths, or the player may create paths by placing towers. A common element to tower defense games is enemies which ignore the blocking effect of towers (such as ghosts or flying units). In the games where the player makes the paths, a rule is no tower can be placed if it will prevent enemies from moving to the exit.

Placing towers costs "points" of some sort, as does upgrading them. Towers have different types, and possibly different upgrade paths. For example, one tower type may be able to shoot single enemies at far distances for minor damage. Another tower type may have a shorter range, but hit an area, rather than a single enemy. Also common are towers which have negative effects on enemies, such as towers slowing their movement.

In any event, I am curious what sort of framework exists for this type of analysis. If I were wanting to something "rigorous," what sorts of math should look at? I doubt anyone would want to make a full model for a game, but I would think it wouldn't be too hard to create certain generalities.

Any insight, information or questions would be welcome.  

[zz1000zz]

The simplest place to start for this topic is probably a single tower and a single enemy. To begin, I will assume the enemy travels in a straight line at a constant rate, passing through the tower's range. The enemy's path through the tower's range would create a chord, the length of which could be calculated.

Dividing the chord's length by the enemy's rate of travel would give the amount of time needed for the enemy to get through the tower's range. This would make it possible to figure out how many attacks the tower would get (dividing the total time by the tower's firing rate). This number, multiplied by the damage of the tower, would give the total damage the tower would do to the enemy. Supposing it is greater than the enemy's HP, the enemy would be destroyed.

Quote:

Chord Length = L
Damage = D
Enemy's Rate of Travel = R
Firing Rate = F
Time = t

L/R = T
F * T = D
HP > D; Survived
HP < D; Destroyed

A slightly more complicated problem would involve multiple enemies. For this problem, it would be useful to know how many attacks the tower needs to destroy the enemy. This would be require dividing the enemy's HP by the tower's damage (taking the ceiling of the value). This number would be multiplied by the tower's firing rate to give a total time consumed by the enemy.

This process would be repeated for the next enemy, with the amount of time already consumed being subtracted from the time of the current enemy. If the enemy's do not come at the exact same time, a delay value would be added to the current enemy's time.

Quote:

Attacks Needed = A
Delay Period = P

A = ceiling(HP/D)
T = T1 - (A1*F) + P

By treating each enemy as an iteration in a series, different values can be passed to variables. This means each enemy need not have the same stats. What I wrote would only work for two enemies, but I know there is a much cleaner way to write it. I am horrible at using series notation, so I am hoping someone could rewrite this to work for any number of enemies.

Anyway, here are some thoughts. Limits need to be placed on some of values. Obviously the Delay Period adjustment cannot cause the total time to go over the individual enemy's base time. Also, this solution doesn't help if enemies survive. In a full solution, stats like current HP would be kept for each enemy, but that seems to needlessly complicate things for now.

My main problem is this approach only works for one tower. I am not sure how it would work with more than one tower if the tower ranges overlapped. You would have multiple series affecting each other with asynchronous starts. I know how to make a solution for any specific scenario, but I have no idea how to make a general solution.  

[Mecill]

I saw someone playing one of these once... (Haven't tried many flash games myself, because I tend to get distracted enough with just Gaia and solitare.) But regarding math and games, it sounds like it might be a form of game theory. I find it amazing that there is a whole field of math concerning the study of games. I recently got a reference book which has a section on game theory I am intending to read for fun sometime.  

[zz1000zz]

Mecill

I saw someone playing one of these once... (Haven't tried many flash games myself, because I tend to get distracted enough with just Gaia and solitare.) But regarding math and games, it sounds like it might be a form of game theory. I find it amazing that there is a whole field of math concerning the study of games. I recently got a reference book which has a section on game theory I am intending to read for fun sometime.

I am somewhat acquainted with game theory. An unfortunate effect of game theory is any mathematical description of a game tends to make people think "game theory." With that said, I am not sure how much game theory would apply to this situation. Nothing I have learned in game theory seems applicable to this problem. My knowledge on the subject is limited, so there could easily be viable applications.

What I have noticed for this issue is I know how to program things which I do not know how to describe mathematically. Adding linear sequences is pretty easy in programming if you use loops, but that doesn't seem like a "solution."  

[Layra-chan]

Game theory is usually applied to multiple agents each with something to optimize. This is not one of those cases; there is only one agent here and the enemies probably don't try to optimize their troop movements based on where they guess your towers would be (or at least not in response to where your towers are).

I think you're missing some variables.

Let's first ignore effects other than damage and consider for the moment only towers that don't do area damage.

Time (since first enemy enters attackable range): t

Per enemy Ei:
Time entering the field: ei
Initial health at time t: Hi(t)
Position at time t: Xi(t)

Per tower Tj:
Rate of fire: Fj
Velocity of projectile: Vj
Damage done by tower in one shot: Dj
Region of influence (relative to tower): Rj
Position: Yj


I think that instead of looking at towers and what they cover, it might be better to divide the field into regions and optimizing for coverage, i.e. how much damage can be done to a given region in a given amount of time. I think this makes more sense when there are towers that do different amounts of damage.

So given a region R within the regions of influence of towers {Tj} (i.e. R is contained in Rj+Yj), we get that if the towers just shoot continuously, the total damage per time is

Σ Fj*Dj

So if a set of enemies {Ei} enters the region R at time t0 with total health

Σ Hi(t0)

then if they stay within R until
t0 + (Σ Hi(t0))/(Σ Fj*Dj)
we can expect them to die.  

[zz1000zz]

Am I missing something, or does that approach not work for more than one tower? Tower ranges would only overlap in part (if at all), so I don't see how that approach could be applied to more than one tower at a time.

I suppose you could use multiple regions, but that would quickly get out of hand.  

[Layra-chan]

I suppose you'd have to scale the attack rate of each tower by the proportion of the tower's attack range the region actually takes up.

So I guess it would end up being total damage per time would be (on average)

Σ Fj*Dj*|R|/|Rj|

Or something like that, assuming the towers just fire randomly at whatever is in their range.
So for larger regions, i.e. regions that aren't contained in the Rj+Yj for all j in some index set, we can write

Σ Fj*Dj*|R∩Rj|/|Rj|

where j ranges over the set of all towers.  

[zz1000zz]

I've been giving this issue (and Layra-chan's posts) some thought, and I think I have a decent enough solution. I approached this in two steps. First, I considered the question of what if all towers hit all enemies within their range.

The first thing I realized I could treat any maze or path as a straight line. The next thing I realized was the solution would be much easier if I standardized all the firing rates. By picking one firing rate, and adjusting any other firing rates to be equal to it (modifying damage to keep things equal), things are greatly simplified. The final thing I realized is I can ignore any visual measurements in the game. Rather than use those, I decided to measure distance in "time an enemy travels per shot." With distance and firing rate being simplified thus, the problem is much easier. Range can be modeled by giving numerical ranges, such as saying tower damage equals three over a range of (2,4). With this approach, all that is needed is a list of simple formulas.

With these changes, the current position of an enemy is easily describe as t - n + 1, where "n" is the number of the enemy. Of course, this assumes each enemy is spaced out at the arbitrary distance being used, but it can easily be scaled as necessary. Once the position of an enemy is known, it is simply passed through each tower's damage formula, with the results being summed. The total damage any enemy has suffered at any time could thus be given as:

ΣdT(t - n + 1)

While this is somewhat useful, it doesn't work for single-target towers. My solution for that issue is somewhat similar, but I am somewhat uncertain about it. If D is total damage, the total damage to a wave at any given time would be:

Dw = ΣdT(t - L, t + l)

l would be the length of the wave, while L would be the length lost. Adding the length of the wave to the position calculation is an obvious and easy step. Subtracting the length lost is important, but less easy. It would have to use a proportion health lost (on the previous iteration?) to total health. While complicated, I think it is necessary as otherwise the tower ranges wouldn't work properly.

With this solution, towers could easily be added, modified and removed. It is pretty simple, and it shouldn't have too large a margin of error. There are two main issues I see contributing to the error in it. One, total damage to a wave will be overestimated if more damage is dealt to a single enemy than needed to destroy it. The larger damage is in proportion to enemy health, the larger this error would be. Two, the length lost variable will be overestimated if damage is spread out amongst the targets. Because these two sources of error are in opposite direction, and because I don't expect them to be particularly large, I think they can just be accepted.

Anyway, I am typing this up right before heading out, so it is a bit rushed. Hopefully my explanation is clear enough to understand my thoughts.

Edit: There is a question I wanted to ask. In my second solution, I wanted to be able to pass a set of values to the tower damage formulas, each of which has a range. How do you write that out?

Second Edit: I feel like there should be a better way to handle the L variable. I don't like the idea of having to make reference to earlier times, but I don't see how it could be avoided. Any thoughts?  

[Layra-chan]

The dependence on the number of enemies still alive is troublesome. Does the total amount of damage a tower can do actually depend on that? Neither the firing rate nor the damage per shot should depend on the total number of enemies within the tower's range. The only dependence should be whether there are any enemies at all in the range where the tower does positive damage; keeping track of the exact range of the enemies positions doesn't really help for a single tower.
The enemies that die will be at the front of the wave, while enemies will be pouring into the tower's range from the back, so the enemies that die don't matter unless all the enemies get killed; the tower's going to keep firing until either the last enemy has passed through the end of the far end of the tower's range or died.

If we let the range of the tower be [1, k], the number of hits needed to down an enemy h, and the initial number of enemies in the wave be n, then the time the last enemy leaves (or dies), will be at either t = n+k (the last enemy escapes) or t = nh (the last enemy dies), whichever comes first.
The total amount of damage inflicted will be (n+k)/h or n, where we normalize the enemies' health to 1. For t < n+k and t
Of course, this becomes really complicated really quickly if there are more than one tower, but that's going to happen regardless.  

[zz1000zz]

For a single tower, the problem is simple, as you discussed. However, I don't see any way to ignore the number of enemies issue once you go over one tower. The solution I offered is the simplest solution I could come up with for multiple towers.

While it may be computationally cumbersome, it seems easy to express and code.