anselm/index.html

## 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>