## Procedurally Generated Content

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

bocochoco
Posts: 317
Joined: Thu Aug 06, 2009 8:22 pm UTC

### Procedurally Generated Content

I've written an implementation of the diamond-square algorithm in Python as part of a world generator for a tile-based game I've been working on. It works well enough, but I am at a loss for how to continue generating content on the fly that lines up correctly when tiled. That is, they tile seamlessly rather than having distinct edges where two sets meet.

Ex.
Spoiler:

This was made by using the values the diamond-square algorithm returns as the Hue in a HSV color, and saving it as a png.

I can't think of a way to smooth out the borders between blocks. Do any of you know of a better way to do this or a way to smooth out the borders?

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

### Re: Procedurally Generated Content

Hmm, what happens if you force the boundary values to agree? E.g. when generating a tile to the right of one which already exists, initialise the left-most column of values with the data from the right-most column of the pre-existing tile, and don't modify these boundary values during the algorithm.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

### Re: Procedurally Generated Content

Finite element methods do something very similar to this. In a finite element model, each element must inherit the boundary properties of its adjoining elements, generally up to a certain level of smoothness.

A more simplified example comes from cubic spline interpolation: If you want to interpolate a set of data using a series of cubics, then you need to enforce some conditions where those cubics meet. It is obviously not sufficient to just force equality at the boundary nodes: otherwise, you'll be non-differentiable at those nodes, and you'll have "corners" in your interpolated curve (which is typically undesirable). In cubic spline interpolation, it is sufficient (and in fact, I believe it is necessary for uniqueness) to force the first derivatives equal to one another. Then you can compute your spline coefficients.

In your case, what I would do is begin by specifying these conditions a priori at the boundary nodes. Specify a value and a gradient (without looking at your code, I assume you must have some gradient-type term in there, because you do not seem to generate based on random point processes). Then, generate the values on the interior nodes. This will ensure that your plateaus or valleys will seamlessly cross tile boundaries.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Procedurally Generated Content

Why tile it? Just generate an infinite blotch procedurally and slice it up. Only compute the areas you need at a given time.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

bocochoco
Posts: 317
Joined: Thu Aug 06, 2009 8:22 pm UTC

### Re: Procedurally Generated Content

Ended wrote:Hmm, what happens if you force the boundary values to agree? E.g. when generating a tile to the right of one which already exists, initialise the left-most column of values with the data from the right-most column of the pre-existing tile, and don't modify these boundary values during the algorithm.

I hadn't thought of that. It would probably just make the boundaries 1-off, but perhaps it would read the values and use them in the calculations.

gorcee wrote:Finite element methods do something very similar to this. In a finite element model, each element must inherit the boundary properties of its adjoining elements, generally up to a certain level of smoothness.

A more simplified example comes from cubic spline interpolation: If you want to interpolate a set of data using a series of cubics, then you need to enforce some conditions where those cubics meet. It is obviously not sufficient to just force equality at the boundary nodes: otherwise, you'll be non-differentiable at those nodes, and you'll have "corners" in your interpolated curve (which is typically undesirable). In cubic spline interpolation, it is sufficient (and in fact, I believe it is necessary for uniqueness) to force the first derivatives equal to one another. Then you can compute your spline coefficients.

In your case, what I would do is begin by specifying these conditions a priori at the boundary nodes. Specify a value and a gradient (without looking at your code, I assume you must have some gradient-type term in there, because you do not seem to generate based on random point processes). Then, generate the values on the interior nodes. This will ensure that your plateaus or valleys will seamlessly cross tile boundaries.

I'm not sure I understand exactly what you're saying here. I don't really use much in the way of gradients, it's all created from random floating point values. Here's the code, if it helps.

Code: Select all

`from random import Randomimport mathclass Generator:    gRoughness = 0.0    gArea = 0.0    randgen = Random()    seed = None        def __init__(self, seed = None):        if seed is not None:            self.seed = seed        else:            self.seed = self.randgen.random()                    def setSeed(self, seed):        self.seed = seed    def generate(self, width, height, roughness):        grid = {(x,y):0 for x in range(0, width) for y in range(0, height)}                    self.randgen.seed(self.seed)                c1 = self.randgen.random()        c2 = self.randgen.random()        c3 = self.randgen.random()        c4 = self.randgen.random()        self.gRoughness = roughness        self.gArea = width + height        self.Divide(grid, 0, 0, width, height, c1, c2, c3, c4)        return grid                    def Divide(self, grid, x, y, width, height, c1, c2, c3, c4):        e1, e2, e3, e4, middle = 0.0,0.0,0.0,0.0,0.0                newWidth = math.floor(width / 2)        newHeight = math.floor(height / 2)                if width > 1 or height > 1:            middle = self.FixNum(((c1 + c2 + c3 + c4) / 4) + self.Displace(newWidth + newHeight))            e1 = self.FixNum((c1 + c2) / 2)            e2 = self.FixNum((c2 + c3) / 2)            e3 = self.FixNum((c3 + c4) / 2)            e4 = self.FixNum((c4 + c1) / 2)                        self.Divide(grid, x, y, newWidth, newHeight, c1, e1, middle, e4)            self.Divide(grid, x + newWidth, y, width - newWidth, newHeight, e1, c2, e2, middle)            self.Divide(grid, x + newWidth, y + newHeight, width - newWidth, height - newHeight, middle, e2, c3, e3);            self.Divide(grid, x, y + newHeight, newWidth, height - newHeight, e4, middle, e3, c4);        else:            c = (c1 + c2 + c3 + c4) / 4                        grid[int(x), int(y)] = c            if width == 2 and height == 2: grid[int(x+1), int(y+1)] = c            if width == 2: grid[int(x+1), int(y)] = c            if height == 2: grid[int(x), int(y+1)] = c                            def FixNum(self, input):        if input < 0: input = 0        elif input > 1: input = 1        return input            def Displace(self, size):        max = size / self.gArea * self.gRoughness        return (self.randgen.random() - 0.5) * max`

WarDaft wrote:Why tile it? Just generate an infinite blotch procedurally and slice it up. Only compute the areas you need at a given time.

Not tiled exactly. Just that a new block would be generated to exist next to another already existing block, extending the 'world'. Essentially, I am trying to make it an infinite world in any given direction. I've generated up to 1024x1024, and it takes longer the bigger you have it generate. 128x128 seems to be the best size for this, though 256x256 worked well too.

Maybe if I modified it to take in an existing set of blocks and pre-populate some of the values.

Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Procedurally Generated Content

So, the diamond square:

Step 1: Start with a nearly infinite patch (power of two). Assign corner values.

Step 2: Determine convexity of patch. Take average of 4 corners, add in a convexity randomizer. Magnitude of convexity randomizer is determined by scale of the patch.

Step 3: Fill in mid-points of patch edges. Take the average of the 4 (including the neighboring center points), and apply convexity randomizer (at a 1/sqrt(2) smaller scale).

Step 4: You now have 4 new square patches. Recurse on the ones you care about "enough steps".

... now we make it demand based.

We start with what is known as a quad tree. Each node in the quad tree has 4 children -- NW, NE, SW and SE. These children can be empty.

Because we are lazy, each node stores 9 points, 4 of which are "optional" (have a bool that says if they are calculated yet). This is not that efficient, but it is far easier to program -- and there is always a programmer:efficiency trade-off. Optimizing this for the factor-of-two memory savings is a second pass.

When you want to know the height of a location, you ask the quadtree. It dispatches it to the appropriate child, creating it if it doesn't exist yet.

To spawn a child, all you need is its 4 corner values. To send a request into a child, you need both its 4 corner values, and its 4 siblings.

A quad node always has 4 corners and its middle value. When you spawn a child, it generates its middle value just from its 4 corners.

To recurse into a child, first you find its 4 siblings. In general, 2 of its siblings will be children of your siblings, and 2 of them will be internal to you.

You ask your siblings for the appropriate child (or null if you don't have siblings in that direction), and spawn/get the children of yourself.

To spawn a child, you build the appropriate edge-center value first. This is generated by averaging the two ends of the edge, your middle value, and (possibly) the middle of the appropriate sibling. Then you add in a convexity random factor (which is modified by scale). As you always have your siblings when queried (be they null or not), this is relatively easy to do.

The result of all of this? We can now build terrain dynamically. The terrain only comes into being when someone requests it.

The time and storage it takes to "start looking" in a particular area is logarithmic in the "huge size" of the map. So if you want a map that is 2^128 pixels accross that is perfectly smooth and uses 64 bit pointers and floating point values, this takes (4 child pointers *8 bytes + 9 floating point values *8 bytes + 4 guard bools * 1 byte) times 128 levels times (4 siblings + actual zoom value) per level = a whole 70k of overhead.

And if each pixel represents a square milimeter of terrain, this generates a flat map that is bigger than the diameter of the visible universe. For 70k of overhead.

Another nice thing about this is you can send your request down with a resolution attached -- ie you want location (x,y) at resolution (blah), and have it return the center value of the patch at that resolution and go no further. This gives your system "nearly infinite zoom in/out" capabilities.

Another neat trick is that you can define a local context of this ridiculously huge map. I'd define such a context as 4 nodes that bound the region, and an offset into the top-left most one. You'll note that a "parent node" can be synthesized that does not align with your original quad-tree grid, because quad-tree nodes are not aware of their parents -- simply hand them off 4 of them to a synthetic one that is better aligned with your local context, and go to town. Such a "local context" trick lets you deal in more sane coordinates (instead of 128 bit ones, for example), and reduces the number of recursion levels required to access a point (the 2^128 map requires 128 recursions).

"Blitting" a region of the map into a flat memory buffer is also reasonably practical, as iteration over a region of the quad tree isn't that tricky. This lets you have the quad tree as "backup", while working in a more simple tile-based system.

---

Have caution when using the above. I just designed it, I haven't implemented it.

I notice that you are using a "heavy" language like python. My memory estimate will go up in such languages. However, my memory estimate was based on a frankly ridiculously huge map -- I suspect a map with coordinate resolution at the cm level that is as large as the surface of the Earth might be sufficient?

That requires 32 levels, or ~18k of overhead. On a 32 bit system using floats instead of doubles, closer to 9k of overhead.

Halfhearted optimization can get this down to 1/2 or less of that. Serious memory optimization would involve an exponential number of virtual table based tree nodes (ie, don't store nil pointers), storing deltas instead of values for the intermediate ones (scaled by the scale factor of the level), removal of redundant corner values, etc, and that could probably drop it down another factor of 2 or more. But I'd advise against optimizing it for memory unless you really need to.
Last edited by Yakk on Wed Apr 13, 2011 1:25 pm UTC, edited 2 times in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

### Re: Procedurally Generated Content

You may also want to try looking at models like Perlin noise. One nice property of noise functions like these are that they continue infinitely in all directions, without directly repeating anywhere. Also, unlike enforcing boundary conditions on your chunk generators, you can do random-access to any point in your infinite world, so you don't have to generate chunks contiguously, and are free to throw away chunks and regenerate them later if you don't want to keep everything in memory.

bocochoco
Posts: 317
Joined: Thu Aug 06, 2009 8:22 pm UTC

### Re: Procedurally Generated Content

Yakk, that is a very good idea. I will look into implementing that sort of functionality tonight. Thank you for the suggestion

letterX wrote:You may also want to try looking at models like Perlin noise. One nice property of noise functions like these are that they continue infinitely in all directions, without directly repeating anywhere. Also, unlike enforcing boundary conditions on your chunk generators, you can do random-access to any point in your infinite world, so you don't have to generate chunks contiguously, and are free to throw away chunks and regenerate them later if you don't want to keep everything in memory.

I found a perlin noise implementation and tested it out, it works great. Seems quite quick as well. Much quicker to generate a new row/column rather than generate a new chunk. I'll play around with this for a while.

Thank you for the help!