Labyrinfinite

• https://cs.wellesley.edu/~pmwh/labyrinfinite/
• Generates incrementally and indefinitely
• Generates a path that’s chaotic and complete

Effervescent

• https://cs.wellesley.edu/~pmwh/effervescent/
• Generates incrementally and indefinitely
• Generates a maze that’s chaotic with fractal connectivity

The Problem

We’d like to incrementally generate interconnected, chaotic, indefinite worlds.

• Indefinite: Generate as much as the player wants to explore
• Incremental: Generate content piece-by-piece on-demand
  • Player exploration controls order of generation
• Interconnected: Structures connect or interact at large scales
  • For example, rivers, roads or geologic features
• Chaotic: We can get many diverse worlds by altering a seed

Rivers

• Hard to generate incrementally, because the flow at any point depends on the entire watershed
• Watersheds cannot overlap each other: every drop of water takes a unique path to the ocean
• Two approaches:
  1. Generate and store rivers separately in big chunks
  2. Talk to your neighbors when generating rivers to pass information around

Big-chunk generation

• With large chunks, seams will be rare
  • E.g., continents on an ocean with separate river systems
  • Chunks are large, so seams are hard to notice

But: Large chunks may require lots of data, erasing the benefit of incremental generation

Local communication

• What if each small chunk simply negotiates with neighbors?
  • E.g., Ask your upstream chunk how much flow to have
• Interconnection constraints satisfied through local information?

But: This can defeat incremental generation through regress: as each chunk asks upstream, we end up needing to generate the whole watershed

Approach

• Generate chunks that are almost completely separated
  • Allows incremental, indefinite generation
• Communicate limited information between chunks to blur seams
  • Maintains some interconnectedness
  • Limit regress of dependencies by regressing towards a common root

Fractal Coordinates

• Overly multiple grid systems at different scales
• Coordinates at a particular scale identify an N×N region of the base coordinate grid
• Offset the larger grids to ensure that for every base grid cell, there is an origin tile at some scale which includes that cell
• Different scale multipliers can be used

(examples will be 2D)

Fractal Coordinates

• At each scale, a tile is identified using $x$ and $y$ coordinates
• An $h$ coordinate identifies the scale, or “height”
• A scale factor $S$ specifies the relationship between the size of a tile at one height and the next
• Each tile has a unique parent tile at the next-higher scale
• Except for the base layer where $h=0$, each tile has $S×S$ child tiles

Benefits

• Generation systems can operate at multiple scales of the coordinate system, and can easily talk to each other
• Thanks to the offset, there are no edges which are edges at every scale
  • There’s always some ancestor tile you could talk to which includes both sides of each of your edges
• Higher-level tiles cover exponentially more area
• Allows for regression to the origin from any point with logarithmic time/space complexity

Regression Concerns

• Communication between chunks creates dependencies, and works against the incremental generation ideal
  • E.g., river cells asking for flow rates
• In the worst case, infinite regression has chunks asking each other for information in a loop
  • Regression must be directed and finite, and will hopefully be short
• Asking a parent tile instead of a neighbor allows a question to be answered with more context

Regression to the Origin

A regression chain from any tile to the origin tile at $h=0$

1. If you are not an origin tile, ask your parent for help
2. If you are an origin tile, then one of your children is also an origin tile, and you can ask that child for help
3. If you are the origin tile at $h=0$, make a decision

Regression Example

• Assume that our scale factor is 5 and we’d like to generate flow values across each edge in an infinite world
• A random process decides to spawn the player at coordinates $(6, 4)$ on the base grid

Regression Guarantees

• Using regression to the origin, we can guarantee that for every tile generated, either:
  1. It is an origin tile, no tiles have been generated at higher heigths, and its parent tile will be able to respect any arbitrary decisions it makes
     • (It must respect decisions already made by its central child)
  2. It is not an origin tile, its parent has already been generated, and it can rely on information from that parent to make decisions that are consistent with its neighbors

Regression is Short

• For a tile at $(x, y)$, it will take $\log_S(\max(x, y))$ steps to reach a parent which is an origin tile, and that parent will require the same number of steps downwards to reach the base-level origin
• For $S=5$ and $x=2^{32}$, this translates to just 28 steps (14 up and 14 down): logarithms make huge values manageable
  • In contrast, even for a fixed chunk size of 500,000, regressing by neighbors to the origin from $x=2^{32}$ requries 8590 steps

Constraints

• Tiles could run constraint-solving for their properties
  • E.g., solve for flow rates that satisfy input = output
• Only a small amount of well-defined information needs to pass between tiles
  • Children at origin constrain part of their parent
  • Parents constrain edges of their non-origin children
• Regression to the origin limits regression chains

Best of Both Worlds?

• Like chunk-based generation, constraints are isolated
  • Seam effects can be mitigated by letting parent tiles which see both sides of an edge help
• Like local communication, tiles can coordinate constraints
  • Regression is controlled by regressing to the origin
• Not strictly incremental any more: must generate connection to origin before we generate an arbitrary tile
  • But this is in practice a small number of tiles, even for targets very far from the origin

In the Paper

• Related work
• Details on the demo systems

Using Fractal Coordinates

• Multi-scale processes are convenient even without constraints or regression
• Very simple to implement, and incremental generation doesn’t impose new limitations
  • Offsets for higher levels is the key non-obvious idea
• Feel free to get in touch!

Next Steps

• Demo for flow generation
• Real game applications
• Fractal wave-function collapse :)