Monday, June 8, 2015

Sprink!

Sprink has been released for iOS and PC!

http://www.basemetalgames.com/sprink.html

As spring awakens from a long winter's rest, Sprink awakes and begins a journey to find a sunflower! Ascend skyward through the seasons, to the stars!

Sprink is a heartwarming, family-friendly platform jumping game about rebirth, working towards your goals, and picking yourself up again when you fall - with a little help from your friends. Enjoy!

In April, I did a month-long game jam on a forum of a friend of mine (http://www.supershigi.com/forums/ - Laura Shigihara, composer for Plants vs. Zombies, game developer and all-around awesome person).  The theme for the game jam was "Spring" - so, of course, the game starts with the story of a spring awakening in the spring.

I had a lot of fun making this game.  It was difficult to get everything scheduled and done in one month, as I not only had to code the game, but also do all of the artwork, music, menus, and probably a dozen other things I have forgotten about.

The last month has been spent fixing up things for iOS, and waiting for approval on the App Store.

Overall, it went quite smoothly.  The game is fairly short, but there is a lot of heart put into it, and you can replay it a lot to try to beat your high score.  :)

Enjoy!

Thursday, January 22, 2015

Interpolation

Interpolation is basically just the creation of intermediate points between two points.  In games, this is quite often used to move an object smoothly from one place to another over several frames.

Linear Interpolation


The basic form of interpolation is linear interpolation (lerp).  This basically looks like:

p = p0*(1 - t) + p1*t

where:
p0 is the start value
p1 is the end value
t is a value between 0 and 1 representing the interpolation amount
p is the current value

This basically represents a straight line segment between p0 and p1, with t representing how far along the line we are.

An equivalent representation is:
p = p0 + (p1 - p0)*t

This form does have some possible performance advantages.  First, there is only one multiplication to perform.  Second, since p0 and p1 are constants, it is also possible to pre-compute the subtraction.

This basic formula also works for vectors, so p0 and p1 can be single floating point values, 2D or 3D points, or vectors of any other size.

This is such a common and basic function that it is an intrinsic function in shader languages.

Normalization


Quite often you will find that the values you want to use as the interpolation amount (t) are not between 0 and 1.

If you have a low and high range, it's fairly straightforward to normalize the values to a range between 0 and 1:

t = clamp((t0 - x0) / (x1 - x0))
where:
x0 is the minimum range value
x1 is the maximum range value
t0 is the current value
clamp is a function that forces values less than 0 to be come 0, and greater than 1 to become 1
t is the normalized value

Smooth Interpolation


Suppose we have three points, p0, p1, and p2.  We can interpolate between p0 and p1, and then from p1 to p2.  This allows us to follow a path through multiple points, but the results are usually not very satisfactory.  For motion of an object, changes in speed and direction are very abrupt and unnatural. 

One easy way to smooth out these transitions is to modify the value of t before doing the interpolation.  The main advantage to this is the ability to reuse the basic linear interpolation function for various non-linear interpolation methods.

Smoothstep is a commonly used function for this purpose.  The smoothstep function, with its first and second derivatives:
t = 3*t0^2 - 2*t0^3
t' = 6*t0 - 6*t0^2
t'' = 6 - 12*t0
where:
t0 is the initial value
t is the new value
t' and t'' are the first and second derivatives

Because t' (the first derivative) is zero at t0=0 and t0=1, there will be less apparent discontinuity as we pass through each point.

The second derivative is still non-zero at t0=1, which may still be perceived as a discontinuity.  In terms of physics, this would be the same as having zero velocity at the end point, but non-zero acceleration.

This function is common enough to be, like lerp, implemented in shader languages.  Implementations for smoothstep typically also include the normalization step, so t = smoothstep(0, 1, t0) is equivalent to the basic smoothstep function.

A smoother possible function is:

t = 6*t0^5 - 15*t0^4+10*t0^3
t' = 30*t0^4 - 60*t0^3 + 30*t0^2
t'' = 120*t0^3 - 180*t0^2 + 60*t0

This will have first and second derivatives equal to zero at t0=0 and t0=1.


Other Curves



There are many other possible functions that you may find useful, depending on the circumstances.  In general, any function that gives output values in the range [0,1] for input in the range [0,1] will work.

t = t0^2
Fast End - starts slowly at t=0, but increases rapidly towards t=1:

t = t0*(2-t0) = 1-(1-t0)*(1-t0)
Fast Start - essentially the inverse of Fast End

t = 2*t0^3 - 3*t0^2 + 2*t0
Fast Start End - fast start, slow middle and fast end values

t = 0.5 - cos(PI*t0)*0.5
Cosine interpolation

Conclusion


I have found it useful to have all of these curves available (and their derivatives and integrals) available in a general-purpose library.

Hopefully there is some useful information here that helps you with your own programming!


Monday, December 15, 2014

Quaternions

Quaternions are an interesting bit of mathematics.  You can read the Wikipedia article if you really want to understand what they're all about (or, attempt to understand, depending how mathematically inclined you are), but I jut want to talk a bit about using them in games.

Note:  this is only dealing with unit quaternions (i.e. length of 1).  In a more generalized case, they can be of any length, but for purposes of expressing rotations in games, they should only be unit length. 



Transformations



When dealing with geometry transformations, we generally need to worry about three things:
  • Translation (change in position)
  • Rotation (change in orientation)
  • Scale (change in size)

In games, we often use a 4x4 affine transformation matrix, as this is very efficient for most hardware to work with.  You can combine translation, rotation and scale into a single matrix.  You can also store this as a 4x3 matrix, as the last row is always (0, 0, 0, 1).

Even better, if you have multiple transformations you want to apply, you just multiply all of the matrices together and get a single matrix that does all of them at once.  This happens a lot in character animation, where the finger is positioned relative to the hand, the hand is relative to the wrist, the wrist is relative to the elbow, the elbow is relative to the shoulder, and so on.

Quaternions are another way of specifying the rotation.  Note that it is only rotation, so if you want to store scale and translation, you need to store those separately.  This is still very space-efficient.  Even using four-component vectors for each, it's still the same size as a 4x3 matrix.  If you don't need scale, it's 4x2.


Notation



There is a lot written about quaternions, but I find a lot of the articles to be pretty confusing.  When talking about programming, a quaternion and vector are essentially identical from a data storage point of view.

I put a quaternion into an (x, y, z, w) vector like this:

x = axis.x * sin(angle/2)
y = axis.y * sin(angle/2)
z = axis.z * sin(angle/2)
w = cos(angle/2)

where 'axis' is the (unit) vector you want to rotate around, and 'angle' is the angle to rotate.

What I find most confusing is people putting the 'cos(angle/2)' component in the first component of the quaternion/vector.  Mathematically there's nothing wrong with this, as long as you're consistent.

In Real Life, this causes a lot of confusion when you want to multiply a vector that has been stored as (x, y, z, w) with a quaternion that has been stored (w, x, y, z), so don't store it that way.  It's worse when articles have labeled the components (q0, q1, q2, q3) and it's not at all obvious what has been stored where.


Inspection


The way quaternions store data, it's possible to get some intuitive understanding of the rotation it represents by inspecting the values.

From the axis/angle assignment above, if angle=0, you get:
(sin(0), sin(0), sin(0), cos(0)) =
(0, 0, 0, 1)

Which is the identity quaternion rotation - if you see (0, 0, 0, 1), there is no rotation. 

For any other rotation, the (x, y, z) components will be some non-zero scale of the rotation axis, so inspecting the (x, y, z) components will give you some idea what axis it's rotating around.

If you remember your trigonometry, the amount of rotation should be obvious too:
  • w = 1 = cos(0/2) means angle=0
  • w = 0.7071 = 1/sqrt(2) = cos((pi/2)/2) means angle=pi/2, or a quarter turn
  • w = 0 = cos(pi/2) means angle=pi, or a half turn

Operations


Quaternion multiplication is completely unintuitive, :
q0 * q1 =
( q0.w*q1.x + q0.x*q1.w + q0.y*q1.z - q0.z*q1.y,
  q0.w*q1.y - q0.x*q1.z + q0.y*q1.w + q0.z*q1.x,
  q0.w*q1.z + q0.x*q1.y - q0.y*q1.x + q0.z*q1.w,
  q0.w*q1.w - q0.x*q1.x - q0.y*q1.y - q0.z*q1.z )

Rotating a vector (v = (x, y, z, 0)) by a quaternion (q) is fairly straightforward:


v' = inverse(q) * v * q

The inverse of the quaternion (x, y, z, w) is (-x, -y, -z, w).


Even if you are storing scale and translation, this is fairly easy:
  • scale = (sx, sy, sz) 
  • rotation = (qx, qy, qz, qw)
  • translation = (tx, ty, tz)
  • scale_inverse = (1/sx, 1/sy, 1/sz)
  • rotation_inverse = (-qx, -qy, -qz, qw)
  • translation_inverse = rotate(rotation_inverse, scale_inverse * (-tx, -ty, -tz))
Compare with the inverse of an arbitrary 4x4 matrix and you'll understand how much more straightforward this is.


Final thoughts


There are a lot of situations where using quaternions can be very helpful - particularly if you need to take the inverse of a transform very frequently.  Having your transforms broken out into separate scale / rotation / translation components can also be very beneficial, depending on how you're animating these values.

This doesn't mean quaternion rotations should be used everywhere - matrix transformations are certainly sufficient.  You will almost certainly need a matrix for rendering, and converting back and forth between quaternions and matrices is not trivial.

Tuesday, December 2, 2014

Random Blog Day

On my mind recently:

I watched @Jonathan_Blow live-coding on twitch.tv - he has been working on his own language, and it's nice to watch someone else have mind-bending code generation problems for a change.  :)

I have a lot of interest in game development languages, though I have primarily focused on scripting, as opposed to an entire game development language.  It's probably a little vague as to which category some things should drop into. 

Conceptually, I like to think of scripting as writing custom code for individual game objects.  This doesn't make it strictly game-specific, but it probably tends to be.  Ultimately, it lets you glue all of the bits of the game engine together into something new.  Also, having some syntactic control can let you specify certain this more easily.  For instance, I have special notation to convert musical beat/measure values into actual time values, and ways to specify timing, sequencing and interpolation.  It could be done in C, but the point is to make it easier to read and write than make it possible.

Engine coding is a fairly different beast.  First, you probably have to talk to third party libraries, even if that's just DirectX, OpenGL, basic operating system, etc.  So, you're probably stuck at some point with whatever language those are written in.  For simpler games you can get away with a higher level language, but for maximum performance and compatability, you're still looking at C/C++.

One interesting idea is to have a sort of pre-compiler that spits out C/C++ code.  I've seen similar things done before, to varying degrees of success.  This is pretty much guaranteed to degrade the already dubious quality of debuggers and debugging, but it's a way to add language features that are otherwise hard to get.  For instance, pre-hashed strings.

-----


In other news, the new World of Warcraft expansion Warlords of Draenor is out.  It is good. :)  They have done a lot of work scripting out quests, and there are a lot of places with a huge number of NPCs wandering around, which helps to bring the world to life a lot more than I remember seeing before.  Some of the battles are truly epic.

You have your own garrison now, which is a pretty cool idea, although we'll have to see how some of the features play out.  Since everyone is doing stuff in their own garrison, you don't see other people as much.  As a hardcore solo player, it doesn't affect me much, just feels a bit weird for an MMO. 

You can also build buildings to give you access to the various professions, including ones you haven't taken on yourself.  On one hand, this seems like a good idea, as it gives you access to some of the crafting you otherwise wouldn't have.  On the other, you can't have all of the buildings at once, and you probably want the ones you do have the professions for, so your choices are kind of limited.


-----

That's all for now - sorry I haven't been posting recently.  Too much going on, not enough stuff that makes good blog posts.  :)

Friday, October 31, 2014

Python Injection

Today's fun stupid code is written in Python.

I have found a few times recently where it was handy to either replace or inject code in specific C++ files, or even level files.  I have done this sort of thing in AWK in the past, but AWK is, well, awkward.

The basic pattern looks like this:


import tempfile

src = "yourfile.txt"

with tempfile.TemporaryFile("w+") as out:
 with open(src, "rU") as f:
  for line in f:
   if line.find('REPLACE ME') != -1:
    out.write('REPLACE WITH')
   else:
    out.write(line)
 
 #Beginning of temp file
 out.seek(0)
 
 #Copy temp file over source
 with open(src, "w") as f:
  for line in out:
   f.write(line)


This just opens a temporary file, scans every line of the source file and writes it to the temporary file, with possible modifications.  Then it jumps back to the beginning of the temporary file and overwrites the source file with the temporary file.

It's probably a good idea to have whatever you're modifying backed up somewhere

It may be easier to just read the entire file into a list of strings and write that back out, but now you know how to use temporary files.  :)

What you do at the 'REPLACE ME' line is up to you - check for a specific sub-string, or exact line.  Similarly for the 'REPLACE WITH' line - replace the line with generated code, insert a new line of code and put the 'REPLACE ME' marker back in as a comment, etc.
I have one version of this that copies a component template .h and .cpp file, replaces 'XXXXX' in the new files with the new component name, and injects the component registration code into the game initialization function.  Creating a new component used to be a chore, now it's easy!