So, the diamond square:
Step 1: Start with a nearly infinite patch (power of two). Assign corner values.
Step 2: Determine convexity of patch. Take average of 4 corners, add in a convexity randomizer. Magnitude of convexity randomizer is determined by scale of the patch.
Step 3: Fill in mid-points of patch edges. Take the average of the 4 (including the neighboring center points), and apply convexity randomizer (at a 1/sqrt(2) smaller scale).
Step 4: You now have 4 new square patches. Recurse on the ones you care about "enough steps".
... now we make it demand based.
We start with what is known as a quad tree. Each node in the quad tree has 4 children -- NW, NE, SW and SE. These children can be empty.
Because we are lazy, each node stores 9 points, 4 of which are "optional" (have a bool that says if they are calculated yet). This is not that efficient, but it is far easier to program -- and there is always a programmer:efficiency trade-off. Optimizing this for the factor-of-two memory savings is a second pass.
When you want to know the height of a location, you ask the quadtree. It dispatches it to the appropriate child, creating it if it doesn't exist yet.
To spawn a child, all you need is its 4 corner values. To send a request into a child, you need both its 4 corner values, and its 4 siblings.
A quad node always has 4 corners and its middle value. When you spawn a child, it generates its middle value just from its 4 corners.
To recurse into a child, first you find its 4 siblings. In general, 2 of its siblings will be children of your siblings, and 2 of them will be internal to you.
You ask your siblings for the appropriate child (or null if you don't have siblings in that direction), and spawn/get the children of yourself.
To spawn a child, you build the appropriate edge-center value first. This is generated by averaging the two ends of the edge, your middle value, and (possibly) the middle of the appropriate sibling. Then you add in a convexity random factor (which is modified by scale). As you always have your siblings when queried (be they null or not), this is relatively easy to do.
The result of all of this? We can now build terrain dynamically. The terrain only comes into being when someone requests it.
The time and storage it takes to "start looking" in a particular area is logarithmic in the "huge size" of the map. So if you want a map that is 2^128 pixels accross that is perfectly smooth and uses 64 bit pointers and floating point values, this takes (4 child pointers *8 bytes + 9 floating point values *8 bytes + 4 guard bools * 1 byte) times 128 levels times (4 siblings + actual zoom value) per level = a whole 70k of overhead.
And if each pixel represents a square milimeter of terrain, this generates a flat map that is bigger than the diameter of the visible universe. For 70k of overhead.
Another nice thing about this is you can send your request down with a resolution attached -- ie you want location (x,y) at resolution (blah), and have it return the center value of the patch at that resolution and go no further. This gives your system "nearly infinite zoom in/out" capabilities.
Another neat trick is that you can define a local context of this ridiculously huge map. I'd define such a context as 4 nodes that bound the region, and an offset into the top-left most one. You'll note that a "parent node" can be synthesized that does not align with your original quad-tree grid, because quad-tree nodes are not aware of their parents -- simply hand them off 4 of them to a synthetic one that is better aligned with your local context, and go to town. Such a "local context" trick lets you deal in more sane coordinates (instead of 128 bit ones, for example), and reduces the number of recursion levels required to access a point (the 2^128 map requires 128 recursions).
"Blitting" a region of the map into a flat memory buffer is also reasonably practical, as iteration over a region of the quad tree isn't that tricky. This lets you have the quad tree as "backup", while working in a more simple tile-based system.
Have caution when using the above. I just designed it, I haven't implemented it.
I notice that you are using a "heavy" language like python. My memory estimate will go up in such languages. However, my memory estimate was based on a frankly ridiculously huge map -- I suspect a map with coordinate resolution at the cm level that is as large as the surface of the Earth might be sufficient?
That requires 32 levels, or ~18k of overhead. On a 32 bit system using floats instead of doubles, closer to 9k of overhead.
Halfhearted optimization can get this down to 1/2 or less of that. Serious memory optimization would involve an exponential number of virtual table based tree nodes (ie, don't store nil pointers), storing deltas instead of values for the intermediate ones (scaled by the scale factor of the level), removal of redundant corner values, etc, and that could probably drop it down another factor of 2 or more. But I'd advise against optimizing it for memory unless you really need to.
Last edited by Yakk
on Wed Apr 13, 2011 1:25 pm UTC, edited 2 times in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BRLast edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.