Skip to content

Instantly share code, notes, and snippets.

@anselm
Last active April 4, 2024 23:42
Show Gist options
  • Save anselm/b372ef016517424eec20ea0ba196d5ab to your computer and use it in GitHub Desktop.
Save anselm/b372ef016517424eec20ea0ba196d5ab to your computer and use it in GitHub Desktop.
sparse_voxel_octree_a_star_babylonjs_gpt4.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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment