For some background
I saw a game called “lethal company”, and I thought I should try and remake it for a long term project.
It’s important to note that everything is inspired by lethal company, but I want my own aspects + performance will also shape the project.
- I have simple creatures in the game, using nodes on the floors (since levels are procedurally generated) so we can’t pre calculate, nodes will appear and disappear as the player moves through the levels.
- Creatures need to have some type of algorithm (weather BSF or A* etc will depend on performance, and amount)
- Creatures need each a unique ability, as for the brakken (sneaks up behind you, if you see it it runs away, has an anger meter, which at 100% will chase you even when looking at it, looking at it to make it run away adds to the anger meter) (see this channel for details on specifics for each AI)
What I want to achieve
Some performance friendly way to have a creature move around objects, walls to get the player in dynamically generated environments.
I have the creature setup for the coil head (wheeping angel) set up already, though it doesn’t use any pathfinding.
current pathfinding code here:
var DynamicPathfinding = pc.createScript('dynamicPathfinding');
// --- Attributes --- //
DynamicPathfinding.attributes.add('target', {
type: 'entity',
title: 'Target Entity',
description: 'Entity to navigate toward'
});
DynamicPathfinding.attributes.add('margin', {
type: 'number',
default: 2,
title: 'Grid Margin',
description: 'Extra margin around the min/max bounding box of the entity + target'
});
DynamicPathfinding.attributes.add('moveSpeed', {
type: 'number',
default: 2,
title: 'Move Speed',
description: 'Movement speed of the entity'
});
DynamicPathfinding.attributes.add('updateInterval', {
type: 'number',
default: 0.5,
title: 'Re-path Interval',
description: 'Seconds between BFS recalculations'
});
DynamicPathfinding.attributes.add('useDiagonals', {
type: 'boolean',
default: false,
title: 'Use Diagonal Neighbors',
description: 'If true, BFS checks 8 directions instead of 4'
});
// --- Internal ---
DynamicPathfinding.prototype.initialize = function () {
if (!this.app.systems.rigidbody) {
console.error("No rigidbody system in the project.");
return;
}
this.path = [];
this.currentNodeIndex = 0;
this.timer = 0;
if (!this.target) {
console.error("No target assigned!");
}
};
DynamicPathfinding.prototype.update = function (dt) {
this.timer += dt;
// Recalculate path after each interval
if (this.timer >= this.updateInterval && this.target) {
this.timer = 0;
this.calculatePath();
}
// Move if we have a path
if (this.path.length > 0) {
this.followPath(dt);
}
};
// --------------------------------------------------
// 1) Calculate BFS grid dynamically
// --------------------------------------------------
DynamicPathfinding.prototype.calculatePath = function () {
// 1. Determine bounding box that covers the entity + target
let entityPos = this.entity.getPosition();
let targetPos = this.target.getPosition();
let ex = Math.floor(entityPos.x);
let ez = Math.floor(entityPos.z);
let tx = Math.floor(targetPos.x);
let tz = Math.floor(targetPos.z);
let minX = Math.min(ex, tx) - this.margin;
let maxX = Math.max(ex, tx) + this.margin;
let minZ = Math.min(ez, tz) - this.margin;
let maxZ = Math.max(ez, tz) + this.margin;
this.width = maxX - minX + 1; // # cells in X
this.height = maxZ - minZ + 1; // # cells in Z
// Store offset so we can map from "grid space" back to "world space"
this.offsetX = minX;
this.offsetZ = minZ;
// Build grid array
this.grid = new Array(this.width);
for (let x = 0; x < this.width; x++) {
this.grid[x] = new Array(this.height);
for (let z = 0; z < this.height; z++) {
this.grid[x][z] = {
moveable: true,
visited: false,
parent: null
};
}
}
// 3. Raycast each cell to detect obstacles
for (let gx = 0; gx < this.width; gx++) {
for (let gz = 0; gz < this.height; gz++) {
// Convert grid coords => world coords
let worldX = gx + this.offsetX + 0.5;
let worldZ = gz + this.offsetZ + 0.5;
let start = new pc.Vec3(worldX, 2, worldZ);
let end = new pc.Vec3(worldX, -1, worldZ);
let moveable = true;
try {
let result = this.app.systems.rigidbody.raycastFirst(start, end);
if (result) {
let hitEntity = result.entity;
if (hitEntity) {
// If we hit ourselves or the target, ignore
if (hitEntity === this.entity || hitEntity === this.target) {
// do nothing, keep moveable = true
} else {
let name = (hitEntity.name || "").toLowerCase();
// If it's not a "floor" or "door," consider it blocked
// (Adjust if you want doors to block movement, etc.)
if (name !== "floor" && name !== "door" && hitEntity.collision) {
moveable = false;
}
}
}
}
} catch (err) {
console.error("Raycast error:", err);
}
this.grid[gx][gz].moveable = moveable;
}
}
// 4. Convert entity/target world coords => local grid coords
let startGrid = {
x: ex - this.offsetX,
z: ez - this.offsetZ
};
let targetGrid = {
x: tx - this.offsetX,
z: tz - this.offsetZ
};
// Check bounds again (margin might not be enough if entity is way outside)
if (!this.inBounds(startGrid.x, startGrid.z)) {
console.warn("Entity grid position out of range after margin expansion:", startGrid);
this.path = [];
return;
}
if (!this.inBounds(targetGrid.x, targetGrid.z)) {
console.warn("Target grid position out of range after margin expansion:", targetGrid);
this.path = [];
return;
}
// 5. BFS from startGrid => targetGrid
for (let x = 0; x < this.width; x++) {
for (let z = 0; z < this.height; z++) {
this.grid[x][z].visited = false;
this.grid[x][z].parent = null;
}
}
this.path = this.bfsPath(startGrid, targetGrid);
// If BFS fails, path = []
if (this.path.length === 0) {
// BFS couldn't find a route
// (obstacles or not enough margin, etc.)
// console.log("No path found from", startGrid, "to", targetGrid);
} else {
this.currentNodeIndex = 0;
}
};
// --------------------------------------------------
// 2) BFS to find path in local grid
// --------------------------------------------------
DynamicPathfinding.prototype.bfsPath = function (start, target) {
let queue = [start];
this.grid[start.x][start.z].visited = true;
while (queue.length > 0) {
let current = queue.shift();
// Found target?
if (current.x === target.x && current.z === target.z) {
// Reconstruct
return this.reconstructPath(target);
}
// Enqueue neighbors
let neighbors = this.getNeighbors(current);
for (let i = 0; i < neighbors.length; i++) {
let n = neighbors[i];
if (this.inBounds(n.x, n.z) &&
!this.grid[n.x][n.z].visited &&
this.grid[n.x][n.z].moveable) {
this.grid[n.x][n.z].visited = true;
this.grid[n.x][n.z].parent = current;
queue.push(n);
}
}
}
return [];
};
DynamicPathfinding.prototype.getNeighbors = function (node) {
// 4 or 8 directions
let directions;
if (this.useDiagonals) {
directions = [
{ x: -1, z: 0 },
{ x: 1, z: 0 },
{ x: 0, z: -1 },
{ x: 0, z: 1 },
{ x: -1, z: -1 },
{ x: -1, z: 1 },
{ x: 1, z: -1 },
{ x: 1, z: 1 }
];
} else {
directions = [
{ x: -1, z: 0 },
{ x: 1, z: 0 },
{ x: 0, z: -1 },
{ x: 0, z: 1 }
];
}
let result = [];
for (let i = 0; i < directions.length; i++) {
let nx = node.x + directions[i].x;
let nz = node.z + directions[i].z;
result.push({ x: nx, z: nz });
}
return result;
};
DynamicPathfinding.prototype.inBounds = function (x, z) {
return (x >= 0 && x < this.width && z >= 0 && z < this.height);
};
// BFS: build path from target->start
DynamicPathfinding.prototype.reconstructPath = function (end) {
let path = [];
let current = end;
while (current) {
path.push(current);
let parent = this.grid[current.x][current.z].parent;
current = parent || null;
}
path.reverse();
return path;
};
// --------------------------------------------------
// 3) Follow the path with physics
// --------------------------------------------------
DynamicPathfinding.prototype.followPath = function (dt) {
if (this.currentNodeIndex >= this.path.length) {
return; // done
}
let node = this.path[this.currentNodeIndex];
// Convert local grid coords back to world space
let worldX = node.x + this.offsetX + 0.5;
let worldZ = node.z + this.offsetZ + 0.5;
let pos = this.entity.getPosition();
let targetPos = new pc.Vec3(worldX, pos.y, worldZ);
let direction = targetPos.clone().sub(pos);
let distance = direction.length();
// If close, go to next node
if (distance < 0.1) {
this.entity.rigidbody.linearVelocity = pc.Vec3.ZERO;
this.currentNodeIndex++;
} else {
// Move toward the node
direction.normalize();
let velocity = direction.scale(this.moveSpeed);
this.entity.rigidbody.linearVelocity = velocity;
}
};
This one is pretty simple, and does have some errors, jitter issues etc.
Any help to improvements, better my AI agents etc, will be greatly appreciated. I know it’s difficult given my constraints. Thank you for reading.
