Skip to content

Instantly share code, notes, and snippets.

@anselm
Last active April 3, 2024 19:28
Show Gist options
  • Save anselm/29c02c7100b9b3e7d4a79d2f1633ab7b to your computer and use it in GitHub Desktop.
Save anselm/29c02c7100b9b3e7d4a79d2f1633ab7b to your computer and use it in GitHub Desktop.
example of a star pathfinding in a 2d grid in babylon3d
<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment