Friday, August 9, 2013

Preparing for AI

Another programming excursion... can you tell I've been doing a lot of that lately? I've been reading up on AI programming  ("Artificial Intelligence", just in case anyone's not familiar with the abbreviation). Technically, it's "weak" AI I'm looking at now, but I'd love to include some strong AI elements in Spacer... Think about it: a game that actively learns how the gamer plays and adapts accordingly.  Sounds awesome to me

This is totally NOT what I'm creating... *shifty eyes*
But I digress,

For my purposes, preparing a game to handle an AI boils down to the old dilemma of whether to use inheritance or composition for game objects.  For now, the only objects in the game  that have any kind of self-control are Ships.  I'm not going into all the details on how the Ship class is setup, but I'd like them to be pooled objects.  Before I started messing with the bulk of the solution discussed below, the only ship present was an instance of a derived class; PlayerShip.  This worked fine for debugging up to this point, but here's why I no longer like using a derived class to exert control over an object:
  1. Using instances of both the base class and its derived class (or instances of two different derived classes) screws up the existing object pooling.  If you have 2 ships in your pool, the first is a PlayerShip and the second is an BotShip, you're gonna need to either re-instantiate when you need a new object (which defeats the whole purpose of object pooling), do a lot of fancy casting to make it work (which is just a headache), or re-design ObjectPools entirely to store and fetch multiple types of objects within the same pool (which, let's face it, is too much work)
  2. The game shouldn't care whether it's updating a PlayerShip or a BotShip!  You don't want a human player or an AI player treated any different when calling the Update method, for instance.  If you do, it's very easy to give abilities to one or the other, or force yourself to repeat logic to prevent that from happening.  If a ship needs to move 200 meters starboard, it doesn't matter who issued the order (Captain Picard or the Borg queen), the game logic should move the ship the same way.
So, how to we address the issue instead? Ask yourself this: what do both ships have or own (as opposed to are or are not)? They both have a Controlling Entity! Not to get too philosophical, but here "Entity" is taken to mean "An independent, decision-making thing". (super technical. I know, right?). But both a human player or an AI decision tree meet this definition! The Entity class just contains a set of basic properties that the ship looks at during it's update phase:

abstract class Entity
{
 // Ship's Input variables:
 protected Vector2 desiredFocalDirection; // The direction the pilot wants the ship to face
 protected Vector2 desiredEngineFireDirection; // The direction the helmsman wants the ship to move
 protected bool activatePrimaryEquipment; // Should you attempt to activate any onboard equipment?
 // Other properties omitted... you get the idea.

 #region Public Properties

 public Vector2 DesiredFocalDirection { get { return desiredFocalDirection; } }
 public Vector2 DesiredEngineFireDirection { get { return desiredEngineFireDirection; } }
 public bool ActivatePrimaryEquipment { get { return activatePrimaryEquipment; } }

 #endregion

 public Entity(){ }

 public abstract void LoadContent(ContentManager content); // Load any resources derived entities need (ex: screen output information for the player to make decisions, or an AI personality)
 public abstract void UnloadContent(); // Clean up!
 public abstract void Update(GameTime gameTime) // Update your ShipInputVariables!

 public virtual void Initialize(Ship givenShip)
 {
  shipControlled = givenShip;
  shipControlled.SetControllingEntity(this);
 }
}

These Entities are maintained by something outside the physics or gameplay calculations, and the "Ship's Input Variables" are set in derived classes: PlayerEntity and BotEntity. In PlayerEntity, they are set by the controller/keyboard input, and in BotEntity: by the AI logic.  Now, we just have to give each ship an Entity (via a SetControllingEntity method), from which it reads it's input variables during it's Update phase. To help clarify, have a much-simplified UML diagram:



So that's it, composition wins out over inheritance... this time.  What's even better? We have a clean separation of responsibility! LocalSpace handles all the physics engine calculations and collision detection, the PlayerEntity handles translating input device states into intention, and the BotEntity handles translating AI decision-making into intention.  Heck, throw an EntityManagement class in there storing a collection (or ObjectPool, anyone?) of Entities to manage adding/removing players: when a player leaves, swap his ship's ControllingEntity with a BotEntity (that's been learning his gameplay style... again, I'm not creating SkyNet), and the action can continue when your friend gets called home for dinner! Feeling like making things more awesome? Create a new class derived from Entity: SquadronEntity, that contains a list of BotEntities, and can override decisions made by the individual bots for a coordinated battle strategy!

... this is how the Technological Singularity will come about, isn't it?...


Thursday, August 1, 2013

Pythagoras and Legos

I think it's safe to say that when we've all started out building with Lego bricks, we've all stuck to the rectilinear grid that's sooo~ conveniently provided by the baseplate (or you had a really dull childhood and didn't build with legos).  Even some of us adult fans of lego are guilty of "sticking to the grid," but today is the day to "Think outside of the block!" (Lego pun #1)

When you sit down for some (as Sheldon puts it) Lego Fun Time, think of each block as it's own right-angled coordinate system of integer-spaced connection points.  Thinking this way, you remember from your really cool high school geometry class that there was this old "stud" (pun #2) named Pythagoras who had quite a bit to say about integers and right angles. It's all conveniently summed up as Pythagorean Triples; that is, sets of integers (a,b,c) that satisfy the equation below.  For your reference, a and b (the two smaller sides that are at a right angle to each other) are called "legs" and c is the "hypotenuse"


Most people are probably thinking "oh man, it's getting mathy, that's about as boring as sorting pieces!" Well, don't be a blockhead (pun #3).  It's easy math, and I'm not asking you to solve equations; you can just look up lists of available Pythagorean triples and use whatever one is convenient for what you're building.  So, what does an old Greek dude have to do with little plastic bricks? Well, Legos only come in integer-sizes, unless, of course, you've cut your pieces >:( , Pythagorean triples are a perfect way to build non-rectilinearly!

There are two ways to use these magic triples: creating "Interior" or "Perimeter" right triangles.  I'll start with Interior, since you can roll with an unmodified list of Pythagorean triples.  For these, you'll need at least two "hinge" pieces to form the angles (this or this; there's probably a couple other pieces that'll work, but these are the most obvious to work with).  The whole idea about using Interior triangles is that the Pythagorean triangle is actually the negative space formed by enclosing a region:

In this example, we've used the (3,4,5) triple.  Your enclosing lengths are equal to the leg and hypotenuse values of your triple, counting in "stud units".  Know what'll make you put on a yellow smiley face? (#4ish) Knowing these triangles can scale! You can double all the lengths of any "primitive triple" (Pythagorean triples where each value is coprime to the others), and it'll still work; (6,8,10), for instance.  

As for Perimeter triangles, you don't need any special pieces, just something to bump your hypotenuse above the studs of your baseplate (I used these for the pic below, but really almost an piece will do).  For these, the bricks themselves form the perimeter of the right triangle.  Now, something REALLY important is our length counting system! Normally, when discussing lego piece sizes, we describe sizes something like "2x4", meaning "two studs by four studs", but the values in the Pythagorean triangles are LENGTH measurements, not UNIT measurements, so for the lego versions of the perimeter triangle to work, we need to measure the distance between studs, not the stud count! This example sums it up:
This example uses the (3,4,5) triangle again, but the lengths, in terms of stud count, is (4, 5, 6).  So, the Pythagorean triples you use when constructing must modified by adding 1 to each value to get to the "standard" Lego stud sizes:


Again, this works for any set (a,b,c) of Pythagorean triples, and can be scaled as well.  

So, those are the basic two uses of Pythagorean triples in Lego building.  

But let's not stop there, our brick bucket isn't empty, yet! (I don't think that counts as a pun...) Strictly speaking, Legos aren't restricted to integer values; with "jumper" plates (this and this, for example), we can make use of the half-integer values, too! These are a little harder to work with, especially since all of the commonly used1 primitive Pythagorean triples have an odd hypotenuse length.  But, it opens up quite a few possibilities. You can take half of each value of a Pythagorean triple (for interior triangles) or a modified triple (for perimeter triangles) for new stud unit sizes.  Below are half-sized examples of the previous two (3,4,5) triangles: 
Half-sized Interior
Half-sized Perimeter

(sorry, camera position parallax distorts them a bit, but they do line up). For clarity, there are two Jumpers in each photo, one in the hypotenuse and another in the vertically-oriented arm.  

So, theory is great, but how do they "stack up" in practice? You tell me! (that totally counts, btw)
This is the apse of my cathedral (Yes, these photos are shameless self-promotion :P ).  It uses two side-by-side (3,4,5) triangles, that might be better seen in the interior shot, where you have the floor tiling to use as guides for where the hinge connections are made.  Also note that you don't have to form a "triangle" using the interior triangle method, you can use the triangle concept to guide where your hinges need to be anchored to the baseplate.

I put together this is a quick 3-minute MOC just for you all, showing a farmer's beat-up, old cow pasture. It shows the use of two perimeter-method triangles; the left-most fence is the (5,12,13) triple, so of course it has a length of 14 studs. That's the easy (and less interesting) one.  The middle patch of fence shows the halving method on a (5,12,13) triple, so it's length is 7.5 studs, and if you count out the stud placement on the ground it comes out to 3.5x7.  Or the arithmetic, if you prefer :

(we're subtracting 1 rather than adding because we're converting from stud units to length units to use in the Pythagorean equation (the first equation in this post), whereas before, we were doing the reciprocal conversion)

So, much better than always working with square, hard edges! In my opinion, at least...

For your convenience, there are eight triples in particular (and their multiples!) that seem to work very well:  
  • (3,4,5)
  • (5,12,13)
  • (8,15,17)
  • (7,24,25)
  • (20,21,29)
  • (12,35,37)
  • (9,40,41)
  • (28,45,53)
I cut the list off at these eight simply because anything with larger arms begins to exceed the standard 48x48 stud baseplate size.  But don't let me stop you if you want to attach several plates together!

I'll take a moment to mention a deviation from this "pure" geometry: like all manufactured plastic parts, there are some mold tolerances engineered into the bricks, which means you can "fudge" the numbers a bit.  For instance, (19,11,22) and (6,15,16) are both approximate Pythagorean triples, which work within the "give" of the lego parts.  These little number fudges don't make a whole lot of difference on small scales, but they can be a source of serious tension when they add together, and can really affect the structural integrity of your model.

So, go sit down the best you can with single-jointed, plastic legs, and have a geometric time!  Happy Building!


1 That'd be an interesting proof: do all primitive Pythagorean triples have an odd-valued hypotenuse? I'll give it some thought after I finish this post.

EDIT: Turns out, yes, the hypotenuse MUST be odd for any primitive Pythagorean triple:
According to this paper, theorem 1.2 shows the hypotenuse can be written:


WLOG, let m be odd (m = 2+ 1), and n be even (n = 2l), where k and l are both integers and selected such that m and n are coprime (though, I state this for completeness, the fact they are coprime is inconsequential to our result).  After some algebra, we get:


Which, of course must be odd, for any pair k and l.  QED.