Cellular automata for 2D map generation

 
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding
View previous topic :: View next topic  
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Thu Sep 07, 2006 4:13 pm    Post subject: Cellular automata for 2D map generation Reply with quote

Long ago, I made a roguelike mud that had a big 2D map shown in a top view. I used CA (cellular automata) to make caverns (all it had were caverns - caverns and orcs) and they were pretty awesome. Is that what folks use to make world maps for all these modern roomless muds that are so popular with the kids nowadays? Or do you draw the maps by hand?

If anybody is interested I could post the approach I used. Unfortunately the actual code is long lost.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Grabnar



Joined: 30 Apr 2006
Posts: 15

PostPosted: Fri Sep 08, 2006 3:53 am    Post subject: Re: Cellular automata for 2D map generation Reply with quote

Kjartan wrote:

If anybody is interested I could post the approach I used. Unfortunately the actual code is long lost.


I'm definitely interested.
Back to top
View user's profile Send private message
Author Message
KaVir



Joined: 11 May 2005
Posts: 565
Location: Munich

PostPosted: Fri Sep 08, 2006 10:24 am    Post subject: Re: Cellular automata for 2D map generation Reply with quote

Kjartan wrote:
Is that what folks use to make world maps for all these modern roomless muds that are so popular with the kids nowadays? Or do you draw the maps by hand?


I can't say what other roomless muds use (because I've never seen any others), but personally I construct the world from tiles (a bit like putting together a jigsaw puzzle). The layout of those tiles can be generated from a hand-drawn map, through in-game terraforming commands, or a combination of the two.

However I did use cellular automaton for generating cloud patterns for the weather.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Fri Sep 08, 2006 8:07 pm    Post subject: Reply with quote

I bet they would make nice clouds. I made some clouds with a sort of fractaly approach once, you can see them here (requires Java to view - drag the "timestep" slider bar to animate).

Ok, here's the approach I used for caverns (in English, as I have no code). It's quite simple, but it made some caverns that I really enjoyed running around in.

Fill in the map with solid rock. Clear a bunch of random horizontal and vertical line segments of random length. (You will have to try different values for "a bunch"). Then run the following randomized CA some number of times (ditto for "some number"):
1. count up the number of rock-filled neighbors of this cell, including the cell itself (so you get a number from 0 to 9)
2. generate a random number from 0 to 9. If it's greater than the number from step 1, set the cell to empty; otherwise don't change it.

By "run" the CA, I mean apply steps 1 and 2 to every cell of the map to generate a new map, then copy the new map over the old map. This randomly erodes away rock from the initial seed linear caverns, which quickly lose their visible linearity.

This produced cave-looking maps that were pretty well connected, so they were good for exploring, but had lots of nice little nooks and side-caverns to hide in.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Sat Sep 09, 2006 3:05 pm    Post subject: Reply with quote

I went ahead and made a java version of the thing. It could use a little work but it demonstrates the basic idea. (May require java 1.4 or better to view, I'm not sure.)
Back to top
View user's profile Send private message Visit poster's website
Author Message
Virago



Joined: 06 Jan 2006
Posts: 12
Location: Just south of Nashville

PostPosted: Sat Sep 09, 2006 3:37 pm    Post subject: Reply with quote

Both versions of this (clouds and caverns) are pretty cool. Thanks for showing us!

Were there ever any design problems that came up because of such a generation method, i.e. people getting stuck in walls? Were caves ever randomized?
Back to top
View user's profile Send private message
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Sat Sep 09, 2006 4:14 pm    Post subject: Reply with quote

I never generated the caves on the fly, I generated them beforehand and stuck them in a file, so people could only get to what they could reach from the entrance. I seem to recall I had some trick for making sure the whole cave was connected, but now I don't remember what it was - the algorithm from my earlier post can produce unconnected regions.

That's about as far as the cave algorithm got - after that I mostly worked on the orcs' hunting algorithms. Because cpu cycles are so cheap, you could do some nice stuff there with limited exhaustive searches. For example, the orcs could look around the cave and pick a good spot to post a guard, that had a view of as much real estate as possible; or, when they were trying to figure out where you had gone (the players could move a bit faster than the orcs at a full run) they could use the same algorithm to determine where they should go to see if they could spot you.
Back to top
View user's profile Send private message Visit poster's website
Author Message
clink



Joined: 12 Aug 2006
Posts: 9

PostPosted: Mon Sep 11, 2006 3:45 pm    Post subject: Reply with quote

Actually, I came across the Perlin noise method a while back, but haven't gotten a chance to experiment with it in a game. It looks promising in that it can be used for elevation, clouds and possibly caves as well.

The page I linked is a good starting place, but there are much better examples of what it can do if you drill down to a few of the resources mentioned on that page.

Clink
Back to top
View user's profile Send private message
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Mon Sep 11, 2006 4:16 pm    Post subject: Reply with quote

I think the "hierarchical functions" I use for the clouds are probably equivalent to 3D Perlin Noise.

The only place Perlin Noise falls down, in my opinion, is in its inability to produce structures that have one dimension much longer than the other dimension. For instance, you will have trouble getting realistic mountain ranges out of it, because it can't produce anything like a ridgeline. I have done some work trying to get around this by combining Perlin Noise with a separately generated network that is imposed from the top down (that is, the network is generated coarsely along with the Perlin Noise, and as the map is refined the network is also refined, adding splits and wiggles and such). I think this can be used to seed ridgelines for finer-detail Perlin Noise to get more realistic mountains; also for rivers, roads, etc. I have a demo of this (requires Java).

What I really want to do is have multiple sets of networks - ridge lines, rivers, and roads, for example - that all interact with each other as the function is refined to more detail. So, rivers run down the valleys between ridgelines, roads run alongside the rivers and build a minimum of bridges, etc. Maybe train tracks that hate to bend or climb are another option.

You can kind of fake extended structures by generating a contour map based on a Perlin Noise height function, but I think that probably isn't a good approach. The structures so generated tend to have lots of loops, which makes them bad for e.g. rivers.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Fri Sep 15, 2006 11:29 am    Post subject: Reply with quote

I also generated cloud formations with CA previously, but now I use 4 dimensional Perlin noise (or is it 3d? one input is time, that's all I recall, been a while since I worked on it). It gives a random-ish look with smooth transitions across time (and the ability to predict the weather is nice). I also use Perlin noise for world creation - since the equations work on just room A and its surroundings, it works well for on demand world creation. By iterating through every coordinate in the world, it came up with this map (it output it as colored ascii whive I loaded in photoshop and blended).

(be warned, huge resolution)

World Map


Section Map



I can see mountain ridges in my game, I'm not sure why you thought that'd be a problem.
Back to top
View user's profile Send private message Send e-mail AIM Address
Author Message
Kjartan



Joined: 13 May 2005
Posts: 110

PostPosted: Fri Sep 15, 2006 11:44 am    Post subject: Reply with quote

Can you post a picture with ridgelines? Maybe we aren't talking about the same things. Here's what I meant by ridgelines (taken from maps.google.com, these are some of the mountains just north of Los Angeles.)

The mountains are very strongly lined up along ridgelines there. The ridgelines branch, but the branching ridgelines include pretty much all of the mountain peaks. This is characteristic of mountains caused by crustal folding followed by erosion, I think.
Back to top
View user's profile Send private message Visit poster's website
Author Message
clink



Joined: 12 Aug 2006
Posts: 9

PostPosted: Mon Sep 25, 2006 7:21 pm    Post subject: Reply with quote

After doing some more research on the Perlin noise algorithm, I have found that it is specifically designed to avoid producing patterns as Kjartan describes. It can be used as an overlay on a base ridgeline pattern to make it look more realistic (flawed).

Not to say you can't (as shown) make interesting looking terrain with the algorithm and some tweaking. But making features that are the result of a complex interaction between geology, weather and other planetary factors, requires something besides noise at the base. I apologize for leading anyone astray.

It is still clearly useful for creating things like weather or cloud patterns where unpredictable transitions are desired, but complete randomness.

clink
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2002 phpBB Group
BBTech Template by © 2003-04 MDesign