Linked repository source
examples/cavern_lab/subsystem/cavern_lab.odin
This read-only view comes from the file in the Gododin repository. It retains its design, example or evidence context.
Download the original file · Return to the guide
// Package cavern is the engine-independent Cavern Lab kernel. It imports no
// Godot, Gododin, or Raylib package. One persistent workspace owns every byte of
// scratch storage needed by the maximum supported workload, so a warm generate
// performs no allocation.
package cavern
import "core:math"
import "core:mem"
import "core:sync"
MIN_DIMENSION :: 8
MAX_DIMENSION :: 1024
MAX_CELLS :: MAX_DIMENSION * MAX_DIMENSION
MAX_SMOOTHING_STEPS :: 12
MAX_CANDIDATES :: 16384
WALL :: u8(255)
FLOOR :: u8(0)
Error :: enum i32 {
None,
Workspace_Unavailable,
Width_Out_Of_Bounds,
Height_Out_Of_Bounds,
Fill_Percent_Out_Of_Bounds,
Smoothing_Steps_Out_Of_Bounds,
Minimum_Region_Size_Out_Of_Bounds,
Validation_Failed,
Mask_Size_Mismatch,
Mask_Cell_Invalid,
Placement_Size_Mismatch,
Placement_Capacity_Exceeded,
Placement_Cell_Size_Invalid,
Placement_Grid_Unavailable,
Cancelled,
}
Settings :: struct {
width: int,
height: int,
seed: u32,
fill_percent: int,
smoothing_steps: int,
minimum_region_size: int,
}
Diagnostics :: struct {
seeded_walls: int,
smoothed_walls: int,
regions_before_cull: int,
culled_regions: int,
culled_cells: int,
connections: int,
final_regions: int,
floor_cells: int,
result_hash: u64,
}
Result :: struct {
cells: []u8,
diagnostics: Diagnostics,
error: Error,
}
// Workspace is the sole allocation owner for the subsystem. Its result view is
// valid until the next successful generate/process_mask call or destruction.
Workspace :: struct {
live: bool,
allocator: mem.Allocator,
allocation_count: u64,
cells: [MAX_CELLS]u8,
scratch: [MAX_CELLS]u8,
labels: [MAX_CELLS]i32,
queue: [MAX_CELLS]i32,
region_first: [MAX_CELLS]i32,
region_sizes: [MAX_CELLS]i32,
flags: [MAX_CANDIDATES]u8,
grid_live: bool,
grid_width: int,
grid_height: int,
flag_count: int,
}
// Vec3 states the locked single-precision engine Vector3 layout as plain Odin
// data (ADR 0060). The compiler verifies the field shape against the engine
// model; this kernel stays engine-independent.
Vec3 :: struct #align(4) {
x, y, z: f32,
}
// Placement is one classify_positions outcome. The flag span is borrowed from
// the workspace and stays valid until the next classification or destruction;
// 255 marks a placeable candidate and 0 a blocked one.
Placement :: struct {
flags: []u8,
placed: int,
error: Error,
}
workspace_create :: proc(allocator: mem.Allocator) -> (^Workspace, bool) {
storage, allocation_error := mem.alloc(size_of(Workspace), align_of(Workspace), allocator)
if allocation_error != nil || storage == nil do return nil, false
workspace := cast(^Workspace)storage
// mem.alloc provides zeroed storage. Assign the small owner fields directly:
// a whole-struct literal here would materialize an 18 MiB temporary on the
// Godot callback stack.
workspace.live = true
workspace.allocator = allocator
workspace.allocation_count = 1
return workspace, true
}
workspace_destroy :: proc(workspace: ^^Workspace) -> bool {
if workspace == nil || workspace^ == nil do return false
owner := workspace^
if !owner.live do return false
allocator := owner.allocator
owner.live = false
if mem.free(rawptr(owner), allocator) != nil do return false
workspace^ = nil
return true
}
settings_valid :: proc(settings: Settings) -> Error {
if settings.width < MIN_DIMENSION || settings.width > MAX_DIMENSION do return .Width_Out_Of_Bounds
if settings.height < MIN_DIMENSION || settings.height > MAX_DIMENSION do return .Height_Out_Of_Bounds
if settings.fill_percent < 0 || settings.fill_percent > 100 do return .Fill_Percent_Out_Of_Bounds
if settings.smoothing_steps < 0 || settings.smoothing_steps > MAX_SMOOTHING_STEPS do return .Smoothing_Steps_Out_Of_Bounds
cell_count := settings.width * settings.height
if settings.minimum_region_size < 1 || settings.minimum_region_size > cell_count do return .Minimum_Region_Size_Out_Of_Bounds
return .None
}
random_next :: proc(state: ^u32) -> u32 {
value := state^
if value == 0 do value = 0x6d2b79f5
value = value ~ (value << 13)
value = value ~ (value >> 17)
value = value ~ (value << 5)
state^ = value
return value
}
is_border :: proc(x, y, width, height: int) -> bool {
return x == 0 || y == 0 || x == width-1 || y == height-1
}
neighbor_walls :: proc(cells: []u8, x, y, width: int) -> int {
count := 0
for offset_y in -1..=1 {
for offset_x in -1..=1 {
if offset_x == 0 && offset_y == 0 do continue
if cells[(y+offset_y)*width+x+offset_x] == WALL do count += 1
}
}
return count
}
count_walls :: proc(cells: []u8) -> int {
result := 0
for cell in cells do if cell == WALL do result += 1
return result
}
label_regions :: proc(workspace: ^Workspace, width, height: int) -> int {
return label_regions_controlled(workspace, width, height, nil)
}
// Returns -1 when cancelled; callers abandon the partial labeling.
label_regions_controlled :: proc(workspace: ^Workspace, width, height: int, cancelled: ^bool) -> int {
cell_count := width * height
for index in 0..<cell_count {
workspace.labels[index] = -1
workspace.region_sizes[index] = 0
workspace.region_first[index] = -1
}
region_count := 0
for start in 0..<cell_count {
if cancelled_now(cancelled) do return -1
if workspace.cells[start] != FLOOR || workspace.labels[start] != -1 do continue
head, tail := 0, 1
workspace.queue[0] = i32(start)
workspace.labels[start] = i32(region_count)
workspace.region_first[region_count] = i32(start)
for head < tail {
index := int(workspace.queue[head])
head += 1
workspace.region_sizes[region_count] += 1
x, y := index % width, index / width
if x > 0 {
neighbor := index-1
if workspace.cells[neighbor] == FLOOR && workspace.labels[neighbor] == -1 {
workspace.labels[neighbor] = i32(region_count)
workspace.queue[tail] = i32(neighbor)
tail += 1
}
}
if x+1 < width {
neighbor := index+1
if workspace.cells[neighbor] == FLOOR && workspace.labels[neighbor] == -1 {
workspace.labels[neighbor] = i32(region_count)
workspace.queue[tail] = i32(neighbor)
tail += 1
}
}
if y > 0 {
neighbor := index-width
if workspace.cells[neighbor] == FLOOR && workspace.labels[neighbor] == -1 {
workspace.labels[neighbor] = i32(region_count)
workspace.queue[tail] = i32(neighbor)
tail += 1
}
}
if y+1 < height {
neighbor := index+width
if workspace.cells[neighbor] == FLOOR && workspace.labels[neighbor] == -1 {
workspace.labels[neighbor] = i32(region_count)
workspace.queue[tail] = i32(neighbor)
tail += 1
}
}
if tail & 1023 == 0 && cancelled_now(cancelled) do return -1
}
region_count += 1
}
return region_count
}
carve_corridor :: proc(cells: []u8, width: int, from_index, to_index: i32) {
x, y := int(from_index)%width, int(from_index)/width
target_x, target_y := int(to_index)%width, int(to_index)/width
for x != target_x {
cells[y*width+x] = FLOOR
if x < target_x do x += 1
else do x -= 1
}
for y != target_y {
cells[y*width+x] = FLOOR
if y < target_y do y += 1
else do y -= 1
}
cells[y*width+x] = FLOOR
}
hash_cells :: proc(cells: []u8) -> u64 {
hash := u64(14695981039346656037)
for cell in cells {
hash = hash ~ u64(cell)
hash *= 1099511628211
}
return hash & 0x7fff_ffff_ffff_ffff
}
validate_result :: proc(workspace: ^Workspace, width, height: int) -> (floor_cells, regions: int, ok: bool) {
return validate_result_controlled(workspace, width, height, nil)
}
validate_result_controlled :: proc(workspace: ^Workspace, width, height: int, cancelled: ^bool) -> (floor_cells, regions: int, ok: bool) {
cell_count := width * height
for index in 0..<cell_count {
if index & 1023 == 0 && cancelled_now(cancelled) do return 0, 0, false
cell := workspace.cells[index]
if cell != FLOOR && cell != WALL do return 0, 0, false
x, y := index % width, index / width
if is_border(x, y, width, height) && cell != WALL do return 0, 0, false
if cell == FLOOR do floor_cells += 1
}
if floor_cells == 0 do return 0, 0, false
regions = label_regions_controlled(workspace, width, height, cancelled)
return floor_cells, regions, regions == 1
}
// generate performs seeded fill, cellular smoothing, flood-fill region culling,
// deterministic region connection, and validation as one pure Odin operation.
generate :: proc(workspace: ^Workspace, settings: Settings) -> Result {
return generate_controlled(workspace, settings, nil)
}
// cancelled_now observes the cooperative cancellation token at the kernel's
// loop boundaries. A nil token is the synchronous path and can never interrupt.
cancelled_now :: proc(token: ^bool) -> bool {
return token != nil && sync.atomic_load(token)
}
// generate_controlled is generate with cooperative cancellation. The token is
// observed only at full-grid or per-region boundaries, so acknowledgement
// latency is bounded by one smoothing pass rather than by one cell.
generate_controlled :: proc(workspace: ^Workspace, settings: Settings, cancelled: ^bool) -> Result {
if workspace == nil || !workspace.live do return {error=.Workspace_Unavailable}
if settings_error := settings_valid(settings); settings_error != .None do return {error=settings_error}
width, height := settings.width, settings.height
cell_count := width * height
cells := workspace.cells[:cell_count]
random_state := settings.seed
for y in 0..<height {
if cancelled_now(cancelled) do return {error=.Cancelled}
for x in 0..<width {
index := y*width+x
if is_border(x, y, width, height) || int(random_next(&random_state)%100) < settings.fill_percent {
cells[index] = WALL
} else {
cells[index] = FLOOR
}
}
}
cells[(height/2)*width+width/2] = FLOOR
return finish_cave_controlled(workspace, settings, cancelled)
}
// process_mask reads an existing row-major occupancy mask (0=floor, 255=wall).
// It validates the complete input before touching workspace storage, then takes
// an owned working copy because smoothing/culling/connection mutate the grid.
// The input is never changed or retained. Borders are closed and the center is
// opened before applying the same pipeline used by seeded generation.
process_mask :: proc(workspace: ^Workspace, mask: []u8, width, height, smoothing_steps, minimum_region_size: int) -> Result {
if workspace == nil || !workspace.live do return {error=.Workspace_Unavailable}
settings := Settings{width=width, height=height, smoothing_steps=smoothing_steps, minimum_region_size=minimum_region_size}
if settings_error := settings_valid(settings); settings_error != .None do return {error=settings_error}
if len(mask) != width*height do return {error=.Mask_Size_Mismatch}
for cell in mask {
if cell != FLOOR && cell != WALL do return {error=.Mask_Cell_Invalid}
}
cells := workspace.cells[:len(mask)]
copy(cells, mask)
for y in 0..<height {
for x in 0..<width {
if is_border(x, y, width, height) do cells[y*width+x] = WALL
}
}
cells[(height/2)*width+width/2] = FLOOR
return finish_cave(workspace, settings)
}
// accept_grid admits Godot-owned occupancy bytes (0=floor, 255=wall) as the
// explicit classification grid without any refinement: classification has to
// run against the exact bytes a scene displays, whatever produced them —
// seeded generation, mask refinement, or a baked asset. Validation completes
// before any workspace mutation, so a rejected grid leaves the previously
// loaded grid in place. Re-accepting the workspace's own result view is the
// identity case: the bytes are already in position, only the dimensions are
// restated.
accept_grid :: proc(workspace: ^Workspace, cells: []u8, width, height: int) -> Error {
if workspace == nil || !workspace.live do return .Workspace_Unavailable
if width < MIN_DIMENSION || width > MAX_DIMENSION do return .Width_Out_Of_Bounds
if height < MIN_DIMENSION || height > MAX_DIMENSION do return .Height_Out_Of_Bounds
if len(cells) != width*height do return .Mask_Size_Mismatch
for cell in cells {
if cell != FLOOR && cell != WALL do return .Mask_Cell_Invalid
}
if len(cells) > 0 && &cells[0] == &workspace.cells[0] {
workspace.grid_live = true
workspace.grid_width = width
workspace.grid_height = height
return .None
}
loaded := workspace.cells[:width*height]
copy(loaded, cells)
workspace.grid_live = true
workspace.grid_width = width
workspace.grid_height = height
return .None
}
// Both entry points supply one initialized, owned grid. Keep its mutation and
// diagnostics together so generation and existing-data processing cannot drift.
finish_cave :: proc(workspace: ^Workspace, settings: Settings) -> Result {
return finish_cave_controlled(workspace, settings, nil)
}
finish_cave_controlled :: proc(workspace: ^Workspace, settings: Settings, cancelled: ^bool) -> Result {
width, height := settings.width, settings.height
cell_count := width * height
workspace.grid_live = true
workspace.grid_width = width
workspace.grid_height = height
cells := workspace.cells[:cell_count]
scratch := workspace.scratch[:cell_count]
diagnostics := Diagnostics{seeded_walls=count_walls(cells)}
for _ in 0..<settings.smoothing_steps {
for y in 0..<height {
// Row-granular observation bounds acknowledgement by one grid row
// at any optimization level, not by one full smoothing pass.
if cancelled_now(cancelled) do return {error=.Cancelled}
for x in 0..<width {
index := y*width+x
if is_border(x, y, width, height) {
scratch[index] = WALL
continue
}
walls := neighbor_walls(cells, x, y, width)
if walls > 4 do scratch[index] = WALL
else if walls < 4 do scratch[index] = FLOOR
else do scratch[index] = cells[index]
}
}
copy(cells, scratch)
}
diagnostics.smoothed_walls = count_walls(cells)
region_count := label_regions_controlled(workspace, width, height, cancelled)
if region_count < 0 do return {error=.Cancelled}
diagnostics.regions_before_cull = region_count
for y in 0..<height {
if cancelled_now(cancelled) do return {error=.Cancelled}
for x in 0..<width {
index := y*width+x
if cells[index] != FLOOR do continue
region := int(workspace.labels[index])
if int(workspace.region_sizes[region]) < settings.minimum_region_size {
cells[index] = WALL
diagnostics.culled_cells += 1
}
}
}
for region in 0..<region_count {
if int(workspace.region_sizes[region]) < settings.minimum_region_size do diagnostics.culled_regions += 1
}
region_count = label_regions_controlled(workspace, width, height, cancelled)
if region_count < 0 do return {error=.Cancelled}
if region_count == 0 {
center := (height/2)*width+width/2
cells[center] = FLOOR
region_count = label_regions_controlled(workspace, width, height, cancelled)
if region_count < 0 do return {error=.Cancelled}
}
for region in 1..<region_count {
if cancelled_now(cancelled) do return {error=.Cancelled}
carve_corridor(cells, width, workspace.region_first[region-1], workspace.region_first[region])
diagnostics.connections += 1
}
floor_cells, final_regions, validation_ok := validate_result_controlled(workspace, width, height, cancelled)
diagnostics.floor_cells = floor_cells
diagnostics.final_regions = final_regions
if cancelled_now(cancelled) do return {error=.Cancelled}
if !validation_ok do return {error=.Validation_Failed}
diagnostics.result_hash = hash_cells(cells)
return {cells=cells, diagnostics=diagnostics, error=.None}
}
// classify_positions classifies Godot-owned candidate instance positions
// against the processed grid: one candidate is placeable when its center cell
// and the four cells sampled one radius away along the world x/z axes are all
// open floor. The y coordinate is ignored because the grid is the cave floor
// plane. The borrowed inputs are callback-scoped, read-only, and never
// retained; the returned flag span is valid until the next classification or
// destruction. World-to-grid mapping floors in f64 exactly like the GDScript
// oracle, so both compute identical flags for identical inputs (ADR 0060).
classify_positions :: proc(workspace: ^Workspace, positions: []Vec3, radii: []f32, origin: Vec3, cell_size: f64) -> Placement {
if workspace == nil || !workspace.live do return {error=.Workspace_Unavailable}
if !workspace.grid_live do return {error=.Placement_Grid_Unavailable}
if !(cell_size > 0) do return {error=.Placement_Cell_Size_Invalid}
if len(positions) != len(radii) do return {error=.Placement_Size_Mismatch}
if len(positions) > MAX_CANDIDATES do return {error=.Placement_Capacity_Exceeded}
placed := 0
for position, index in positions {
radius := f64(radii[index])
placeable := grid_sample_open(workspace, f64(position.x), f64(position.z), origin, cell_size) &&
grid_sample_open(workspace, f64(position.x)+radius, f64(position.z), origin, cell_size) &&
grid_sample_open(workspace, f64(position.x)-radius, f64(position.z), origin, cell_size) &&
grid_sample_open(workspace, f64(position.x), f64(position.z)+radius, origin, cell_size) &&
grid_sample_open(workspace, f64(position.x), f64(position.z)-radius, origin, cell_size)
flag := u8(0)
if placeable {
flag = WALL
placed += 1
}
workspace.flags[index] = flag
}
workspace.flag_count = len(positions)
return {flags=workspace.flags[:len(positions)], placed=placed, error=.None}
}
grid_sample_open :: proc(workspace: ^Workspace, world_x, world_z: f64, origin: Vec3, cell_size: f64) -> bool {
grid_x := math.floor((world_x - f64(origin.x)) / cell_size)
grid_z := math.floor((world_z - f64(origin.z)) / cell_size)
if grid_x < 0 || grid_z < 0 || grid_x >= f64(workspace.grid_width) || grid_z >= f64(workspace.grid_height) {
return false
}
return workspace.cells[int(grid_z)*workspace.grid_width+int(grid_x)] == FLOOR
}