Documentation
¶
Overview ¶
Package worldgen generates the family's tile-grid dungeons: binary space partitioning carves rooms into leaves, L-shaped corridors join them into one connected map, short dead-end stubs add texture, and flood-fill utilities answer reachability and distance questions about the result.
The tile grid itself belongs to each game; Generate digs through the Carver interface, tuned by a Config (DefaultConfig is the family's conventional constants), and returns the rooms as geom.Rect values. FloodDist produces a Field of step distances behind plain predicates, with Reachable and StepsBetween as shorthands and Neighbors4 as the shared adjacency.
Not every world is a dungeon. NewLattice generates the other shape the family builds on: a grid of nodes joined by axis-aligned edges with varied spacing, which a game reads as streets, districts or regions as it likes. [Lattice.Thin] then drops a share of those edges without stranding a node, which is what stops a generated grid looking like graph paper.
Randomness flows from RNG (seeded by NewRNG), so a seed reproduces the same map everywhere.
Index ¶
- func Generate(rng *RNG, c Carver, cfg Config) []geom.Rect
- func Neighbors4(c geom.Coord) [4]geom.Coord
- func Reachable(w, h int, src, dst geom.Coord, solid func(geom.Coord) bool) bool
- func StepsBetween(w, h int, src, dst geom.Coord, solid func(geom.Coord) bool) int
- func WeightedChoice(rng *RNG, weights []float64) int
- type Axis
- type Carver
- type Config
- type Field
- type Lattice
- type LatticeConfig
- type LatticeEdge
- type LatticeNode
- type Plan
- type RNG
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Generate ¶
Generate partitions the carver's area, digs one room per leaf, joins sibling partitions with L-shaped corridors, adds dead-end stubs, and returns the rooms. The same seed always produces the same map.
Example ¶
ExampleGenerate carves a connected dungeon into a caller-owned grid and confirms the rooms reach one another. The same seed always produces the same map.
package main
import (
"fmt"
"github.com/danielriddell21/crucible/geom"
"github.com/danielriddell21/crucible/worldgen"
)
// tiles is a minimal [worldgen.Carver]: a rectangular grid of open/solid
// cells that a game would back with its own tile type.
type tiles struct {
w, h int
open []bool
}
func (t *tiles) Width() int { return t.w }
func (t *tiles) Height() int { return t.h }
func (t *tiles) Open(x, y int) bool { return t.open[y*t.w+x] }
func (t *tiles) Carve(x, y int) { t.open[y*t.w+x] = true }
func (t *tiles) solid(c geom.Coord) bool {
if c.X < 0 || c.Y < 0 || c.X >= t.w || c.Y >= t.h {
return true
}
return !t.open[c.Y*t.w+c.X]
}
func main() {
grid := &tiles{w: 48, h: 40, open: make([]bool, 48*40)}
rooms := worldgen.Generate(worldgen.NewRNG(1), grid, worldgen.Config{})
first, last := rooms[0].Center(), rooms[len(rooms)-1].Center()
fmt.Println("connected:", worldgen.Reachable(grid.w, grid.h, first, last, grid.solid))
}
Output: connected: true
func Neighbors4 ¶
Neighbors4 returns the four orthogonal neighbours of a cell.
func Reachable ¶
Reachable reports whether dst can be reached from src on a w×h grid whose solid cells block movement.
func StepsBetween ¶
StepsBetween returns the orthogonal step distance from src to dst, or -1 when dst is unreachable.
func WeightedChoice ¶
WeightedChoice returns an index in [0, len(weights)) chosen with probability proportional to weights[i], drawing from rng. It returns -1 when weights is empty or sums to zero. Negative weights are treated as zero, and zero-weight entries are never chosen.
Games use it to pick a kind — an item, a hazard, a spawn — from a table of relative frequencies while a level is generated.
Example ¶
ExampleWeightedChoice picks a kind from a table of relative frequencies, the way a generator chooses which item or hazard to place.
package main
import (
"fmt"
"github.com/danielriddell21/crucible/worldgen"
)
func main() {
rng := worldgen.NewRNG(1)
weights := []float64{1, 3, 6} // common, uncommon, rare split 10/30/60
var counts [3]int
for range 1000 {
counts[worldgen.WeightedChoice(rng, weights)]++
}
fmt.Println(counts[0] < counts[1] && counts[1] < counts[2])
}
Output: true
Types ¶
type Carver ¶
Carver is the surface a generator digs a level into. Coordinates are always within [0, Width) × [0, Height). Open reports whether a cell has already been dug; Carve digs one.
type Config ¶
type Config struct {
// MinLeaf is the smallest partition edge that may still be split.
MinLeaf int
// MaxLeaf is the edge length above which a partition must split.
MaxLeaf int
// MinRoom is the smallest room edge.
MinRoom int
// RoomPad keeps rooms this many cells inside their leaf.
RoomPad int
// MaxDepth caps the partition depth.
MaxDepth int
// StopChance is the probability that a small-enough partition stops
// splitting early, for size variety.
StopChance float64
// StubAttempts is how many times to try carving a dead-end stub.
StubAttempts int
// MaxStubs caps the number of stubs carved.
MaxStubs int
}
Config tunes BSP generation. The zero value selects the family's conventional constants.
func DefaultConfig ¶
func DefaultConfig() Config
DefaultConfig returns the constants the family's games generate with.
type Field ¶
Field is a per-cell distance field produced by FloodDist. Cells that were not reached hold -1.
func FloodDist ¶
func FloodDist(w, h int, src geom.Coord, solid func(geom.Coord) bool, step func(from, to geom.Coord) bool) Field
FloodDist breadth-first floods a w×h grid from src and returns the orthogonal step distance to every reachable cell. solid reports cells the flood may not enter. step, when non-nil, additionally gates each move from one cell to the next — the games use it for height rules such as "you can only climb so far in one step".
type Lattice ¶ added in v1.0.0
type Lattice struct {
// Nodes and Edges are the graph. IDs index these slices.
Nodes []*LatticeNode
Edges []*LatticeEdge
// Min and Max bound the node positions generated so far.
Min, Max geom.Vec2
// contains filtered or unexported fields
}
Lattice is a grid of nodes joined by axis-aligned edges, cut from a Plan and grown a region at a time.
It is the shared skeleton under a street plan, a district map, an overworld of connected regions: the engine owns the topology and the geometry, and the game attaches its own meaning to it. Nothing here knows what an edge is for.
Build one with NewLattice for a world of fixed size, or NewGrowable followed by Lattice.Grow for one that extends as far as anybody travels. Either way node and edge IDs are permanent: growth appends and never renumbers, so an agent holding an edge from an hour ago still holds it.
func NewGrowable ¶ added in v1.0.0
func NewGrowable(seed uint64, cfg LatticeConfig) *Lattice
NewGrowable returns an empty lattice over a seed's plan. Nothing exists until Lattice.Grow is called.
func NewLattice ¶ added in v1.0.0
func NewLattice(seed uint64, cfg LatticeConfig) *Lattice
NewLattice builds a complete lattice of the configured size, centred on the origin, for a world that does not grow.
func (*Lattice) Cell ¶ added in v1.0.0
Cell returns the cell whose node lies nearest a world position. It is the inverse of Plan.Pos, and what a caller uses to work out which part of the world to grow next.
func (*Lattice) CellsAround ¶ added in v1.0.0
CellsAround returns the rectangle of cells covering a radius about a world position, for passing to Lattice.Grow. The rectangle always reaches past the radius rather than stopping inside it, so nothing within the radius is left ungrown.
func (*Lattice) Grow ¶ added in v1.0.0
Grow generates every node and edge in a rectangle of cells that does not exist yet, and returns the IDs of the nodes it added. Cells already grown are left alone, so overlapping calls are cheap and repeatable.
Edges are created between neighbouring cells only when both ends exist, and growing an adjoining region later fills in the edges that span the join.
func (*Lattice) Node ¶ added in v1.0.0
func (l *Lattice) Node(col, row int) *LatticeNode
Node returns the node at a cell, or nil where none has been grown.
type LatticeConfig ¶ added in v1.0.0
type LatticeConfig struct {
// Cols and Rows are how many grid lines to lay out on each axis, for a
// world of fixed size. [NewGrowable] ignores them.
Cols, Rows int
// MinSpan and MaxSpan bound the gap between consecutive grid lines, in
// world units. Each gap varies independently, which is what stops the
// result looking like graph paper.
MinSpan, MaxSpan float64
// Thin is the share of edges to drop, breaking up the regularity of the
// grid. Zero keeps every edge.
//
// Which edges go is decided from their position rather than by shuffling,
// and no node may lose more than one, so thinning never strands a junction
// or leaves a dead end however the lattice was grown.
Thin float64
}
LatticeConfig tunes lattice generation.
type LatticeEdge ¶ added in v1.0.0
type LatticeEdge struct {
// ID indexes the edge in [Lattice.Edges]. Like node IDs, stable for life.
ID int
// A and B are the node IDs at each end. A is always the lower Col or Row,
// so Dir points along increasing X or Y.
A, B int
// Axis is which way the edge runs.
Axis Axis
// Dir is the unit vector from A to B, and Length the distance between them.
Dir geom.Vec2
Length float64
}
LatticeEdge joins two nodes of a Lattice.
type LatticeNode ¶ added in v1.0.0
type LatticeNode struct {
// ID indexes the node in [Lattice.Nodes]. IDs are never reused and never
// renumbered, so anything holding one stays valid as the lattice grows.
ID int
// Pos is the node's position in world units.
Pos geom.Vec2
// Col and Row are the node's cell, which may be negative.
Col, Row int
// Edges holds the IDs of the edges meeting here.
Edges []int
}
LatticeNode is one junction of a Lattice.
func (*LatticeNode) Degree ¶ added in v1.0.0
func (n *LatticeNode) Degree() int
Degree returns how many edges meet at the node.
type Plan ¶ added in v1.0.0
type Plan struct {
// contains filtered or unexported fields
}
Plan is the infinite grid of lines a Lattice is cut from.
Every line's position is a function of its index alone, so any part of the grid can be worked out without generating the rest of it. That is what lets a world grow: a patch generated an hour into a drive lines up exactly with one generated at the start, because neither depended on the other having happened. Indices are signed and unbounded in both directions.
The alternative — walking outward adding a random gap each time — makes a line's position depend on every draw before it, so two patches generated independently disagree about where their shared edge is and the roads do not meet.
func NewPlan ¶ added in v1.0.0
NewPlan returns the grid of lines for a seed, with gaps between consecutive lines spread across [minSpan, maxSpan]. A range that is empty or inverted collapses to a uniform spacing.
type RNG ¶
type RNG struct {
// contains filtered or unexported fields
}
RNG is the deterministic random source used across the family's generators, with the conventional integer-range and probability helpers.
func NewRNG ¶
NewRNG returns a generator seeded the way the family's games seed their levels, so a seed reproduces the same map everywhere.
Source Files