This is quite a lengthy tutorial.  It includes a brief introduction to pixel shaders in general; a tour of the most important aspects of Pixel Bender for use creating shaders specifically for Flash; directions for integrating the custom shader you create into a Flash project; and full source for two simple examples.

Some Introductions

Shaders, specifically pixel shaders.  These are programs that operate on an image on a per-pixel basis.  Per-pixel means the program operates on each pixel individually, without reference to operations carried out on other pixels.  Because shaders operate in this per-pixel manner they very well suited to parallel processing: Having many instances of the shader operating at the same time, each on their own pixel.  Operating per-pixel means that there are certain tasks that are well suited to being performed by a shader as well as many tasks that are completely unsuitable.

Filters, Effects, Blendmodes, Kernels.  There's a lot of terminology floating around depending on where you read about stuff.  I'm going to call everything a Shader, because that's the name of the class I end up using in Flash for everything (not the best method for naming things, but still.) To give a very rough idea to help you follow other documents: Filters and Effects are applied to just one image; Blendmodes are applied to two (or more, in theory?) images; a Kernel is the thing you make when you type code into Pixel Bender.

Pixel Bender.  The Pixel Bender Toolkit, to give it its full name, is a neat program made by Adobe to produce custom filters and effects for use in a variety of their applications.  A large amount of its functionality is unavailable for use in Flash.  Beware when reading general information about Pixel Bender; a lot of it is not going to apply to us.  Pixel Bender is available for free from Adobe (look to the right of the page.)  Pixel Bender was known as Hydra when it was in development, so you may see that name crop up around the place too.

Here be monsters

Using Pixel Bender to make shaders for Flash is - to put it politely - prone to inconsistencies.  The Pixel Bender Toolkit lets you run your shader within it to test it.  What you see in the preview will quite often not match what comes out in Flash.  I'm attempting to build up a record of ways in which the two do not match but it's far from complete.  Just be aware that you should test primarily in Flash and not rely on the inbuilt preview.

What's the point

So Pixel Bender can make buggy programs that are limited to operating on images in a per-pixel basis.  Why am I bothering learning this?

Because it's fast!

You might like to look at a normal mapping example I put together recently.

Flash programs are pretty slow generally, and are limited to executing in a single thread.  Consider if you want to tint an image red in Flash.  If you're hopelessly naïve you might write something like:

for (var x:int = 0; x < image.width; x++)
{
   for (var y:int = 0; y < image.height; y++)
   {
      var colour:uint = image.getPixel(x, y);
      colour = (colour | 0xff0000); //set the red channel to 255
      image.setPixel(x, y, colour);
   }
}

This will be slow.  It'll be slow because of the BitmapData.getPixel and BitmapData.setPixel operations being called huge numbers of times, but on a more general level it's slow because you're visiting each pixel in turn when you could be performing that operation on all the pixels at once.  This is effectively what a custom shader from Pixel Bender does.

Your shader will not actually operate on all the pixels at once, as it's limited by the number of threads it can execute on the machine its on.  But thinking of it as operating on every pixel at once is a useful mental model.

Pixel Bender was designed to run on GPUs, which are especially well suited to performing many parallel tasks.  When running in Flash it is actually limited to using the CPU.  This means it's not nearly as fast as it could be, but it still has the potential to be many times faster than plain old actionscript.

To the Pixel Bender!

Let's get right in and actually make a shader and get it working in Flash.

Download and install Pixel Bender.

Set a couple of options within Pixel Bender (Edit menu, Preferences...) to tell it you'll be exporting to Flash:

Select New Kernel from the File menu.

You'll now have the code for a shader that does nothing.  Excellent!

<languageVersion : 1.0;>
kernel NewFilter
<  namespace : "Your Namespace";
   vendor : "Your Vendor";
   version : 1;
   description : "your description";
>
{
   input image4 src;
   output pixel4 dst;
   void
   evaluatePixel()
   {
      dst = sampleNearest(src,outCoord());
   }
}

Oh no, this isn't Actionscript!  Time to learn a new language.  Good news is it's easy, and you can ignore most of it.

So what actually matters here?

input image4 src;

This declares a variable of the type image4 named src, and says that this variable will hold the input that our shader is given.  Later we'll see how a shader can have multiple input images.

The type image4 just means that it's an image with 4 colour channels: Red, green, blue and alpha.  There is also image3 if you want to ignore the alpha channel.

output pixel4 dst;

This declares a variable of the type pixel4 named dst, and says that whatever value we put in this variable will be the output of the shader.  pixel4 is a single pixel with 4 colour channels.

But wait!  We're taking a whole image as input, and only giving a single pixel as output?  Shouldn't this be producing a whole image?

I was just getting to that.

The evaulatePixel() function is the heart of our shader.  It is executed once for each pixel of the source image.  It produces just a single pixel - our output variable named dst - which is then built up to form the finished image.

void
evaluatePixel()
{
   dst = sampleNearest(src,outCoord());
}

Here's the evaluatePixel function in full.  The only bit you ever need change is between the curly braces.  In this case it takes the result of the built-in function sampleNearest and assigns that to dst.  Note that unlike actionscript functions where you use 'return' to have a function produce a value, evaluatePixel just sets the value of the variable that we've previously defined as the shader's output.

What does sampleNearest do?  Press F1 in Pixel Bender to get the documentation.  The majority of the documentation doesn't apply to us (most sections end with "Flash player note: X is not supported in Flash Player.")  But it has lists of built-in functions and data types, most of which are supported.  sampleNearest gives us the value of a single pixel from the image passed as the first parameter, which in this case is src.  Which pixel to return is determined by the second parameter, which in this case is the result of another built-in function: outCoord. This function returns a float2 value giving the position of the pixel that in this instance evaluatePixel was called on.

Vector data types

Unlike actionscript, Pixel Bender uses something called vector data types.  These store several values within one variable.  For instance a position in two-dimensional space can be specified by a float2 value, which is just two floating point values (basically the same as number in actionscript) joined together.  You can access the individual values, or operate on them as a whole.  Let's take an example:

void
evaluatePixel()
{
   pixel4 myPixelVariable;
   myPixelVariable = sampleNearest(src, outCoord());
   dst = myPixelVariable * 2.0;
}

First new thing:

pixel4 myPixelVariable;

Simply declares a variable named myPixelVariable which is of type pixel4.

myPixelVariable = sampleNearest(src, outCoord());

As you'd expect we can assign a value to it.

dst = myPixelVariable * 2.0;

Then we can multiply the whole thing by 2, and assign that to our output variable.

This is exactly the same as performing:

dst.r = myPixelVariable.r * 2.0;
dst.g = myPixelVariable.g * 2.0;
dst.b = myPixelVariable.b * 2.0;
dst.a = myPixelVariable.a * 2.0;

Isn't that neat.

myPixelVariable.r is accessing one of the four elements that make up the variable.  The elements can also be accessed by:

myPixelVariable[0], myPixelVariable[1], myPixelVariable[2], myPixelVariable[3]

myPixelVariable.x, myPixelVariable.y, myPixelVariable.z, myPixelVariable.w

myPixelVariable.s, myPixelVariable.t, myPixelVariable.u, myPixelVariable.v

The suffixes [0], .r, .x and .s are all equivalent.

You can access several elements of a vector-type variable at once.

myPixelVariable.rg *= 2.0;

Will multiply just the red and green channels by two.

You can also assign values between elements of a vector-type:

myPixelVariable.rgb = myPixelVariable.brg;

This assigns the blue value of the pixel to be the red value, the red to the green and the green to the blue.

You can specify each element of a vector-type like so:

myPixelVariable.rgb = float3(0.5, 0.2, 0.8);

Fussy about types

Notice that in the examples above we multiply by 2.0 rather than just 2.  This is because unlike actionscript, Pixel Bender doesn't do implicit conversion.  What that means is that it will interpret 2 as an integer, and not know how to multiply that by the float values of a pixel4 variable.  Writing the value as 2.0 makes it clear that you want it treated as a float. You could also use float(2) to explicitly convert the integer into a float.

Slightly weirdly there seems to be little difference between pixel4 and float4.  I think there's a difference in how accurately the values are stored, but they are largely interchangeable.

A working shader

Let's pull that together into a simple working shader so we can move on to implementing it in Flash:

kernel NewFilter
<    namespace : "Your Namespace";
     vendor : "Your Vendor";
     version : 1;
     description : "your description";
>
{
    input image4 src;
    output pixel4 dst;

    void
    evaluatePixel()
    {
        dst = sampleNearest(src,outCoord());
        dst.r *= 2.0;
    }
}

This will just take each pixel from an image and double the red channel.

We can give this a quick test within Pixel Bender.  Just Load Image 1... from the File menu and select any old photo you have laying around. Then hit the Run button (or F5) and the photo will be displayed with a red tint.

Now choose Export Filter for Flash Player... from the File menu.  This will create a .pbj file containing Pixel Bender byte code which Flash will be able to understand.  Whenever you change a shader you're working on, remember you'll need to re-export it to have those changes show up in Flash.

And in to Flash

Once you know how, getting the shader in to your Flash program is actually quite simple.  The basic technique is very similar to embedding an image, font or sound:

[Embed(source = 'TestShader.pbj', mimeType = 'application/octet-stream')]
private var TestShader:Class;

And that's it embedded! To create an instance of the shader:

var myShader:Shader = new Shader(new TestShader() as ByteArray);

The shader we've created requires an input image, so we need to point myShader at an image to use as its input.

myShader.data.src.input = myBitmapData;

This assumes we already have an image loaded and named myBitmapData. Note that the src corresponds to the name we gave the input variable in Pixel Bender.

To actually run the shader, we make use of a ShaderJob.

myJob:ShaderJob = new ShaderJob(myShader, outputBitmapData);
myJob.start(true);

Again this assumes we already have a bitmapData object named outputBitmapData which is ready to receive the finished image (it should be created as the same size as the input image.)  The true value passed when calling start on myJob tells Flash you want to wait until the job is complete before continuing.  It's possible to pass false instead and have the shader execute asynchronously, but that brings up a whole lot of other issues and a pretty major bug.

Putting this all together into a program that'll actually work:

package
{
	import flash.display.Bitmap;
	import flash.display.BitmapData;
	import flash.display.Shader;
	import flash.display.ShaderJob;
	import flash.display.Sprite;
	import flash.utils.ByteArray;

	public class PrettyShader extends Sprite
	{
		//embed the shader
		[Embed(source = 'TestShader.pbj', mimeType = 'application/octet-stream')]
		private var TestShader:Class;

		//embed an image to test it on
		[Embed(source = 'SomeImage.jpg')]
		private var SomeImage:Class;

		public function PrettyShader()
		{
			//set up the input and output BitmapDatas
			var myBitmapData:BitmapData = (new SomeImage() as Bitmap).bitmapData;
			var outputBitmapData:BitmapData = new BitmapData(myBitmapData.width, myBitmapData.height);

			//set up the Shader
			var myShader:Shader = new Shader(new TestShader() as ByteArray);
			myShader.data.src.input = myBitmapData;

			//create the ShaderJob
			var myJob:ShaderJob = new ShaderJob(myShader, outputBitmapData);

			//and run it!
			myJob.start(true);

			//display the input and output.
			var before:Bitmap = new Bitmap(myBitmapData);
			addChild(before);
			var after:Bitmap = new Bitmap(outputBitmapData);
			after.x = before.width;
			addChild(after);
		}
	}
}

Remember to set your compiler to target Flash Player 10, and you should end up with something rather like this:

We're actually almost done now!  There are two more things to cover:  multiple image inputs, and parameters.

Multiple images as inputs

The example above just takes one image and fiddles with the colour a little.  You can do much more powerful things if you work with more than one image.

In Pixel Bender all we need to do is add an extra input statement for each image we want to sample from.  For example:

kernel NewFilter
<    namespace : "Your Namespace";
     vendor : "Your Vendor";
     version : 1;
     description : "your description";
>
{
    input image4 srcOne;
    input image4 srcTwo;
    output pixel4 dst;

    void
    evaluatePixel()
    {
        float2 positionHere = outCoord();
        pixel4 fromOne = sampleNearest(srcOne, positionHere);
        pixel4 fromTwo = sampleNearest(srcTwo, positionHere);
        float crossfade = positionHere.x / 400.0;
        dst = fromOne * crossfade + fromTwo * (1.0 - crossfade);
    }
}

This will sample from both images, and mix them together depending on the horizontal position of the pixel in question. You might notice that I create a float2 variable named positionHere to store the result of outCoord(), this is simply to save calling the function multiple times when I know it'll give the same result.  Unnecessary premature optimisation or just being tidy?  You decide!

The changes in Flash are just as simple.  Simply assign another BitmapData as the shader's second input:

myShader.data.srcOne.input = myBitmapData;
myShader.data.srcTwo.input = myOtherBitmapData;

Parameters
Parameters are simply variables that are used within the shader and can be set from within Flash.  Like input images and the output pixel, parameters are defined outside of the evaluatePixel function.  As well as specifying the data type that the parameter should be you give minimum, maximum and default values.

Here is the above shader amended with two parameters:

kernel NewFilter
<    namespace : "Your Namespace";
     vendor : "Your Vendor";
     version : 1;
     description : "your description";
>
{
    input image4 srcOne;
    input image4 srcTwo;
    output pixel4 dst;

    parameter float middleOfFade
    <
         minValue: -1.0;
         maxValue: 1.0;
         defaultValue: 0.0;
    >;

    parameter int widthOfImage
    <
         minValue: 0;
         maxValue: 5000;
         defaultValue: 400;
    >;

    void
    evaluatePixel()
    {
        float2 positionHere = outCoord();
        pixel4 fromOne = sampleNearest(srcOne, positionHere);
        pixel4 fromTwo = sampleNearest(srcTwo, positionHere);
        float crossfade = middleOfFade + (positionHere.x / float(widthOfImage));
        if (crossfade > 1.0) crossfade = 1.0;
        if (crossfade < 0.0) crossfade = 0.0;
        dst = fromOne * crossfade + fromTwo * (1.0 - crossfade);
    }
}

In this case we use two parameters, for two quite different purposes. You might have noticed that the previous versions relied on a constant value of 400.0 in the calculation of crossfade. This was the width of the image in use, but of course our shader should be ready to accept other sized images too so the parameter widthOfImage was added.  Secondly the parameter middleOfFade is added to allow interactive changes to how the two source images are mixed.

As a side note, Pixel Bender actually includes some built-in functions for determining the size of input images, but they are not available when exporting for the Flash player.

If you test this shader in Pixel Bender it will display some sliders that let you alter your parameters on the fly and see what effect they have.

Passing values to your shader from Flash is again fairly simple, although slightly obscure.

myShader.data.middleOfFade.value = [0.2];

Notice that you use .value when setting a parameter, but .input when setting an input image.  You also have to put your value inside an array first.  It makes more sense if you need to pass values into a float3 variable:

myShader.data.someFloat3Variable.value = [0.1, 0.6, 0.3];

All together now
A working Flash program that uses a shader with two image inputs and parameters.

package
{
	import flash.display.Bitmap;
	import flash.display.BitmapData;
	import flash.display.Shader;
	import flash.display.ShaderJob;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.utils.ByteArray;

	public class PrettyShader extends Sprite
	{
		//embed the shader
		[Embed(source = 'TestShader.pbj', mimeType = 'application/octet-stream')]
		private var TestShader:Class;

		//embed the images to test it with
		[Embed(source = 'SomeImage.jpg')]
		private var SomeImage:Class;
		[Embed(source = 'SecondImage.jpg')]
		private var OtherImage:Class;

		private var myShader:Shader;
		private var outputImage:BitmapData;

		private var count:Number = 0;
		private const twoPi:Number = Math.PI * 2;

		public function PrettyShader()
		{
			//set up the input and output BitmapDatas
			var firstImage:BitmapData = (new SomeImage() as Bitmap).bitmapData;
			var secondImage:BitmapData = (new OtherImage() as Bitmap).bitmapData;
			outputImage = new BitmapData(firstImage.width, firstImage.height);

			//set up the Shader
			myShader = new Shader(new TestShader() as ByteArray);
			myShader.data.srcOne.input = firstImage;
			myShader.data.srcTwo.input = secondImage;

			//set parameters
			myShader.data.widthOfImage.value = [firstImage.width];
			myShader.data.middleOfFade.value = [0.0];

			//display the output.
			addChild(new Bitmap(outputImage));

                        //update every frame
			addEventListener(Event.ENTER_FRAME, perFrame);
		}

		private function perFrame(e:Event = null):void
		{
			//update realtime parameter
			count += 0.05;
			if (count > twoPi) count -= twoPi;
			myShader.data.middleOfFade.value = [Math.sin(count)];

			//create the ShaderJob
			var myJob:ShaderJob = new ShaderJob(myShader, outputImage);

			//and run it!
			myJob.start(true);
		}
	}
}

Here it is running:

I think that is about all for now.  There is plenty more to learn about both Pixel Bender and using shaders in Flash, but this should give you everything you need to get some cool stuff working.

Of course making those awesome shaders is another topic altogether.

As a final note, keep in mind that it is possible to use custom shaders as BlendModes or Filters directly in Flash.  I have found that doing so ended up being more complex (or at least confusing), didn't allow for the creation of anything that couldn't be achieved through the use of Shader and ShaderJob, and may even run slightly slower.

This is very much a work in progress.  I'm mainly posting it now so I can link to it in other posts.  It is also worth pointing out that these are problems that I have encountered on my particular set up, so it's not at all clear where in the chain these occur. Please do suggest any you find in the comments.  If you can manage to get someone from Adobe to pay attention, that'd be good too!

Comparing vector-type variables

Say you've got two float3 variables and want to see if they're identical.  The following should work:

(one == two)

This does work when testing in Pixel Bender, but seems to always return false when compiled for Flash.  To get around this, compare the elements of the vector-type variables separately:

(one.r == two.r && one.g == two.g && one.b == two.b)

Clamp

There's a handy built-in function called clamp.  This takes three values: x, min, max.  If x is between min and max it just returns x; if x is smaller than min then it returns min; if x is larger than max then it returns max.  This works fine in Pixel Bender, but can fail (only fails in the case of x > max?) when compiled for Flash.  Get around it by using a pair of simple if statements.

Cancelling a save on exit

This isn't really about Pixel Bender for Flash, but a general annoyance.  Upon closing Pixel Bender when it has an unsaved file open, it asks if you want to save it giving options Save, Don't Save, Cancel.  Clicking cancel will cause Pixel Bender to close and abandon the file.  The expected behaviour is for cancel to cancel the whole quit operation.

Sampling outside of an image

Behaviour varies between Pixel Bender and Flash when a shader attempts to sample a pixel from outside the bounds of an image.  In Pixel Bender, a black pixel is returned.  In Flash a pixel identical to the closest pixel that is within the image bounds is returned.

Normalise function creates artefacts

I don't have this properly pinned down, but I think it's related to the first few pixels of each shader instance being processed in interpreted mode (rather than Just in Time) which causes it to use slightly different math functions.  Artefacts have tended to be black rows of 3 pixels length on the right-hand side of the image.  Such artefacts only appear in Flash.

Change from:

myVector = normalize(myVector);

To:

myVector /= length(myVector);

Just beware division by zero.

Flash Player crashes with shaders on large images

On certain browser / OS / hardware set-ups the Flash Player will crash when attempting to run a Pixel Bender shader on a large image.  I can't recreate the crash on my machine, but it looks like the size limit is between 1024x1024 and 1500x1500 (the former works fine, the latter causes the crash.)  It is still possible to put large images through a shader, you just need to chop them up into bite-sized parts first then stitch them together again after they've been through the shader.  Exactly how you do that is going to depend on what your shader's doing.

Order of declaring parameters

When declaring parameters for a shader, you should list float type values before float2 type values.  Presumably there needs to be similar ordering for other types, but I've not experimented.  The parameters 'just break' in seemingly arbitrary ways if they're listed out of that order.

Colour-blindness is pretty common.  Designing a game or other visual experience so that it can be enjoyed by someone with the condition is pretty easy.  So let's do it!

An article on Negative Gamer about Bioshock 2 failing to do it.

Concise advice from wearecolorblind.com

Contrast Analyser - A very neat program that can approximate what someone with particular types of colour-blindness see when they look at a given image.  Use the "select window" option in the Image menu and just point it at whatever you're working on.

An interesting colour adjustment algorithm that claims to make coloured areas of images easier to differentiate by those with colour-blindness.  If it does work it looks like the type of thing that could be rather easily made into a shader.

Really I should post this after a nice tutorial explaining all about ShaderJob and custom shaders and PixelBender.  But having spent today finding the bug I feel I should post it.

A Rapid Introduction

A ShaderJob allows you to apply a shader to an image (or a 'shader' to a set of data, which is mechanically very similar.)  The nice thing about ShaderJobs is they can be run asynchronously.  This means I can start off a ShaderJob to do a fancy lighting effect, and whilst it's doing that my program can carry on executing and working on AI or whatever.  This is thanks to the ShaderJob executing in its own threads separate from the single thread that all the rest of an Actionscript program executes in.  The performance increase from finally being able to use something close to multithreading (what the shader can actually do is cruelly limited) is significant.

And the Problem

Sadly, it all breaks if you try to run multiple ShaderJobs simultaneously.  Ideally, they should be able to just all run at once - that's kind of the point of multiple threads.  Instead the documentation claims that they're kept in a queue and executed one after the other.  Which is a shame, but isn't actually the problem!

Instead of being kept in a queue, additional ShaderJobs just silently vanish.  Start a ShaderJob to blur an image of a circle, then start a ShaderJob to blur an image of a square.  If the ShaderJob for the circle is set to be asynchronous then the ShaderJob for the square will never execute.  No errors are produced; it just silently fails.

The 'neat' thing is that so long as an asynchronous ShaderJob is running in the background, any further ShaderJobs started (whether synchronous or not) will be silently destroyed.  It is possible to avoid this by tracking when an asynchronous ShaderJob completes and not allowing the creation of new ShaderJobs until then.  But if the execution of significant parts of your program has to wait for an asynchronous process to finish then it rather defeats the purpose of it being asynchronous.

I managed to find a report of the issue on Adobe's forums from a year ago, although they didn't seem to discover the full range of the  asynchronous ShaderJob's murderous intentions.

In Summary

Only run a ShaderJob asynchronously if you are certain that no other ShaderJobs will be started until it has finished executing.

Use the mouse to position the lightsource.  This demo's normal map was made by following an excellent tutorial on producing normal maps from photographs by Ryan Clark.  The shader is of my own design but is nothing special at all, and I think it's slightly buggy still working correctly.

On my machine this runs at a capped 50fps, whilst trying to do the exact same pixel calculations 'manually' with bitmapData methods manages 2 to 3 fps.  I would post a SWF of the manual version too but it has a decent chance of timing out the flash plugin.

This is all thanks to the magic and wonder of Pixel Bender, which lets you write your own shaders/filters/blendmodes for use in a range of Adobe's products - including Flash.  Basically it lets you write an operation that will be executed on every pixel in a given image.  The good bit is that the execution of that operation will take advantage of the parallel nature of the task and split its operation into threads, so showing a huge increase in performance from the single-thread bound Flash Player.  You may also read about how Pixel Bender pushes its calculations on to the GPU, but it actually doesn't do that when executing in Flash.

Sadly a significant amount of its features are disabled for Flash, and there are still plenty of oddities and inconsistencies that even in my brief testing I've come up against.  Despite that, I think it's worthy of investigation simply because of the huge increase in performance it can give - it's also free and works fine without needing to use the Flash IDE.

Once I'm a little more certain that I'm doing things right I'll write up an introduction tutorial for using Pixel Bender in Flash projects. Edit: Here it is.

The problem: We have generated a neat platformer level, and want to be able to automatically lay neighbour-sensitive tiles over it so that they fit properly.

Neighbour Sensitive Tiles

Super Mario's tiles are not neighbour sensitive;  the stone block always looks the same if it's floating alone or if it's part of a wall.

That's fine for many games, but can look out of place if you're trying to create a more organic feel in a level, or just wanting to cut down on repeated patterns.  Neighbour sensitive tiles overcome this by matching their appearance to the presence of their neighbours.

A 1-bit Map

Let's imagine that with some clever techniques we have generated a level layout for a platformer game that consists of either stone or empty air at each grid location.  This can be represented as a 1-bit image - that is each pixel's state will be determined by a single bit, so either on indicating rock or off to indicate open air.  Here's a section of such a map, greatly enlarged and with grid lines added:

A Tileset

A tile set is simply a collection of the graphics that may be used to fill in a map.  Mario's tileset is quite small, consisting of just a few different types of block and scenery, whilst ours will have many graphics for the same type of tile:

Valuing Neighbours

To determine which tile should go at each spot on the map, we shall examine that spot's immediate neighbours (for now we'll ignore diagonal neighbours.)  Rather than writing a huge if/else-if statement to handle all the possible combinations of neighbours, we will use a system that assigns values to each direction.

A value is found for each location by looking at its neighbours and adding up the values for whichever ones have stone present.  So if the spot we're examining has a neighbour above it that is also filled with stone then it is given the value 1.  If it has stone-filled neighbours above and below then the value is 1 + 4, so 5.

You may notice that the values assigned to the directions are the same as the values of the positions in a binary number and this is no surprise; both are ways of representing possible combinations of 4 units which can each be in an on or off (stone or air) state.

Here is the map segment with the value of each tile filled in.  You might like to manually work out the value for a couple of the tiles yourself so you're clear on how it works.

Adding the Tiles

The order in which the tileset is laid out above is not arbitrary; it is laid out so that each tile matches what would be expected of a tile in the map that would be assigned that value.  Once we have a value assigned for each spot on the map we just need to look up that number in the tileset and place the correct tile there:

Wonderful!

Taking it Further

Part One - Removing Air

Whilst the above works very neatly for platforms floating in air, it doesn't yet fully handle two tile types.

Instead of a platformer imagine we're working on a top-down 2D RTS with two tile types of grass and water.  In such a case we would expect every spot on the map to have a tile graphic present; there's no open spaces like in our platformer.  This means that every spot on the map will need to have a value generated from its neighbours to determine which tile fits there.

We can use exactly the same neighbour valuing system as before, but we now need a way to differentiate between there being grass or water at the spot being examined itself.  This is actually very simply done - just add an extra value for the location itself, following the same 2 to the power of n pattern from the other values:

Let's decide that the presence of water means you do add on that position's value, whilst the presence of grass means you do not.  So a grass tile surrounded on all sides by grass would be numbered at 0.  A grass tile with water to the top and left would be 1 + 8 = 9.  A water tile surrounded on all sides by grass would be 16.  A water tile with water on all sides would be 1 + 2 + 4 + 8 + 16 = 31

Part Two - Greater Variety

How do we handle adding additional types of terrain?

Let's say we have three types of terrain in our top-down game: water, grass, and forest.  As well as water and grass meeting, we must now also deal with water and forest meeting as well as grass and forest meeting.

Previously there was two possibilities for each neighbour position (grass or water) so we used a binary counting system.  There's now three possibilities so we shall use a trinary counting system.  Our neighbour valuing system needs to be adjusted to match the new counting system:

Just as the binary counting system followed the pattern of 2 to the power of n, this follows the pattern of 3 to the power of n.

Using a trinary system each position has three possible states: grass, water, forest; or 0, 1, 2.  When there is grass in a given position, we ignore the value (multiply it by 0).  When there is water in the position we add on the value given (multiply it by 1).  When there is forest in the we add on twice the value (multiply it by 2.)

So if we had a tile that was forest with water above it, water to the right, forest below and grass to the left: 81 * 3 + 1 * 2 + 3 * 1 + 9 * 3 + 27 * 0 = 275

You might notice at this point that you'll need to draw 324 tile graphics to cover all the possible combinations in a three-terrain map.  This is a lot of tiles to draw by hand.  I would strongly advise looking into at least partially automated methods of producing the multitude of tile combinations.

Of course the system can be extended in just the same way for greater numbers of terrain types, but the number of tile graphics you would need would be even more huge.  Instead I would recommend placing some limits on what tiles are allowed to neighbour one-another.  For instance if forest and water tiles are never allowed to directly touch then the above example will need several hundred less tile graphics.

Firstly, a short explanation of what I'm trying to do:  There are plenty of examples of procedurally generated (or "randomly generated") level content for games, but they often lack a certain type of structure.  Generally they are used to produce very open worlds, where the player is free to explore as they like.  I am trying to make something that will create worlds with gated progression.  At its simplest this is Doom with a locked door that needs the red key which is off on a side path protected by monsters.  Less obviously lock-and-key examples would be games like Zelda and Metroid, where you need to gain certain abilities or special items to reach some areas.

Initially I thought to generate a simple world (maybe something like a Roguelike dungeon) and then develop techniques for adding on progression gates over it.  My first breakthrough came with giving up this idea. Instead I worked on generating the gating mechanisms at the same time as I generate the layout of the world.

My second breakthrough was to forget about the physical layout of the world.  What actually mattered was the connections of possible-movement between game areas.  So instead of working on a map of the world, I now work on a graph with the nodes as areas of the world and the edges as pathways between those areas that the player can move along.

Here's a graph representing a very simple world:

The player starts in the node at the red arrow, and wants to get to the node with the chequered flag.  But the pathway is blocked with a lock, so the player must first travel to the node with the key.  Not at all complex, but now the world has some progression structure to it.  This graph's layout was generated by a general purpose "add a goal, and lock it away" function - before that function was called, the graph consisted just of the starting node.  The neat thing is that the same function can be used to place the key, so creating:

When choosing where to add the node containing the key, the algorithm limits itself to picking amongst those nodes that it knows are accessible to a player who can access the lock.  This means that there was no possibility for the cyan key to be locked behind the pink door, as the cyan lock is accessible to a player with no keys at all and so the cyan key must be too.  The placing of the cyan lock now means that the pink lock/key no longer satisfy these requirements, but so long as they satisfied them when they were placed, and all locks placed afterwards satisfy them, it is guaranteed that with some work the player will be able to open the pink lock.

Here's where my world-graph generator is at currently.  The player starts at the red node, and wants to explore the world (there are actually specific 'goal' nodes in the map, but I figure it has enough confusing colours already.)  The player can freely move along the grey lines, but must have the correctly coloured key to travel along the coloured lines.  The nodes that hold keys are coloured indicating what key they contain.

There's a fair bit going on that isn't covered here, but I'll explain it all eventually.  The main issue I'm dealing with currently is the occasional creation of paths that cross one-another.  I am able to detect when that happens and can just discard the map and try again, but it'd be nice to just not have it happen at all.  I'm also working on making the linearity of the final map more controllable - currently it's just chance if the player can reach all the keys from the start or if they're hidden behind other doors so necessitating a specific order in which the keys can be collected.

That's all for now, I'm sure plenty more to come.

The concept is that the protagonist, Gomez, thinks he lives in a 2D world just like all those other characters in sidescrolling platformers.  But he soon discovers that really the world is 3D but it objects just behave as if they are projected on to a 2D plane, and of course he has the power to change which plane the world is projected to.

From one viewpoint two platforms might appear right next to one another, whilst if viewed from the side you would see they're actually miles apart.  The key to Fez is that when objects are viewed so that they appear to be next to one-another, they actually are next to one-another, and Gomez can easily hop between them.

I really like this attempt to make some sense of the apparently 2D world in which so many games operate.  Because of course almost no "2D" games really are showing us a 2D world.  So long as any elements of the world are allowed to overlap or there's any concept of things being in the background, the game's world must involve a third dimension.  Don't even get me started on two dimensional digestive systems.

I was interested in the challenges and design decisions that would need to be met when implementing the world of Fez, so I had a go myself.  It's pretty rough around the edges, and it's just a movement prototype set in a tiny world; but I think it's quite fun.  It almost goes without saying that I learnt a great deal making this.  I'm not taking this prototype any further; if you want to play it for real go buy Fez when it's released next year!

Pathfinding is a term used to describe the problem of trying to find the shortest path between two points.  In the case of Maggot Blaster, I needed to find the shortest path between each enemy, and the player.  Both were constantly on the move, the environment was complex and changing, and there were liable to be a lot of enemies.

The heightmap

Focusing on trying to make the game cope with very large numbers of enemies, I decided to use something like a hive mind approach.  Rather than each enemy work out their own path, a central AI will produce a global "heightmap" that all the enemies will use to find their own path using a much more simple (and fast) algorithm.

A screenshot showing the usually invisible pathfinding heightmap superimposed over a map.

Above you can see their heightmap from a very old build of the game.  Hidden under the brightest area you can just about make out the player.  From the player, the light spreads out as you'd expect in open areas but is blocked by walls and instead must find another route to get to those areas.

If you're placed anywhere on that heightmap then you can be guaranteed to find the player if you simply always move towards whatever local direction is brighter.  You don't get the exact shortest route as the heightmap is generated in such a way that implies you can only move in the four cardinal directions, when enemies can actually move in any direction.  However it always turns out "close enough", with the only artefact being a tendency for enemies to want to approach directly along one of the cardinal directions.

From heightmap to movement

Translating the heightmap data to enemy movement is very simple.  Just look at the values of the heightmap in the grid squares directly above, below, left and right of the grid square that the enemy currently occupies.  Using just those values, an acceleration is applied to the enemy split proportionally between whatever directions have the greatest increase in brightness compared to the current grid square.  To put it in less words, you imagine the heightmap is showing the contours of land with the bright areas are lower; then have the enemy slide down the slopes.

The characteristics of this sliding vary between enemies which give rise to some unique movement styles despite them all using the same pathfinding technique.  The basic slower enemies proceed along the heightmap at a reasonable speed and with well controlled acceleration.  Meanwhile the 'crazy purple buggers' (you'll see when you play the game) have a very high top speed but fairly low acceleration, which means they'll get up lots of speed when rushing towards the player but often overshoot their target or appear to skid past doorways they're aiming for.  It really helps give the various enemies their own character.

Suddenly, swarming

A problem with a few hundred enemies all following the same heightmap with the same rules is that they'll tend to all follow the same path and end up constantly overlapping.  Suddenly your amazing feat of producing masses of enemies looks like you've just produced one caterpillar enemy.

Information on how many enemies are in each grid square is already maintained for use in collision detection.  Whilst generating the heightmap I simply darken each grid square based on how many enemies are known to be there.  This has the effect of slightly shifting the paths generated from the heightmap so that they avoid other enemies.  As this alteration to the values take place during the generation of the heightmap they are carried through and keep the overall heightmap consistent: If the player is inside a building with two entrances and one is already filled with enemies then a new enemy approaching from outside will be likely to enter through the other entrance.

Not only did this change keep the enemies from forming boring orderly lines, but it also helped avoid a situation where the player can just stand at one doorway shooting all who come through it; the density of enemies at that entrance will encourage fresh enemies to seek an alternate route to the player even if it is a slightly longer distance.

Unexpected benefits

Now that a heightmap is being maintained for the whole level, I was able to find some other handy uses for it.

Finding ammo crates is an integral part of the game - they force the player to keep moving, and push them into dangerous and tense situations.  However it isn't fun just having no idea where the ammo is to start with.  So when the player is at a low ammo state the heightmap is used to draw a path of dots from the player to the nearest ammo crate.  How do I find which ammo crate is nearest? Simply look at the value on the heightmap where each crate is and compare them.

Similarly the heightmap value is used to determine if the player is close enough to cause maggots to notice them and start chasing.  Probably faster than working out the 'true' distance, and avoids maggots being able to see you through a wall.

Earlier versions of the procedural map generator would occasionally produce areas that were inaccessible.  The heightmap only holds values for areas that are accessible, so I was able to use it to identify these areas and avoid spawning anything in there.

The heightmap is also used when determining where to spawn fresh enemies.  As well as never spawning an enemy in a location visible on the screen I sometimes want to make sure an enemy is at a minimum distance.  For instance that crazy purple one I mentioned earlier has a special scream/roar sound when it spawns, so I want a little delay before it actually reaches the player's screen.  Simply limit spawning to areas with the correct range of values on the heightmap.

This one didn't make it into the final game, but it is possible to simply reverse how enemies react to the heightmap and they'll produce rather convincing fleeing behaviour.  Typically their fleeing would lead them into a dead-end corner of a building where they would sit quivering.

The future!

I'm very interested in using multiple heightmaps, and having entities switch between which they're following depending on what behaviour they should be producing at the time.  A "take cover" heightmap could be produced with areas that are out of line of sight of the player being the most bright.  Each entity could make up its own mind on if it would be best chasing, fleeing, or taking cover and pick the corresponding heightmap to follow.  Imagine hundreds of tiny infantry units scurrying behind cover as the player's mechanical war machine stomps by.

This was actually the plan from the start for what became Maggot Blaster, but such is the way of games.