Idea for roguelike map generation #4
Description
Yet another interesting video!
I'm very sorry for disturbing you again, but I hope you welcome feedback and
discussion in any case. Well, here is my take on your new approach. To start
with, I would trust the algorithms more, even though I also make departures
here and there (as can be seen below).
What I would do:
Split the problem in smaller parts, trust the algos:
a.) Room placement: Iterative random placement with collision avoidance.
As the total space isn't really big (even in the case of a slow computer),
we can afford test-and-throw away approach to placing rectangles.
Brute force. Can be changed later.
So: Create a dungeon layout with rooms that are spatially separated,
avoiding overlaps or rooms being too close together.
b.) Corridor generation: Prim's algorithm for Minimum Spanning Trees (MST).
This ensure that all generated rooms are connected to each other with the
minimum total length of corridors, preventing isolated rooms and creating
an efficient path network. It can get hairy otherwise; a spiders web.
Prim’s algorithm is not inherently graphical or 2D. It’s a graph algorithm,
meaning it works on an abstract mathematical graph: a set of nodes (vertices)
connected by edges with weights, usually representing cost, distance, time,
etc. Here: distance.
Prim’s algo grows the MST one node at a time, always choosing the smallest-weight
edge that connects a new node to the already-built tree. It’s a greedy algorithm.
At each step, it picks the best local option, hoping this leads to a global optimum
(which it does for MSTs).
So when we have the abstract dungeon ready, we can layout the visual paths.
c.) Corridor pathfinding: Heuristic L- (and to make it more interesting Z-shaped)
paths. So, create direct corridors between rooms that are easy to navigate and
visualise.
Sketch through JavaScript/HTML
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Optimized Dungeon Layout Game</title>
<style>
body { margin: 0; font-family: Arial, sans-serif; }
#canvas { border: 1px solid black; background-color: #f0f0f0; }
#controls { padding: 10px; background-color: #ddd; }
button { margin: 5px; padding: 5px 10px; }
#stats { margin-top: 10px; font-size: 12px; }
</style>
</head>
<body>
<div id="controls">
<button onclick="game.resetDungeon()">Reset Dungeon</button>
<button onclick="game.clearCanvas()">Clear Canvas</button>
<button onclick="game.toggleAnimation()">Toggle Animation</button>
<button onclick="game.clearHistory()">Clear History</button>
<div id="stats"></div>
</div>
<canvas id="canvas" width="800" height="600"></canvas>
<script>
const CONFIG = {
gridSize: 20,
roomCount: 10,
minRoomSize: 30,
maxRoomSize: 60,
minRoomDistance: 40,
maxPlacementAttempts: 50,
dotSpeed: 120, // pixels per second
pauseTime: 1000, // milliseconds
historyDecayTime: 30000, // 30 seconds before rooms become less avoided
maxHistorySize: 50 // max number of visits to remember
};
// pools for memory management
class ObjectPool {
constructor(createFn, resetFn) {
this.createFn = createFn;
this.resetFn = resetFn;
this.pool = [];
this.active = [];
}
get() {
let obj = this.pool.pop();
if (!obj) {
obj = this.createFn();
}
this.active.push(obj);
return obj;
}
release(obj) {
const index = this.active.indexOf(obj);
if (index > -1) {
this.active.splice(index, 1);
this.resetFn(obj);
this.pool.push(obj);
}
}
releaseAll() {
while (this.active.length > 0) {
this.release(this.active[0]);
}
}
}
// Vector utility class
class Vector2 {
constructor(x = 0, y = 0) {
this.x = x;
this.y = y;
}
set(x, y) {
this.x = x;
this.y = y;
return this;
}
copy(other) {
this.x = other.x;
this.y = other.y;
return this;
}
distance(other) {
return Math.hypot(this.x - other.x, this.y - other.y);
}
normalize() {
const len = Math.hypot(this.x, this.y);
if (len > 0) {
this.x /= len;
this.y /= len;
}
return this;
}
scale(factor) {
this.x *= factor;
this.y *= factor;
return this;
}
add(other) {
this.x += other.x;
this.y += other.y;
return this;
}
}
// Visit history tracker
class VisitHistory {
constructor() {
this.visits = new Map(); // roomIndex -> array of visit times
this.totalVisits = 0;
}
recordVisit(roomIndex) {
const currentTime = performance.now();
if (!this.visits.has(roomIndex)) {
this.visits.set(roomIndex, []);
}
const roomVisits = this.visits.get(roomIndex);
roomVisits.push(currentTime);
this.totalVisits++;
// only recent visits within history size limit!
if (roomVisits.length > CONFIG.maxHistorySize) {
roomVisits.shift();
}
// clean up old visits
this.cleanupOldVisits(currentTime);
}
cleanupOldVisits(currentTime) {
const cutoffTime = currentTime - CONFIG.historyDecayTime;
for (let [roomIndex, visits] of this.visits) {
const filteredVisits = visits.filter(time => time > cutoffTime);
if (filteredVisits.length === 0) {
this.visits.delete(roomIndex);
} else {
this.visits.set(roomIndex, filteredVisits);
}
}
}
getVisitCount(roomIndex) {
return this.visits.has(roomIndex) ? this.visits.get(roomIndex).length : 0;
}
getRecentVisitCount(roomIndex, timeWindow = 10000) {
if (!this.visits.has(roomIndex)) return 0;
const currentTime = performance.now();
const cutoffTime = currentTime - timeWindow;
return this.visits.get(roomIndex).filter(time => time > cutoffTime).length;
}
getUnvisitedRooms(totalRooms) {
const unvisited = [];
for (let i = 0; i < totalRooms; i++) {
if (!this.visits.has(i)) {
unvisited.push(i);
}
}
return unvisited;
}
getLeastVisitedRooms(totalRooms, count = 3) {
const roomCounts = [];
for (let i = 0; i < totalRooms; i++) {
roomCounts.push({
roomIndex: i,
visitCount: this.getVisitCount(i),
recentVisits: this.getRecentVisitCount(i)
});
}
// sort by recent visits first, then by total visits
roomCounts.sort((a, b) => {
if (a.recentVisits !== b.recentVisits) {
return a.recentVisits - b.recentVisits;
}
return a.visitCount - b.visitCount;
});
return roomCounts.slice(0, count).map(item => item.roomIndex);
}
clear() {
this.visits.clear();
this.totalVisits = 0;
}
getStats() {
const uniqueRoomsVisited = this.visits.size;
const totalVisits = Array.from(this.visits.values()).reduce((sum, visits) => sum + visits.length, 0);
return { uniqueRoomsVisited, totalVisits };
}
}
// MST impl. using Prim's algorithm
class MST {
static generate(rooms) {
if (rooms.length === 0) return [];
const edges = [];
const visited = new Set();
const distances = new Map();
// start with first room
visited.add(0);
// add all edges from first room
for (let i = 1; i < rooms.length; i++) {
const dist = rooms[0].position.distance(rooms[i].position);
distances.set(`0-${i}`, dist);
edges.push({ from: 0, to: i, weight: dist });
}
const mstEdges = [];
while (visited.size < rooms.length && edges.length > 0) {
// find minimum weight edge connecting visited to unvisited
edges.sort((a, b) => a.weight - b.weight);
let minEdge = null;
let minIndex = -1;
for (let i = 0; i < edges.length; i++) {
const edge = edges[i];
if (visited.has(edge.from) && !visited.has(edge.to)) {
minEdge = edge;
minIndex = i;
break;
}
}
if (minEdge) {
mstEdges.push(minEdge);
visited.add(minEdge.to);
// add new edges from the newly connected room
for (let i = 0; i < rooms.length; i++) {
if (!visited.has(i)) {
const key = `${minEdge.to}-${i}`;
if (!distances.has(key)) {
const dist = rooms[minEdge.to].position.distance(rooms[i].position);
distances.set(key, dist);
edges.push({ from: minEdge.to, to: i, weight: dist });
}
}
}
edges.splice(minIndex, 1);
} else {
break;
}
}
return mstEdges;
}
}
class Room {
constructor(x, y, id) {
this.position = new Vector2(x, y);
this.id = id;
this.width = Math.floor(Math.random() * (CONFIG.maxRoomSize - CONFIG.minRoomSize + 1)) + CONFIG.minRoomSize;
this.height = Math.floor(Math.random() * (CONFIG.maxRoomSize - CONFIG.minRoomSize + 1)) + CONFIG.minRoomSize;
this.visitCount = 0;
this.lastVisitTime = 0;
}
getConnectionPoint(targetRoom) {
const left = this.position.x - this.width / 2;
const right = this.position.x + this.width / 2;
const top = this.position.y - this.height / 2;
const bottom = this.position.y + this.height / 2;
let nearestX = Math.max(left, Math.min(right, targetRoom.position.x));
let nearestY = Math.max(top, Math.min(bottom, targetRoom.position.y));
// if point is inside room, move to nearest edge
// think this is like "rougelike" style?
if (nearestX > left && nearestX < right && nearestY > top && nearestY < bottom) {
const distances = [
{ pos: left, coord: 'x', val: nearestX - left },
{ pos: right, coord: 'x', val: right - nearestX },
{ pos: top, coord: 'y', val: nearestY - top },
{ pos: bottom, coord: 'y', val: bottom - nearestY }
];
const nearest = distances.reduce((min, curr) => curr.val < min.val ? curr : min);
if (nearest.coord === 'x') {
nearestX = nearest.pos;
} else {
nearestY = nearest.pos;
}
}
return new Vector2(nearestX, nearestY);
}
draw(ctx, visitHistory) {
const visitCount = visitHistory.getVisitCount(this.id - 1);
const recentVisits = visitHistory.getRecentVisitCount(this.id - 1, 5000);
// color based on visit history
let fillColor = '#1E90FF'; // blue
if (visitCount === 0) {
fillColor = '#32CD32'; // green for unvisited
} else if (recentVisits > 0) {
fillColor = '#FF6B6B'; // red for recently visited
} else if (visitCount > 0) {
fillColor = '#FFA500'; // orange for visited but not recent
}
ctx.fillStyle = fillColor;
ctx.fillRect(
this.position.x - this.width / 2,
this.position.y - this.height / 2,
this.width,
this.height
);
// draw checkerboard pattern
ctx.fillStyle = visitCount === 0 ? '#228B22' : '#4682B4';
const cellSize = 5;
for (let i = 0; i < this.width - 4; i += cellSize) {
for (let j = 0; j < this.height - 4; j += cellSize) {
if ((Math.floor(i / cellSize) + Math.floor(j / cellSize)) % 2 === 0) {
ctx.fillRect(
this.position.x - this.width / 2 + 2 + i,
this.position.y - this.height / 2 + 2 + j,
cellSize,
cellSize
);
}
}
}
// draw room ID and visit count
ctx.fillStyle = '#000';
ctx.font = '12px Arial';
ctx.fillText(`R${this.id}`, this.position.x - 10, this.position.y - 5);
if (visitCount > 0) {
ctx.fillText(`(${visitCount})`, this.position.x - 10, this.position.y + 10);
}
}
}
// class with optimised path generation
class Corridor {
constructor(roomA, roomB) {
this.roomA = roomA;
this.roomB = roomB;
this.path = this.generatePath();
this.totalLength = this.calculateLength();
}
generatePath() {
const startPoint = this.roomA.getConnectionPoint(this.roomB);
const endPoint = this.roomB.getConnectionPoint(this.roomA);
const path = [startPoint];
const minOffset = CONFIG.gridSize * 1.5;
const dx = endPoint.x - startPoint.x;
const dy = endPoint.y - startPoint.y;
// path type based on distance
if (Math.abs(dx) > Math.abs(dy)) {
this.addHorizontalPath(path, startPoint, endPoint, minOffset);
} else {
this.addVerticalPath(path, startPoint, endPoint, minOffset);
}
path.push(endPoint);
return path;
}
addHorizontalPath(path, start, end, minOffset) {
const dx = end.x - start.x;
const dy = end.y - start.y;
const horizontalOffset = dx > 0 ? minOffset : -minOffset;
const firstX = start.x + horizontalOffset;
path.push(new Vector2(firstX, start.y));
if (Math.abs(dy) > minOffset) {
const targetX = end.x + (dx > 0 ? -minOffset : minOffset);
path.push(new Vector2(targetX, start.y));
path.push(new Vector2(targetX, end.y));
} else {
const midY = (start.y + end.y) / 2;
path.push(new Vector2(firstX, midY));
const targetX = end.x + (dx > 0 ? -minOffset : minOffset);
path.push(new Vector2(targetX, midY));
path.push(new Vector2(targetX, end.y));
}
}
addVerticalPath(path, start, end, minOffset) {
const dx = end.x - start.x;
const dy = end.y - start.y;
const verticalOffset = dy > 0 ? minOffset : -minOffset;
const firstY = start.y + verticalOffset;
path.push(new Vector2(start.x, firstY));
if (Math.abs(dx) > minOffset) {
const targetY = end.y + (dy > 0 ? -minOffset : minOffset);
path.push(new Vector2(start.x, targetY));
path.push(new Vector2(end.x, targetY));
} else {
const midX = (start.x + end.x) / 2;
path.push(new Vector2(midX, firstY));
const targetY = end.y + (dy > 0 ? -minOffset : minOffset);
path.push(new Vector2(midX, targetY));
path.push(new Vector2(end.x, targetY));
}
}
calculateLength() {
let length = 0;
for (let i = 1; i < this.path.length; i++) {
length += this.path[i].distance(this.path[i - 1]);
}
return length;
}
draw(ctx) {
if (this.path.length < 2) return;
ctx.strokeStyle = '#FF0000';
ctx.lineWidth = 4;
ctx.beginPath();
ctx.moveTo(this.path[0].x, this.path[0].y);
for (let i = 1; i < this.path.length; i++) {
ctx.lineTo(this.path[i].x, this.path[i].y);
}
ctx.stroke();
}
}
// smart movement system with history-aware pathfinding
class MovementSystem {
constructor(visitHistory) {
this.position = new Vector2();
this.targetPosition = new Vector2();
this.velocity = new Vector2();
this.currentRoomIndex = 0;
this.targetRoomIndex = 0;
this.currentPath = [];
this.pathIndex = 0;
this.isMoving = false;
this.pauseTimer = 0;
this.connectionMap = new Map();
this.visitHistory = visitHistory;
}
initialize(rooms, corridors) {
if (rooms.length === 0) return;
this.buildConnectionMap(rooms, corridors);
this.currentRoomIndex = Math.floor(Math.random() * rooms.length);
this.position.copy(rooms[this.currentRoomIndex].position);
this.targetPosition.copy(this.position);
this.isMoving = false;
this.pauseTimer = 0;
// record initial room visit
this.visitHistory.recordVisit(this.currentRoomIndex);
}
buildConnectionMap(rooms, corridors) {
this.connectionMap.clear();
for (let i = 0; i < rooms.length; i++) {
this.connectionMap.set(i, []);
}
for (let corridor of corridors) {
const roomAIdx = rooms.indexOf(corridor.roomA);
const roomBIdx = rooms.indexOf(corridor.roomB);
this.connectionMap.get(roomAIdx).push({
roomIndex: roomBIdx,
path: corridor.path
});
this.connectionMap.get(roomBIdx).push({
roomIndex: roomAIdx,
path: [...corridor.path].reverse()
});
}
}
update(deltaTime, rooms) {
if (rooms.length < 2) return;
if (this.isMoving) {
this.updateMovement(deltaTime);
} else {
this.pauseTimer += deltaTime;
if (this.pauseTimer >= CONFIG.pauseTime) {
this.startNewJourney(rooms);
}
}
}
updateMovement(deltaTime) {
if (this.pathIndex >= this.currentPath.length) {
this.completeJourney();
return;
}
const target = this.currentPath[this.pathIndex];
const distance = this.position.distance(target);
const moveDistance = CONFIG.dotSpeed * (deltaTime / 1000);
if (distance <= moveDistance) {
this.position.copy(target);
this.pathIndex++;
} else {
// smooth interpolation
const direction = new Vector2(target.x - this.position.x, target.y - this.position.y);
direction.normalize().scale(moveDistance);
this.position.add(direction);
}
}
chooseNextRoom(rooms) {
const connections = this.connectionMap.get(this.currentRoomIndex);
if (!connections || connections.length === 0) return null;
// get unvisited rooms first
const unvisitedRooms = this.visitHistory.getUnvisitedRooms(rooms.length);
// filter connections to only include unvisited rooms, if any exist
let preferredConnections = connections.filter(conn =>
unvisitedRooms.includes(conn.roomIndex)
);
if (preferredConnections.length === 0) {
// if no unvisited rooms are directly connected, use least visited
const leastVisited = this.visitHistory.getLeastVisitedRooms(rooms.length, 5);
preferredConnections = connections.filter(conn =>
leastVisited.includes(conn.roomIndex)
);
}
// if still no preferred connections, use all connections but weight them
if (preferredConnections.length === 0) {
preferredConnections = connections;
}
// weight selection based on visit history
const weightedConnections = preferredConnections.map(conn => {
const visitCount = this.visitHistory.getVisitCount(conn.roomIndex);
const recentVisits = this.visitHistory.getRecentVisitCount(conn.roomIndex, 10000);
// lower weight means higher preference
let weight = 1;
if (visitCount === 0) {
weight = 0.1; // strongly prefer unvisited
} else {
weight = 1 + (visitCount * 0.5) + (recentVisits * 2);
}
return { ...conn, weight };
});
// weighted random selection (inverse weight - lower weight = higher chance)
const totalInverseWeight = weightedConnections.reduce((sum, conn) => sum + (1 / conn.weight), 0);
let random = Math.random() * totalInverseWeight;
for (let conn of weightedConnections) {
random -= (1 / conn.weight);
if (random <= 0) {
return conn;
}
}
// fallback to last connection
return weightedConnections[weightedConnections.length - 1];
}
startNewJourney(rooms) {
const selectedConnection = this.chooseNextRoom(rooms);
if (selectedConnection) {
this.targetRoomIndex = selectedConnection.roomIndex;
this.currentPath = selectedConnection.path;
this.pathIndex = 0;
this.isMoving = true;
this.pauseTimer = 0;
}
}
completeJourney() {
this.isMoving = false;
this.pauseTimer = 0;
this.currentRoomIndex = this.targetRoomIndex;
this.currentPath = [];
this.pathIndex = 0;
// record the visit
this.visitHistory.recordVisit(this.currentRoomIndex);
}
draw(ctx) {
// outer glow
ctx.shadowBlur = 15;
ctx.shadowColor = '#FF6B35';
ctx.fillStyle = '#FF6B35';
ctx.beginPath();
ctx.arc(this.position.x, this.position.y, 8, 0, 2 * Math.PI);
ctx.fill();
// inner bright center
ctx.shadowBlur = 5;
ctx.shadowColor = '#FFFF00';
ctx.fillStyle = '#FFFF00';
ctx.beginPath();
ctx.arc(this.position.x, this.position.y, 4, 0, 2 * Math.PI);
ctx.fill();
// reset shadow
ctx.shadowBlur = 0;
}
}
// separate! rendering concerns
class Renderer {
constructor(canvas) {
this.canvas = canvas;
this.ctx = canvas.getContext('2d');
}
clear() {
this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
}
drawGrid() {
this.ctx.strokeStyle = '#ccc';
this.ctx.lineWidth = 1;
for (let x = 0; x < this.canvas.width; x += CONFIG.gridSize) {
this.ctx.beginPath();
this.ctx.moveTo(x, 0);
this.ctx.lineTo(x, this.canvas.height);
this.ctx.stroke();
}
for (let y = 0; y < this.canvas.height; y += CONFIG.gridSize) {
this.ctx.beginPath();
this.ctx.moveTo(0, y);
this.ctx.lineTo(this.canvas.width, y);
this.ctx.stroke();
}
}
render(rooms, corridors, movementSystem, visitHistory) {
this.clear();
this.drawGrid();
// corridors
for (let corridor of corridors) {
corridor.draw(this.ctx);
}
// rooms with history visualisation
for (let room of rooms) {
room.draw(this.ctx, visitHistory);
}
// moving dot
movementSystem.draw(this.ctx);
}
}
class Game {
constructor() {
this.canvas = document.getElementById('canvas');
this.renderer = new Renderer(this.canvas);
this.visitHistory = new VisitHistory();
this.rooms = [];
this.corridors = [];
this.movementSystem = new MovementSystem(this.visitHistory);
this.animationRunning = true;
this.lastTime = 0;
// object pools
this.roomPool = new ObjectPool(
() => new Room(0, 0, 0),
(room) => {
room.position.set(0, 0);
room.id = 0;
}
);
this.vectorPool = new ObjectPool(
() => new Vector2(),
(vector) => vector.set(0, 0)
);
}
initialize() {
this.generateRooms();
this.connectRooms();
this.movementSystem.initialize(this.rooms, this.corridors);
this.startGameLoop();
}
generateRooms() {
// clear existing rooms
this.roomPool.releaseAll();
this.rooms = [];
const usedPositions = [];
for (let i = 0; i < CONFIG.roomCount; i++) {
let attempts = 0;
let validPosition = false;
let x, y;
while (!validPosition && attempts < CONFIG.maxPlacementAttempts) {
x = Math.random() * (this.canvas.width - CONFIG.maxRoomSize) + CONFIG.maxRoomSize / 2;
y = Math.random() * (this.canvas.height - CONFIG.maxRoomSize) + CONFIG.maxRoomSize / 2;
validPosition = true;
for (let pos of usedPositions) {
if (Math.hypot(pos.x - x, pos.y - y) < CONFIG.minRoomDistance) {
validPosition = false;
break;
}
}
attempts++;
}
if (validPosition) {
const room = new Room(x, y, i + 1);
this.rooms.push(room);
usedPositions.push({ x, y });
}
}
}
connectRooms() {
this.corridors = [];
if (this.rooms.length === 0) return;
const mstEdges = MST.generate(this.rooms);
for (let edge of mstEdges) {
const corridor = new Corridor(this.rooms[edge.from], this.rooms[edge.to]);
this.corridors.push(corridor);
}
}
update(deltaTime) {
if (this.animationRunning) {
this.movementSystem.update(deltaTime, this.rooms);
this.updateStats();
}
}
updateStats() {
const stats = this.visitHistory.getStats();
const unvisitedCount = this.visitHistory.getUnvisitedRooms(this.rooms.length).length;
const statsDiv = document.getElementById('stats');
statsDiv.innerHTML = `
Rooms Visited: ${stats.uniqueRoomsVisited}/${this.rooms.length} |
Total Visits: ${stats.totalVisits} |
Unvisited: ${unvisitedCount}
`;
}
render() {
this.renderer.render(this.rooms, this.corridors, this.movementSystem, this.visitHistory);
}
gameLoop(currentTime) {
const deltaTime = currentTime - this.lastTime;
this.lastTime = currentTime;
this.update(deltaTime);
this.render();
requestAnimationFrame((time) => this.gameLoop(time));
}
startGameLoop() {
this.lastTime = performance.now();
this.gameLoop(this.lastTime);
}
resetDungeon() {
this.generateRooms();
this.connectRooms();
this.visitHistory.clear();
this.movementSystem.initialize(this.rooms, this.corridors);
}
clearCanvas() {
this.rooms = [];
this.corridors = [];
this.visitHistory.clear();
this.movementSystem.initialize(this.rooms, this.corridors);
}
clearHistory() {
this.visitHistory.clear();
}
toggleAnimation() {
this.animationRunning = !this.animationRunning;
}
}
// Initialize game
const game = new Game();
game.initialize();
window.game = game;
</script>
<script>
// Event listeners for buttons
document.getElementById('resetDungeon').addEventListener('click', () => {
game.resetDungeon();
});
document.getElementById('clearCanvas').addEventListener('click', () => {
game.clearCanvas();
});
document.getElementById('clearHistory').addEventListener('click', () => {
game.clearHistory();
});
document.getElementById('toggleAnimation').addEventListener('click', () => {
game.toggleAnimation();
});
</script>
</body>
</html>a.) When generateRooms() is called, it attempts to place a specified number of
rooms (CONFIG.roomCount) randomly within the canvas bounds. For each new room,
it generates a random (x, y) coordinate. But before "placing" it,
it checks if this new room's potential position is too close to any previously
placed rooms (closer than CONFIG.minRoomDistance).
If it is too close, the position is discarded, and a new random position is
attempted. This process is repeated for a maximum number of attempts
(CONFIG.maxPlacementAttempts) to prevent infinite loops if a valid
placement becomes impossible.
b.) The MST.generate() method is responsible for connecting the rooms. It
treats the rooms as nodes in a graph and the potential corridors between
them as edges. It then applies a variation of Prim's Algorithm to find a
Minimum Spanning Tree (MST) of this graph. This you have explored already
in depth--I think. Prim's algorithm starts with an arbitrary node (here,
the first room) and iteratively adds the "cheapest" edge (shortest distance
between rooms) that connects a visited node to an unvisited node, until all
nodes are visited.
c.) Within the Corridor class, the generatePath() method creates a "path"
(a series of Vector2 points) that the "dot" will follow. The "dot" here
is an enhancement to illustrate further additions to the game. Instead of
complex pathfinding algorithms like A* (which I first tried, but would be
overkill for simple room-to-room connections), it uses a heuristic approach:
-
It first finds the closest "connection point" on the boundary of each
room to the other room's center. This heuristic mimics the visual
appearance of paths one might traverse in a Manhattan-like grid
(which you have in your video), but it's not a direct application
of the Manhattan distance formula for pathfinding.
It's more of a "rectilinear routing" strategy. -
It then generates an L-shaped or Z-shaped path depending on whether
the horizontal or vertical distance between the rooms is greater.
This involves adding one or two intermediate points to create a
"jog" that avoids cutting directly through rooms or creating
excessively long diagonal paths. TheminOffsetensures the bends
are a certain distance from the room edges.
There are some additions to the code, which only is there to show possible
extensions. The "dot" is wandering the maze and keeps a history where
it has been. The memory however has its limits and the dots forgets
where it has been. Suitable for revisiting rooms ..
Translating code from JavaScript to a pseudo-C style .. Code written
in one programming language can often be transcribed into another.
The result may be awkward or clumsy if the programming idioms differ
too much, but more often than not, the underlying structure and logic
remain clearly recognisable. Translating it "down" with some
access to OO, the code is as follow (including my additions).
The object/class concepts can naturally be simulated also, to
the obvious consequence of much more code ..
STRUCT CONFIG {
INT gridSize;
INT roomCount;
INT minRoomSize;
INT maxRoomSize;
INT minRoomDistance;
INT maxPlacementAttempts;
FLOAT dotSpeed;
INT pauseTime;
INT historyDecayTime;
INT maxHistorySize;
};
// --- Utils ---
CLASS ObjectPool {
FUNCTION createFn;
FUNCTION resetFn;
ARRAY pool;
ARRAY active;
CONSTRUCTOR(createFn, resetFn) {
THIS.createFn = createFn;
THIS.resetFn = resetFn;
// Init pool and active arrays
}
Object get() {
IF (pool IS NOT EMPTY) {
obj = POP FROM pool;
} ELSE {
obj = CALL createFn();
}
ADD obj TO active;
RETURN obj;
}
VOID release(Object obj) {
IF (obj IS IN active) {
REMOVE obj FROM active;
CALL resetFn(obj);
ADD obj TO pool;
}
}
VOID releaseAll() {
WHILE (active IS NOT EMPTY) {
CALL release(FIRST ELEMENT OF active);
}
}
}
CLASS Vector2 {
FLOAT x, y;
CONSTRUCTOR(x = 0, y = 0) {
THIS.x = x;
THIS.y = y;
}
VOID set(FLOAT x, FLOAT y) {
THIS.x = x;
THIS.y = y;
}
VOID copy(Vector2 other) {
THIS.x = other.x;
THIS.y = other.y;
}
FLOAT distance(Vector2 other) {
RETURN SQRT(POW(THIS.x - other.x, 2) + POW(THIS.y - other.y, 2));
}
VOID normalize() {
FLOAT len = distance(NEW Vector2(0,0)); // Euclidian distance from origin
IF (len > 0) {
THIS.x /= len;
THIS.y /= len;
}
}
VOID scale(FLOAT factor) {
THIS.x *= factor;
THIS.y *= factor;
}
VOID add(Vector2 other) {
THIS.x += other.x;
THIS.y += other.y;
}
}
// special addition
CLASS VisitHistory {
MAP<INT, ARRAY<FLOAT>> visits; // roomIndex -> array of visit times
INT totalVisits;
CONSTRUCTOR() {
// Init visits map and totalVisits
}
VOID recordVisit(INT roomIndex) {
FLOAT currentTime = GET_CURRENT_TIME_MS();
IF (visits DOES NOT HAVE roomIndex) {
visits.SET(roomIndex, NEW ARRAY<FLOAT>());
}
ADD currentTime TO visits.GET(roomIndex);
totalVisits++;
// Remove oldest visits, if history size exceeded
IF (visits.GET(roomIndex).LENGTH > CONFIG.maxHistorySize) {
REMOVE FIRST ELEMENT FROM visits.GET(roomIndex);
}
cleanupOldVisits(currentTime);
}
VOID cleanupOldVisits(FLOAT currentTime) {
FLOAT cutoffTime = currentTime - CONFIG.historyDecayTime;
FOR EACH roomIndex, visitsArray IN visits {
FILTER visitsArray TO KEEP ONLY TIMES > cutoffTime;
IF (filteredVisitsArray IS EMPTY) {
REMOVE roomIndex FROM visits;
} ELSE {
visits.SET(roomIndex, filteredVisitsArray);
}
}
}
INT getVisitCount(INT roomIndex) {
RETURN visits.HAS(roomIndex) ? visits.GET(roomIndex).LENGTH : 0;
}
INT getRecentVisitCount(INT roomIndex, INT timeWindowMs) {
// Similar to getVisitCount, but filters for visits within timeWindowMs
}
ARRAY<INT> getUnvisitedRooms(INT totalRooms) {
ARRAY<INT> unvisited;
FOR (INT i = 0; i < totalRooms; i++) {
IF (visits DOES NOT HAVE i) {
ADD i TO unvisited;
}
}
RETURN unvisited;
}
ARRAY<INT> getLeastVisitedRooms(INT totalRooms, INT count) {
ARRAY<STRUCT {INT roomIndex, INT visitCount, INT recentVisits}> roomCounts;
// Populate roomCounts with visit data for all rooms
// Sort roomCounts by recentVisits then by visitCount (ascending)
// Return 'count' number of roomIndexes from the sorted list
}
VOID clear() {
visits.CLEAR();
totalVisits = 0;
}
STRUCT {INT uniqueRoomsVisited, INT totalVisits} getStats() {
// Calc and return stats
}
}
// --- game logic ---
// Minimum Spanning Tree generator (using Prim's Algorithm concept)
CLASS MST {
STATIC ARRAY<STRUCT {INT from, INT to, FLOAT weight}> generate(ARRAY<Room> rooms) {
IF (rooms IS EMPTY) RETURN EMPTY ARRAY;
ARRAY<STRUCT {INT from, INT to, FLOAT weight}> edges;
SET<INT> visited;
MAP<STRING, FLOAT> distances; // Stores distances, to avoid recomputing
ADD 0 TO visited; // Start with first room
// Add initial edges from room 0 to all others
FOR (INT i = 1; i < rooms.LENGTH; i++) {
FLOAT dist = rooms[0].position.distance(rooms[i].position);
distances.SET("0-i", dist);
ADD {from: 0, to: i, weight: dist} TO edges;
}
ARRAY<STRUCT {INT from, INT to, FLOAT weight}> mstEdges;
WHILE (visited.SIZE < rooms.LENGTH AND edges IS NOT EMPTY) {
// Sort edges by weight
SORT edges ASCENDING BY weight;
STRUCT {INT from, INT to, FLOAT weight} minEdge = NULL;
INT minIndex = -1;
FOR (INT i = 0; i < edges.LENGTH; i++) {
STRUCT edge = edges[i];
IF (visited HAS edge.from AND visited DOES NOT HAVE edge.to) {
minEdge = edge;
minIndex = i;
BREAK;
}
}
IF (minEdge IS NOT NULL) {
ADD minEdge TO mstEdges;
ADD minEdge.to TO visited;
// Add new edges from the newly connected room to unvisited rooms
FOR (INT i = 0; i < rooms.LENGTH; i++) {
IF (visited DOES NOT HAVE i) {
STRING key = CONCAT(minEdge.to, "-", i);
IF (distances DOES NOT HAVE key) {
FLOAT dist = rooms[minEdge.to].position.distance(rooms[i].position);
distances.SET(key, dist);
ADD {from: minEdge.to, to: i, weight: dist} TO edges;
}
}
}
REMOVE edge AT minIndex FROM edges;
} ELSE {
BREAK; // No more connections possible
}
}
RETURN mstEdges;
}
}
// A Room in the dungeon
CLASS Room {
Vector2 position;
INT id;
INT width, height;
// (Additional properties for drawing, not! core logic)
CONSTRUCTOR(x, y, id) {
THIS.position = NEW Vector2(x, y);
THIS.id = id;
THIS.width = RANDOM_INT(CONFIG.minRoomSize, CONFIG.maxRoomSize);
THIS.height = RANDOM_INT(CONFIG.minRoomSize, CONFIG.maxRoomSize);
}
Vector2 getConnectionPoint(Room targetRoom) {
// Calc the point on this room's boundary closest to the target room's center.
// If the target room's center is inside this room, move the point to the nearest edge.
// This is a "roguelike" connection style, which I guess we are after.
RETURN NEW Vector2(nearestX, nearestY);
}
VOID draw(Context ctx, VisitHistory visitHistory) {
// If we also want to simulate the rest of the JS code:
// Determine fill color based on visit history (unvisited, recently visited, visited)
// Draw rectangle for room
// Draw checkerboard pattern
// Draw room ID and visit count text
}
}
CLASS Corridor {
Room roomA, roomB;
ARRAY<Vector2> path;
FLOAT totalLength;
CONSTRUCTOR(roomA, roomB) {
THIS.roomA = roomA;
THIS.roomB = roomB;
THIS.path = generatePath();
THIS.totalLength = calculateLength();
}
ARRAY<Vector2> generatePath() {
Vector2 startPoint = roomA.getConnectionPoint(roomB);
Vector2 endPoint = roomB.getConnectionPoint(roomA);
ARRAY<Vector2> path = {startPoint};
// Generate a path with intermediate points using "L" or "Z" shapes
// based on relative positions of startPoint and endPoint.
// This creates "optimised" L-shaped or Z-shaped corridors.
IF (ABS(endPoint.x - startPoint.x) > ABS(endPoint.y - startPoint.y)) {
addHorizontalPath(path, startPoint, endPoint, CONFIG.gridSize * 1.5);
} ELSE {
addVerticalPath(path, startPoint, endPoint, CONFIG.gridSize * 1.5);
}
ADD endPoint TO path;
RETURN path;
}
VOID addHorizontalPath(ARRAY<Vector2> path, Vector2 start, Vector2 end, FLOAT minOffset) {
// Adds points for a horisontal-priority path (e.g., start -> horisontal_turn -> vertical_turn -> end)
}
VOID addVerticalPath(ARRAY<Vector2> path, Vector2 start, Vector2 end, FLOAT minOffset) {
// Adds points for a vertical-priority path (e.g., start -> vertical_turn -> horizontal_turn -> end)
}
FLOAT calculateLength() {
// Sums distances between consecutive points in 'path'
RETURN totalLength;
}
VOID draw(Context ctx) {
// Draw lines connecting points in 'path'
}
}
// If we are after simulation as the JS script ..
// Handles the movement of the "dot" through the dungeon
CLASS MovementSystem {
Vector2 position;
Vector2 targetPosition;
Vector2 velocity;
INT currentRoomIndex;
INT targetRoomIndex;
ARRAY<Vector2> currentPath;
INT pathIndex;
BOOL isMoving;
FLOAT pauseTimer;
MAP<INT, ARRAY<STRUCT {INT roomIndex, ARRAY<Vector2> path}>> connectionMap; // Adjacency list for graph
VisitHistory visitHistory;
CONSTRUCTOR(visitHistory) {
THIS.visitHistory = visitHistory;
// Init position, velocity, etc.
}
VOID initialize(ARRAY<Room> rooms, ARRAY<Corridor> corridors) {
// Build connectionMap from rooms and corridors
// Set initial position to a random room
// Record initial room visit
}
VOID buildConnectionMap(ARRAY<Room> rooms, ARRAY<Corridor> corridors) {
// Populate connectionMap: For each room, list connected rooms and the path to them.
// Ensures bidirectional connections.
}
VOID update(FLOAT deltaTime, ARRAY<Room> rooms) {
IF (isMoving) {
updateMovement(deltaTime);
} ELSE {
pauseTimer += deltaTime;
IF (pauseTimer >= CONFIG.pauseTime) {
startNewJourney(rooms);
}
}
}
VOID updateMovement(FLOAT deltaTime) {
IF (pathIndex IS AT END OF currentPath) {
completeJourney();
RETURN;
}
Vector2 target = currentPath[pathIndex];
FLOAT distance = position.distance(target);
FLOAT moveDistance = CONFIG.dotSpeed * (deltaTime / 1000.0);
IF (distance <= moveDistance) {
position.copy(target);
pathIndex++;
} ELSE {
// Move partially towards target
Vector2 direction = NEW Vector2(target.x - position.x, target.y - position.y);
direction.normalize().scale(moveDistance);
position.add(direction);
}
}
STRUCT {INT roomIndex, ARRAY<Vector2> path} chooseNextRoom(ARRAY<Room> rooms) {
ARRAY<STRUCT {INT roomIndex, ARRAY<Vector2> path}> connections = connectionMap.GET(currentRoomIndex);
IF (connections IS EMPTY) RETURN NULL;
// PRIORITY:
// 1. Unvisited directly connected rooms.
// 2. If none, least visited rooms (globally or within a small set).
// 3. Otherwise, use all connections and apply weights based on visit history
// (lower weight for less visited/less recently visited).
// Select one connection using a weighted random approach.
RETURN selectedConnection;
}
VOID startNewJourney(ARRAY<Room> rooms) {
STRUCT selectedConnection = chooseNextRoom(rooms);
IF (selectedConnection IS NOT NULL) {
targetRoomIndex = selectedConnection.roomIndex;
currentPath = selectedConnection.path;
pathIndex = 0;
isMoving = TRUE;
pauseTimer = 0;
}
}
VOID completeJourney() {
isMoving = FALSE;
pauseTimer = 0;
currentRoomIndex = targetRoomIndex;
currentPath = EMPTY ARRAY;
pathIndex = 0;
visitHistory.recordVisit(currentRoomIndex);
}
VOID draw(Context ctx) {
// Draw the moving dot with glow effects
}
}
CLASS Renderer {
Canvas canvas;
Context ctx;
CONSTRUCTOR(canvas) {
THIS.canvas = canvas;
THIS.ctx = canvas.getContext('2d');
}
VOID clear() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
}
VOID drawGrid() {
// Draw a background grid on the canvas
}
VOID render(ARRAY<Room> rooms, ARRAY<Corridor> corridors, MovementSystem movementSystem, VisitHistory visitHistory) {
clear();
drawGrid();
FOR EACH corridor IN corridors { corridor.draw(ctx); }
FOR EACH room IN rooms { room.draw(ctx, visitHistory); }
movementSystem.draw(ctx);
}
}
// --- Main ---
// The logic here might be dependent on the exact impl.
// which can vary.
CLASS Game {
Canvas canvas;
Renderer renderer;
VisitHistory visitHistory;
ARRAY<Room> rooms;
ARRAY<Corridor> corridors;
MovementSystem movementSystem;
BOOL animationRunning;
FLOAT lastTime;
// Object Pools (roomPool, vectorPool)
CONSTRUCTOR() {
// Get canvas element
// Init renderer, visitHistory, movementSystem
// Init object pools
// Set initial animation state
}
VOID initialize() {
generateRooms();
connectRooms();
movementSystem.initialize(THIS.rooms, THIS.corridors);
startGameLoop();
}
VOID generateRooms() {
// Clear existing rooms
// Try to place CONFIG.roomCount rooms randomly on the canvas
// Each room must be at least CONFIG.minRoomDistance from others.
// Use CONFIG.maxPlacementAttempts to avoid infinite loops if placement is difficult.
// Use roomPool to get new Room objects.
}
VOID connectRooms() {
// Clear existing corridors
IF (rooms IS EMPTY) RETURN;
ARRAY<STRUCT {INT from, INT to, FLOAT weight}> mstEdges = MST.generate(THIS.rooms);
FOR EACH edge IN mstEdges {
ADD NEW Corridor(rooms[edge.from], rooms[edge.to]) TO corridors;
}
}
VOID update(FLOAT deltaTime) {
IF (animationRunning) {
movementSystem.update(deltaTime, THIS.rooms);
updateStats();
}
}
VOID updateStats() {
// Get stats from visitHistory and update display.
}
VOID render() {
renderer.render(THIS.rooms, THIS.corridors, THIS.movementSystem, THIS.visitHistory);
}
VOID gameLoop(FLOAT currentTime) {
FLOAT deltaTime = currentTime - lastTime;
lastTime = currentTime;
update(deltaTime);
render();
// Request next animation frame (similar to a continuous loop)
REQUEST_ANIMATION_FRAME(gameLoop);
}
VOID startGameLoop() {
lastTime = GET_CURRENT_TIME_MS();
gameLoop(lastTime);
}
VOID resetDungeon() {
generateRooms();
connectRooms();
visitHistory.clear();
movementSystem.initialize(THIS.rooms, THIS.corridors);
}
VOID clearCanvas() {
THIS.rooms = EMPTY ARRAY;
THIS.corridors = EMPTY ARRAY;
visitHistory.clear();
movementSystem.initialize(THIS.rooms, THIS.corridors); // Re-initialise with empty rooms to stop movement
renderer.clear();
updateStats(); // Update stats display to reflect cleared state
}
VOID toggleAnimation() {
animationRunning = !animationRunning;
}
VOID clearHistory() {
visitHistory.clear();
updateStats();
}
}
// Global game instance
Game game;
// On window load (or similar event)
VOID main() {
game = NEW Game();
game.initialize();
}Rgds!
/Set
Originally posted by @Feyerabend in #3 (comment)
Metadata
Metadata
Assignees
Labels
No labels