# Evolving a Terrain Generator

I just recently asked this question and the conclusion seems to be that using genetic programming (GP) for Procedural Game Content Creation hasn't really been done. I want to change that.

I'm fairly certain GP could be deployed to help find a new terrain generator. The question I'm getting to is how might this be achieved?

All GPs have a few basic parts that can be generalized for all GPs (parent selection, recombination, mutation, survival). I can figure those out on my own. The issue arises in the problem specific parts. These are how you represent the problem in code (this usually uses a tree), and how you evaluate how good a generator might be (this can be one or more values).

# The questions in a nutshell:

• How would you represent a terrain generator in a way that can be parsed into a tree?

• What kind of terrain would this have to generate? (heightmap, vertex graph,...)

The less this is based on a hightmap the better.

• What would be used to evaluate the fitness of a solution?

ex: we want interesting terrain so we could have one of the values be the average change in the normals for each vertex on the terrain.

• I really feel you don't want GP for this, but GA. The algorithms for creating noise, for example, are really hard to generate on the fly and it would be harder to create a fitness function than it would be to create a system that satisfies it. GA is more suitable to tweaking the parameters of an existing system. – DampeS8N Oct 26 '11 at 11:35
• GP makes interesting solutions humans never really think of. Thats what I'm looking for. GP is tough to use, and this probably wouldn't be the best way to use this in the industry, but it would show some major feasibility if it turns out. – Alex Shepard Oct 27 '11 at 22:33

You may have some luck with an approach similar to Karl Sims' genetic images.

He uses a simple set of operators in a LISP-like language such that any operator's output can be utilised to influence the image, similarly to in some shader languages (ie. a scalar would be a greyscale value, a vector3 would be RGB, etc..).

Though I guess that's implementation stuff, so what you probably want is his keywords, which (iirc) contain all the basics:

• trig functions (sin, cos, tan, etc..)
• position (x, y)
• basic math operators ( sqrt, pow, abs, inverse )
• noise functions ( fBm, noise2, noise3 )
• other fractals ( mandelbrot, julia )
• interpolation functions ( lerp, quad, step, smoothstep )

(Some of the above may not be in his implementation; I found his work a long time ago and have actually made a few attempts at what you're describing over the years - so memories may be leaking :)

# Keeping it interesting (and fast)

I had a bit of luck with a multi-layered approach which massively reduced the amount of dead evolutions.

1. a set of ranges are generated for each operator (or mutated from previous rounds)
• these ideally keep the values within a "sane" range for each function, but can evolve into ranges which have surprisingly useful results, which seems like the "right" thing to do
2. generate a few algorithm trees
• for each of these generate a few heightmaps at random positions and evaluate fitness
• if we have a lot of good matches then evolve down this branch a bit, perturbing the ranges from step 1 slightly in each child
• otherwise, we've probably got bad ranges, go back to step 1

# However...

Now I've conveniently skipped over the fitness algorithm, I mostly used Karl Sims' approach of "unnatural selection" where you see the current generation in the middle square of a bunch of offspring (popularised by Kai's Power Tools back in the day - here's an image of what I mean)..

However you could probably have a set of training images, perhaps some from satellite imagery and a few artificial ones with particular qualities and then maybe use wavelet or 2D FFT analysis on them vs. the terrain you're testing?

This is an interesting topic, but I doubt what you needed an answer on :)

EDIT: ahh. had to remove a bunch of links because I'm a new user :-|

• This seems to lead to the same thing I was getting at, the algorithms are not meant for constant random generation of content but in training the generation towards a single or limited set of results... and still requires a human to make the selection. – James Oct 26 '11 at 16:44
• From what I can figure fitness would have to be based on some statistical analysis of the results. The factors that I could come up with are the amount of variance inside of a single generated terrain averaged over some number of generated terrains (maximized) and that values standard deviation (minimized, for stability of the variance). But then I guess we would have to maximize the average change in heights between any two generated terrains as well. – Alex Shepard Oct 26 '11 at 17:43
• @Alex perhaps this paper will be of interest too. I imagine if you turned some of the mentioned technique on its head you could use it to guide the fitness. (Or it could well just be what you want :) – pentaphobe Oct 31 '11 at 5:45
• @phobius WOAH!! Cool. I need to explore it some more, but it looks really promising. Now to turn it into a search problem... – Alex Shepard Nov 1 '11 at 15:07

I am not sure you can answer this question but I feel an explanation as to why might be a helpful enough answer. So, Answers in a nutshell:

• You will want to pick a terrain generation where certain aspects of it can simply be based off of data values. This is not hard to do but does require you to pick a terrain generation. Since the area I am working in is in voxel generation, things like sampling rates, tunneling passes, elevation levels etc would be things that can be put into data and 'evolved' over.
• Kind of goes hand in hand with the first part. It doesn't matter really what form of generation you go with as long as you can set different properties of it. This choice should have more to do with the type of game you are looking to make.
• This is where it breaks down. I can not think of a way to measure this aside from a Person actually looking at the world and going "Oh that's nice". But this removes the computer doing its own self iteration. This also implies that you are going to use this form of generation to create a single world in the end, looking for the 'best' one as opposed to a random one every time.

Genetic Algorithms are usually used to solve a known problem where you can define the environment through rules. Then you can create data sets that represent different properties that affect how things react to the rules. The computer then plays a 'round' with the initial data set, selects the top X number, mixes their values after pairing them together and does another round.. A common example of this is 'breeding a better troll' (doing the breeding to find a set of values where the troll generally does very well in its environment (Is able to hunt and eat, either kill or stay away from villagers, can collect loot and amass all the shiny objects it desires, etc).

I am just not sure what you are trying to accomplish is applicable in the realm of terrain generation. The only thing I can come up with would be game content sorts of evaluations where you did not want to plan out a world but wanted to make one that AI pathing can be calculated in nicely or something like that. Even with this however you are looking for a single or at the least limited set of worlds.

• Ah... I think you are confusing evolutionary algorithms with genetic programs. EAs are used for optimizing and tweaking inputs to an algorithm. GPs are used for building the algorithm itself and that is what I'm looking for. Good answer though. As a note: these terrains don't have to be realistic, just interesting. – Alex Shepard Oct 26 '11 at 0:17
• If you can not define 'interesting' in a programmatic manner, then you are going to have the problem I am trying to get at in the answer. – James Oct 26 '11 at 0:27

What kind of terrain would this have to generate? (heightmap, vertex graph,...)

Definitely a vertex graph (a mesh), it is compact storage-wise and can be rasterized (tesselated) on demand.

How would you represent a terrain generator in a way that can be parsed into a tree?

Cellular automata. I can think of two implementations:

1. Rule-set automata, maybe with elements of finite-automata (when the current state, like attempts counter or idle time, is taken into account).

• Each node is initialized with a random state
• Each node have an instance of solver attached
• Each solver keep calculating next state until it runs out of rules or reaches its ideal state (I'm done here)
• All next states are calculated first and then applied all at once before the next calculations start, so the calculation order won't matter

Rule-set itself may be represented as a branching decision tree or simple command batch (not sure if it will work)

It's just one rule set for every node

1. World-builders. Instead of applying a solver for every single node you can create just a bunch of them and allow them to navigate the mesh.

• Each builder have its own rule-set
• Prevent them from entering the node occupied by another builder
• Each builder may be represented as a branch of the tree
• During the evolution builders may duplicate

Still, I'm afraid that the second approach needs to be backed by the first one: initial randomness needs to be smoothed and I'm not sure if builders can do the trick. Every living cell does have mitochondria after all.

What would be used to evaluate the fitness of a solution?

The integrity of the resulting terrain - it' shouldn't look like a mish-mash. And the diversity - generally we want as much of available variations to be represented as possible (the flat wasteland from one edge to another is no fun). Maybe something more complex like how neighboring nodes fit each other (tundra in the middle of the desert, what?)

Gotta try it for my self with my mesh generator when/if have some spare time =)