Ceasar's Mind

Follow me: @Ceasar_Bautista

Posts Tagged ‘rts

Command 0.02

leave a comment »

The initial AI failed because nodes failed to consider the strength of their moves beyond attacking the nodes that they were immediately connected to. This version attempts to fix that, using a depth first search on each node:

The AI still has a way to go though. It makes no effort to keep track of how many units it has sent to a node, often sending more than it should. On the same note, it makes no effort to keep track of how many units the player has sent to a node, or for that matter, could send. Hopefully I can fix that soon.

Basically, it works like this: First it selects a blue node to analyze, then it finds all of its neighbors (called children). If the any of the children are not blue or don’t connect anything except for the parent, then it scores the node by figuring out how much time it would take to capture the node. If the node is blue and has children of its own however, then it analyzes that node, but all the while keeping track of the ancestors so that the current generation doesn’t mistake an ancestor for one of it’s children, preventing infinite loops in the search.

However, through testing the AI I encountered a few problems. Perhaps the worst thing was that I had labeled all my variables weird names, which made it very difficult to track what was going on. When my code performed badly, it was extremely hard to debug because I had not only had to figure out what each variable was doing, but I also had to figure out what variable was keeping track of what. So the point here: Make sure you label stuff nicely. Typically, it’s okay to use shorthand in keeping with your style, but for complicated stuff save your self the trouble and label things nicely.

Secondly, while going through the search the AI actually would overwrite the values of nodes sometimes, so I had to make special variables just to keep track of the scores of the nodes at each level of search.

Written by Ceasar Bautista

2010/07/16 at 19:37

Progress

leave a comment »

So it’s been kind of quiet here lately, and that’s because I’ve been studying up on Java so that I could develop a proper game in order to develop a proper AI. The game here (currently titled “Command”) is based off of Little Stars for Little Wars, almost exactly at the moment, although I have a few minor plans for the future. Anyhow, here is a quick demo:

As you can see, the AI is still in need of work (I just put that together hours ago). But I’m excited for the prospects!

Currently, the AI works by making a list of all the planets it is connected to, and then scoring them. The score is calculated by dividing the gains by the costs. The gains in most cases is the additional production, except of course if the planet is already owned by you. The costs include the distance, the current strength, and the projected strength of the planet when the army arrives. The depth as you can tell, is still rather shallow though, which is why the AI functions so oddly in the video.

Also, I should note, that this AI will be used plainly to understand macro level decision making. I suppose I will have to play around with it in the future in order to make it simulate real conditions a bit better, but at the moment it ought to give a fairly decent idea of how to one should manage armies strategically.

Written by Ceasar Bautista

2010/07/13 at 23:41

Prioritizing Targets

with one comment

Not sure where this belongs exactly yet, but I figured it was worth mentioning. In regards to all of these Hit Points and Damage things, there is a way to prioritize which targets you take out besides what’s most convenient and it’s simple really: Determine which unit is dealing the most damage per hit point, and kill him first.

Take for example, Halo 3. Consider you encounter the two enemies above simultaneously. The one on the left is called a Hunter, armed with a large Assault Cannon, and on the right is a Grunt, armed with a Fuel Rod Cannon. Both weapons are extremely dangerous. However, the Hunter is very difficult to kill, possessing thick armor and a large metallic shield on his left arm which no projectile can penetrate, while the Grunt is very easy to kill, possessing no armor and very little hit points.

The decision before you is this: To target the Hunter first and attempt to dodge both weapons while attempting to find a weak spot in its armor,  or to shoot at the Grunt and kill him quickly and then to fight the Hunter alone. Not much of a choice unless you like a challenge.

Mathematics tell us to take exactly the same course of action in RTS battles. Put simply, to figure out which unit to strike first, determine the DPS of all enemy units and divide it by their hit points and then strike the unit which has the highest result. Usually though, this is intuitively obvious.

Factor in Capital

In strategy games though, there is also capital. That is, while in most cases a damaged unit can be regenerated or repaired, sometimes even for no cost besides time, a dead unit stays dead, and is a permanent loss of resources. With this in mind, the priority can shift to striking the unit with the highest cost to hit point ratio.

Ultimately, it comes down to whether or not you can successfully ensure a kill. If it’s not possible, then it’s best to prioritize by damage to health ratios in order to preserve the hit points of your force. Otherwise, it’s significantly better to take out what you can and then regenerate your units before fighting again on much less level ground.

Why Cheap Units Are Still Useful

The idea of worrying about capital losses usually means trying to invest minimally in weak units since they die very easily. I’ve often wondered if I should make a new formula to adjust for this problem, making expensive units less and less cost effective. I think though that cheap units are underestimated. The one power that they have over their more expensive counterparts is that they can be in multiple places at once. Utilized correctly, this feature can overwork an enemy defense and allow you to penetrate where a more expensive force couldn’t. (The trick is to set it up so that the cheap provides provide an extra kick for your other more expensive units, making each one more powerful individually, and then striking the enemy. He’ll be unable to divert his resources as necessary since they are all centralized in expensive units.) However, this is based off of my experiences with Naval Commander, which accidentally was balanced “incorrectly” since the attack mechanism would choose a random target in range instead of focusing on the weak units, effectively making the strength of units scale linearly. I’ll have to play with the idea a little more in the future.

Written by Ceasar Bautista

2010/06/21 at 23:56

Flanking – Part 1

leave a comment »

With the math behind pricing in mind, it’s obvious that forces grow in strength exponentially with each unit in the party. Not only is our force stronger though, but we take less damage. However, party strength is limited by space. If a unit can’t get the enemy in range, he can’t help the party.

Basics

The basic idea here is rather simple. All of that math explained before assumes that all units in a force can attack. But that isn’t necessarily the case. What battles are really all about are creating situations where you have more units attacking than your opponent does.

The simplest and perhaps most common of these scenarios is the flank of a line formation. In the image to the right, the black army is positioned to flank the white army. All three of the black units can attack the bottom white unit, but only the bottom white unit can strike back. The other two white units don’t have any targets in range.

If white does not react quickly, black will fight each unit individually, and crush all three of them losing only one unit in the process.

(Line formations are extremely effective at flanking because of their ability to wrap around vertices, but their vertices are also extremely vulnerable.)

The Impact of Formation

Besides the actual size of units, formation can affect the effectiveness of an enemy flank. Consider the two images presented here.

In the image above, four black units are surrounded by an army of white. Due to their shape, they reduce up to 16 attacks down to 8.

Now consider this second image.  In it, an army of nine black units fend off a larger army of white. Due to their shape however, they reduce up to 36 attacks down to 12.

Notice the number of vertices stays the same despite the increasing amount of units. Side length increases instead, decreasing the percentage of your units being flanked. Consequently, bigger shapes are better. Furthermore,  if the terrain is favorable, it can sometimes be possible to construct a straight line from one impassable point to another, eliminating vertices altogether!

This knowledge is particularly useful when using units that are expensive since, at least in my experience, they are balanced assuming that the enemy strikes in full force. By rearranging your army’s formation or exploiting impassable terrain, you can force enemy units to strike individually and increase the effectiveness of your units exponentially!

The Impact of Range

Besides collision size, the other factor that affects a player ability to flank is range. Basically, more range means more unit can sit along the circumference of the range from the target, and increase the effectiveness of a flank. Furthermore,  if a group of units possess a range greater than their targets, not only will they able to position themselves along a wider circumference, but units can position themselves in a series of lines, drastically increasing the effectiveness of their attacks.

In the picture above, the white army has a small range, and the circumference along which they can align is also fairly tiny.

Compare the above picture to the previous one. In this, the white army has significantly increased attack range, permitting many more units to join in the attack.

Because of this property of Range, it can easily disrupt the balance of games. Given enough time, a patient player might construct an large army of long-ranged units that knock-out enemy units before receiving any return fire, instantly spelling defeat for his opponent. (I’ve seen this happen in many Tower War games, including my own Expansion. But this is not at all an uncommon phenomenon.)

Conclusion

So basically, at this point, it should be obvious that besides collision size, formation and range can impact the effectiveness of a flank.

Written by Ceasar Bautista

2010/06/17 at 21:33

Posted in Uncategorized

Tagged with , , , ,

Balancing Forces

leave a comment »

Let me start this post with an email from my friend Vinh, as he explains the core concepts of force strength particularly well.

This formula relates n amount of Unit 1, and n amount of Unit 2. I call it the “N vs N” formula where N obviously stands for the amount units.

Basically I started with this formula:

H1*D1 = H2*D2

But what would happen if there are 2 of Unit 2? Lets call these two units “Force 2.”

Intuition would tell me to multiply the attributes of Unit 1 by 2, in order to balance the two forces. However, if we just plug in numbers we can see that this doesn’t work out. Force 2 will still have an edge.

We can demonstrate this with a scenario.

H1*D1 = H2*D2

H1 = 100 H2 = 50
D1 = 1 D2 = 2

Since there are 2 of Unit 2, we multiply H1 by 2 to balance it.

H1 = 200 D1 = 1

1 Unit of Force 2 will die in 50 seconds, during which time Force 2 will deal a total of 200 damage and kill Force 1 completely! Both forces do not kill each other at the same time and therefore they are not balanced.

Obviously there is a trick involved here. We have to derive a formula mathematically. Intuition fails us here.

For both forces to be balanced, they must kill each other at the same time. Given a set amount of time (T), both forces must deal the same amount of damage.

Now if we set T equal to the time the unit is alive, which is his HP divided by the enemy’s damage and arbitrarily balance against an enemy whose damage is equal to 1 we can get a unit’s net damage.

D1 * T = D1 * (H1/1) = D1 * H1 = Net Damage

We can conclude that in order to be balanced, both forces must deal the same amount of Net Damage.

Force 2 has 2 Units, and therefore the total time the whole Force is alive is modeled differently.

1 Unit in the Force 2 will eventually die, within the time that he is alive the whole of Force 2 does 2 times his damage (since there are 2 units).

So, 2*(D2*H2) = Net Damage. However, this is not the whole story, since there is still one more unit alive. The damage that the solo unit does when he is alive also contributes to the Net Damage, therefore we must add his damage to the formula.

2*(D2*H2) + (D2*H2) = Net Damage.

Now we set the Net Damage of Unit 1 and 2 equal to get

H1*D1 = 2*(D2*H2) + (D2*H2).

I’ll shorten this letter by letting you clarify this with your own scenario.

Using mathematically induction I can prove this to be true if Force 2 is comprised of 3 units (And Force 1 still has 1 Unit).

H1*D1 = 3*(H2*D2) + 2*(H2*D2) + (H2*D2) (I can add the terms together)
H1*D1 = 6*(H2*D2)

Now what if it was a 2 vs 3 situation?

Using the pattern that I found, this would be my guess

2*(H1*D1) + (H1*D1) = 3(H2*D2) + 2*(H2*D2) + (H2*D2)
3*(H1*D1) = 6*(H2*D2)

Once again, I’ll leave you to make a scenario to clarify this formula. It should work out.

Take note that the amount of Units in both Forces is a relative term. It isn’t really the “amount” of units, its actually the ratio between their cost.

For 1 v 1 scenario, both Units cost the same amount. For 1 v 2, Unit 2 cost half as much as Unit 1. For 1 v 3, Unit 2 cost a third as much as Unit 1, etc. . .

So in fact, a 2 v 2, or a 3 v 3 scenario is modeled by the same formula as a 1 v 1 scenario, since their ratios will reduce to 1 : 1.

-Vinh

As we can see, the strength of a force grows exponentially with each additional unit. (Assuming units take up no space and don’t overkill their targets.) We can conclude then that a unit that costs twice as much as another unit should be exponentially more powerful. (The particular function for determining the strength of a unit given is price is given by the triangular numbers. Equally, the triangular numbers model the strength of a homogeneous force as it increases in size.)

If we multiply a force’s strength by the raw strength of any unit in the force we can find the true strength of a force. I arbitrarily chose to call this value K. K is a useful concept because it allows us to determine the prices of units by simply solving the equation on the right for x, which represents the number of units in the force. Since the number of units is directly proportional to the price, simply divide another constant arbitrary value by x in order to obtain prices.

From actually putting this formula to use, I’ve found a few problems. First off, it’s very difficult to be precise. Not much of a problem, but a problem nonetheless. Secondly, the formula is strictly for pricing units in respect to combat. Since many attributes have utility along other dimensions, movement speed for example, the pricing is not exactly accurate. Finally, as mentioned before, collision size is not accounted for either. Theoretically, collision size should be directly proportional to cost, with larger units being bigger, but as that’s not always the case it can really break the numbers sometimes.

Nevertheless, the formula should be a decent start for any designer.

Written by Ceasar Bautista

2010/06/17 at 13:21

1v1 Combat

leave a comment »

At the lowest level of the RTS, units have to be balanced against other units. Typically this is achieved by first guessing approximate values for a unit and then play-testing extensively until the unit no longer breaks the game. Play-testing anything enough should always return acceptable results.
However, there is undoubtedly a math to it all. Some laws of RTS nature. They are not at all simple however, and it’s probably impractical to figure them out, but it’s kind of fun and in certain ways useful.

Anyway, the first thing I looked at was how to balance one unit against another. To do so, I imagined a two-dimensional world that was completely empty of everything except the two units to be balanced, placed apart so that neither could immediately strike the other. From there, the idea was that if both units could kill each other at the same time, the two were balanced.

I examined only four basic attributes to start: Damage per second, Hit Points, Range, and Movement Speed. To start, I considered basic scenarios. For example, imagine the following two units:

Unit A Unit B
Hit Points 10 X
Damage 1 1
Range 10 0
Speed 0 2
What value of X will work to make things fair? Well, since Unit A has more range than Unit B, Unit B will be doing the running and with two speed it will take 5 seconds. During each of those seconds, he will take 1 damage from A, for a total of 5 damage. Then B will proceed to strike A, and with A’s 10 HP and B’s 1 Damage, it will take 10 seconds for B to kill A, during which time B will take another 10 Damage. So we add the two together and see B will take a total of 15 Damage. B should therefore have 15 HP to be balanced against A.

Furthermore, we can say that if A is balanced against B, and B is balanced against C, then A is balanced against C, even if A and C were not to kill each other at the same time. This is important because speed provides an advantage only if the unit has less range than the enemy.

Using the transitive property, the easiest way to balance units is to pit them against the Universal Unit (UU). The UU has 1 damage, 1 speed, 0 range, and infinite HP.

A general formula can be constructed, where Unit 1 has longer range than Unit 2:
(R1-R2)/S2*D1+H1/D2*D1=H2
OR:
(R1-R2)/S2+H1/D2=H2/D1

Personally, I find that a bit confusing. And worse, it doesn’t fully cover everything since there is no mention of S1. The formula is incomplete and had me confused for a very long time.

The solution came as an epiphany when I was looking stats of units had I generated that were “fair.” As such, there is very little evidence besides the idea being evidence for itself. But it does in many ways make sense. So instead of that other formula, it turns out that balance can be simplified as such:

(H1+R1)*(D1+S1)=(H2+R2)+(D2+S2)=…=K

K represents an arbitrary value of the designers choice and effectively, the value of the unit (and so the price).

This formula seems to make intuitive sense. Units with high range do well with high damage, but not so well with high HP. In fact, for the most part, such a unit would plainly suck. Likewise, a unit with high damage and high speed but low HP and low Range would also suck. It would never make it to it’s enemy alive. (Such units can be useful however. It’s just that in 1v1 they aren’t at all.) On the other hand, a unit with high HP and high damage though would be pretty solid.

Now, this formula only effectively explains 1v1 match-ups and doesn’t do a good job at all when it comes to mixed units or even just group combat. But it does give a pretty solid way of balancing units at the most basic level to start.

Countering
So, we know that (H+R)*(D+S)=K, but that doesn’t exactly tell us how to counter. Fortunately, it’s really rather simple.

The basic idea is to nullify the opponent’s strength. If an enemy unit is fast, render its speed useless by attacking it with tough units that possesses little range. If an enemy unit has excessively powerful attacks, swarm it with expendable units so as to waste the enemy’s strength. If a unit has excessive hit points, employ units that deal heavy damage in short bursts so as  to minimize overkill. And finally, if an enemy unit long range, attack  it with a unit that moves quickly to make full use of the speed.

This seems to be intuitive, but a player may easily miss the fact that if units are properly balanced, then these match-ups must be in your favor- the numbers force it to be so.

Written by Ceasar Bautista

2010/06/16 at 21:14

Posted in Uncategorized

Tagged with , , , ,

The Power of Speed

leave a comment »

Speed is perhaps the single most valuable attribute a unit can have. While it’s not particularly useful without some power to back it up, speed can be nasty when utilized by an intelligent player.

Basics

At the most basic level, speed has some very direct power to it. In the picture above, let’s assume that Blue’s units move faster than Red’s and that both units are equally powerful and subsequently obliterate each other when they meet. For the most part, Blue’s speed does nothing for him except move the location of the front line. If Blue is twice as fast, he’ll control twice as much of the line. Alone, this is not particularly useful. However, in one dimensional space one there is one advantage still: For every additional unit you have, the front line will be pushed back  a certain distance proportional to your speed and the rate of general production. Effectively, each units gives you the percentage of all speed controlled (your unit speed / (your unit speed + opponent’s unit speed)) multiplied by the distance between your opponent’s units. Some implications:

  • There’s a certain strength in slow units in that the distance between allied units is relatively short, making it more difficult for an opponent to gain space. Fast units however initially control more space and capture space quicker.
  • Effectively, this means that the less quick production is, the more important each individual unit becomes. This is rather obvious when production is slowed down to an extreme, to a point where a single extra unit could travel unopposed to the enemy base.

In isolation, this is not particularly useful. But when combined with multiple control points it’s really extremely powerful.

Batteries

The real strength of speed is made apparent when batteries are available or can be formed. In the picture to the right, Blue will be able to strike Red’s left node and defeat him before the right node can move in to suppress Blue’s advantage.

The real beauty here though is that each node connected through allied nodes can always trade space in order to reinforce another node. The slower your opponent is or otherwise the more distance between you two, the more resources can be directed elsewhere. And by temporarily redistributing resources, a player can conceivably strengthen a particular node enough to knock out an enemy one, and subsequently use the extra production to win the game.

More to come…

Written by Ceasar Bautista

2010/06/07 at 23:51