Start Your Day with Verlet

Verlet integration.  What is it, even?

Well, once upon a time, I would give my moving objects the following components:  Location, Velocity, Acceleration, Drag.  Then, each cycle, assuming 's' is seconds elapsed, I would do this:

velocity += acceleration * s * s;
velocity -= velocity * drag;
location += velocity * s;

And that worked well enough as a model.

Now, instead, I have Location, PriorLocation, Acceleration, and Drag, and lastS is the s from the previous cycle, and I do this:

Vector2 velocity = (location - priorLocation) * (s / lastS);
velocity -= velocity * drag;
priorLocation = location;
location = location + velocity + (acceleration * s * s);

Why make the change?  At first glance, it appears to be doing the same thing, but in a much more complicated fashion.

The answer is it's simpler in the long run.  Because the velocity is calculated on the fly from the positions of the entities, I can freely move entities around as a result of springs, or collisions, or whatever other reasons, and I need not change the velocity of the entity at all -- it is automatically changed.

The technical answer is it's also much more accurate.  But that's not often a germane issue in game programming.  Physical accuracy in games is a choice that you make or not, according to your purposes.

C# ES

Entity Systems are the future of MMORPGs, or so I am told.  And for one- or two-man teams they are a Godsend, especially thanks to the linguistic quirks of C#.

What is an Entity System, you ask?  Well, the link above will give you a much more expert description from someone who has moved through the history leading from Object Oriented Programming to Entity Systems.  But I'm going to take a shot here and now because many programmers find ES confusing, and maybe if I hit it from a different angle than Adam Martin, you'll find it easier to understand.

Traditional OOP game programming has you turning different entities in your game into different classes, usually with a complicated hierarchy (Moving Object --> Ship --> Hero Ship... etc).

ES, on the other hand, divvies up components and systems.  Components are data (like current location, or which graphic to use), and systems are logic (a system for moving things, a system for drawing things, and so on).

Components are stored in hash tables, one table for each potential data set.  Systems crawl the relevant hash tables and operate on the data.  For instance, a Movement System might loop through the Velocity hash table, and update the corresponding entries in the Location hash table.  What is a hash table, you ask?  Answer:  It's a really fast way of storing data so you can look it up using a key.  How do I make me one of them hash tables you ask (or don't, if, unlike me, you actually went to school).  Answer:  You don't need to.  C# comes preloaded with a hash table class called Dictionary<key, value>, where 'key' is the variable type you want to use for keys (I tend to use integers, myself), and 'value' is the variable type for what you want to store in the dictionary.

Which, in turn, leads to the concept of Entities.  An entity is just a key to a hash table entry.  If two different hash tables full of components each have an entry under the same key, those two components are assumed to 'go together'.

That's all an Entity is.  It's a key held in common by one or more components, so that systems that need more than one component (like movement, which needs velocity and location, or art, which needs graphic and location), or systems that share components (like movement, which needs velocity and location, or art, which needs graphic and location) can easily look up the components they need.

Seriously.  A standard Euler physics loop cycle looks like this:

foreach (int Entity in Velocity.Keys)
{
    Location[Entity] += Velocity[Entity];
}

That easy.

"Wait," says the hash-table illiterati (or someone who can write hash tables in their sleep, but knoweth not C#), "that looked like an array lookup!"

Indeed.  My new favorite feature of C# is the indexer syntax, which allows you to access data within a class using the same syntax you would use to look up data within an array.  Dictionary<key, value> has it's indexer built so you can just pretend the key to the Dictionary was an array key and call it good.  It's just that simple!

K, says you, how do I get some of that sweet, sweet ES action for myself?

There's some discussion of the topic on Adam Martin's blog (but first make sure you read the above-linked articles and their comments for the full context).  There's some more stuff on a Wiki created just for that purpose, and even a pre-made entity system designed for C# by people who are much smarter than me.  But since I'm a rebel, and I dislike using engines I do not fully understand, I'm gonna roll my own naive ES using C# and XNA.

Here's how it works:

1:  Create categorical classes with public component dictionaries.

That is, I might have:

public static class Art
{
   public static Dictionary<int, int> Sprite;
   // ... etc...

   static Art()
   {
       Sprite = new Dictionary<int, int>();
       //We need lots of these...
   }

}

Technically, we don't have to stick them into category classes.  It just helps keep the autocomplete uncluttered if each component (as there will be several) is tucked in its own little mental folder.

2: Add Helper functions to the category classes to clean things up.

public static void Kill(int Entity)
{
   Sprite.Remove(Entity);
   Tint.Remove(Entity);
   Frame.Remove(Entity);
   // ... etc...
}

3: Create an Entity System Class to manage the whole shebang.

Behold:

public static class ES
{
   static Stack<int> Free;
   static List<int> Dead;
   static int Current = 0;

   public static int NextEntity
   {
       get
       {
           return (Free.Count > 0) ? Free.Pop() : Current++;
       }
   }

   static ES()
   {
       Free = new Stack<int>();
       Dead = new List<int>();
   }

   public static Update(float ElapsedSeconds)
   {
       Dead.Clear();

       //All systems get updated here.

       // Assuming Thanatos is the category class
       //that tracks whether things are dead or not...
       foreach (int E in Thanatos.DeathFlag.Keys)
           Dead.Add(E);
       foreach (int E in Dead) Kill(E);
   }

   static void Kill(int Entity)
   {
       Art.Kill(Entity);
       Physics.Kill(Entity);
       Thanatos.Kill(Entity);
       //And so on.

       Free.Push(Entity);
   }

}

Viola.  Now, you can get unused keys from the ES class, and when you set your death flag, it will automatically clean everything up for you and add your slightly-used Entity back to the pool of available keys.

Anyhow, I've been playing with this for a little while, and results have been excellent.  More after I sleep.