Noise Generation

[Alan]

As part of a new game project, I've been tasked with producing a large scale playing map which is subdivided into multiple regions. Initially I considered 4 separate regions, so dividing the playing area into 4 would seem simple, however given the size of the map, this does not really produce what I need. There are a number of problems which need to be investigated here; as the size of the map cannot be known in advance - players are essentially positioned at a random point along an every increasing spiral. The test data has a radius of 1250 odd places (or towns) if you want to look at it like a normal map. The question is; is there a method of subdividing the entire area given into a small number of regions which themselves span multiple locations - similar to how countries may look?

The ideal code (any language within reason is acceptable) should take an x,y coordinate pair and return a number between 1 and (say) 10 inclusive which determines which region those coordinates belong to. Obviously mt_rand(1, 10) is not going to work here.

I've looked at perlin noise, and simple addition of scaled sin/cos waves - neither of which provided decent results. Voronoi noise looks as if it may have interesting results, though I'd prefer something a little more random in its edges. Plasma fractals (Diamond square) were considered but they appear to require the size of the playing area to be known before hand

[sniko]

4 separate regions

As you considered 4 separate regions, why did you stop at 4 when it didn't produce what you needed? 1250 / 4 = 312.5; as in 4 regions would have (say) 312 places (towns). We could get this even further, and divide those 4 separate regions in half; creating 8 regions = 156.25 places (towns), and eventually reiterate that process until an accepted result is reached?

I see you mentioned radius, so this map is a circle or sphere, right? - or did I interpret incorrectly? Therefore, we get a random point along an ever increasing spiral mathematically by adopting the radius and manipulating it.

Moving on.

Is there a method of subdividing the entire area given into a small number of regions which themselves span multiple locations - similar to how countries may look?

From my knowledge, kind of.

Let's say we went out into a field and threw a mesh somewhere on our field (map). The area covered by our mesh would be our largest area; our countries. To then get the smaller places ("states") we'd throw another mesh [on top of the one we'd just thrown], which, if you can imagine, would give the impression of the "countries" being built up by the "states" (from the more defined mesh). Essentially, we're just moving back to the 4-8-16-32... separate region "puzzle", which again was something that didn't give the result you were looking for.

Question, and it may be a dumb question; why not adopt Voroni noise, and apply another algorithm on top of that - Worley noise, Plasma fractals, or even, Perlin noise?

Edited February 14, 2014 by sniko

[Alan]

Remember that nothing is known about the eventual size of the playing field - in fact at any point, there is no way to tell just how big it would get. In tests, the approximate radius of the area (assuming roughly circular) was 1250 and given a point every now and again along the length of the spiral (unlike the attached image), I was looking at around 1 million points.

Adding noise together is often like hashing the string representation of a hash - it actually reduces the entropy and becomes far more difficult to write a single generator which given a simple coordinate pair, returns a sane, useful value.

This shows a rough concept using a linear (Archimedes) spiral. This is representational only, the current point (or town coordinate if you prefer) uses a much more complex algorithm however the region generation routine is by necessity identical no matter what underling routine is used to generate the location of the points.

Note that in the above example, there is 5 separate regions, none of them bisect a point (though that can be ignored as the current algorithm will ensure that no matter what type of noise generator is used to create the regions, no region boundary can every bisect a point.

The scale of the regions would by necessity need to be controlled - as obviously having 100 million points with only 5 regions and a layout as seen above, would mean that we could guess that there would be one very small (yellow) region surround by 4 much larger (almost 25% each of the whole area) regions - hardly a viable proposition. What is needed is something whereby regions have a roughly even coverage, perhaps split into multiple separate regions.

[sniko]

Ah, I see.

If there's no way to tell how big it would get; would that suggest an infinite range, or is there an absolute limit at 1 million points?

What is needed is something whereby regions have a roughly even coverage, perhaps split into multiple separate regions. - is this not the 4-8-16 puzzle we went through earlier? Whereby we split the playing field up in such a manner that results in an "even coverage"?

We could adopt the "divide-and-conquer algorithm"?

[Alan]

Sadly not infinite, however I'd hazard a guess that 1 million points is the upper limit of what a single server (or rather a single cluster) will run without any degradation in speed. It looks like simplex noise might be the solution, producing what seems to be pleasing gradients, with a little mathematical trickery I suspect this will suffice however I'm going to keep looking for other solutions.

Simplex noise with 3 levels in a terminal (75% scale)