Generating Procedural Worlds in Inventaverse (Part 1) - By Josh Hollis

It's a problem every programmer is faced with, early in their career.  You know... "Removing elements as you traverse an array changes the total number of array elements thus opening a gateway to the nether-world."  Although this is closely related to the problem that is the focus of this article, this is not the problem today.  Allow me to set the stage.

So there I was, writing algorithms for the purpose of generating procedural worlds in my indie game project, Inventaverse (a retro styled 2d massive multiplayer maker game that runs on the web).  The randomly generated worlds in question, need to have a good mix of open space, floating islands and tunnels.  Why?  Because Inventaverse features 14 playable characters, each with a unique play style.  Some have grappling hooks, some fly, some can dig through the ground, so building a random world generator that will consistently pose a challenge is not a trivial problem.  

Not impossible, but not trivial.

I know what you're thinking: "Why not use cellular automaton to generate random topographies".  I was thinking the same thing.  I pulled up some code I had written centuries ago that does just that.


Here's how it works.
1. Populate a matrix(2D array) with random values between 0 and 1.
2. Snap those values to 0 or 1 by checking if they're less than, or greater than a supplied parameter, we'll call it Q.
3. Evaluate the neighboring values of each index in the matrix, how many of them are 1's?
4. If the number of neighbors with a value of 1 is greater than some supplied parameter(C) then we set the value of the array at the index in question to 1.  Otherwise, we set it to 0.

The results were great.  They were random, lots of space, floating islands, tunnels, awesome!  However, there was a very noticeable artifact.  The topographies generated by this method were all somewhat... slanted.  After some brief investigation it occurred to me that the mere act of traversing the array top to bottom, left to right, was causing the anomaly.

See the upper-left to lower-right tendency?

When using a cellular automaton in this way, you're evaluating the neighbors around the current index, then subsequently changing the current value to 1 a portion of the time.  The slanting I was seeing was a side affect of altering the values in the matrix in a specific order.  And sometimes, it looked really cool!  I considered the slanting effect a moment and decided to keep it around, for variety!  

But clearly we couldn't have a slanted world every time, so I set out to traverse the matrix in such a way that the map generated wouldn't be skewed in any particular direction.  My options were as follows:

1. Consider the source matrix as immutable, write the results of my transformations to a new matrix and return that.
2. Traverse the matrix non-linearly by scanning the matrix in a back and forth fashion.

 
I opted for the latter.

So, now instead of processing the 2D array from top to bottom, left to right, I processed it left to right, then right to left, then left to right etc.

Uniformly distributed randomness, perfecto!

Doing this solved the problem straight away.  So I pulled the "slanted" world generation logic into a separate function which I called "Linear", and put the scanning style world generation logic into another method called "Scan".  Then I came up with the idea of processing the matrix by using spiral traversal, and the results were awesome.  

But that, my friends, is a story for another day.

Until next time...