Procedurally Generated Structures over large quantitys of chunks in 3D Terrain Generator

Question

I am creating large scale worlds using 16*16*16 voxel chunks which are stacked up to 32*32*32 in dimensions and I have hit a bit of a Bump in the road so to speak.

I want to create large structures that span 20+*20+*20+ chunks in volume which are created from procedurally generated structures as well as using templates for some of the content. Now I have an issue. The visual render range is up to 32*32*32 chunks and while I have up to maybe 40*40*40 chunks held in memory at a time when possible.

The structures can be anything like towns, dungeons and roads. I was thinking something like perlin worms for roads and just lay them over the terrain in the x,z and then analyze the path for bridges etc..

The structures and collection of structures need to be pre-generated before the player is within visual range or work more like perlin noise does for heightmaps (best solution). (to avoid the players seeing the generator at work). They also need to be consistent with the world seed every time.

I have thought about this a bit and have 3 possible solutions.

1) Generate the structures based on a point of origin for the structure generator. This causes several issues though as even if I generate from the center of the structure, the structures can easily cross into the potential visual range of the player.

2) Pre-Generate "unreachable" chunks and then page them in and out in order to generate the structures using the above method. This also seems rather unnecessary.

3) I had an idea for dungeon generation in which I generate point clouds/nodes for rooms.

Steps:

a) When the generator finds a "node" it creates an x, y and z size to create a box basing it from the originator point of the room** (centre or corner of the room) and the room type.

**x,y,z relative to 0,0,0 worldspace calculated like so new Vector3((chunkX*16)+voxelX,(chunkY*16)+voxelY,(chunkZ*16)+voxelZ)

b) Once a room size is calculated, check for overlaps and if one is found do one of several things. If the room overlap is high up lower it down till either the roof or the floor are flush. If the roof is flush build a stairs up to the room and remove the walls that intersect.

b) Look Down, North and East for a room maybe with a small cone and attempt to create a hallway between them.

This would probably work somewhat, especially if the center of the dungeon is the main hall/boss room.

This would be different for towns, cities, and surface dungeons. Still seems a little choppy though. Any ideas?

All methods need to analyze the terrain in large quantities for a valid location to spawn the structures.

I was hoping somebody might have a more organic solution or even just a simpler solution that doesn't require me to "Look" so far ahead.

Thank you in advance.

Answer 1

It looks to me that there are two different points in your question:

1. What would be the best way to pre-generate structures before the player is within visual range in a voxelized scenario?
2. Is your reasoning for generating 3d dungeons ok?

The first question has many implications. One of them is addressed by the link suggested by Thorinll (how to manage structures larger than your chosen voxel chunk size).

But you seem to be particularly interested in finding a method for generating things at a safe distance from player and also being able to repeat the generation process easily again.

As mentioned in your own question, it's all related to your pseudo-random noise (PRN) generator. Any PRN can be repeated, because they are deterministic. Moreover, an adequate PRN should also give you the necessary coherence [1] so you can partially generate structures at one moment, generating the rest of them later.

What you don't seem to consider is that you don't need to pre-generate all your structure to position it in a safe distance from player. I.e.: You don't need to generate all dungeon rooms to figure it out how big it is, you could just determine its bounding box before hand.

Neither you seem to be dealing with infinitely large structures, so I guess you could consider your PRN space equivalent to world space and use a point lattice [2] to determine if there's a structure in a given world point or not. You should only take care to choose an interval (between your points) large enough so that you can fit the biggest of your structures without colliding to another.

You could also "play" with the coherence of your noise to make sure that the parts (rooms) of a structure are never (or very much unlikely) unrelated. For that you just have to map a range of numbers to the types of rooms adequately. For example, if you map [0.0, 0.25) => kitchen, [0.25, 0.5) => living room, [0.5, 0.75) => bedroom, [0.75, 1.0] => bathroom, it would be unlikely or even impossible to have a kitchen beside a bathroom, because it would be unlikely or impossible to find a 0.0 besides a 0.75.

Also, you could trigger your generation routine whenever the player moves from intervals on this lattice. You could start "loading" your strutures' metadata to RAM at a certain distance from player, just like you would do with paged terrains.

This way there should never be a structure popping from out of nowhere, crossing "(...) into the (...) visual range of the player".

On your question about your method for generating a 3d dungeon, I think have done something similar to it on this game:

http://www.ludumdare.com/compo/ludum-dare-28/?action=preview&uid=30821

But, although the game is "2.5D", the level generation is in 2D. I just had a few room shapes which I was randomly attempting to fit along each other following a very simple heuristic. Despite the fact that it was very unoptimized, it ran fast enough to generate reasonably big levels.

[1] http://libnoise.sourceforge.net/glossary/index.html#coherentnoise

[2] http://mathworld.wolfram.com/PointLattice.html