anselm/astar_babylon3d.html

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