Adaptive Grids are a procedural generation technique for area and point based topologies that can expand to n-dimensional space.
Preamble:
Although ROAM was a technique that inspired temporal ROAM (Later, VRWorlds), there has been an unresolved question on how to adapt the self-similarity of right triangles to 3 dimensions and above. I’ve been considering a square / cube based approach that exhibits the near-parent properties of ROAM, but have usually run afoul of being unable to conceptualize it into a working model past the main recursive function. A breakthrough in going from 3x3 to 4x4 grids as a starting point has spawned a lot of additional pieces to fall into place.
Introduction:
Realtime Optimally Adaptive Meshes (ROAM) have certain key features when attempting to build procedurally generated content (like terrain).
- Scaleable depth: ROAM allows one part of the map to be generated more deeply than another part of the map. This is important in terrain generation as a potentially infinite terrain can be generated without infinite memory / storage requirements to generate the entire world at the proposed granularity.
- Deterministic depth: ROAM can be configured to always return the same division given the same parents. This allows the scaleable depth to continue to generate the same result given a very high level starting parent set, which in turn allows ROAM to roll up and forget previously expanded areas in favour of the currently viewed area.
- Continuous mesh deformation: Any change made by ROAM continues to keep the mesh cohesive and continuous due to the reliance of splitting pairs of right triangles together based on known parents. This largely removes issues of creasing and tent-poling inherent in many terrain generation techniques.
Adaptive Grids attempt to mimic these traits, but be based off a grid (of squares for 2-dimensional space, cubes for 3-dimensional space, etc).Continuous mesh deformation is currently not retained for the eventual mesh itself, but utilises parental involvement to remove creasing.
Adaptive Grid core algorithm:
(The algorithm is explained for a 2-dimensional surface using squares. Extensions to higher dimensions are trivial, but covered formally later.)
Given a set of parents arranged in a 3x3 grid of squares, the Adaptive Grid generates a 3x3 grid ½ the size centered on the middle square. The new squares rely on the parents that they overlap with. This means that the new middle square is determined solely by the middle parent; the new cardinal squares are determined by the middle square and the adjacent parent (Eg: New square to the north requires the middle parent and the northern parent); and the new corner squares are determined by the middle square and the 3 other parental squares in that diagonal direction (Eg: New square to the NorthEast requires the middle, North, East & NorthEast parents).
Since the algorithm produces another 3x3 grid at a deeper layer, the algorithm can be recursively applied to create an arbitrary depth.
Top Layer:
If a top layer of 3x3 is used to initiate the algorithm, it can continue to develop infinite depth, but no method of developing breadth of grid when at an arbitrary depth. Any requirement to develop anything other than the centre grid requires the rebuilding of another parent in the previous layer to make the requested square a centre square. The parent would also require a grand-parent in the layer above, and so on, eventually breaking due to the absence of a parent outside of the initial 3x3 layer.
To allow a defined space for breadth generation, the Adaptive Grid is initiated with a 4x4 grid. This allows the generation of a grid of arbitrary size or arbitrary depth to be generated within a 1x1 size square centred on the midpoint of the 4x4 grid. (Eg: an initial grid of 4x4 squares of 128 unit length can generate a 64x64 grid with 2 unit length inside a 128x128 space centered on the middle of the initial grid)
4x4 grid layer progression:
When initiating an Adaptive Grid with a 4x4 layer, the amount of squares in each fully expanded subsequent layer increases with this observed sequence:
| Layer 1 | Layer 2 | Layer 3 | Layer 4 | Layer 5 |
| 4 | 5 | 7 | 11 | 19 |
The calculation for each layer follows the sequence: Layer(n) = Layer(n-1)*2-3
Proof of defined space:
Since the child 3x3 grid is located centrally over the parent 3x3 grid, the middle child is a direct shrinking of the parent middle square. Continued shrinking makes the centre square reduce the area around the centre point, but never will reduce the centre point to nothingness or deviate from the centrepoint. The sides of the square asymptote to the central point. Since the side length of each square is the same across the entire grid, as the middle square side length reduces toward 0, so too does the outer squares. Therefore the outside of the outer squares also asymptotes toward the central point, which is 1.5 units in from the outside of each outer square.
Applying this asymptote to a 4x4 grid means that the outside of the outer squares will only ever need to be brought in by 1.5 units when creating a grid of infinite depth. Removing 1.5 units from the borders of the 4x4 grid leaves a 1x1 unit area that cannot be reached, thus leaving the area to be rendered by an arbitrary grid size (Eg: If the requirement for a 1000x1000 grid is needed covering an area of 100 m2 (side 10m), a starting Adaptive Grid of side 40m or larger is required).
Simple Scratch application to help demonstrate Adaptive Grids
