Godot Procedural Generation

# bsp_tree_rooms.gd
# Binary Space Partitioning for structured floor plans
extends Node

class RoomNode:
	var x: int; var y: int; var w: int; var h: int
	var left: RoomNode; var right: RoomNode
	
	func split():
		# Logic to split vertically or horizontally 
		# until min_room_size is reached.
		pass

# cellular_automata_dungeon.gd
# Smooth cave generation using Cellular Automata (4/5 rule)
extends Node

@export var width := 60
@export var height := 40
@export var fill_percent := 45

var map: Array = []

func generate_caves():
	_random_fill()
	for i in range(5):
		_smooth_map()
	return map

func _smooth_map():
	var new_map = map.duplicate(true)
	for x in range(1, width - 1):
		for y in range(1, height - 1):
			var neighbors = _get_neighbor_count(x, y)
			if neighbors > 4:
				new_map[x][y] = 1 # Wall
			elif neighbors < 4:
				new_map[x][y] = 0 # Floor
	map = new_map

func _get_neighbor_count(grid_x, grid_y):
	var count = 0
	for x in range(grid_x-1, grid_x+2):
		for y in range(grid_y-1, grid_y+2):
			if x != grid_x or y != grid_y:
				count += map[x][y]
	return count

func _random_fill():
	map.clear()
	for x in range(width):
		map.append([])
		for y in range(height):
			map[x].append(1 if randi() % 100 < fill_percent else 0)

# drunknard_walk_path.gd
# Simple path generation for dungeons or rivers
extends Node

func generate_path(start: Vector2i, steps: int) -> Array[Vector2i]:
	var current = start
	var path: Array[Vector2i] = [start]
	var directions = [Vector2i.UP, Vector2i.DOWN, Vector2i.LEFT, Vector2i.RIGHT]
	
	for i in range(steps):
		var dir = directions[randi() % 4]
		current += dir
		if not path.has(current):
			path.append(current)
			
	return path

# skills/procedural-generation/scripts/dungeon_generator.gd
extends Node2D

## Dungeon Generator Expert Pattern
## BSP-based room placement with FastNoiseLite for terrain variation.

class_name DungeonGenerator

@export var room_count := 10
@export var min_room_size := Vector2i(5, 5)
@export var max_room_size := Vector2i(12, 12)
@export var map_size := Vector2i(100, 100)

var noise := FastNoiseLite.new()
var rooms: Array[Rect2i] = []

func _ready() -> void:
	noise.seed = randi()
	noise.frequency = 0.05

func generate() -> Array[Rect2i]:
	rooms.clear()
	
	# BSP rectangle subdivision
	var initial_rect := Rect2i(Vector2i.ZERO, map_size)
	var partitions := [initial_rect]
	
	# Split into smaller partitions
	while partitions.size() < room_count:
		var partition: Rect2i = partitions.pick_random()
		partitions.erase(partition)
		
		var split_rects := _split_rect(partition)
		if split_rects.size() == 2:
			partitions.append_array(split_rects)
		else:
			partitions.append(partition)  # Couldn't split, keep it
	
	# Create rooms inside partitions
	for partition in partitions:
		var room := _create_room_in_partition(partition)
		if room.has_area():
			rooms.append(room)
	
	return rooms

func _split_rect(rect: Rect2i) -> Array[Rect2i]:
	# Can't split if too small
	if rect.size.x < min_room_size.x * 2 or rect.size.y < min_room_size.y * 2:
		return []
	
	var split_horizontal := randf() > 0.5
	
	if split_horizontal:
		var split_y := randi_range(rect.position.y + min_room_size.y, rect.end.y - min_room_size.y)
		return [
			Rect2i(rect.position, Vector2i(rect.size.x, split_y - rect.position.y)),
			Rect2i(Vector2i(rect.position.x, split_y), Vector2i(rect.size.x, rect.end.y - split_y))
		]
	else:
		var split_x := randi_range(rect.position.x + min_room_size.x, rect.end.x - min_room_size.x)
		return [
			Rect2i(rect.position, Vector2i(split_x - rect.position.x, rect.size.y)),
			Rect2i(Vector2i(split_x, rect.position.y), Vector2i(rect.end.x - split_x, rect.size.y))
		]

func _create_room_in_partition(partition: Rect2i) -> Rect2i:
	var room_w := randi_range(min_room_size.x, min(max_room_size.x, partition.size.x - 2))
	var room_h := randi_range(min_room_size.y, min(max_room_size.y, partition.size.y - 2))
	
	var room_x := partition.position.x + randi_range(1, partition.size.x - room_w - 1)
	var room_y := partition.position.y + randi_range(1, partition.size.y - room_h - 1)
	
	return Rect2i(room_x, room_y, room_w, room_h)

func get_noise_value_at(pos: Vector2i) -> float:
	return noise.get_noise_2d(float(pos.x), float(pos.y))

## EXPERT USAGE:
## var gen := DungeonGenerator.new()
## gen.room_count = 15
## add_child(gen)
## var rooms := gen.generate()
## 
## # Use rooms to place tiles
## for room in rooms:
##     for x in range(room.position.x, room.end.x):
##         for y in range(room.position.y, room.end.y):
##             tilemap.set_cell(0, Vector2i(x, y), 0, Vector2i.ZERO)

# fast_noise_noise2d_master.gd
# Advanced usage of FastNoiseLite for terrain and heightmaps
extends Node

# EXPERT NOTE: Noise generation is expensive. Generate noise maps 
# into a typed Array or Image rather than querying 'get_noise_2d' per tile.

var noise := FastNoiseLite.new()

func _ready() -> void:
	noise.seed = randi()
	noise.frequency = 0.01
	noise.noise_type = FastNoiseLite.TYPE_PERLIN
	
	# Generate a 100x100 heightmap image for faster sampling
	var img = noise.get_image(100, 100)
	# Process image data...

# l_system_tree_gen.gd
# Procedural tree/plant growth using L-Systems
extends Node3D

# Turtle graphics approach to plant generation.

func draw_lsystem(axiom: String, rules: Dictionary, iterations: int):
	var current = axiom
	for i in range(iterations):
		var next = ""
		for char in current:
			next += rules.get(char, char)
		current = next
	# Then iterate characters to draw lines/branches
	return current

# marching_squares_metaballs.gd
# Smooth contour generation (Marching Squares algorithm)
extends Node

# EXPERT NOTE: Use Marching Squares for organic-looking terrains, 
# liquid simulations, or influence maps.

func get_contour_index(tl: float, tr: float, br: float, bl: float, threshold: float) -> int:
	var index = 0
	if tl >= threshold: index |= 8
	if tr >= threshold: index |= 4
	if br >= threshold: index |= 2
	if bl >= threshold: index |= 1
	return index

# mesh_gen_infinite_terrain.gd
# Dynamic Mesh generation for 3D terrain [ArrayMesh]
extends MeshInstance3D

# EXPERT NOTE: For infinite 3D terrain, generating a custom ArrayMesh 
# is better than tiling StaticBody3D planes.

func generate_plane(width: int, depth: int):
	var am = ArrayMesh.new()
	var st = SurfaceTool.new()
	st.begin(Mesh.PRIMITIVE_TRIANGLES)
	
	# Generate vertices with noise height
	for z in range(depth):
		for x in range(width):
			var y = 0 # noise.get_noise_2d(x, z)
			st.add_vertex(Vector3(x, y, z))
	
	# Generate indices...
	st.generate_normals()
	am = st.commit()
	mesh = am

# multi_threaded_chunk_gen.gd
# Offloading heavy proc-gen tasks to WorkerThreadPool
extends Node

# EXPERT NOTE: Procedural generation creates 'frame-time spikes'. 
# Offloading to a thread prevents the game from freezing.

func request_chunk(chunk_pos: Vector2i):
	WorkerThreadPool.add_task(_generate_chunk_task.bind(chunk_pos))

func _generate_chunk_task(pos: Vector2i):
	# Heavy noise calculations here
	var data = _calc_data(pos)
	
	# Pass data back to main thread for node instantiation
	call_deferred("_finalize_chunk", pos, data)

func _calc_data(_pos): return []
func _finalize_chunk(_pos, _data): pass

# poisson_disk_sampling_2d.gd
# Blue-noise distribution for non-overlapping object placement
extends Node

# EXPERT NOTE: Poisson Disk Sampling is superior to random placement 
# for trees, rocks, and spawns because it guarantees a minimum 
# distance between objects, preventing 'clumping'.

func generate_points(width: float, height: float, radius: float, k: int = 30) -> Array[Vector2]:
	var points: Array[Vector2] = []
	var spawn_points: Array[Vector2] = []
	
	spawn_points.append(Vector2(width/2, height/2))
	
	while spawn_points.size() > 0:
		var spawn_index = randi() % spawn_points.size()
		var spawn_centre = spawn_points[spawn_index]
		var accepted = false
		
		for i in range(k):
			var angle = randf() * PI * 2
			var dir = Vector2(cos(angle), sin(angle))
			var candidate = spawn_centre + dir * randf_range(radius, 2*radius)
			
			if _is_valid(candidate, width, height, radius, points):
				points.append(candidate)
				spawn_points.append(candidate)
				accepted = true
				break
		
		if not accepted:
			spawn_points.remove_at(spawn_index)
			
	return points

func _is_valid(p, w, h, r, points):
	if p.x < 0 or p.x > w or p.y < 0 or p.y > h: return false
	for other in points:
		if p.distance_to(other) < r: return false
	return true

class_name ProcGenGraphLayout
extends Node

## Expert pattern for managing dungeon layouts using AStar data structures.
## Decouples logical connections (rooms/hallways) from physical geometry.

var layout_graph := AStar2D.new()

## Adds a room node to the layout.
func add_room(id: int, pos: Vector2) -> void:
	layout_graph.add_point(id, pos)

## Connects two rooms with a hallway.
func connect_rooms(id_a: int, id_b: int, bidirectional: bool = true) -> void:
	layout_graph.connect_points(id_a, id_b, bidirectional)

## Returns all rooms in the layout.
func get_all_rooms() -> PackedInt64Array:
	return layout_graph.get_point_ids()

## Returns connections for a specific room (e.g. to determine where doors should be).
func get_room_connections(id: int) -> PackedInt64Array:
	return layout_graph.get_point_connections(id)

## Returns the spatial distance between two connected rooms.
func get_hallway_length(id_a: int, id_b: int) -> float:
	return layout_graph.get_point_position(id_a).distance_to(layout_graph.get_point_position(id_b))

class_name ProcGenMarchingCubesBase
extends MeshInstance3D

## Base class for 3D terrain generation using ArrayMesh.
## Provides the foundation for Marching Cubes or Voxel geometry.

func update_geometry(vertices: PackedVector3Array, normals: PackedVector3Array, indices: PackedInt32Array) -> void:
	var surface_array = []
	surface_array.resize(Mesh.ARRAY_MAX)
	
	surface_array[Mesh.ARRAY_VERTEX] = vertices
	surface_array[Mesh.ARRAY_NORMAL] = normals
	surface_array[Mesh.ARRAY_INDEX] = indices
	
	var arr_mesh = ArrayMesh.new()
	# PRIMITIVE_TRIANGLES is the standard for 3D surfaces
	arr_mesh.add_surface_from_arrays(Mesh.PRIMITIVE_TRIANGLES, surface_array)
	
	self.mesh = arr_mesh
	
	# Optimization: Generate collision if needed
	# create_trimesh_collision() 

class_name ProcGenSeedHistory
extends Node

## Expert Seed & State History Manager.
## Ensures deterministic procedural generation and allows "undo/redo" of random sequences.

var rng := RandomNumberGenerator.new()
var state_history: Array[int] = []

func _ready() -> void:
	rng.randomize()

## Seeds the generator and clears history.
func initialize_seed(new_seed: int) -> void:
	rng.seed = new_seed
	state_history.clear()

## Records the current RNG state before a generation step.
func push_state() -> void:
	state_history.append(rng.state)

## Restores the RNG to a previous state.
func pop_state() -> void:
	if state_history.is_empty(): return
	rng.state = state_history.pop_back()

## Returns the current seed string (useful for sharing).
func get_seed_string() -> String:
	return str(rng.seed)

# wave_function_collapse_lite.gd
# Procedural tile arrangement using WFC principles
extends Node

# EXPERT NOTE: WFC is excellent for city generation or 
# complex level layouts where tiles must obey adjacency rules.

var entropy_map: Array = []

func iterate():
	# 1. Find cell with lowest entropy
	# 2. Collapse it to a random valid state
	# 3. Propagate changes to neighbors
	pass
func propagate(_x, _y): pass
func collapse(_x, _y): pass
func find_lowest_entropy(): return Vector2i.ZERO

# skills/procedural-generation/code/wfc_level_generator.gd
extends Node

## Wave Function Collapse (WFC) Expert Pattern
## Generates rule-based tile maps with zero constraint violations.

@export var grid_size: Vector2i = Vector2i(10, 10)
@export var tile_library: Array[Resource] # Contains TileData with adjacency rules

var _grid: Array = [] # 2D array of 'Cell' objects

class Cell:
    var possibilities: Array = [] # List of TileData
    var collapsed: bool = false
    var selected_tile: Resource = null

func _ready() -> void:
    # 1. WFC Initialization
    _init_grid()
    _collapse_next()

func _init_grid() -> void:
    for x in grid_size.x:
        _grid.append([])
        for y in grid_size.y:
            var cell = Cell.new()
            cell.possibilities = tile_library.duplicate()
            _grid[x].append(cell)

func _collapse_next() -> void:
    # 2. Entropy Selection
    # Expert logic: Select the cell with the FEWEST possibilities 
    # to collapse next (Min-Entropy Heuristic).
    var cell = _find_lowest_entropy()
    if not cell: 
        print("Level Generation Complete")
        return
        
    cell.selected_tile = cell.possibilities.pick_random()
    cell.collapsed = true
    cell.possibilities = [cell.selected_tile]
    
    # 3. Constraint Propagation
    # Update neighbors based on the newly selected tile's rules.
    _propagate_constraints()
    
    # Recursively collapse until finished
    _collapse_next()

func _find_lowest_entropy() -> Cell:
    # Basic min-entropy search...
    return null

func _propagate_constraints() -> void:
    # Placeholder for the AC-3 or similar arc-consistency algorithm
    pass

## EXPERT NOTE:
## Use 'Poisson Disk Sampling': For object distribution (trees/rocks), 
## use Poisson Disk instead of pure Random to ensure a minimum 
## distance between items, preventing unrealistic 'clumping'.
## For 'procedural-generation', use 'WorkerThreadPool' to run 
## generation in the background, allowing for 'Infinite World' 
## loading without frame-stutters.
## NEVER use 'randi()' for map seeds; use a unique 'RandomNumberGenerator' 
## instance per level to ensure the same seed ALWAYS produces the same map.