From f66771603d26d8953b574748b91d0ff035551816 Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Fri, 27 May 2022 14:58:39 -0500
Subject: add basic terrain generation

---
 main.js            | 21 ++++++++++++++
 modules/Terrain.js | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 103 insertions(+)
 create mode 100644 main.js
 create mode 100644 modules/Terrain.js

diff --git a/main.js b/main.js
new file mode 100644
index 0000000..d02e0fb
--- /dev/null
+++ b/main.js
@@ -0,0 +1,21 @@
+import Voronoi from './modules/3rdparty/rhill-voronoi-core.js';
+import Terrain from './modules/Terrain.js';
+
+const $ = id => document.getElementById(id)
+
+window.onload = () => {
+	let canvas = document.createElement('canvas');
+	canvas.setAttribute('width', window.innerWidth);
+	canvas.setAttribute('height', window.innerHeight);
+	const ct = canvas.getContext('2d');
+
+	const scale = Math.min(window.innerWidth, window.innerHeight);
+	ct.scale(scale, scale);
+	
+	const terrain = new Terrain();
+	terrain.renderGrid(ct);
+
+	
+	const root = $('root');
+	root.appendChild(canvas);
+}
diff --git a/modules/Terrain.js b/modules/Terrain.js
new file mode 100644
index 0000000..ca0ab77
--- /dev/null
+++ b/modules/Terrain.js
@@ -0,0 +1,82 @@
+'use strict';
+
+import Voronoi from './3rdparty/rhill-voronoi-core.js';
+
+import { useAverage } from './Util.js';
+import { QuadTree } from './Geometry.js';
+
+
+/* from here on up, we always assume that points live in the range [(0,0), (1,1)) */
+
+function lloydRelax(point_set, density) {
+	/* setup quadtree and averages */
+	let tree = new QuadTree(1,1);
+	let averages = {};
+	for (let i=0; i<point_set.length; i++) {
+		const point = point_set[i];
+		point.index = i;
+		tree.insert(point);
+
+		let [avg, append] = useAverage();
+		const cent_x = { avg, append };
+		[avg, append] = useAverage();
+		const cent_y = { avg, append };
+		averages[i] = { cent_x, cent_y };
+	}
+
+	/* compute average centroids */
+	for (let x=0; x<1; x += 1/density) {
+		for (let y=0; y<1; y += 1/density) {
+			const point = { x, y };
+			const closest = tree.closest(point);
+			const { cent_x, cent_y } = averages[closest.index];
+			cent_x.append(point.x);
+			cent_y.append(point.y);
+		}
+	}
+
+	/* return centroid points */
+	const result = [];
+	for (let i=0; i<point_set.length; i++) {
+		const point = { x: averages[i].cent_x.avg(), y: averages[i].cent_y.avg() };
+		result.push(point);
+	}
+	return result;
+}
+
+
+class Terrain {
+	constructor() {
+		const N_SEED_POINTS = 2**14;
+		const N_RELAX_ITERATIONS = 1;
+		const RELAX_DENSITY = 400;
+		const randomPoint = () => ({x: Math.random(), y: Math.random()});
+
+		let seed_points = [];
+		for (let i=0; i<N_SEED_POINTS; i++) seed_points.push(randomPoint());
+
+		for (let i=0; i<N_RELAX_ITERATIONS; i++)
+			lloydRelax(seed_points, RELAX_DENSITY);
+
+		const v = new Voronoi();
+		this.graph = v.compute(seed_points, {xl: 0, xr: 1, yt: 0, yb: 1});
+
+		this.tree = new QuadTree(1,1);
+		for (let v of this.graph.vertices) this.tree.insert(v);
+	}
+
+
+	renderGrid(ct) {
+		ct.lineWidth = 0.001;
+		for (let edge of this.graph.edges) {
+			ct.beginPath();
+			ct.moveTo(edge.va.x, edge.va.y);
+			ct.lineTo(edge.vb.x, edge.vb.y);
+			ct.closePath();
+			ct.stroke();
+		}
+	}
+}
+
+export { lloydRelax };
+export default Terrain;
-- 
cgit v1.2.1