Blog

Layer-Based Procedural Generation

One of the problems you'll face when creating an infinite procedurally generated world is that your procedural algorithm is not completely context-free: For example, some block might need to know about neighboring blocks.

To use graphics processing as an example, you might have an initial noise function which is completely context-free, but very often an interesting procedural generation algorithm will also involve a blur filter, or something else where the local result depends on the neighboring data. But since you only have a part of the world loaded/generated at a time, what do you do at the boundaries of the loaded area? The neighboring pixels or data isn't available there since it isn't loaded/generated yet. The layer-based approach I describe in this post and video is a way to address this issue.

I hinted at this layer-based approach in the overview post Technologies in my Procedural Game The Cluster. I have also written a post Rolling Grids for Infinite Worlds with the source code for the RollingGrid class I use for achieving practically infinite grids; only bounded by the Int32 min and max values.

I use two different layer-based approaches in The Cluster: Encapsulated layers and internal layers.

Encapsulated layers are the most flexible and what I've been using the most. Encapsulated layers can depend on other encapsulated layers, but don't know about their implementation details, and different encapsulated layers can use completely different sizes for the chunks that are loaded. I might go more in details with this some other time.

Recently I implemented the simpler internal layers. Internal layers are tightly coupled. They share the same grid, but chunks in the grid can be loaded up to different layer levels. I explain this in more detail in this video below. That's it for now. You can read all the posts about The Cluster here.

6 comments:

Sam Swain said...

First, I must say; this is great stuff, and very much along the lines of something I'm working on. Mine is more of the variable scale layers that you allude to also working on :)
Second, I have a question though. On the layer where you choose the radii of the circles, if you are allowing circles to extend out of their square, how are you avoiding overlap without introducing a dependency between adjacent squares in the same layer? This could mean you get different results depending on the direction you approach the square.
I'd be interested in talking this through with you as it's something I'm really interested in.

Rune Skovbo Johansen said...

Overlapping of the circles is avoided by using data from lower layers to calculate max allowed radii. E.g. when calculating radii in layer N, the only data needed from adjacent cells is the positions of worlds, not the radii of the worlds. Since positions were calculated in layer N-1 (or earlier), there is no dependency on data from the same layer in adjacent cells.

Feel free to comment more or mail me directly to discuss more.

Sam Swain said...

Ooh, just noticed your reply. Sorry.

I see what you're getting at, but I'm still not convinced I'm afraid. Surely if two adjacent cells in layer 2 work out their city radii based on the points in the 9 cells in layer 1, they are calculating radii based on a different set of source points. Even though they are only generating radii for their own cell, they will be making assumptions about what the other (adjacent) cell is going to produce. The only way I can see this working is if the calculations are naturally pessimistic in their radii decisions are some kind of 'minimum value' so that they happen to avoid generating an overlapping city.

It is hard to explain what I mean. I'll think some more about what I'm getting at. It may not apply to your specific algorithms though so you never see it. :)

Sam

Rune Skovbo Johansen said...

The simple approach to avoid overlapping is that each world uses a radius that's half of the minimum distance to the neighbor planets (of which all are known because their positions was generated in the previous layer). This ensures no overlap.

I wanted greater variety in the sizes though, so I assigned a random radius multiplier value to each world. A world can then take the radius multipliers of neighboring worlds into account when generating its own radius, though it still multiplies the final value by its own radius multiplier. Again, no overlap is guaranteed.

Unknown said...

Very interesting approach! Can you tell more about the algorithm which moves the points on layer1 to make them a little bit even distributed?

Thanks, Michael

Rune Skovbo Johansen said...

Thanks Michael. Each point is influenced by each other point that's within a specific influence-distance.

If the distance between them is exactly the influence-distance, the point is pushed away from the other point by 0% times the influence-distance.

If the distance between is practically 0, then it's pushed away by 40% the influence-distance. For anything in between it's linear interpolation between that (0% and 40%).

The push vectors are added up and finally applied to the point but stored under a new variable. The original position is still kept around to avoid ordering dependency. Adjusted positions are only ever calculated based on original positions of neighbor points.