Selecting points randomly in regions corresponding with neighbors, avoiding infinite recursion

Question

Pardon the wall of text. I'll add images later. I need to generate a somewhat realistic map of cubic meter voxels, with water, sand, grasses, trees, minerals, deserts, beaches, islands, etc, without any sort of voronoi cop-out(i.e. be smart about relating these factors to each other). Yes, this is a game.

I figured I'd generate critical points randomly and interpolate them for elevation and humidity readings, but I'm at a loss with random generation. Basically I need a somewhat even distribution of points without having to make the full list at once. I need to generate roughly 20x20x20 at a time, and probably work with approximately 1000x1000x1000 cells of critical points, but I'd expect strange things to happen at the edges of the large cells. Does anyone know of any way to select points in this way? The real trouble is that points should prefer to be in proximity to others in "mountain-range" style chains.

The problem here is that this is happening across these 1-km cells.

I can simply pick points this way within a cell, but since a cell and its neighbor need to be dependent on each other, my trivial algorithm would have encountered the need to head to infinity for one of these cells, or see a grid-like pattern of broken chains. The chains should not break more frequently on cell boundaries. If they do a somewhat problematic wafer-like pattern shows in generation and makes for a poor generation that is unusable for design/gameplay reasons.

n.b. For the purposes of these, the system-level random generator can be seeded and is practically uniform. As far as within a cell, I can select chains just fine.

I also considered having a cell spill over into any ungenerated cells so its chains start connected to existing ones, but that would break the determinism of generation simply based on location and seed, adding order of generation as a factor.

Again, for the purposes of realism and design I'm trying to stay away from using Perlin. Or should I post on gamedev.SE?

Answer 1

The key concept is to create the interfaces between a cell and all six of its neighbors before filling in the cell. Picture creating your entire world as a grid of hollow boxes, but before you do that, create it as a wire-frame outline, but before you do that, create the grid of wire-frame intersections.

Here's a simplistic approach -- you'll have to improve this. First, consider this method of generating the entire world at once:

(1) select all the vertex voxels -- perhaps the upper north west voxel in each cell -- and set its world attributes to reasonable values based entirely on location and seed.

(2) select the lines of voxels connecting the vertices, and fill in all their world attributes, based on location and seed, but constrained to match up with the existing vertex voxel values at each end.

(3) select the planes of voxels describing the faces bounded by the existing lines, and fill in in all their world attributes, based on location and seed, but constrained to match up with the existing line voxel values along the edges.

(4) fill in the cell, based on location and seed, but constrained to match up with the existing bounding six faces.

Now, consider that this method doesn't need to be done all at once. All that is necessary is that you create all six faces of a cell before filling it in, and that you create all four bounding lines of a face before you fill that in, and that you create the two end points of a line before filling that in. After the first cell, some of these will already exist.

The reason I said that you'll have to improve this idea is that it produces noticeable gradient boundaries at the cell boundaries. I'm afraid that each interface voxel will not only need to contain world attributes, but the rate of change of each attribute across the interface at that point. This implies that each line voxel will have to contain two rates of change for each attribute, and each vertex, three.

I'm not going to describe how you would constrain the gradient of a world attribute as it approaches a voxel with a predefined gradient because I'm sure you can handle it, my answer is already too long, and I don't know how.