Yourself

So, Kerbal Space Program. You build rockets, you shoot your Kerbals into space, you bring them back. Or you blow things up.

I've always had a soft spot for space games. But a space game where you not only get to build your own spacecraft and fly it, but you fly it subject to real life orbital mechanics? **** yeah.

The game is currently in alpha and under development. There's a free demo version which is currently only one version behind the paid version, but the paid version has a few extra helpful features (specifically the orbit prediction is more robust, it will show you a patched conics trajectory when you will encounter another gravitational body), which makes getting to the two moons considerably easier. Oh, did I forget to mention that there are moons that you can land on? Well there are. Currently there's only one planet in the solar system (although you can leave that planetary system and enter a solar orbit if you want). Eventually, though, there will be multiple planets. It looks promising so far.

So I've been dabbling with procedural content generation for some years now and especially looking at noise generation. For those that don't know, noise is a way of generating pseudo-random values over some space in a deterministic way. That is a noise function assigns one value to each point in space. If I give it the same coordinates, it will always give the same noise value. The reason it's pseudo-random is that if you back up and look at it from far away, it looks something like this (in 2D):

http://www.ultimatepronoun.com/images/noise/turbX.png

Now, this isn't just any noise, this is what's called coherent noise (or sometimes gradient noise). Plain old noise might simply look like static, but coherent noise has a few important properties. The first property is that it's smooth (or in mathematical terms, it's differentiable). So if you move a little bit in any direction the noise value will only change by a little bit. The other property is that it has a constant frequency (so mathematically its Fourier transform peaks at a narrow band). The frequency is associated with the size of the noise features, so higher frequencies mean smaller features (the noise changes more rapidly but still remains smooth).

So that's what noise is. What can we do with it? One obvious application is in generating textures. Manipulating noise in the right way can allow you to do anything from generating clouds and fire to different kinds of rock or even organic looking textures. You can even use it to generate animated textures by taking 2D slices of 3D noise. It can also help in the generation of textures that map onto a sphere without any seams. Doing this manually can be very difficult, but 3D noise makes it easy. I'll go into more detail later.

Another of the common applications of noise is to use it to generate height maps and terrain. By adding together different frequencies of noise scaled by different amounts you can get very convincing terrain.

Another application is in perturbing other functions in space. This application is called turbulence and involves perturbing the input coordinates to another function by noise. I.e. before evaluating another function at a given point, p/i], we first compute the value of two different noise functions at p and then add the result onto [i]p and send it to the next function. First, let's start with two functions that have no turbulence added just to see what they look like normally:

http://www.ultimatepronoun.com/images/noise/mandelbrot.png
http://www.ultimatepronoun.com/images/noise/checkerboard.png

Now, turbulence has two parameters that we can control: frequency and power. The frequency of the turbulence is just the frequency of the underlying noise functions. The power is a number that we multiply the noise functions by when we add it to a point. So no turbulence is just the same as turbulence with 0 power. So let's add some turbulence with frequency 1 and a low power of 1/16 to our images and see what happens:

http://www.ultimatepronoun.com/images/noise/mandelbrot_p00625_f1.png
http://www.ultimatepronoun.com/images/noise/checkerboard_p00625_f1.png

They get warped and bent a little bit. The checkerboard now looks a little wavy. Let's try increasing the frequency to 4.

http://www.ultimatepronoun.com/images/noise/mandelbrot_p00625_f4.png
http://www.ultimatepronoun.com/images/noise/checkerboard_p00625_f4.png

It's almost like looking through a bumpy pane of glass now. The overall shape is preserved, but the boundaries are warped and twisted. Let's lower the frequency back to 1 and try increasing the power to 1/4.

http://www.ultimatepronoun.com/images/noise/mandelbrot_p025_f1.png
http://www.ultimatepronoun.com/images/noise/checkerboard_p025_f1.png

So we can get more dramatic changes. Turbulence can fundamentally change the way functions behave in an interesting way.

So now that we know what noise is and what we can do with it, we've come to the most important part: how do we make noise? I'll save that for later.

Well, I'm taking a course in probability over the summer so I decided I'd start a topic since it's a particularly relevant field to games. There are all sorts of applications of random numbers and if you can understand probability you will have greater control over how randomness impacts your game and how to balance it or achieve a certain affect.

Now, I could sit down and create a whole "lesson plan" starting with basic counting and combinatorics and then move on to random variables (both discrete and continuous), but it'd take an awfully long time to organize that and I think I'd rather just have people ask questions.

To get things started, one of the things I'm particularly interested in and one of the most important things someone could understand is how functions change probability distributions. For example, consider the following:

x = random(1);
y = x*x;

The variable x is uniformly distributed between 0 and 1. Roughly speaking that means that any particular value in that range is equally likely (this isn't precisely correct). Now, y also lies between 0 and 1, but is y uniformly distributed?

Now, the point of this post is mostly just to link to a game.  This would typically be more appropriate for games in general since it's not a Game Maker game.  However, the way this game is played makes it highly relevant to programming.  I feel it helps to get you thinking algorithmically.  So here it is:

Manufactoria

The idea is pretty simple.  Use a set of tools to guide robots to the exit.  Getting them to the exit isn't difficult, the difficult part is only letting specific robots through.  Each robot has a tape with colored dots on it and each level presents a challenge to only allow robots that match a certain criteria.  Some levels even let you write your own dots to the tape and ask you to transform the incoming robot's tape in some way.

I posted this here to generate some kind of discussion.  If you want to talk about what's actually in the levels and how you solved them, please use the spoiler tags so you don't inadvertently ruin the fun for someone else.

The following script takes two arguments which are both ds_list indices.  It then takes the elements of the second list and appends them to the elements of the first list.  This means that the first list gets modified.

{
	var l1, l2, s1, s2, sr, n, hex;
	hex = "0123456789ABCDEF";
	l1 = argument0; l2 = argument1;
	s1 = ds_list_write(l1); s2 = ds_list_write(l2);
	sr = string_copy(s1, 1, 8);
	n = ds_list_size(l1) + ds_list_size(l2);
	repeat (4) {
		sr += string_copy(hex, ((n & $f0) >> 4) + 1, 1)
		   +  string_copy(hex, (n & $0f) + 1, 1);
		n = n >> 8;
	}
	sr += string_delete(s1, 1, 16) + string_delete(s2, 1, 16);
	ds_list_read(l1, sr);
	return l1;
}