Someone here posted the idea of using a cellular automaton to create terrain, with more realistic rivers, streams and etc. I've Googled and looked at articles for hours, and found only one non-specific master's thesis. Has anyone worked on this? In particular, it would be really great for games generation if the automata could be run with a pre-determined border, so newly generated terrain could be linked with existing terrain. I have no idea what I might do with this, but I needed a break from coding stupid client-side &#106avascript!

Interesting idea.
I think, one state has to be "No terrain selected yet", otherwise rivers whould flood everything and look... er.. rather like an ocean.

One part of the transistion function whould look like:
X(2dimensional list neighbours, self) = if (self != "no terrain selected yet) then self;

After that, we have to define how terrain shall be generated. And I think we need a nondeterministic transistion function or we whould get boring shapes (If I calculated that right in my mind ;) ) It should be a function, which weights the surrounding areas into several probabilities, for example, if a forest-tile is next to an unselected tile, the probability of the tile becoming a forest rises and the probability of staying unselected sinks. Obviously, if all 8 surronding squares are equal, the probability of becoming the same landshape should be 1.

Generation whould be plotting several starting cells on fields and just iterate until no more unselected tiles are left.



Furthermore, you could think about a second or a third iteration on a meta-level. For example, you could generate something like "deep forest" on an existing forest or "high mountains" on existing mountains.
And even furthermore, we could look at more fields than the 8 fields surrounding the cell...


I gotta think about that a bit and maybe I'll code some testing programs about that. :)

Look at Penny Sweetser's research. She gave an interesting presentation on this topic at the AGDC in 2004, based (IIRC) on her PhD research.

Cheers,

Timkin

Quote:

Original post by ID Merlin Someone here posted the idea of using a cellular automaton to create terrain, with more realistic rivers, streams and etc. I've Googled and looked at articles for hours, and found only one non-specific master's thesis. Has anyone worked on this? In particular, it would be really great for games generation if the automata could be run with a pre-determined border, so newly generated terrain could be linked with existing terrain. I have no idea what I might do with this, but I needed a break from coding stupid client-side &#106avascript!

I have done a system that does that. Its not overly generalized and is a system for a large world (with partial generate on the fly) with an array of seed values that are built to a valid pattern (rivers not flowing upstream into each other, etc...) The seed values then are used to build a basic template pattern that can be randomized somewhat within its own area. I also had it do patterns for coastlines and mountain ranges.


As Ive written here before I found that doing 'on-the-fly' full incremental creation can be impossible because once you create a chunk you cant backtrack once the player sees it to resolve conflicts in patterns growing in different directions and then coming back together. The more complex the scenery, the more conflicts there are to resolve. (example- a major river curves back onto another major river because of semi-random direction variations, it cant suddenly stop -- it has to have a source which usually is a network of smaller
rivers coming from mountain runnoff or springs (and sometimes a lake which has its own feed-in pattern).



The system I did had cells (river endpoints) that traversed the terrain map and wandered and branched following rules (mostly tables with percentages and branch frequency thresholds to control direction change and right/left/Y branching).
When branches happen additional cells are created heading off in a different direction (and usually a differnt size with different parameterized behavior).

You could use something like that and also have it carve out a V contour (mesh heighmap) perpendicular to its direction (with varying steepness depending on erosion factors like rock not carving the same as sedimentary areas) -- this having it cut a realistic drainage patterned terrain with intersting overlapping patterns of branches....




Keyword to find more along similar subject:


Infinite worlds

procedural generation

Quote:

Original post by Timkin Look at Penny Sweetser's research. She gave an interesting presentation on this topic at the AGDC in 2004, based (IIRC) on her PhD research. Cheers, Timkin

Very interesting, and thought provoking. I wonder if a CA would work well for weather simulation? A completely random system for weather over a continent would give bizarre results in some cases, but a CA could be made where the weather propogates across the continent, following the "imagined" jet stream from west to east. The cells could span medium-sized map areas, so the computations wouldn't be very demanding at all.

You could also look into how actual weather prediction works when designing weather simulation algorithms.

Quote:

Original post by Vorpy You could also look into how actual weather prediction works when designing weather simulation algorithms.

I thought about that. I haven't Googled anything yet. I'm thinking that an ad-hoc, simple system could provide just enough "realism" (willing suspension of dis-belief) that it would be good enough.

I built a quick PHP prototype of the weather CA. Would it be appropriate to post the source here? (It's not really AI.) Or would it go better in game programming, or somewhere else?

Just post a link to it, so that people can download it if they like.

As for the weather CA, you might get some good success from using a two-layer approach. On the upper level CA you generate meso-scale variability in the weather. Each grid square of the upper level contains a CA grid of finer resolution for the lower level. This lower level CA is constrained by the upper level grid it is contained in. You'd also have to satisfy boundary constraints. Does this make sense?

Cheers,

Timkin

I implemented a two-layer approach. The upper layer is the "jet stream" layer, using a simple sin function to simulate the way the jet stream moves across N. America. Currently, that only has a wind direction and velocity. The lower, weather layer has wind, temperature and moisture, which are used to calculate clouds and precipitation, if any.

I'll have to think about the upper level having some constraints on the lower, as that would remove some of the chaotic touchiness of the simulation which can lead to frigid cold or intense heat.

You can play with it at the ca_weather page. There is also a link to download a zip containing the source and graphics files.

There is a LOT of room for improvement, and any suggestions would be welcome!