StarCraft II: Terran vs. Hard Terran AI Strategy

My experiments with StarCraft II have revealed a weakness in the hard Terran AI in a custom game.  Simply put, a sufficiently sized army of marines can take out the AI...  Let's look at the specifics, shall we?

First, send every SCV mining the mineral field.  Start training SCVs so that you have exactly 11.  Don't train more, or else 50 minerals will be set aside for the unit - and you want those 50 minerals.

Ok, got 10?  One more is being trained?  Good.  Take an SCV that is mining and get it to build a Supply Depot, and hold shift and right-click the mineral field after giving the order to build the Supply Depot.  This ensures the SCV doesn't need any micromanagement and will automatically returning mining once it's done building.

Have enough for a Vespene Gas Refinery?  Build one!  You'll need it.  And start training 3 more SCVs, sending them to the Vespene Geyser.  You only need one, we'll be more bound to minerals.

As the number of collected minerals increase, keep on building SCVs to collect even more minerals (about 2 per mineral field is ideal with an extra or two to use for building).  At the earliest possible moment, build a barracks, a bunker, and another barracks.  You want two barracks, but need a bunker.  Make sure the entrances to your base have at least one bunker.  Build a reactor on each barrack.

Now, you can produce 4 marines in parallel.  Start building an army.  First fill the bunkers, then just build more marines, Supply Depots, and SCVs...

While all of that is happening, you'll want to build an Orbital Command, an Engineering Bay, a Sensor Tower, and a Factory (with attached reactor).  In that order.  The orbital command allows you to upgrade the Supply Depots for more units (without spending precious minerals that could go towards building more marines) and quickly collect minerals using harvesters...  Also, spying on the enemy is always a good idea.

Ideally, 5 minutes total have passed.  The enemy should be preparing an attack with marines and marauders.  Keep the bunker safe, and away you go!

Try to minimize the casualties on the first attack by the AI - then immediately counter-attack if you can have about 10 to 20 marines.  You might also have a few Hellions by now too.

The strategy essentially boils down to upgrading marines and taking advantage of the ability to produce 4 marines and 2 hellions rather quickly to send into the battle field.  It works against the hard Terran AI, it might also work against Zerg and Protoss.  You also have to admit that you'll lose many units, and that ideally you're on the offensive, and not stuck protecting your base.  Being defensive won't help if the AI progresses too far ahead along the tech tree...  You might want some Medivacs - but I rather enjoy the suicide trips.

The last thing that I do is have an SCV build turrets (just in case) and additional Command Centres.  These Command Centres I like to fly off to rarely checked islands, or nearby mineral fields.  Once landed, transform them into a Planetary Fortress and start mining minerals.  Mine as many as you can!

You'll also be more effective if you focus the fire-power of the marines on specific targets rather than letting them attack and defend what they want (which is, for our purposes, good enough).

Particles on iPad : part IV

I should note that I'm not doing standard particles (with emitters, colour change, limited life span, etc.) as described by Reeves in 1983 - for that I suggest reading [Reeves83].

What I'm looking at is stably modelling, with a decent frame-rate, massive system of interacting small spherical objects - which I loosely call particles.  My initial attempt was to use smoothed particle hydrodynamics in order to imbue the masses of particles with the appearance of fluid flow (see [Monaghan92]).  That didn't work as I'd had hoped.  So I went to modelling particles using a finite element method.

The issue with the finite element method is best explained with a column of a dozen particles high falling and colliding with the ground.  Assume the column is perfectly aligned so that these spherical objects do not slide to the side.  Consider the time of impact.  On the first frame, the bottom particle will hit the ground and a repulsive force will be applied.  On the second frame that repulsive force will be applied to that particle and the one above it.  However the particle above it still has quite a bit of speed and due to the collision is applying a bit of a downward force.  In the end, it can take a few hundred frames before the system starts to show a stable result.  In the meantime the user is presented with particles unrealistically entering each other's physical space.

That led me to search for solutions that would simultaneously solve for all the collisions - some sort of magic way to prevent the visual oddities while the system stabilizes itself.  A way to more quickly reach a stable state if you prefer.

So I ended up writing the equations that solved for the collisions and see how to solve them as a single set of equations; not treating each individually.  The obvious method, I believed, was to write it out as a matrix.  Then, inverting and solving the system would lead to the desired solution (of course, I'd be forced to use a relaxation scheme...).

Then came the issue:  let's say I'm solving for "k" - a value indicating how far a particle should move.  I have at least 4 equations (one per colliding particle) used to determine each "k".  I could solve for "k" locally for each equation easily - however which equation would give me the "better" answer so that I could obtain a solution through relaxation?  Averaging the results should be satisfactory...

However, what am I computing?  A form of pressure.  Pressure accumulates where there are plenty of particles.  Taking the gradient of the pressure would give me a force pointing towards the best direction for the particles to avoid collisions.  A bit of doodling on paper revealed that pressure would be a function of density (how close particles are to each other).

Doesn't this sound awfully familiar?  Yes - a fluid simulation using smoothed particle hydrodynamics would do exactly that.  I've just started to re-invent the wheel.  So; let's stop reinventing and see what went wrong.

My particles were overly compressing each other.  As though they were not being forced apart - as though pressure was never strong enough to repel them.  Another observation is that the system would not stabilize...

Now; let's take another step back.  Let's consider pressure in more detail.  Pressure in an incompressible system to be precise.  Pressure should build-up as the system forces itself into a corner / against an obstacle.  That is, pressure is not local to a small set of particles.  Specifically, the force of pressure will want to minimize pressure.

Imagine a local system, whose gradient points downward to a set of particles with little/no pressure in comparison.  Now these particles form the liquid in a glass of water.  These particles below are tightly packed, so they should equally repel - not be the destination for - a new particle.

So I'm going to review the equations, better plan how I'll model the particles on paper.  Then implement a new version in the coming weeks.  Maybe a few posts on my thoughts may appear in the meanwhile...

How Could I Live Without Property Lists?

I've started to use property lists.  At first I avoided them since I thought they were daunting, but they are the easiest thing in the world to use!

What's the first thing we should do?  First, let's get the path to our property list from the main bundle:

NSBundle *mb = [NSBundle mainBundle];

NSString *dataPath = [mb pathForResource:@"MyPropertyListFile" ofType:@"plist"];

Second, for good measure, we should make sure that the object was found:

if (dataPath == nil)

NSLog(@"Unable to find MyPropertyListFile p.plist");

Ok, you'd want to do more than output a simple line of text.   Next, we want to open the file.  I recommend mapping the file to memory - so if the system gets low on resources it can the memory used by the contents of the property list file:

NSData *data = [NSData dataWithContentsOfMappedFile:dataPath];

Next; let's get the content found within our property list:

NSDictionary *Plist

= [NSPropertyListSerialization propertyListFromData:data

mutabilityOption:0

format:NULL

errorDescription:nil];

Ok.  That's it!  The contents of the property list file is within the dictionary.  To be honest, the method I'm using will be deprecated soon - but it works in iOS 3.x where the newer method only work in iOS 4.x.  Nonetheless, they both do something very similar.

Now, using a property list editor (either XCode or the one in the Utilities folder within the Applications folder) - edit your property lists as you please.  Dictionary types allow you to assign string keys to values (of varying type).  Arrays give you a list.  The others are scalar types.

What's great is that each maps to their underlying NSObject counterparts.  So a dictionary in a property list becomes an NSDictionary.

I'm aware that property lists can act as data sources and do much more complicated work.  However, they make for very nifty configuration files.  With less than a dozen lines of code you can open a property list and extract data from it.

With external configuration files so easy to set up; there is little excuse to hard code values that might change later on.

<minirant>

I used to write my own parsers to load configurations from external files.  Then I started to dump them in header files.  However, property lists are a much more elegant solution as they don't need a recompile.  Data can simply be queried from a dictionary root object...

</minirant>

Particles on iPad : Part III

I've worked out a few stability issues.  The iPod touch, first generation, seems to handle about 200 particles on screen (each colliding and exerting forces on each other) at about 15fps.  Not ideal...  I'm going to delve back into the math books and learn until I can implement a better integration scheme.

I have fixed the stability issues.  The force repelling the particles acted like a one-way spring.  That is, it just ejected stuff but did not apply forces to bring them back towards the particle (well, sphere).  My springs now are the same equation; but they have an area of effect equal to the radius of the particle.  This ensures that the maximum force that is applied to bring the particles together does not exceed the force that is used to repel particles.

Another issue was that my clamping of velocities to satisfy the stability criterion was done after the velocity was applied to the positions.  This meant that particles could travel further than what was safe (in other words, the distance it could travel before the simulation would oscillate to explosion).

Lastly, even all of this worked very nicely; I got the same jumbling I got with the SPH method, but a bit better.  The problem was that as particles were pushed down (say due to gravity), they would compress temporarily as the system (indirectly) resolved the pressure each frame.  Ideally, I'd want zero compression - or zero divergence.

To fix this last issue; I believe I need to brush up on the underlying mathematics.  Namely linear algebra to get a better hold of the concept of eigenvectors and eigenvalues in order to work out implicit methods to numerical integration.

The other problem is speed.  At 200 interacting particles, the iPod isn't a speed daemon.  It's rather slow.

In the end; because of speed and math - I'm shelving my particle idea for a year or so for hardware to improve and my knowledge of mathematics to improve.

In the meanwhile; working within my current limits, I'm mentally playing with a means of gameplay that would take advantage of the multi-touch screens.  For iPods/iPads I'm very interested in what interactions I can achieve which were impossible or impractical using regular game controllers, mice, and keyboards.

Particles and the iPad: Part II

I haven't given up on particles - and intend to get a system working where the world is composed of small particles that interact with each other.  My latest experiment consists of a simple discrete element method.  The method works perfectly for collisions; however as I try to introduce springs between particles the model starts to explode.

The reason is that the force from the spring is quite big and amplifies the forces from the other particles.  The simple solution would be more time steps; however I believe that there must have a better way to do this.

My next experiment will involve altering the repulsive and spring forces.  First; they will not vary as much based upon distance.  That is, the force will not go to infinity as two particles approach the limit of overlapping.  Similarly, for my springs, the force will appear like a sine-wave.  It will be very strong for a short radius and gracefully diminish over distance, sort of like a magnet.

The former strategy will help reduce the apparent visuals from explosions by preventing particles from exiting a collision with massive force.  However, without the springs this section is perfectly stable; which makes me believe I shouldn't play with it...

The latter will provide a smoother function for springs.  It's more for visual appeal than stability.  For stability, though, I will need to rework the spring algorithms so that they do not exert too much force.

A final note; I might re-introduce pressure calculations a la smoothed particle hydrodynamics.  It will provide more realistic motion for my particles which are currently synthetically confined to the plane.  Actually, first, I'll get them off the plane by adding a bit of random jitter to their initial position.  The shear force should give the effect that I'm looking for...

Anyhow; back to the drawing board...

SPH on iPad

I've just implemented my first SPH solver.  It's quite stable; and it runs at a decent speed.  I'm happy that it works; but haven't gotten to do much else this weekend.

My current solver is literally what Muller described in Particle-Based Fluid Simulation for Interactive Applications.  I don't want to go experimental on the first version, simply I'm searching for a feel on how the simulation reacts to stimuli; and what it might be useful for.

First, this is not behaving the way I expected.  The method, for lack of better words, uses a set of particles to approximate what occurs within the space.  I was expecting it to behave more like a massive cluster of discrete particles.

My issue is that density is computed based on the effect a particle has on other particles.

My interest in particle-based simulations is finite particles.  Essentially a ball-pit.  Cheaper-to-compute particles but more of them.  Essentially, massive atoms whose complex interactions yield fluid flow.  This experiment led me to a few conclusions which will dictate my next experiment.

First; pressure for incompressible flow - I believe - is very similar as to how balls in a ball-pit function.  As such, I'd look at the laws of rigid-body motion to do the pressure.  Namely, the forces arising due to collisions.  If no ball can enter the area of another ball, I've done it right.  But to make sure that human error wasn't the cause; I'll compare Muller's equations to those of rigid body motion to see how they differ.

Second; viscosity is a force that arises from interactions of nearby particles.  The motion should rub off.  For that, I'd use a simple area of effect - that is nearby (colliding) atoms have a given velocity, whose average is weighted and blended with the current atom's velocity.  The reason for limiting the area of effect to colliding particles is to ensure there is no "space" between atoms.  I'm aiming for a very fine approximation of fluid flow; not one that is coarse.

Third; I'm interested in non-uniform matter.  That is, each atom is not just water or air; but half could be water and half could be air.  The last thing I'd add to the system are springs.  Implicit springs to neighbours based upon stickiness factors.  I want goop.  Semi-solids.

Last; there are one-time springs - used for solids.  A coarse representation of glue.

Finally.  As I said, I should review the equations that I've implemented.  See and better understand how they compare to the equations for rigid-body motion before I build the next prototype.

Why SPH on iPad?  Doesn't it seem ridiculous?  Consider a video-game.  Right now we are stuck in a rut where things are coded for a purpose...  Wouldn't it be great to be able to paint properties of materials and let the game engine do the rest?  Clothes and fluids should be intrinsically the same material.

Or so I believe for now.  I'll comment on the next prototype...

Meaning of Life

Often times I begin to wonder, like most people on this planet, what the purpose of life is.  Some, sure of their answer, say that it is to reproduce.

I'd argue otherwise, using a few simple concepts:

Reversibility: Anything that we do, we could imagine it potentially occurring in reverse.  For example, drop a vase.  The vase shatters.  The shattering of the vase, the final resting position of the fragments, depend upon how the vase was held when it dropped.  If we were to reverse time, then the vase would re-construct itself.

Going backwards assumes that from time t+1 we can reach time t without any pre-disposed information.  The broken vase, again, could only reconstruct itself if we were also present in the mix of dropping, that the displaced air required something to take it's place...  The whole complex system allows this.

Determinism:  Since we can, if we were deities, extrapolate what would happen in the future and learn what happened in the past - there must be only one way forward and one way back in time (according to our world view).

More convincingly, determinism allows us to make choices and be able to accurately deduce the consequences.  It allows us to make sense of this world.

Order:  We like things that are organized.  Nature is very well organized.  We seem to self-organize for gain as we see fit.  We constantly further try to organize this world; be it by a system of roads (the visible) or dividing spaces...

Conclusion:  Briefly; I think that we are seeing the forest for the trees in terms of our purpose (or the meaning of life if you prefer).  If we reproduce, we are just another cog in the wheel that keeps on pushing evolution forward.  But given the overly predictable nature of our world; something is amiss.

Consider the solution to a dozen mathematical equations.  They can be solved by putting them into matrices, and solving.  There are even means of solving the equations indirectly to obtain an answer through multiple iterations.

I think we're in this system that is searching for a final, stable, phase.  That the ultimate meaning of life is the final stable solution of everything.  Once chaos ends.

And by the time we figure it out, it will be too late.  We will have already served our purpose.