anselm · April 3, 2024 19:28
diff --git a/astar_babylon3d.html b/astar_babylon3d.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>


 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////

 // Setup engine

 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(0, 10, -1), scene)
 camera.setTarget(BABYLON.Vector3.Zero())
 camera.attachControl(canvas, true)

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

 //var octree = scene.createOrUpdateSelectionOctree()
 //const xyz = new BABYLON.Vector3(0,0,0)
 //const results = octree.intersects(xyz,1,false)
 //console.log(results)

 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////


 ///////////////////////////////////////////////////////////////////////////////////////////////////
 // a-star test

 function dataset_neighbors(dataset,currentNode) {
 	let children = []
 	const candidates = [
 		{ x:0, y:-1},
 		{ x:0, y:1},
 		{ x:-1, y:0},
 		{ x:1, y:0}
 	]
 		for (let newPosition of candidates) {
 		let pos = {x:currentNode.position.x + newPosition.x, y:currentNode.position.y + newPosition.y }
 		if (pos.x >= dataset.length-1 || pos.x < 0 || pos.y >= dataset.length || pos.y < 0) continue;
 		if (dataset[pos.y][pos.x] != 0) continue;
 		let newNode = new Node(currentNode, pos)
 		children.push(newNode)
 		}
 		return children
 }

 function dataset_estimate(a,b) {
 			Math.abs(a.position.x - b.position.x) + Math.abs(a.position.y - b.position.y);
 }	

 class Node {
 	constructor(parent = null, position = null) {
 		this.parent = parent;
 		this.position = position;
 		this.g = 0; // Distance from start node
 		this.h = 0; // Heuristic - Estimated distance from current node to end node
 		this.f = 0; // Total cost
 	}

 	isEqual(other) {
 		return this.position.x === other.position.x && this.position.y === other.position.y;
 	}
 }

 function astar(dataset, start, end) {

 	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.isEqual(endNode)) {
 			let path = [];
 			let current = currentNode;
 			while (current != null) {
 				path.push(current.position);
 				current = current.parent;
 			}
 			return path.reverse(); // Return reversed path
 		}

 		// Generate children
 		let neighbors = dataset_neighbors(dataset,currentNode)

 		// Loop through neighbors
 		for (let child of neighbors) {
 			// Child is on the closed list
 			if (closedList.find(closedChild => closedChild.isEqual(child))) continue;

 			// Create the f, g, and h values
 			child.g = currentNode.g + 1;
 			child.h = dataset_estimate(child,endNode)
 			child.f = child.g + child.h;

 			// Child is already in the open list
 			if (openList.find(openNode => openNode.isEqual(child) && 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
 }

 //////////////////////////////////////////////////////////////////////////////////////////////////////////

 let grid = [
 	[0, 0, 0, 0, 1, 1, 1],
 	[0, 0, 1, 0, 0, 0, 1],
 	[1, 0, 1, 0, 0, 0, 1],
 	[1, 0, 1, 0, 0, 0, 1],
 	[1, 0, 0, 0, 0, 0, 0],
 	[1, 0, 0, 0, 0, 0, 0]
 ]

 const res = astar(grid, {x:0,y:0}, {x:3,y:4} )
 console.log(res)

 function paint_astar(scene) {
 	for(let y = 0; y < grid.length; y++) {
 		const row = grid[y]
 		for(let x = 0; x < row.length; x++) {
 			let value = row[x]
 			if(!value) continue
 			const obj = BABYLON.MeshBuilder.CreateBox("object", {width: 1, height: 1, depth: 1}, scene)
 			obj.position.x = x - grid.length / 2
 			obj.position.z = -y + grid.length / 2
 		}
 	}

 	for(let i = 0; i < res.length; i++) {
 		const {x,y} = res[i]
 		const obj = BABYLON.MeshBuilder.CreateSphere("entity", {diameter: 1}, scene)
 		obj.position.x = x - grid.length / 2
 		obj.position.z = -y + grid.length / 2
 	}

 }


 paint_astar(scene)


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


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////

	// Setup engine

	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(0, 10, -1), scene)
	camera.setTarget(BABYLON.Vector3.Zero())
	camera.attachControl(canvas, true)

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

	//var octree = scene.createOrUpdateSelectionOctree()
	//const xyz = new BABYLON.Vector3(0,0,0)
	//const results = octree.intersects(xyz,1,false)
	//console.log(results)

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////


	///////////////////////////////////////////////////////////////////////////////////////////////////
	// a-star test

	function dataset_neighbors(dataset,currentNode) {
	let children = []
	const candidates = [
	{ x:0, y:-1},
	{ x:0, y:1},
	{ x:-1, y:0},
	{ x:1, y:0}
	]
	for (let newPosition of candidates) {
	let pos = {x:currentNode.position.x + newPosition.x, y:currentNode.position.y + newPosition.y }
	if (pos.x >= dataset.length-1 \|\| pos.x < 0 \|\| pos.y >= dataset.length \|\| pos.y < 0) continue;
	if (dataset[pos.y][pos.x] != 0) continue;
	let newNode = new Node(currentNode, pos)
	children.push(newNode)
	}
	return children
	}

	function dataset_estimate(a,b) {
	Math.abs(a.position.x - b.position.x) + Math.abs(a.position.y - b.position.y);
	}

	class Node {
	constructor(parent = null, position = null) {
	this.parent = parent;
	this.position = position;
	this.g = 0; // Distance from start node
	this.h = 0; // Heuristic - Estimated distance from current node to end node
	this.f = 0; // Total cost
	}

	isEqual(other) {
	return this.position.x === other.position.x && this.position.y === other.position.y;
	}
	}

	function astar(dataset, start, end) {

	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.isEqual(endNode)) {
	let path = [];
	let current = currentNode;
	while (current != null) {
	path.push(current.position);
	current = current.parent;
	}
	return path.reverse(); // Return reversed path
	}

	// Generate children
	let neighbors = dataset_neighbors(dataset,currentNode)

	// Loop through neighbors
	for (let child of neighbors) {
	// Child is on the closed list
	if (closedList.find(closedChild => closedChild.isEqual(child))) continue;

	// Create the f, g, and h values
	child.g = currentNode.g + 1;
	child.h = dataset_estimate(child,endNode)
	child.f = child.g + child.h;

	// Child is already in the open list
	if (openList.find(openNode => openNode.isEqual(child) && 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
	}

	//////////////////////////////////////////////////////////////////////////////////////////////////////////

	let grid = [
	[0, 0, 0, 0, 1, 1, 1],
	[0, 0, 1, 0, 0, 0, 1],
	[1, 0, 1, 0, 0, 0, 1],
	[1, 0, 1, 0, 0, 0, 1],
	[1, 0, 0, 0, 0, 0, 0],
	[1, 0, 0, 0, 0, 0, 0]
	]

	const res = astar(grid, {x:0,y:0}, {x:3,y:4} )
	console.log(res)

	function paint_astar(scene) {
	for(let y = 0; y < grid.length; y++) {
	const row = grid[y]
	for(let x = 0; x < row.length; x++) {
	let value = row[x]
	if(!value) continue
	const obj = BABYLON.MeshBuilder.CreateBox("object", {width: 1, height: 1, depth: 1}, scene)
	obj.position.x = x - grid.length / 2
	obj.position.z = -y + grid.length / 2
	}
	}

	for(let i = 0; i < res.length; i++) {
	const {x,y} = res[i]
	const obj = BABYLON.MeshBuilder.CreateSphere("entity", {diameter: 1}, scene)
	obj.position.x = x - grid.length / 2
	obj.position.z = -y + grid.length / 2
	}

	}


	paint_astar(scene)


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