genesis_engine.py

"""Genesis engine: lightweight geometry, graph and procedural generators.

This module provides a compact but useful set of utilities for 2D vector
math, simple graph and triangular-mesh representations, an L-system based
generator for procedural structures, and tiny IO/export helpers (OBJ/JSON).

The code is dependency-free (only Python stdlib) and intended to be safe to
add to the repository as a self-contained demonstration of geometry and
generation primitives.

Key pieces:
- Vector2D: small 2D vector helper
- Graph: node/edge graph with simple layout support
- Mesh: triangular mesh builder and simple Delaunay-like splitter (not
  production-grade but useful for small demos)
- LSystem: compact L-system interpreter for procedural geometry
- exporters: write OBJ and JSON representations

The module includes a small CLI demo when executed directly.
"""

from __future__ import annotations

import json
import math
import random
from dataclasses import dataclass, field
from typing import Dict, Iterable, List, Optional, Sequence, Tuple

##########################
# Vector utilities
##########################


@dataclass(frozen=True)
class Vector2D:
	x: float
	y: float

	def __add__(self, other: Vector2D) -> Vector2D:
		return Vector2D(self.x + other.x, self.y + other.y)

	def __sub__(self, other: Vector2D) -> Vector2D:
		return Vector2D(self.x - other.x, self.y - other.y)

	def __mul__(self, s: float) -> Vector2D:
		return Vector2D(self.x * s, self.y * s)

	def dot(self, other: Vector2D) -> float:
		return self.x * other.x + self.y * other.y

	def cross(self, other: Vector2D) -> float:
		return self.x * other.y - self.y * other.x

	def length(self) -> float:
		return math.hypot(self.x, self.y)

	def normalized(self) -> Vector2D:
		l = self.length()
		if l == 0:
			return Vector2D(0.0, 0.0)
		return Vector2D(self.x / l, self.y / l)

	def rotate(self, ang_rad: float) -> Vector2D:
		c = math.cos(ang_rad)
		s = math.sin(ang_rad)
		return Vector2D(self.x * c - self.y * s, self.x * s + self.y * c)

	def tuple(self) -> Tuple[float, float]:
		return (self.x, self.y)


def polygon_area(points: Sequence[Vector2D]) -> float:
	if len(points) < 3:
		return 0.0
	a = 0.0
	for i in range(len(points)):
		x1, y1 = points[i].tuple()
		x2, y2 = points[(i + 1) % len(points)].tuple()
		a += x1 * y2 - y1 * x2
	return 0.5 * abs(a)


def centroid(points: Sequence[Vector2D]) -> Vector2D:
	if not points:
		return Vector2D(0.0, 0.0)
	sx = sum(p.x for p in points)
	sy = sum(p.y for p in points)
	n = len(points)
	return Vector2D(sx / n, sy / n)

##########################
# Graph primitives
##########################


@dataclass
class Node:
	id: int
	pos: Vector2D
	data: dict = field(default_factory=dict)


@dataclass
class Edge:
	a: int
	b: int
	weight: float = 1.0


class Graph:
	"""Simple undirected graph with node positions for layout and export."""

	def __init__(self) -> None:
		self._nodes: Dict[int, Node] = {}
		self._edges: List[Edge] = []
		self._next_id = 1

	def add_node(self, pos: Vector2D, data: Optional[dict] = None) -> int:
		nid = self._next_id
		self._next_id += 1
		self._nodes[nid] = Node(id=nid, pos=pos, data=data or {})
		return nid

	def add_edge(self, a: int, b: int, weight: float = 1.0) -> None:
		if a not in self._nodes or b not in self._nodes:
			raise KeyError("both nodes must exist to add an edge")
		self._edges.append(Edge(a=a, b=b, weight=weight))

	def nodes(self) -> Iterable[Node]:
		return list(self._nodes.values())

	def edges(self) -> Iterable[Edge]:
		return list(self._edges)

	def to_dict(self) -> dict:
		return {
			"nodes": [{"id": n.id, "pos": n.pos.tuple(), "data": n.data} for n in self.nodes()],
			"edges": [{"a": e.a, "b": e.b, "weight": e.weight} for e in self.edges()],
		}

	def bounding_box(self) -> Tuple[Vector2D, Vector2D]:
		pts = [n.pos for n in self.nodes()]
		if not pts:
			return Vector2D(0, 0), Vector2D(0, 0)
		minx = min(p.x for p in pts)
		miny = min(p.y for p in pts)
		maxx = max(p.x for p in pts)
		maxy = max(p.y for p in pts)
		return Vector2D(minx, miny), Vector2D(maxx, maxy)

	def random_layout(self, seed: Optional[int] = None, scale: float = 1.0) -> None:
		if seed is not None:
			random.seed(seed)
		for n in self._nodes.values():
			n.pos = Vector2D((random.random() - 0.5) * scale, (random.random() - 0.5) * scale)

	def radial_layout(self, center: Optional[Vector2D] = None, radius: float = 1.0) -> None:
		nodes = list(self._nodes.values())
		if not nodes:
			return
		if center is None:
			center = centroid([n.pos for n in nodes])
		n = len(nodes)
		for i, node in enumerate(nodes):
			ang = 2 * math.pi * (i / max(1, n))
			node.pos = Vector2D(center.x + math.cos(ang) * radius, center.y + math.sin(ang) * radius)

##########################
# Mesh primitives
##########################


@dataclass
class Triangle:
	a: int
	b: int
	c: int


class Mesh:
	"""A tiny triangular mesh container (indexed vertices + triangles).

	This is intentionally minimal: utility methods to add points/triangles and
	to export to OBJ. It also contains a simple ear-clipping polygon triangulator
	for simple polygons.
	"""

	def __init__(self) -> None:
		self.vertices: List[Vector2D] = []
		self.triangles: List[Triangle] = []

	def add_vertex(self, p: Vector2D) -> int:
		self.vertices.append(p)
		return len(self.vertices) - 1

	def add_triangle(self, a: int, b: int, c: int) -> None:
		self.triangles.append(Triangle(a, b, c))

	def to_obj(self) -> str:
		lines: List[str] = []
		for v in self.vertices:
			lines.append(f"v {v.x:.6f} {v.y:.6f} 0.0")
		for t in self.triangles:
			# OBJ indices are 1-based
			lines.append(f"f {t.a + 1} {t.b + 1} {t.c + 1}")
		return "\n".join(lines)

	def from_polygon_earclip(self, poly: Sequence[Vector2D]) -> None:
		"""Triangulate a simple polygon using ear clipping. Returns triangles in place.

		Not suitable for complex, self-intersecting polygons. Intended for demos.
		"""
		pts = [Vector2D(p.x, p.y) for p in poly]
		n = len(pts)
		if n < 3:
			return
		# We'll append the polygon vertices to the mesh; remember base index
		base_index = len(self.vertices)
		for p in pts:
			self.add_vertex(p)

		idx = list(range(n))

		# helper to check if vertex i is an ear (using polygon-local indices)
		def is_convex(i0, i1, i2) -> bool:
			a = pts[i0]
			b = pts[i1]
			c = pts[i2]
			# positive cross indicates counter-clockwise (convex for CCW polygons)
			return (b - a).cross(c - b) > 0

		def point_in_triangle(pt: Vector2D, a: Vector2D, b: Vector2D, c: Vector2D) -> bool:
			# barycentric technique
			v0 = c - a
			v1 = b - a
			v2 = pt - a
			dot00 = v0.dot(v0)
			dot01 = v0.dot(v1)
			dot02 = v0.dot(v2)
			dot11 = v1.dot(v1)
			dot12 = v1.dot(v2)
			denom = dot00 * dot11 - dot01 * dot01
			if denom == 0:
				return False
			u = (dot11 * dot02 - dot01 * dot12) / denom
			v = (dot00 * dot12 - dot01 * dot02) / denom
			return u >= 0 and v >= 0 and (u + v) <= 1

		# Ear clipping main loop
		while len(idx) > 3:
			ear_found = False
			for k in range(len(idx)):
				i_prev = idx[(k - 1) % len(idx)]
				i_curr = idx[k]
				i_next = idx[(k + 1) % len(idx)]
				if not is_convex(i_prev, i_curr, i_next):
					continue
				a = pts[i_prev]
				b = pts[i_curr]
				c = pts[i_next]
				# ensure no other point is inside triangle
				any_inside = False
				for j in idx:
					if j in (i_prev, i_curr, i_next):
						continue
					if point_in_triangle(pts[j], a, b, c):
						any_inside = True
						break
				if any_inside:
					continue
				# record triangle (indices offset by base_index)
				self.add_triangle(base_index + i_prev, base_index + i_curr, base_index + i_next)
				# remove ear vertex from polygon index list
				idx.pop(k)
				ear_found = True
				break
			if not ear_found:
				# fallback: stop to avoid infinite loop on degenerate polygons
				break

		# final triangle
		if len(idx) == 3:
			self.add_triangle(base_index + idx[0], base_index + idx[1], base_index + idx[2])

##########################
# L-system / procedural generator
##########################


class LSystem:
	"""A very small L-system interpreter.

	The LSystem applies one-step symbol rewriting using provided rules, then
	optionally interprets the final string into 2D turtle geometry commands.
	Supported turtle commands in the interpreter:
	- F: move forward and draw
	- f: move forward without drawing
	- +: turn right by angle
	- -: turn left by angle
	- [: push state
	- ]: pop state

	The interpreter returns a list of line segments (pairs of Vector2D).
	"""

	def __init__(self, axiom: str, rules: Dict[str, str]):
		self.axiom = axiom
		self.rules = rules

	def generate(self, iterations: int) -> str:
		s = self.axiom
		for _ in range(max(0, iterations)):
			out = []
			for ch in s:
				out.append(self.rules.get(ch, ch))
			s = "".join(out)
		return s

	def interpret_turtle(self, program: str, step: float = 1.0, angle_deg: float = 25.0) -> List[Tuple[Vector2D, Vector2D]]:
		angle_rad = math.radians(angle_deg)
		pos = Vector2D(0.0, 0.0)
		dir_vec = Vector2D(0.0, 1.0)
		stack: List[Tuple[Vector2D, Vector2D]] = []
		segments: List[Tuple[Vector2D, Vector2D]] = []

		for ch in program:
			if ch == "F":
				new_pos = pos + dir_vec * step
				segments.append((pos, new_pos))
				pos = new_pos
			elif ch == "f":
				pos = pos + dir_vec * step
			elif ch == "+":
				dir_vec = dir_vec.rotate(-angle_rad)  # right turn
			elif ch == "-":
				dir_vec = dir_vec.rotate(angle_rad)  # left turn
			elif ch == "[":
				stack.append((pos, dir_vec))
			elif ch == "]":
				if stack:
					pos, dir_vec = stack.pop()
			else:
				# ignore unknown symbols
				pass

		return segments

##########################
# Small helpers / exporters
##########################


def export_graph_json(graph: Graph, path: str) -> None:
	with open(path, "w", encoding="utf-8") as fh:
		json.dump(graph.to_dict(), fh, indent=2)


def export_mesh_obj(mesh: Mesh, path: str) -> None:
	with open(path, "w", encoding="utf-8") as fh:
		fh.write(mesh.to_obj())


##########################
# Example high-level generators
##########################


def random_point_cloud(n: int, radius: float = 1.0, seed: Optional[int] = None) -> List[Vector2D]:
	if seed is not None:
		random.seed(seed)
	pts = [Vector2D((random.random() - 0.5) * 2 * radius, (random.random() - 0.5) * 2 * radius) for _ in range(n)]
	return pts


def make_grid_graph(rows: int, cols: int, spacing: float = 1.0) -> Graph:
	g = Graph()
	ids = []
	for r in range(rows):
		row_ids = []
		for c in range(cols):
			nid = g.add_node(Vector2D(c * spacing, r * spacing))
			row_ids.append(nid)
		ids.append(row_ids)
	for r in range(rows):
		for c in range(cols):
			if c + 1 < cols:
				g.add_edge(ids[r][c], ids[r][c + 1])
			if r + 1 < rows:
				g.add_edge(ids[r][c], ids[r + 1][c])
	return g


def polygon_to_mesh(poly: Sequence[Vector2D]) -> Mesh:
	m = Mesh()
	m.from_polygon_earclip(poly)
	return m

##########################
# CLI demo and small smoke test
##########################


def demo_lsystem_tree(iterations: int = 4, step: float = 1.0, angle: float = 25.0) -> Mesh:
	# A simple plant-like L-system (Algae-like variant)
	rules = {
		"X": "F-[[X]+X]+F[+FX]-X",
		"F": "FF",
	}
	ls = LSystem(axiom="X", rules=rules)
	prog = ls.generate(iterations)
	segs = ls.interpret_turtle(prog, step=step, angle_deg=angle)

	# Build a mesh by creating thin rectangles for segments (crude)
	mesh = Mesh()
	# For each segment create two vertices offset perpendicular to the segment
	for a, b in segs:
		v = b - a
		n = Vector2D(-v.y, v.x).normalized() * (step * 0.1)
		ia = mesh.add_vertex(a + n)
		ib = mesh.add_vertex(a - n)
		ic = mesh.add_vertex(b + n)
		id = mesh.add_vertex(b - n)
		# two triangles
		mesh.add_triangle(ia, ib, ic)
		mesh.add_triangle(ib, id, ic)
	return mesh


def demo_pipeline() -> None:
	print("Genesis engine demo:\n")
	print("- Generating grid graph 4x4")
	g = make_grid_graph(4, 4, spacing=1.0)
	print(f"  nodes: {len(list(g.nodes()))}, edges: {len(list(g.edges()))}")
	print("- Generating random polygon and triangulating via ear clipping")
	poly = [Vector2D(math.cos(a) * (1 + 0.3 * math.sin(3 * a)), math.sin(a) * (1 + 0.3 * math.cos(5 * a))) for a in [i * 2 * math.pi / 12 for i in range(12)]]
	m = polygon_to_mesh(poly)
	print(f"  mesh vertices: {len(m.vertices)}, triangles: {len(m.triangles)}")
	print("- Generating L-system tree and exporting OBJ sample (in-memory)")
	tree_mesh = demo_lsystem_tree(iterations=3, step=0.6, angle=22.5)
	print(f"  tree mesh vertices: {len(tree_mesh.vertices)}, triangles: {len(tree_mesh.triangles)}")
	# show small metrics
	area = polygon_area(poly)
	print(f"- sample polygon area: {area:.4f}")


if __name__ == "__main__":
	# Simple smoke-run to verify nothing crashes
	demo_pipeline()


##########################
# Additional utilities
##########################


class GridIndex:
	"""Simple spatial hash / grid index for 2D points.

	Useful for small-to-medium point sets where we need fast nearest
	or radius queries without external dependencies.
	"""

	def __init__(self, cell_size: float = 1.0):
		self.cell_size = float(cell_size)
		self._cells: Dict[Tuple[int, int], List[int]] = {}
		self._points: List[Vector2D] = []

	def _cell(self, p: Vector2D) -> Tuple[int, int]:
		return (int(math.floor(p.x / self.cell_size)), int(math.floor(p.y / self.cell_size)))

	def insert(self, p: Vector2D) -> int:
		idx = len(self._points)
		self._points.append(p)
		key = self._cell(p)
		self._cells.setdefault(key, []).append(idx)
		return idx

	def radius_query(self, p: Vector2D, r: float) -> List[Tuple[int, Vector2D]]:
		r = float(r)
		cx, cy = self._cell(p)
		delta = int(math.ceil(r / self.cell_size))
		out: List[Tuple[int, Vector2D]] = []
		for dx in range(-delta, delta + 1):
			for dy in range(-delta, delta + 1):
				for idx in self._cells.get((cx + dx, cy + dy), []):
					pt = self._points[idx]
					if (pt - p).length() <= r:
						out.append((idx, pt))
		return out


def poisson_disc_samples(radius: float, domain: Tuple[float, float, float, float], k: int = 30, seed: Optional[int] = None) -> List[Vector2D]:
	"""Bridson's Poisson-disc sampling in a rectangular domain.

	domain: (xmin, ymin, xmax, ymax)
	"""
	if seed is not None:
		random.seed(seed)
	xmin, ymin, xmax, ymax = domain
	width = xmax - xmin
	height = ymax - ymin
	cell_size = radius / math.sqrt(2)
	grid_w = int(math.ceil(width / cell_size))
	grid_h = int(math.ceil(height / cell_size))
	grid: List[List[Optional[int]]] = [[None] * grid_h for _ in range(grid_w)]

	def to_grid(p: Vector2D) -> Tuple[int, int]:
		gx = int((p.x - xmin) / cell_size)
		gy = int((p.y - ymin) / cell_size)
		return gx, gy

	samples: List[Vector2D] = []
	active: List[int] = []

	# first sample
	first = Vector2D(xmin + random.random() * width, ymin + random.random() * height)
	samples.append(first)
	gx, gy = to_grid(first)
	grid[gx][gy] = 0
	active.append(0)

	while active:
		idx = active[int(random.random() * len(active))]
		base = samples[idx]
		found = False
		for _ in range(k):
			r = random.uniform(radius, 2 * radius)
			theta = random.random() * 2 * math.pi
			cand = Vector2D(base.x + r * math.cos(theta), base.y + r * math.sin(theta))
			if not (xmin <= cand.x <= xmax and ymin <= cand.y <= ymax):
				continue
			cgx, cgy = to_grid(cand)
			ok = True
			for i in range(max(0, cgx - 2), min(grid_w, cgx + 3)):
				for j in range(max(0, cgy - 2), min(grid_h, cgy + 3)):
					sidx = grid[i][j]
					if sidx is None:
						continue
					if (samples[sidx] - cand).length() < radius:
						ok = False
						break
				if not ok:
					break
			if ok:
				samples.append(cand)
				grid[cgx][cgy] = len(samples) - 1
				active.append(len(samples) - 1)
				found = True
				break
		if not found:
			active.remove(idx)

	return samples


def refine_mesh(mesh: Mesh, max_edge_length: float) -> Mesh:
	"""Refine mesh by subdividing triangles that contain edges longer than max_edge_length.

	This performs a single-pass refinement (one subdivision iteration). It's
	intentionally simple and deterministic for demo purposes.
	"""
	new = Mesh()
	# copy existing vertices
	for v in mesh.vertices:
		new.add_vertex(Vector2D(v.x, v.y))

	def mid(a: int, b: int) -> int:
		va = new.vertices[a]
		vb = new.vertices[b]
		mpt = Vector2D((va.x + vb.x) * 0.5, (va.y + vb.y) * 0.5)
		return new.add_vertex(mpt)

	for tri in mesh.triangles:
		a, b, c = tri.a, tri.b, tri.c
		va = mesh.vertices[a]
		vb = mesh.vertices[b]
		vc = mesh.vertices[c]
		dab = (va - vb).length()
		dbc = (vb - vc).length()
		dca = (vc - va).length()
		if dab <= max_edge_length and dbc <= max_edge_length and dca <= max_edge_length:
			new.add_triangle(a, b, c)
			continue
		# split edges where needed, create midpoints
		mab = mid(a, b) if dab > max_edge_length else -1
		mbc = mid(b, c) if dbc > max_edge_length else -1
		mca = mid(c, a) if dca > max_edge_length else -1

		# simple cases: if all three edges split -> 4 new triangles
		if mab != -1 and mbc != -1 and mca != -1:
			new.add_triangle(a, mab, mca)
			new.add_triangle(mab, b, mbc)
			new.add_triangle(mca, mbc, c)
			new.add_triangle(mab, mbc, mca)
		else:
			# fallback: if only one edge split, replace by two triangles
			if mab != -1 and mbc == -1 and mca == -1:
				new.add_triangle(a, mab, c)
				new.add_triangle(mab, b, c)
			elif mbc != -1 and mab == -1 and mca == -1:
				new.add_triangle(b, mbc, a)
				new.add_triangle(mbc, c, a)
			elif mca != -1 and mab == -1 and mbc == -1:
				new.add_triangle(c, mca, b)
				new.add_triangle(mca, a, b)
			else:
				# mixed or two splits: attempt a conservative split by adding original triangle
				new.add_triangle(a, b, c)

	return new


def laplacian_smooth(mesh: Mesh, iterations: int = 1, lam: float = 0.5) -> None:
	"""In-place Laplacian smoothing of vertex positions.

	lam in (0,1) controls the amount of smoothing per iteration.
	"""
	if not mesh.vertices:
		return
	# build adjacency
	adj: List[set] = [set() for _ in mesh.vertices]
	for t in mesh.triangles:
		adj[t.a].update([t.b, t.c])
		adj[t.b].update([t.a, t.c])
		adj[t.c].update([t.a, t.b])

	for _ in range(max(0, iterations)):
		new_positions: List[Vector2D] = [v for v in mesh.vertices]
		for i, v in enumerate(mesh.vertices):
			neighbors = adj[i]
			if not neighbors:
				continue
			sx = sum(mesh.vertices[j].x for j in neighbors) / len(neighbors)
			sy = sum(mesh.vertices[j].y for j in neighbors) / len(neighbors)
			new_positions[i] = Vector2D(v.x + lam * (sx - v.x), v.y + lam * (sy - v.y))
		mesh.vertices = new_positions


def export_mesh_svg(mesh: Mesh, path: str, scale: float = 100.0, margin: float = 10.0) -> None:
	"""Export mesh to a simple SVG file (triangles stroked).

	This is a convenience for quick visual checks; it writes a minimal SVG.
	"""
	if not mesh.vertices:
		with open(path, "w", encoding="utf-8") as fh:
			fh.write("<svg xmlns='http://www.w3.org/2000/svg'></svg>")
		return
	xs = [v.x for v in mesh.vertices]
	ys = [v.y for v in mesh.vertices]
	minx, miny, maxx, maxy = min(xs), min(ys), max(xs), max(ys)
	w = (maxx - minx) * scale + 2 * margin
	h = (maxy - miny) * scale + 2 * margin
	def to_xy(v: Vector2D) -> Tuple[float, float]:
		return ((v.x - minx) * scale + margin, (maxy - v.y) * scale + margin)

	lines: List[str] = []
	lines.append(f"<svg xmlns='http://www.w3.org/2000/svg' width='{w:.0f}' height='{h:.0f}'>")
	lines.append("<g fill='none' stroke='black' stroke-width='1'>")
	for t in mesh.triangles:
		a = mesh.vertices[t.a]
		b = mesh.vertices[t.b]
		c = mesh.vertices[t.c]
		xa, ya = to_xy(a)
		xb, yb = to_xy(b)
		xc, yc = to_xy(c)
		lines.append(f"<path d='M {xa:.2f} {ya:.2f} L {xb:.2f} {yb:.2f} L {xc:.2f} {yc:.2f} Z'/>")
	lines.append("</g>")
	lines.append("</svg>")
	with open(path, "w", encoding="utf-8") as fh:
		fh.write("\n".join(lines))


## small additional smoke-run to exercise new utilities when run directly
if __name__ == "__main__":
	# generate Poisson-disc samples inside unit square
	pts = poisson_disc_samples(0.08, (0.0, 0.0, 1.0, 1.0), seed=42)
	print(f"Poisson samples generated: {len(pts)}")
	# build a mesh from a regular polygon and refine it
	poly = [Vector2D(math.cos(a), math.sin(a)) for a in [i * 2 * math.pi / 8 for i in range(8)]]
	m = polygon_to_mesh(poly)
	print(f"Original mesh: v={len(m.vertices)}, t={len(m.triangles)}")
	m2 = refine_mesh(m, max_edge_length=0.8)
	print(f"Refined mesh: v={len(m2.vertices)}, t={len(m2.triangles)}")
	laplacian_smooth(m2, iterations=2, lam=0.4)
	# export SVG to temporary file for quick visual check (file path safe to overwrite)
	try:
		export_mesh_svg(m2, "genesis_sample.svg")
		print("Exported genesis_sample.svg")
	except Exception:
		# ignore filesystem errors in restricted environments
		pass