anselm · April 4, 2024 23:42
diff --git a/index.html b/index.html
 <!DOCTYPE html>
 <html xmlns="http://www.w3.org/1999/xhtml">

 	<head>
 		<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
 		<title>Babylon Template</title>

 		<style>
 			html, body {
 				overflow: hidden;
 				width: 100%;
 				height: 100%;
 				margin: 0;
 				padding: 0;
 			}
 			#renderCanvas {
 				width: 100%;
 				height: 100%;
 				touch-action: none;
 			}
 		</style>

 		<script src="https://cdn.babylonjs.com/babylon.js"></script>

 	</head>

 	 <body>

 	<canvas id="renderCanvas"></canvas>

 <script>

 //////////////////////////////////////////////////////////////////////////////////////////////////
 // BABYLON 3D
 //////////////////////////////////////////////////////////////////////////////////////////////////

 const canvas = document.getElementById("renderCanvas")
 const engine = new BABYLON.Engine(canvas, true)
 const scene = new BABYLON.Scene(engine)
 engine.runRenderLoop(function () { scene.render() })
 window.addEventListener("resize", function () { engine.resize() })

 const camera = new BABYLON.FreeCamera("camera1", new BABYLON.Vector3(4, 20, -18), scene)
 camera.setTarget(new BABYLON.Vector3(4,0,10))
 camera.attachControl(canvas, true)

 const light = new BABYLON.HemisphericLight("light", new BABYLON.Vector3(1, 1, 10), scene)
 light.intensity = 0.7;

 // babylon octree - just isn't clear what is going on exactly - like is it sparse?
 //var octree = scene.createOrUpdateSelectionOctree()
 //const xyz = new BABYLON.Vector3(0,0,0)
 //const results = octree.intersects(xyz,1,false)
 //console.log(results)

 //////////////////////////////////////////////////////////////////////////////////////////////////
 // SPARSE VOXEL OCTREE
 //////////////////////////////////////////////////////////////////////////////////////////////////

 class Voxel {
 	constructor(x=0, y=0, z=0) {
 		this.x = x;
 		this.y = y;
 		this.z = z;
 	}
 	isEqual(other) {
 		return this.x === other.x
 			&& this.y === other.y
 			&& this.z === other.z
 	}
 	score(other) {
 		Math.abs(this.x - other.x) + Math.abs(this.y - other.y) + Math.abs(this.z - other.z);
 	}
 }

 class OctreeNode {

 	constructor(level, x, y, z, size) {
 		this.level = level; // The current level in the tree
 		this.x = x;         // The node's position in space
 		this.y = y;
 		this.z = z;
 		this.size = size;   // The size of the node's space
 		this.children = []; // The node's children
 		this.voxels = [];   // The voxels contained in this node
 	}

 	// Method to subdivide the node into 8 children
 	subdivide() {
 		// Base case: do not subdivide further
 		if (this.level === 0) return;
 		const childSize = this.size / 2;
 		for (let dx = 0; dx < 2; dx++) {
 			for (let dy = 0; dy < 2; dy++) {
 				for (let dz = 0; dz < 2; dz++) {
 					const childX = this.x + dx * childSize;
 					const childY = this.y + dy * childSize;
 					const childZ = this.z + dz * childSize;
 					const child = new OctreeNode(this.level - 1, childX, childY, childZ, childSize);
 					this.children.push(child);
 				}
 			}
 		}
 	}

 	// Helper method to check if a voxel fits within this node
 	fitsInNode(voxel) {
 		return voxel.x >= this.x && voxel.x < this.x + this.size &&
 				voxel.y >= this.y && voxel.y < this.y + this.size &&
 				voxel.z >= this.z && voxel.z < this.z + this.size;
 	}

 	// Method to add a voxel to the node
 	addVoxel(voxel) {

 		// Check if the voxel fits in this node
 		if (!this.fitsInNode(voxel)) return false

 		// Base case: add voxel to this node
 		if (this.level === 0 || this.size <= 1) {
 			this.voxels.push(voxel);
 			return true;
 		}

 		// Recursively add the voxel to the correct child
 		for (const child of this.children) {
 			if (child.addVoxel(voxel)) return true;
 		}

 		// Subdivide and then try to add the voxel again
 		if (this.children.length === 0) {
 			this.subdivide();
 			return this.addVoxel(voxel);
 		}

 		// Should not reach here
 		return false;
 	}

 	// Fetch voxel if any
 	query(x, y, z) {

 		// Check if the coordinates are outside the bounds of this node
 		if (!this.fitsInNode({x, y, z})) return null

 		// Base case: If this is a leaf node, check the voxels in this node
 		for(const voxel of this.voxels) {
 			if(voxel.x === x && voxel.y === y && voxel.z === z) return voxel
 		}

 		// @todo is it worth doing this test?
 		//if (this.level === 0 || this.size <= 1) {
 		//	return this.voxels.some(voxel => voxel.x === x && voxel.y === y && voxel.z === z);
 		//}

 		// Recursively check children
 		for (const child of this.children) {
 			const voxel = child.query(x, y, z)
 			if(voxel) return voxel
 		}

 		return null
 	}


 	// Method to find the neighbors of a voxel at (x, y, z)
 	neighbors(voxel) {
 		const neighbors = []

 		const directions = [
 			[1, 0, 0], [-1, 0, 0],
 			[0, 1, 0], [0, -1, 0],
 			[0, 0, 1], [0, 0, -1],
 		]

 		directions.forEach(([dx, dy, dz]) => {
 			const neighborX = voxel.x + dx
 			const neighborY = voxel.y + dy
 			const neighborZ = voxel.z + dz
 			const candidate = this.query(neighborX, neighborY, neighborZ)
 			if(candidate) {
 				neighbors.push(candidate)
 			}
 		})

 		return neighbors
 	}

 }

 //////////////////////////////////////////////////////////////////////////////////////////////////
 // VISUALIZE OCTREE IN BABYLON3D SUPPORT
 //////////////////////////////////////////////////////////////////////////////////////////////////

 OctreeNode.prototype.visualizeOctreeNode = function(node = null, depth=0) {

 	if(node == null) node = this

    // Define the size and position for the box representing the current node
    var position = new BABYLON.Vector3(
    	node.x + node.size / 2,
    	node.y + node.size / 2,
    	node.z + node.size / 2)
    
    // Create a box for the current node
    var box = BABYLON.MeshBuilder.CreateBox("box", {size: node.size}, scene);
    box.position = position;
    
    // Create a wireframe material
    // var wireframeMaterial = new BABYLON.StandardMaterial("wireframeMat", scene);
    // wireframeMaterial.wireframe = true;
    // wireframeMaterial.diffuseColor = new BABYLON.Color3(0, 1, 0); // Green
    // box.material = wireframeMaterial;

    // Create a partially transparent material
    var transparentMaterial = new BABYLON.StandardMaterial("transparentMat", scene);
    transparentMaterial.alpha = 0.1;
    transparentMaterial.diffuseColor = new BABYLON.Color3(1, 0, 0);
    box.material = transparentMaterial;

    // Recursively visualize children nodes
    node.children.forEach(child => {
        this.visualizeOctreeNode(child, depth+1)
    });
 }


 //////////////////////////////////////////////////////////////////////////////////////////////////
 // ASTAR SUPPORT
 //////////////////////////////////////////////////////////////////////////////////////////////////

 OctreeNode.prototype.astar = function(start, end) {

 	class Node {
 		constructor(parent = null, voxel = null) {
 			this.parent = parent
 			this.voxel = voxel
 			this.g = 0
 			this.h = 0
 			this.f = 0
 		}
 	}

 	let openList = []
 	let closedList = [] // a set cannot be used

 	let startNode = new Node(null,start)
 	let endNode = new Node(null,end)

 	openList.push(startNode)

 	while (openList.length > 0) {
 		let currentNode = openList[0];
 		let currentIndex = 0;

 		// Get/reduce the current node with the lowest f score
 		for (let index = 0; index < openList.length; index++) {
 			if (openList[index].f < currentNode.f) {
 				currentNode = openList[index];
 				currentIndex = index;
 			}
 		}

 		// Move the current node from the open to the closed list
 		openList.splice(currentIndex, 1)
 		closedList.push(currentNode)

 		// Found the goal?
 		if (currentNode.voxel.isEqual(endNode.voxel)) {
 			let path = []
 			let current = currentNode
 			while (current != null) {
 				path.push(current.voxel)
 				current = current.parent
 			}
 			return path.reverse()
 		}

 		// find neighbors
 		let voxels = this.neighbors(currentNode.voxel)

 		// Loop through neighbors
 		for (let voxel of voxels) {

 			// Child is on the closed list
 			if (closedList.find(closedChild => closedChild.voxel.isEqual(voxel))) continue;

 			// Create the f, g, and h values
 			const child = new Node(currentNode,voxel)
 			child.g = currentNode.g + 1
 			child.h = child.voxel.score(endNode.voxel)
 			child.f = child.g + child.h

 			// Child is already in the open list
 			if (openList.find(openNode => openNode.voxel.isEqual(child.voxel) && child.g > openNode.g)) continue;

 			// Add the child to the open list
 			openList.push(child);
 		}
 	}

 	return []; // Return an empty path if there is no path
 }

 OctreeNode.prototype.visualize = function(res) {

 	this.visualizeOctreeNode()

    var transparentMaterial = new BABYLON.StandardMaterial("transparentMat", scene)
    transparentMaterial.alpha = 0.2
    transparentMaterial.diffuseColor = new BABYLON.Color3(0, 0, 1)

 	// paint voxels
 	let z = 0
 	for(let x = 0; x < database.size; x++) {
 		for(let y = 0; y < database.size; y++) {
 			if(!this.query(x,y,0)) continue
 			const obj = BABYLON.MeshBuilder.CreateBox("object", {width: 1, height: 1, depth: 1}, scene)
 			obj.position.x = x + 0.5
 			obj.position.y = y + 0.5
 			obj.position.z = z + 0.5
 			obj.material = transparentMaterial
 		}
 	}

 	// paint the astar path
 	for(let i = 0; i < res.length; i++) {
 		const {x,y,z} = res[i]
 		const obj = BABYLON.MeshBuilder.CreateSphere("entity", {diameter: 1}, scene)
 		obj.position.x = x + 0.5
 		obj.position.y = y + 0.5
 		obj.position.z = z + 0.5
 		//obj.material = transparentMaterial
 	}
 }



 //////////////////////////////////////////////////////////////////////////////////////////////////
 // ASTAR TEST AND VIEW
 //////////////////////////////////////////////////////////////////////////////////////////////////

 const database = new OctreeNode(3, 0, 0, 0, 8);

 database.addVoxel( new Voxel(0,0,0) )
 database.addVoxel( new Voxel(1,0,0) )
 database.addVoxel( new Voxel(2,0,0) )
 database.addVoxel( new Voxel(3,0,0) )
 database.addVoxel( new Voxel(4,0,0) )
 database.addVoxel( new Voxel(4,1,0) )
 database.addVoxel( new Voxel(4,2,0) )
 database.addVoxel( new Voxel(4,3,0) )
 database.addVoxel( new Voxel(4,4,0) )
 database.addVoxel( new Voxel(5,0,0) )
 database.addVoxel( new Voxel(5,1,0) )
 database.addVoxel( new Voxel(5,0,0) )
 database.addVoxel( new Voxel(5,3,0) )
 database.addVoxel( new Voxel(5,4,0) )

 const res = database.astar(database.query(0,0,0),database.query(5,4,0))

 database.visualize(res)

 </script>
 </body>
 </html>
	<!DOCTYPE html>
	<html xmlns="http://www.w3.org/1999/xhtml">

	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
	<title>Babylon Template</title>

	<style>
	html, body {
	overflow: hidden;
	width: 100%;
	height: 100%;
	margin: 0;
	padding: 0;
	}
	#renderCanvas {
	width: 100%;
	height: 100%;
	touch-action: none;
	}
	</style>

	<script src="https://cdn.babylonjs.com/babylon.js"></script>

	</head>

	<body>

	<canvas id="renderCanvas"></canvas>

	<script>

	//////////////////////////////////////////////////////////////////////////////////////////////////
	// BABYLON 3D
	//////////////////////////////////////////////////////////////////////////////////////////////////

	const canvas = document.getElementById("renderCanvas")
	const engine = new BABYLON.Engine(canvas, true)
	const scene = new BABYLON.Scene(engine)
	engine.runRenderLoop(function () { scene.render() })
	window.addEventListener("resize", function () { engine.resize() })

	const camera = new BABYLON.FreeCamera("camera1", new BABYLON.Vector3(4, 20, -18), scene)
	camera.setTarget(new BABYLON.Vector3(4,0,10))
	camera.attachControl(canvas, true)

	const light = new BABYLON.HemisphericLight("light", new BABYLON.Vector3(1, 1, 10), scene)
	light.intensity = 0.7;

	// babylon octree - just isn't clear what is going on exactly - like is it sparse?
	//var octree = scene.createOrUpdateSelectionOctree()
	//const xyz = new BABYLON.Vector3(0,0,0)
	//const results = octree.intersects(xyz,1,false)
	//console.log(results)

	//////////////////////////////////////////////////////////////////////////////////////////////////
	// SPARSE VOXEL OCTREE
	//////////////////////////////////////////////////////////////////////////////////////////////////

	class Voxel {
	constructor(x=0, y=0, z=0) {
	this.x = x;
	this.y = y;
	this.z = z;
	}
	isEqual(other) {
	return this.x === other.x
	&& this.y === other.y
	&& this.z === other.z
	}
	score(other) {
	Math.abs(this.x - other.x) + Math.abs(this.y - other.y) + Math.abs(this.z - other.z);
	}
	}

	class OctreeNode {

	constructor(level, x, y, z, size) {
	this.level = level; // The current level in the tree
	this.x = x; // The node's position in space
	this.y = y;
	this.z = z;
	this.size = size; // The size of the node's space
	this.children = []; // The node's children
	this.voxels = []; // The voxels contained in this node
	}

	// Method to subdivide the node into 8 children
	subdivide() {
	// Base case: do not subdivide further
	if (this.level === 0) return;
	const childSize = this.size / 2;
	for (let dx = 0; dx < 2; dx++) {
	for (let dy = 0; dy < 2; dy++) {
	for (let dz = 0; dz < 2; dz++) {
	const childX = this.x + dx * childSize;
	const childY = this.y + dy * childSize;
	const childZ = this.z + dz * childSize;
	const child = new OctreeNode(this.level - 1, childX, childY, childZ, childSize);
	this.children.push(child);
	}
	}
	}
	}

	// Helper method to check if a voxel fits within this node
	fitsInNode(voxel) {
	return voxel.x >= this.x && voxel.x < this.x + this.size &&
	voxel.y >= this.y && voxel.y < this.y + this.size &&
	voxel.z >= this.z && voxel.z < this.z + this.size;
	}

	// Method to add a voxel to the node
	addVoxel(voxel) {

	// Check if the voxel fits in this node
	if (!this.fitsInNode(voxel)) return false

	// Base case: add voxel to this node
	if (this.level === 0 \|\| this.size <= 1) {
	this.voxels.push(voxel);
	return true;
	}

	// Recursively add the voxel to the correct child
	for (const child of this.children) {
	if (child.addVoxel(voxel)) return true;
	}

	// Subdivide and then try to add the voxel again
	if (this.children.length === 0) {
	this.subdivide();
	return this.addVoxel(voxel);
	}

	// Should not reach here
	return false;
	}

	// Fetch voxel if any
	query(x, y, z) {

	// Check if the coordinates are outside the bounds of this node
	if (!this.fitsInNode({x, y, z})) return null

	// Base case: If this is a leaf node, check the voxels in this node
	for(const voxel of this.voxels) {
	if(voxel.x === x && voxel.y === y && voxel.z === z) return voxel
	}

	// @todo is it worth doing this test?
	//if (this.level === 0 \|\| this.size <= 1) {
	// return this.voxels.some(voxel => voxel.x === x && voxel.y === y && voxel.z === z);
	//}

	// Recursively check children
	for (const child of this.children) {
	const voxel = child.query(x, y, z)
	if(voxel) return voxel
	}

	return null
	}


	// Method to find the neighbors of a voxel at (x, y, z)
	neighbors(voxel) {
	const neighbors = []

	const directions = [
	[1, 0, 0], [-1, 0, 0],
	[0, 1, 0], [0, -1, 0],
	[0, 0, 1], [0, 0, -1],
	]

	directions.forEach(([dx, dy, dz]) => {
	const neighborX = voxel.x + dx
	const neighborY = voxel.y + dy
	const neighborZ = voxel.z + dz
	const candidate = this.query(neighborX, neighborY, neighborZ)
	if(candidate) {
	neighbors.push(candidate)
	}
	})

	return neighbors
	}

	}

	//////////////////////////////////////////////////////////////////////////////////////////////////
	// VISUALIZE OCTREE IN BABYLON3D SUPPORT
	//////////////////////////////////////////////////////////////////////////////////////////////////

	OctreeNode.prototype.visualizeOctreeNode = function(node = null, depth=0) {

	if(node == null) node = this

	// Define the size and position for the box representing the current node
	var position = new BABYLON.Vector3(
	node.x + node.size / 2,
	node.y + node.size / 2,
	node.z + node.size / 2)

	// Create a box for the current node
	var box = BABYLON.MeshBuilder.CreateBox("box", {size: node.size}, scene);
	box.position = position;

	// Create a wireframe material
	// var wireframeMaterial = new BABYLON.StandardMaterial("wireframeMat", scene);
	// wireframeMaterial.wireframe = true;
	// wireframeMaterial.diffuseColor = new BABYLON.Color3(0, 1, 0); // Green
	// box.material = wireframeMaterial;

	// Create a partially transparent material
	var transparentMaterial = new BABYLON.StandardMaterial("transparentMat", scene);
	transparentMaterial.alpha = 0.1;
	transparentMaterial.diffuseColor = new BABYLON.Color3(1, 0, 0);
	box.material = transparentMaterial;

	// Recursively visualize children nodes
	node.children.forEach(child => {
	this.visualizeOctreeNode(child, depth+1)
	});
	}


	//////////////////////////////////////////////////////////////////////////////////////////////////
	// ASTAR SUPPORT
	//////////////////////////////////////////////////////////////////////////////////////////////////

	OctreeNode.prototype.astar = function(start, end) {

	class Node {
	constructor(parent = null, voxel = null) {
	this.parent = parent
	this.voxel = voxel
	this.g = 0
	this.h = 0
	this.f = 0
	}
	}

	let openList = []
	let closedList = [] // a set cannot be used

	let startNode = new Node(null,start)
	let endNode = new Node(null,end)

	openList.push(startNode)

	while (openList.length > 0) {
	let currentNode = openList[0];
	let currentIndex = 0;

	// Get/reduce the current node with the lowest f score
	for (let index = 0; index < openList.length; index++) {
	if (openList[index].f < currentNode.f) {
	currentNode = openList[index];
	currentIndex = index;
	}
	}

	// Move the current node from the open to the closed list
	openList.splice(currentIndex, 1)
	closedList.push(currentNode)

	// Found the goal?
	if (currentNode.voxel.isEqual(endNode.voxel)) {
	let path = []
	let current = currentNode
	while (current != null) {
	path.push(current.voxel)
	current = current.parent
	}
	return path.reverse()
	}

	// find neighbors
	let voxels = this.neighbors(currentNode.voxel)

	// Loop through neighbors
	for (let voxel of voxels) {

	// Child is on the closed list
	if (closedList.find(closedChild => closedChild.voxel.isEqual(voxel))) continue;

	// Create the f, g, and h values
	const child = new Node(currentNode,voxel)
	child.g = currentNode.g + 1
	child.h = child.voxel.score(endNode.voxel)
	child.f = child.g + child.h

	// Child is already in the open list
	if (openList.find(openNode => openNode.voxel.isEqual(child.voxel) && child.g > openNode.g)) continue;

	// Add the child to the open list
	openList.push(child);
	}
	}

	return []; // Return an empty path if there is no path
	}

	OctreeNode.prototype.visualize = function(res) {

	this.visualizeOctreeNode()

	var transparentMaterial = new BABYLON.StandardMaterial("transparentMat", scene)
	transparentMaterial.alpha = 0.2
	transparentMaterial.diffuseColor = new BABYLON.Color3(0, 0, 1)

	// paint voxels
	let z = 0
	for(let x = 0; x < database.size; x++) {
	for(let y = 0; y < database.size; y++) {
	if(!this.query(x,y,0)) continue
	const obj = BABYLON.MeshBuilder.CreateBox("object", {width: 1, height: 1, depth: 1}, scene)
	obj.position.x = x + 0.5
	obj.position.y = y + 0.5
	obj.position.z = z + 0.5
	obj.material = transparentMaterial
	}
	}

	// paint the astar path
	for(let i = 0; i < res.length; i++) {
	const {x,y,z} = res[i]
	const obj = BABYLON.MeshBuilder.CreateSphere("entity", {diameter: 1}, scene)
	obj.position.x = x + 0.5
	obj.position.y = y + 0.5
	obj.position.z = z + 0.5
	//obj.material = transparentMaterial
	}
	}



	//////////////////////////////////////////////////////////////////////////////////////////////////
	// ASTAR TEST AND VIEW
	//////////////////////////////////////////////////////////////////////////////////////////////////

	const database = new OctreeNode(3, 0, 0, 0, 8);

	database.addVoxel( new Voxel(0,0,0) )
	database.addVoxel( new Voxel(1,0,0) )
	database.addVoxel( new Voxel(2,0,0) )
	database.addVoxel( new Voxel(3,0,0) )
	database.addVoxel( new Voxel(4,0,0) )
	database.addVoxel( new Voxel(4,1,0) )
	database.addVoxel( new Voxel(4,2,0) )
	database.addVoxel( new Voxel(4,3,0) )
	database.addVoxel( new Voxel(4,4,0) )
	database.addVoxel( new Voxel(5,0,0) )
	database.addVoxel( new Voxel(5,1,0) )
	database.addVoxel( new Voxel(5,0,0) )
	database.addVoxel( new Voxel(5,3,0) )
	database.addVoxel( new Voxel(5,4,0) )

	const res = database.astar(database.query(0,0,0),database.query(5,4,0))

	database.visualize(res)

	</script>
	</body>
	</html>