Hornvale::Specification

A semi-formal specification of Hornvale.

Rather than getting bogged down in implementation details immediately, I want to declare this idea ¹ in some kind of coherent, unambiguous fashion. You know, so I can just write what I want instead of having to specify ownership semantics.

World

The Game World can be modeled as a directed graph G = (V, E) where:

• V is a set of vertices, with each vertex v ∈ V representing a region in the game.
• E is a set of edges, with each edge e ∈ E representing a passage between regions. An edge is an ordered pair (v_i, v_j) indicating a passage from region v_i to region v_j.

World Seed

Each world is generated by a distinct seed value, the World Seed, which determines pseudorandom number generation through each of the subsequent layers of the world structure. Specifics of this are implementation details.

Graph Generation

Vertices are generated on an infinite unit cartesian coordinate plane.

The initial vertex is always generated at (0, 0). It is given a seed value, a Region Seed, equal to that of the World Seed.

We expand outward, adding new vertices, using a discretized version of Bridson's algorithm (see reference implementation and example).

We connect the vertices into a minimum spanning tree using Prim's algorithm, which seems to be well-suited to incremental growth (see reference implementation and example).

Then we can randomly add cycles (see reference implementation).

This can easily generate more regions than anyone could explore, but we can modify these algorithms to expand incrementally in the direction of exploration.

Vertex/Region

Each vertex is given a seed value equal to the World Seed modified by its own x and y coordinates (specifics are an implementation detail; this could be just concatenating the world seed and the x and y coordinates and hashed, or ( W + A ⋅ x² + B ⋅ y³ ) mod M where A and B are prime numbers and M is a very large prime number close to INT_MAX, etc).

Juice and Chunk Loading and Unloading

Each vertex corresponds to a region of the game world. The world is infinite but our hardware is not; consequently, we must use a chunk management system to determine how to direct computing resources to the world. This leads us to a concept of "juice," which is an attempt to model the engagement and interest of the player in a given region, and use that to determine how computing resources are allocated.

We can describe J_current, the total current juice of the region, as follows:

• J_current = w_proximity ⋅ J_proximity + w_linger ⋅ J_linger
  • w_proximity is some fractional weight for the proximity factor
  • w_linger is some fractional weight for the lingering factor
  • J_proximity (d) = J₀ ⋅ e^-λd
    • J_proximity (d) is the juice level at distance d
    • J₀ is the juice level at the player's location
    • λ is the decay constant, determining how quickly the juice level decreases with distance
    • d is the distance from the player’s current position.
  • J_linger (t) = L ÷ ( 1 + e^{-k(t - t₀)} )
    • J_linger (t) is the juice level at time t
    • L is the maximum juice level
    • k is the steepness of the curve, determining how quickly the juice level falls off
    • t₀ is the time at which the player leaves the region, serving as the midpoint of the sigmoid curve

If J_current falls below some threshold value J_min, the region is declared to be effectively devoid of interest and can be unloaded until such a time that its juice once again exceeds that threshold.

The following visualization simulates these changes to J_current; the character moves between chunks, and chunks are loaded (invisible -> visible) and are unloaded (visible -> invisible).

More Fun With Juice

In addition, we can also monitor a longer-term cumulative trend:

• J_engagement = J_engagement + Δ J ⋅ t
  • J_engagement is a cumulative measurement of how much a player has engaged with a region.
  • Δ J ⋅ t is a measure of how much the juice has changed this turn. This will always be at least zero, though it may be rounded down to zero judiciously.

And we can compare the current state to that historic trend:

• J_decay = J_engagement ⋅ e^{-λ(t - t₀)}
  • J_decay is an indicator of how much a player has engaged with a region recently
  • λ is the decay constant, determining how quickly the juice level decreases with time since last engagement
  • t₀ is the time at which the player last interacted with the region

This can be used as a trigger for "hey, remember me?" type events.

Footnotes

1. "You can't just say that your game exists." "I didn't say it. I declared it." ↩