Sunday, December 2, 2012

(re)inspiration for world generation.

Kind of a long post, be forewarned.

A few days ago I heard about a coding retreat that had the intention of coding up conway's game of life.  I had never coded that but heard about it numerous times and had always wanted to.  I was no available to go on the day of the retreat, but I did have some time that evening.  The kids had just been put to bed so I decided to break out a new cocos2d project and see just how difficult it would be to make this happen.

Three hours later I was posting to the cocos2d forum some example code on how to do it with the TMX map generator I wrote some time ago and cocos2d itself.  Here's a picture of the program running, and the source is linked in the cocos2d thread.

I was pretty happy with it.  It was a single evening, I went to bed at a reasonable time and I had something tangible (heh, well as much as software can be tangible) to show for it.

Fast forward a few days and something (probably a tweet I saw) got me to thinking about terrain generation again.  When I had stopped over a year ago I had been playing around with implementing simplex noise, which is basically an optimized version of perlin noise.  Which, if you've not heard, is basically a way of seeding random patterned static or 'noise'.  Feeling confident because of the conway code above I thought "Hey, that's using TMX maps.  I bet I could use the same basic code and some noise to do some terrain generation."

This time though I was a bit smarter.  Rather than try to implement simplex noise myself, I started looking around on github for something I could use.  After all, if someone has just what I'm looking for I could just use it rather than try to mess with all the math I've forgotten over the years.  After a little looking around I found this project.  No readme or instructions, but it looked contained and concise, so I gave it a shot.  It went fairly well at first, other than having to map via #defines some of the instructions that were GCC only to their LLVM counterparts.  I got it working with a little effort but I soon realized that for an iOS project this would not work -- it had non-ARM instructions which, while I'm sure are incredibly efficient, aren't available on iOS devices.

So I started looking again.  After a bit more digging I found this project, again on github.  It says it's c++ but has a .c extension, so I'm not really sure which it really is.  (And I don't really care...)  This was a bit more usable and allowed me to quickly take some of my previous tile-based textures...

Note that the numbers I wrote above are 0 based, while GIDs are 1 based.

...and see what I could get done.  I fairly soon had terrain generation going.  The problem was that it looked a little like clown barf.  Not nearly as useful as I was expecting.

I should diverge here and mention that I was using the simplex noise as a height map.  I like the idea of percentage based terrain so I took my noise values, floating point -1.0 to 1.0, added 1 then divided by two to get numbers from 0.0 to 1.0, thereby able to use them as percentages.  I then said 0.0-0.20 is water, 0.21-0.30 is sand, 0.31-0.70 is grass, etc.  The ranges act like elevation, going from water to sand to grass to hills to mountains.  So, patterned clown barf, but way way too zoomed out to be used as elevation.  As I was passing in my x/y coordinates to the simplex noise calculation, and via a little inspiration, I realized I needed to do some zooming on my values.

After some experimentation, a division (zoom?) by 15-25 seemed to work the best.  At a division of 25 the map looks something like this:

That's more like it!  Not bad for a few hours of work.  Certainly in the right direction, that's for sure.

(Oh, If you're looking, there's code at the bottom!  =) )

That was about a week ago.  I have since added CCPinchPanZoomController with my map to be able to...  er...  pinch, pan, and zoom.  Primarily zooming out.  This gave me a better guide of what I was looking at, especially all zoomed out.

Unfortunately that looks a bit generic.  So I got the idea to try and merge 2 different simplex noise calculations together.  I learned pretty quickly two things.  First, if you use totally unrelated seeds then you get less than ideal results.  Closer to clown barf again.  lots of ways to get it back to looking like static, but that wasn't what I wanted.  Second, I learned that adding the results of the two seeds together also gets you clown barf.

I have been able to get some interesting effects even if I haven't gotten the look that I wanted.

By using a modified seed (well using the original seed and making seed2 equal to "seed << 8" (seed bitshifted by 8) and then rather than adding the seeds together using either/or as my percentage I was able to get results that looked something like this:

Basic 2 noise generation

A step in the right direction, but not quite what I'm looking for.  The current iteration, though I'm not finished tweaking it, looks something like this:

I'll be changing this some more (mostly taking the grass and varying it with sand near the water and some additional lakes/water probably).  I could likely turn this into some sort of wetlands or swampy area.

I've also made a couple of different island styled maps as well:

Both of these have slightly different code paths for generation and neither are perfect, but I think I'll use the second as a base for a terrain type.

Speaking of terrain types, this new approach will allow me to use minecraft like biomes by using separate noise.  I had wondered how biomes work in minecraft but I think I'm beginning to understand at least one way to pull it off.  Different noise for different biomes and the biomes themselves are just a really zoomed in noise set themselves.  Likely with rivers along the biome edges in some cases.  I've also wondered for edges of biomes if you could have a swath where you vary your height percentages via a mix of the two biome types.  This way it would be less jarring at the edges.  I may try that out, if I do I'll document it here.

Additionally I should mention that I have plans for additional things.  I'd like to get back to points of interest (mines/caves, towns, etc) with possible roads and rivers generated as well.  I think roads were somewhat painful last go around so we will see how fast I get to those.  =)  I'd love to do forests that have their own set of noise as well as other "above ground" types of things.  Rocky terrain, vegetation, even things like animal dens would be cool.  The freeing thing here is that I don't necessarily have to place all of this at map generation time if I don't want to.  It can be a new map overlaid on top or even sprites on the base map (depending on performance).  Lots of work to be done.

Since I'm documenting this process I may as well put up some code snippets for anyone who wants to follow along at home.

Another small diversion:  In TMX maps (which is what I'm using here) you have values called gid's or global ids, that represent tiles.  Your tile atlas image starts in the top left at 1 and wraps on the right to the next line.  The way I've chosen to use the TMXGenerator I am assigning the gids directly in this project, which means a bunch of magic numbers.

This code gets called via the TMXGenerator class, which basically tells the generator what tile to put at each x/y coordinate.

I have also set up a basic enumeration for land types that you'll see used.

The comment lies, these are NOT by GID.  Oops.

Here is the original code for the "basic 2 noise generation" map above.

The mods there that I have neglected to talk about server to give different ratios to the different noise patterns.  I'm not entirely sure I remember how perlin noise works, but I believe I am making my own "octaves" here in a roundabout way using the two different seeds together.

The current iteration is a bit more complex.  It has the same basic structure, but rather than plugging in the values directly I made a function called landTypeFromValues that can be a bit more complex.  So it starts like this:

which is very similar to the original.  It however calls 2 functions that will be of interest:

This simply converts our type to a gid from the tile atlas.  I wrote this because I actually have 4 water tiles that are interchangeable and makes the water more realistic.  Presumably I'd want to do that with the other types as well, and this function allows for that.  ideally instead of using arc4random we'd be using a seeded number generator so it would create the same exact map every time.  Maybe later.  =)

The idea here is to not only do a generic elevation, but when you're in the water vary the water so that we can have some islands.  I should note here that this is experimental code and while it seems to work there are probably better ways of doing this.  I'm mostly iteratively looking at what's generated and tweaking as I go.  I hope to get a better feel for things as I do a little more work here and I won't have to do it that way.

The island codes are very similar, and surprisingly little code change.

The more the terrain varies the more complex these functions can get, likely spawning additional functions with all the other extras I mentioned above.

Just in case you really are following along at home, here is the rest of the TMXGenerator related code. Between the code posted here and above and github you should be able to reproduce my results.  Note that I used cocos2d 2.1 beta 3 to set up this project by modifying one of the stock hello world templates.

and the header

and finally, the stock code:

I hope that you find this introduction to terrain generation useful.  I am far from an expert, but I'm beginning to hit the point where I am (somewhat!) comfortable navigating procedurally generated chaos.  =)

No comments:

Post a Comment