Mazes continued

Apologies for the outage, I have been sick for the past few days.  Little has been accomplished since late friday evening.  However, I did get some good coding in that evening and would like to share some of the results with you.

Before that though I would be remiss if I didn't give a nod to Jamis for his great blog about mazes.  I had my implementation done before I saw his page, but it's definitely a fantastic resource, and helped me flesh out my understanding of what I am doing.

Anyhow, shortly after my last post I went after making rooms.  Rooms turned out to be harder than I expected.  I first tried to make random rooms placed randomly around the map, allowing for overlaps. That didn't work out as well as I'd hoped.  I added some collision detection of sorts to the random placement of rooms as well as boundaries between rooms and the results were much better.  Once I had the rooms more or less placed as random rectangles, I moved to making 2 to 4 exits per room.  At this point I switched the depth-first algorithm to be after room generation and it very nicely made corridors between the rooms.  (You are in a maze of twisty passages all alike!)  Finally I added code to the corridor searching to say if they had found a room exit or not.  If they did not then they were "trimmed" and re-filled, leaving the larger dead-ends out.  There are still dead ends because of the way my code works though--any dead end that branches off of an exit gets kept.  That will need to be addressed.

Here are some pictures, both with and without the dead end trimming.

I like the overall look with the dead ends intact.  However for the project I'm doing I think I'd like to trim all dead ends as well as make the corridors straighter (rather than randomly turning at every possible juncture).  I'll probably work on that some tomorrow.  In addition, better odd shaped rooms would be useful here as well.

I also dropped my room code over the top of the caves project I did a bit ago and changed the tiles so the rooms were slightly different.  Just for fun.  There could be uses to a mixture of these two methods, though this is very rough.

As usual, the source to the new maze with rooms can be found here.

Edit:  Added with additional code to a github repo by request.

(Comment out lines 267-268 in DungeonLayer.m to stop the dead-end removal.)

More later!

Mazes

I've taken a little time today to work on dungeons some more.  Caves are good, but not quite what I am trying to achieve.  I may refactor the caves some to be a mixture of natural caves and also carved out rooms.  For the moment though I want more "man-made" types of dungeons.  So I've started looking at maze generation and how that would work.  I'll then move on to rooms and connecting them hopefully with the maze generation code.

I've been looking around and there are some very good and well documented ways of making mazes.  Check out this link from wikipedia and also this one that is more comprehensive, though a bit heavier read.  I've also been referring some to drow's great resource here, though not using the source, just the brief description.

Here is my first phase of maze generation, using the same atlas as I made for the cave generation.

127x127 generation

It also works for much smaller mazes.

9x9 map

The project does have it's warts though.  maps greater than 127x127 don't seem to render properly (the data seems to be there, maybe a cocos2d bug?) and non-square maps don't get traversed correctly.  But all in all a decent depth-first recursive prototype.

Per usual you can get the source here.

Cave Generation

And just like that...

Cave generation.

I basically did the following from this link:

"The basic idea is to fill the first map randomly, then repeatedly create new maps using the 4-5 rule: a tile becomes a wall if it was a wall and 4 or more of its nine neighbors were walls, or if it was not a wall and 5 or more neighbors were. Put more succinctly, a tile is a wall if the 3x3 region centered on it contained at least 5 walls. Each iteration makes each tile more like its neighbors, and the amount of overall "noise" is gradually reduced."

This was done with cellular automaton, similar to the game of life simulation.  Cool stuff.

You can get the source here.

I've not done much lately on the terrain generation project.  However I have yet to write code for dungeon or maze generation.  I am going to make that as a next attempt.  I hope to have something to show here in the next few days depending on how much time I have to work on it.

I also wanted to add a link here for posterity.  It's a fantastic resource for procedurally generated content and contains lots of good information on what it is, how it's used, and resources to implementations that are out there.  The angband variants seem to have a great grasp on AI and dungeon generation and there are articles for that there as well.  Good stuff!

Edges!

So, I dug up my old tile edge code last night.  I was able to integrate it into the simplex noise project fairly easily, though there were a couple of snags because of the differences in the way that terrain type was handled underneath.  I was the happiest with the rotation code as almost nothing had to change there.

I've also added a toggle with an additional atlas to show the terrain edges.  Here is an example.

Some basic terrain edges

Terrain edges that are obviously different for visualization

I'm very happy with how this has turned out.  It would be a fairly solid foundation for a procedurally generated overhead map system.  There are some things I'd prefer worked better (the GID less tied to the tile types for example, or hills and mountains being better for edges), but overall this is a good starting place.

You can get the code here.

Source posted

I've updated my code a little and put an example up that you can download here.  It's the screens I've previously posted about with a menu system.  This is prototype code, not production ready code.  Enjoy!

Height Mapping Tests

I've been playing around with different types of generation.  Some are better than others.  There are some interesting possibilities though.  I am considering making this project into a cocos2d example project, possibly for the TMXGenerator.

I have done all of these with the framework that I laid out in my previous post.  I have in some cases changed the mod1 and mod2 values though for the most part those stayed constant.  For the marshlands specifically I changed those to be very small to make it more varied.  The rest of the time this is height mapping two simplex noise passes in conjunction with each other.

Here are a few examples that I have saved the code for.

Large layered grass and water

Simple watery beach area

Desert Area

Canyons and hills

lakes

high terrain

islands v3

small layers

Marshland

Noisy lakes and mountains

odd islands

Whew!  That was a lot of tweaking!  For the most part all of those took 5 minutes or less, though a few (like the noisy lakes) took way longer just because I was tweaking them over and over to get the effect I was looking for.

All of this working with height maps makes me want to add a "random" height map system.  One that can build a range of height information and mix that range info with 2 (or more?) simplex noise values that are related.  Hmm...  I could probably base it all off of the same seed number as well.  Interesting.  Anyway, it would be a lot of work to do what I've done here -- this took probably 2 hours of playing around.  Building a randomizer would likely take a bit longer than that.  However once done it would be really cool to save interesting height map generations for later use.

I also am itching to get the tile edges working as well.  I think I need to do some maintenance though and make the new button actually work properly rather than leaking memory all over the place.  Not to mention having sliders to change the generation would be great as well.  Kind of a particle generator for maps I guess.  =)

I hope to post more soon.

(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.  =)