Generation Algorithms and Potential Performance Pits

[Praxian]

I've been thinking about the procedural generation of terrain, and I've begun to write some algorithms for it. I've run into some issues. Fair warning, this is a long post. Lots of questions.

First, let's talk about some high-level stuff to make sure we are on the same page. First, the terrain will be made of voxels (having multiple sized voxels can create some really nice structures, see Stellar Overload (warning, vibrant streamer hair)). These voxels will form the terrain in accordance to pseudo-random coherent noise generator functions. The resultant terrain must subjected to an array of analysis functions to populate the terrain with assets and to determine the the coefficients of the environmental matrix for the AI. There are additional functions that may decided the placement of rivers, paths, caves, or other special kind of structures that require terrain modification. All of these I am developing algorithms for. I've also been considering erosion as a way to make terrain more natural looking, but I'll talk about that later.

Okay, If we decided on a Biome model like 7dtd or minecraft, different variations of those noise functions can be used. For instance, a plane would use a low amplitude and spread out noise function, to ensure no point is too high and a lot of very gradual slopes appear. I can think of some alternatives to the biome model, but I won't go into them here. Anyways, minecraft initializes by generating the locale terrain and as you move about the world, the rest seems to be generated as new chunks load (at least this is what appears to happen). 7dtd appears to do it differently, since the world is finite, the entire world seems to load upon start up, and none of it is generated in real time.

I am interested in creating a fairly high fidelity world, and to do that a lot of functions will be needed to generate, populate, and analyze the terrain. I'm going to just assume all of these will be rather expensive computationally, and if the player(s) is exploring, new chunks must be created in real time, since we can't generate them all at once because the world will be ``infinite.''

My first question is: Should there be any rendering or performance considerations baked into the fundamental structure of my generation algorithms, like limiting the length of rivers and paths?

My second question: When initializing the world, how much of the world should be generated? A small amount, then have it generate more in the background on other threads? An arbitrarily large could be generated so that more can be dedicated to performance if the player(s) decide to stick around their starting area. Doing this would be more akin to generating something the size of a 7dtd world, but with a border, then kicking in the generation functions once they cross over that border.

My third question: How big should the world feel? We could have life size mountain ranges that take days to traverse game time, or have a mountain biome the size of the embry-riddle, and only take a few minutes to cross. I think this is mostly a question of taste, as the sizes should certainly be somewhere in between and dependent on the methods of travel available to the player. I feel like this question also can be expanded into a sense of place. Should we have minimaps, normal maps, or no maps? Again 7dtd and minecraft provide an interesting contrast. Minecraft is played mostly with no map, and I find that leads to a feeling of androgyny, with many of the shapes, colors, blocks, and resources being the same almost everywhere, there is a persistent feeling of relative location. 7dtd on the other hand I think does the sense of place better, the map providing an absolute frame of reference from the first minute of game play.

My fourth question: Should values for the environmental matrix generated during terrain generation, or be determined by terrain analysis algorithms. Say iron abundance is a part of the environmental matrix. When generated a chunk maybe generated with a large vein of iron, the algorithm creating this vein of iron can either report the value to the environmental matrix or the area can be sweeped by a terrain analysis function and the value be reported to the environmental matrix there. Maybe there is a potential to multithread this process, have once thread generate, another sweep for iron content, and another find out where rocks should be placed. This brings up another performance point. If a new chunk has not interacted with AI, maybe we can avoid loading or building the environmental matrix.

My fifth question: Molten H2O. Should we have oceans? I think lakes and ponds can just be placed in low points, maybe connect them with rivers using pathfinding algorithms that look for more low points. Also, how do we want to do water? A lot of voxel games seem to have a hard hard time with water, 7dtd is a prime example, Minecraft is the only example that has done it well, that I can think of at least. Maybe that can be source of inspiration for us, especially if we go for a more stylized graphical style.

My sixth question: Should we do weather? Although difficult, I think there is an enormous amount of potential.

My seventh question: Options option options. Is there a downside to making a lot of variables public? I personally think that we should give the player(s) as many options as we can. To prevent overwhelming more casual players, we can have a host of fun presents.

My eighth question: How long can this post possibly be? Not too much longer.

My ninth question: Do you guys have any suggestions or considerations?

[JakeNeighbors]

@Praxian

1. Not really, but look at 2
2. Don't think about it as "when initializing the world". The algorithm should be designed to that should I need a chunk, I get chunk. The player when spawning/moving/teleporting wherever on the map, it doesn't matter. The player object needs a chunk that they don't have, they call the function, now they have it. One cute feature (if even remotely feasible) would be generate a simplified (fast) algorithm to approximate distant terrain. Which would be replaced when the time is right.
3. Bigness of world is a @Mikemikenmike question. It would be nice if there was an parameter in the terrain generator to scale this up and down. But, low priority in contrast to getting the algorithm working. Personally I say massive. Massive with small voxels.
4. I would say yes and no. The terrain generation function (in my mind) should be something like generate_terrain(x, y, z, seed). Therefore, requesting deeper terrain should behave like everything else.
5. I would just say to have a certain depth z be the water table (if we do water). Doing water is up to you and @Mikemikenmike
6. Doing weather is fine. Mixing that in with crafting objects that are influenced by weather gets a bit tricky.
7. My Christmas list for settings include: a default settings button (nuke settings to default), general options (use these to rock and roll fast), advanced sections for details in tabs (think graphics settings menu / sound menu / etc but with terrain settings / ai options / etc), export settings to be used for a dedicated server in JSON/YAML format.
8. I have honestly seen worse
9. It would be neat to make a map that could infinitely scale like minecraft (well until it hits the max signed long integer size). The further you go, the algorithm will provide.

[Praxian]

1. See 2
2. Coolness, I'm thinking the terrain can easily be instantiated in layers. The first layer being the voxels, and the second being like large foliage, trees boulders, that kind thing. I also know a common distant terrain technique is to place 2d sprites at a distance. A rendered distant height map instead of rendering distance voxels might be a good idea too,
3. Scaling parameters are a great idea. I can only foresee performance issues at large scales in high locations were LARGE amounts of voxels are visible and need to be rendered, but maybe that could be solved with 2.
4. Ahh I think you misunderstood. I was asking if the terrain generator should be include terrain analysis functionalitiy or if the terrain should be analysed after generation by seperate functions, and not during. I think it should be separate, that way new or updated analysis functions don't break the generation mechanism, plus maybe more versatility for parallel processing.
5. I think that is a good way to begin with water, but that might leave high elevation terrain with no lakes.
6. It would be pretty neat getting custom windmills working.
7. Sounds good, lets make sure we begin with those setting being available in mind.
8. I'm sure it will get worse haha
9. That is the plan, having non-physical boundaries is lame. Also, I think that a simple erosion function, essentially another layer that deforms the terrain in coherent ways, say valleys around rivers, would add a lot to the realism to the world.