Rabidgremlin's
Soapbox

After watching this fantastic interview with Sean Murray about No Man’s Sky I’ve been inspired to write a bit about procedural content generation. I’ve been tinkering with procedural content generation for years, using it for everything from creating games levels to generating sample data for testing and it is a fascinating subject.

So what is procedural content generation?

Wikipedia says “procedural generation is generating content algorithmically rather than manually… The term procedural refers to the process that computes a particular function”. The Procedural Content Generation Wiki suggests it “is the programmatic generation of game content using a random or pseudo-random process that results in an unpredictable range of possible game play spaces… procedural content generation should ensure that from a few parameters, a large number of possible types of content can be generated”.

That’s quite a mouthful! Basically the idea is to get the computer to generate content so you don’t have to :)

Lindenmayer systems

To get the ball rolling I’m going to start with Lindenmayer systems or L-systems. Developed by Hungarian biologist Aristid Lindenmayer in 1968 to describe and model the growth of plants, L-systems can be used to generate amazingly complex structures from a set of very simple rules.

An L-system is represented by a simple string of characters (much like a DNA string) for example “FG+G-F. A very simple system would consist of just a single letter, for example “F”.

It also has bunch of rules. These are simple substitutions that define how each letter in the system should be replaced or expanded.

For example we might have two rules that say “F=G-F-G” and “G=F+G+F”, which basically says replace all F’s with “G-F-G” and replace all G’s with “F+G+F”.

To generate our output we simply iterate a number of times, applying the rules to the result of the previous iteration.

For example if we start with:

• Start: F
• Rules:
  • F=G-F-G
  • G=F+G+F

And we iterate once, we get:

G-F-G

If we iterate again (applying the rules again), we get:

F+G+F-G-F-G-F+G+F

And after you iterate 5 times you land up with this enormous string:

G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G+F+G+F-G-F-G-F+G+F+G-F-G+F+G+F+G-F-G+F+G+F-G-F-G-F+G+F+G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F+G-F-G+F+G+F+G-F-G+F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F+G-F-G+F+G+F+G-F-G+F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G+F+G+F-G-F-G-F+G+F+G-F-G+F+G+F+G-F-G+F+G+F-G-F-G-F+G+F+G-F-G+F+G+F+G-F-G-F+G+F-G-F-G-F+G+F-G-F-G+F+G+F+G-F-G

Enter the turtle

So great, you now have a very long line of text but it doesn’t seem very useful…

Well imagine a tiny little turtle, this turtle is dragging a pen behind himself and everywhere he walks he leaves a line. He is also a very well trained little turtle and he can follow commands to walk forward or turn left or turn right.

So looking at our string again let’s define that F and G means “go forward 80 steps” and - means “turn left 60 degrees” and + means “turn right 60 degrees”. Then lets turn our generated strings into a list of commands for our wee friend, the turtle.

With 2 iterations (and a result of  F+G+F-G-F-G-F+G+F) our turtle will draw the following:

If we keep incrementing our iterations, our turtle will draw:

With 8 iterations we end up with quite a cool pattern (known as a Sierpinski Triangle). It could be used as a nice (but predictable) maze for a game or perhaps an interesting texture.

Teleporting Turtle

Let’s teach our turtle some new tricks. Firstly we will teach him to remember his current location and which direction he facing. Next we will teach him to teleport from his current position back to a previous one that he has remembered. We’ll tie these to the [ and ] characters in our L-system strings.

These new commands let us create branching structures, perfect for generating organic things like plants.

For example with a very simple L-system like this:

• Start: F
• Rules:
  • F[+F]F[-F][F]
• Iterations: 5
• Angle: 20

We get this neat plant:

With these very simple types of rules we can generate a swag of different plants:

Small changes, big impact

One of the nice things about procedural content generation is that a small tweak to the input parameters can result in big changes in the output. The following animation shows the same L-system but with varying iterations, angles and step lengths.

A new dimension

Lastly, our turtle doesn’t necessarily need to only draw only lines or operate in 2 dimensions. Laurens Lapre created a great tool in the early 90’s called LPARSER which generated 3D models using L-systems. Below are a couple of these models rendered in Blender. As you can see in the “spider” and “air horse” examples, organic creatures can also be generated using L-systems. Laurens’ tool also has a mutate function that mutates the generated system to great effect.

Wrapping up

Phewww, well that was longer then I expected! If you’d like to find out more about L-systems then check out  The Algorithmic Beauty of Plants by P. Prusinkiewicz and A. Lindenmayer. Also all the code (mostly Processing) used to generate the images above can be found here.

If you enjoyed this post then check out my other posts on procedural content generation.

I’d thought I’d give the Kinect Fusion demos a try. Kinect Fusion allows you to take 3D scans of things by waving your Kinect around. It’s designed to work with the desktop/Windows version of the Kinect but I’d thought I’d give it a go with the Kinect from my old XBox 360.

Turns out it works pretty well. The resolution is pretty low but if you were using one of the new Kinect v2s things would be a lot cripser.

Here is a selfie (holding the Kinect at arms length):

And here is one of son number 1 (who did a fantastic job of sitting very very still):

You if you want to give it a try yourself you can download the Kinect SDK from here.

Actually it’s more what I did last month.

RC simulator

A mate of mine bought himself a swish RC quad-copter. As part of the package he bought Phoenix RC. It is a simulator that allows you to plug your RC controller into a PC and you can then practice flying (and crashing) virtual RC models before tackling the real ones. Very useful and it clearly proved that I should never attempt to fly a real RC helicopter.

Kinect

Believe it or not, I’m actually getting paid to hack a Kinect. Im using the OpenNI framework so hacking really consists of installing the software and then using a nice high-level framework that does all the hard work for you. I’ve been very impressed with the skeleton tracking.  I’ve been able to simultaneously track 3 people with full skeletons without any issues.  This is the guide I used to install the base software. You should also check out the Ogre and Unity demos.

Unity

Whilst tinkering with the Kinect I ran through the Unity 3D platformer tutorial. Unity is very impressive. If you want to create a 3d game I’d start here.  The basic version is free. The cross platform nature of the engine is impressive to.

Auckland Buses app

I finally got around to releasing my Auckland Buses app for Android. It only took a few hours to put together.  I’m experimenting with an ad supported model. The app has about 225 users, averages around 25 impressions a day. So far I’ve made 49c so not really a money maker :) What is interesting is the fairly poor fill rates I get some days.  If you had marketing dollars to spend,  mobile ads might be the way to go as not many people seem to be tapping them.

That’s about it…