A
Mir ist noch ein technisches Detail aufgefallen:
// North neighbour
if (m_CellStack.top().Y > 0 && (cellOffset(0, -1) & CELL_VISITED) == 0)
neighbours.push_back(0);
// East neighbour
if (m_CellStack.top().X < m_MazeArray.width() - 1 && (cellOffset(1, 0) & CELL_VISITED) == 0)
neighbours.push_back(1);
// South neighbour
if (m_CellStack.top().Y < m_MazeArray.height() - 1 && (cellOffset(0, 1) & CELL_VISITED) == 0)
neighbours.push_back(2);
// West neighbour
if (m_CellStack.top().X > 0 && (cellOffset(-1, 0) & CELL_VISITED) == 0)
neighbours.push_back(3);
// Draw Cell
if (m_MazeArray(x, y) & CELL_VISITED)
e.draw().fillRectangle(cellPos, ivec2(m_PathWidth, m_PathWidth), m_Color.Visited);
else
e.draw().fillRectangle(cellPos, ivec2(m_PathWidth, m_PathWidth), m_Color.Free);
// Draw passageways between cells
if (m_MazeArray(x, y) & CELL_PATH_S) // South
e.draw().fillRectangle(
ivec2(cellPos.x, cellPos.y + m_PathWidth),
ivec2(m_PathWidth, m_CellStride - m_PathWidth),
m_Color.Visited);
if (m_MazeArray(x, y) & CELL_PATH_E) // East
Du willst/solltest hier, an den 7 Vorkommen, nicht & sondern den kurzschließenden Op && verwenden... minimaler Geschwindkeitszuwachs.
Ich habe aus deiner C++Anwendung mal HTML/JS gemacht, weil ich hier keinen C-Compiler habe, und das mal ausprobieren wollte... leider sehr langsam. Die Algorithmen habe ich dabei nicht geändert:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Maze and Circles Simulation</title>
<style>
:root {
color-scheme: dark;
font-family: system-ui, sans-serif;
background: #16202a;
color: #e8f0f5;
}
body {
margin: 0;
padding: 1rem;
min-height: 100vh;
box-sizing: border-box;
}
main {
max-width: 1160px;
margin: 0 auto;
}
h1 {
margin: 0 0 .35rem;
font-size: 1.35rem;
}
p {
margin: 0 0 .8rem;
color: #b9cbd5;
}
.canvas-wrap {
overflow: auto;
border: 1px solid #334b5a;
background: #9dd8ee;
box-shadow: 0 8px 24px #0005;
}
canvas {
display: block;
width: 900px;
height: 760px;
max-width: 100%;
margin: 0 auto;
cursor: crosshair;
touch-action: none;
}
.controls {
display: flex;
flex-wrap: wrap;
gap: .55rem 1.25rem;
margin-top: .8rem;
padding: .7rem .85rem;
border: 1px solid #334b5a;
background: #1d2b36;
color: #c8d8df;
font-size: .92rem;
}
button {
border: 1px solid #668394;
border-radius: .25rem;
padding: .2rem .7rem;
background: #29414f;
color: inherit;
cursor: pointer;
}
button:hover {
background: #355769;
}
</style>
</head>
<body>
<main>
<h1>Maze and circles</h1>
<p>Wait for the maze to finish, then hold the left mouse button (or touch) to drop circles.</p>
<div class="canvas-wrap">
<canvas id="simulation" width="900" height="760" aria-label="Maze and circles physics simulation"></canvas>
</div>
<div class="controls">
<span><strong>Left/right:</strong> generation delay</span>
<span><strong>Enter:</strong> reset</span>
<button id="reset" type="button">Reset</button>
</div>
</main>
<script>
(() => {
"use strict";
const canvas = document.getElementById("simulation");
const ctx = canvas.getContext("2d");
const resetButton = document.getElementById("reset");
const WIDTH = canvas.width;
const HEIGHT = canvas.height;
const EPSILON = 0.0001;
const GRAVITY = {x: 0, y: 9.81 * 2};
const ITERATIONS = 2;
const SUBSTEPS = 6;
const MAX_STEP_DISPLACEMENT = 3;
const MAX_CORRECTION = 2;
const WALL_RESTITUTION = 0.25;
const CIRCLE_RESTITUTION = 0.20;
const CIRCLE_MASS = 10;
const CIRCLE_DAMPING = 0.5;
const CIRCLE_RADIUS = 4;
const WALL_RADIUS = 1;
const CELL_PATH_N = 0x01;
const CELL_PATH_E = 0x02;
const CELL_PATH_S = 0x04;
const CELL_PATH_W = 0x08;
const CELL_VISITED = 0x10;
const maze = {
width: 12,
height: 16,
pathWidth: 35,
pathGap: 2,
position: {x: 170, y: 100},
cells: [],
stack: [],
visited: 0,
generating: false,
generationDelay: 0,
delayTimer: 0,
get stride() {
return this.pathWidth + this.pathGap;
},
get totalWidth() {
return this.width * this.stride;
},
get totalHeight() {
return this.height * this.stride;
},
reset() {
this.cells = new Array(this.width * this.height).fill(0);
this.stack = [];
this.visited = 0;
this.delayTimer = 0;
const x = Math.floor(Math.random() * this.width);
const y = Math.floor(Math.random() * this.height);
this.stack.push({x, y});
this.cell(x, y).value |= CELL_VISITED;
this.visited = 1;
this.generating = true;
},
index(x, y) {
return y * this.width + x;
},
cell(x, y) {
const index = this.index(x, y);
return {
get value() {
return maze.cells[index];
},
set value(value) {
maze.cells[index] = value;
}
};
},
generate(dt) {
if (!this.generating) {
return false;
}
this.delayTimer += dt;
if (this.generationDelay > 0 && this.delayTimer < this.generationDelay) {
return false;
}
this.delayTimer = 0;
if (this.visited >= this.cells.length) {
this.generating = false;
return true;
}
const current = this.stack[this.stack.length - 1];
const neighbours = [];
if (current.y > 0 && !(this.cell(current.x, current.y - 1).value && CELL_VISITED)) {
neighbours.push(0);
}
if (current.x < this.width - 1 && !(this.cell(current.x + 1, current.y).value && CELL_VISITED)) {
neighbours.push(1);
}
if (current.y < this.height - 1 && !(this.cell(current.x, current.y + 1).value && CELL_VISITED)) {
neighbours.push(2);
}
if (current.x > 0 && !(this.cell(current.x - 1, current.y).value && CELL_VISITED)) {
neighbours.push(3);
}
if (neighbours.length === 0) {
this.stack.pop();
} else {
const direction = neighbours[Math.floor(Math.random() * neighbours.length)];
let next;
if (direction === 0) {
this.cell(current.x, current.y - 1).value |= CELL_VISITED | CELL_PATH_S;
this.cell(current.x, current.y).value |= CELL_PATH_N;
next = {x: current.x, y: current.y - 1};
} else if (direction === 1) {
this.cell(current.x + 1, current.y).value |= CELL_VISITED | CELL_PATH_W;
this.cell(current.x, current.y).value |= CELL_PATH_E;
next = {x: current.x + 1, y: current.y};
} else if (direction === 2) {
this.cell(current.x, current.y + 1).value |= CELL_VISITED | CELL_PATH_N;
this.cell(current.x, current.y).value |= CELL_PATH_S;
next = {x: current.x, y: current.y + 1};
} else {
this.cell(current.x - 1, current.y).value |= CELL_VISITED | CELL_PATH_E;
this.cell(current.x, current.y).value |= CELL_PATH_W;
next = {x: current.x - 1, y: current.y};
}
this.stack.push(next);
this.visited++;
}
return false;
}
};
const physics = {
circles: [],
walls: [],
reset() {
this.circles = [];
this.walls = [];
},
createCircle(pos, radius) {
if (!(radius > 0)) {
return;
}
this.circles.push({
pos: {x: pos.x, y: pos.y},
vel: {x: 0, y: 0},
radius,
fill: "#f28c28",
frame: "#101820"
});
},
createWall(start, end, radius, color) {
if (radius <= 0 || Math.hypot(end.x - start.x, end.y - start.y) ** 2 < EPSILON) {
return;
}
this.walls.push({
start: {x: start.x, y: start.y},
end: {x: end.x, y: end.y},
radius,
color
});
},
update(frameDt) {
const dt = Math.min(frameDt, 1 / 30);
for (let step = 0; step < SUBSTEPS; step++) {
this.integrate(dt);
this.solveCollisions(dt);
}
this.circles = this.circles.filter((circle) => {
return circle.pos.x - circle.radius >= 0 &&
circle.pos.x + circle.radius <= WIDTH &&
circle.pos.y - circle.radius >= 0 &&
circle.pos.y + circle.radius <= HEIGHT;
});
},
integrate(dt) {
const frameDamping = Math.pow(CIRCLE_DAMPING, dt);
const maxSpeed = MAX_STEP_DISPLACEMENT / dt;
for (const circle of this.circles) {
circle.vel.x += GRAVITY.x * dt;
circle.vel.y += GRAVITY.y * dt;
circle.vel.x *= frameDamping;
circle.vel.y *= frameDamping;
const speed = Math.hypot(circle.vel.x, circle.vel.y);
if (speed > maxSpeed) {
circle.vel.x *= maxSpeed / speed;
circle.vel.y *= maxSpeed / speed;
}
circle.pos.x += circle.vel.x * dt;
circle.pos.y += circle.vel.y * dt;
}
},
solveCollisions(dt) {
const slop = 0.01;
const inverseMass = 1 / CIRCLE_MASS;
const inverseMassSum = inverseMass + inverseMass;
const restThreshold = 2 * Math.hypot(GRAVITY.x, GRAVITY.y) * dt;
for (let iteration = 0; iteration < ITERATIONS; iteration++) {
for (let i = 0; i < this.circles.length; i++) {
for (let j = i + 1; j < this.circles.length; j++) {
const a = this.circles[i];
const b = this.circles[j];
const delta = {x: b.pos.x - a.pos.x, y: b.pos.y - a.pos.y};
const radiusSum = a.radius + b.radius;
const distanceSquared = delta.x * delta.x + delta.y * delta.y;
if (distanceSquared >= radiusSum * radiusSum) {
continue;
}
let distance = Math.sqrt(distanceSquared);
let normal;
if (distance < EPSILON) {
const theta = ((i * 31 + j * 17) % 360) * Math.PI * 2 / 360;
normal = {x: Math.cos(theta), y: Math.sin(theta)};
distance = 0;
} else {
normal = {x: delta.x / distance, y: delta.y / distance};
}
const penetration = radiusSum - distance;
const correction = Math.min(Math.max(penetration - slop, 0), MAX_CORRECTION) /
inverseMassSum;
a.pos.x -= normal.x * correction * inverseMass;
a.pos.y -= normal.y * correction * inverseMass;
b.pos.x += normal.x * correction * inverseMass;
b.pos.y += normal.y * correction * inverseMass;
}
}
for (const circle of this.circles) {
for (const wall of this.walls) {
const wallVector = {
x: wall.end.x - wall.start.x,
y: wall.end.y - wall.start.y
};
const wallLengthSquared = wallVector.x * wallVector.x + wallVector.y * wallVector.y;
if (wallLengthSquared < EPSILON) {
continue;
}
const toCircle = {
x: circle.pos.x - wall.start.x,
y: circle.pos.y - wall.start.y
};
const t = Math.max(0, Math.min(1,
(wallVector.x * toCircle.x + wallVector.y * toCircle.y) / wallLengthSquared));
const closest = {
x: wall.start.x + wallVector.x * t,
y: wall.start.y + wallVector.y * t
};
const delta = {x: circle.pos.x - closest.x, y: circle.pos.y - closest.y};
const distanceSquared = delta.x * delta.x + delta.y * delta.y;
const collisionRadius = circle.radius + wall.radius;
if (distanceSquared >= collisionRadius * collisionRadius) {
continue;
}
const distance = Math.sqrt(distanceSquared);
const normal = contactNormal(delta, distance, wallVector);
if (!normal) {
continue;
}
circle.pos.x += normal.x * Math.max(collisionRadius - distance - slop, 0);
circle.pos.y += normal.y * Math.max(collisionRadius - distance - slop, 0);
}
}
}
for (let iteration = 0; iteration < ITERATIONS; iteration++) {
for (let i = 0; i < this.circles.length; i++) {
for (let j = i + 1; j < this.circles.length; j++) {
const a = this.circles[i];
const b = this.circles[j];
const delta = {x: b.pos.x - a.pos.x, y: b.pos.y - a.pos.y};
const distanceSquared = delta.x * delta.x + delta.y * delta.y;
const radiusSum = a.radius + b.radius;
if (distanceSquared > radiusSum * radiusSum) {
continue;
}
const distance = Math.sqrt(distanceSquared);
if (distance < EPSILON) {
continue;
}
const normal = {x: delta.x / distance, y: delta.y / distance};
const relativeVelocity = {
x: b.vel.x - a.vel.x,
y: b.vel.y - a.vel.y
};
const velocityAlongNormal = relativeVelocity.x * normal.x +
relativeVelocity.y * normal.y;
if (velocityAlongNormal >= 0) {
continue;
}
const restitution = -velocityAlongNormal < restThreshold ? 0 : CIRCLE_RESTITUTION;
const impulseMagnitude = -(1 + restitution) * velocityAlongNormal / inverseMassSum;
const impulse = {
x: normal.x * impulseMagnitude,
y: normal.y * impulseMagnitude
};
a.vel.x -= impulse.x * inverseMass;
a.vel.y -= impulse.y * inverseMass;
b.vel.x += impulse.x * inverseMass;
b.vel.y += impulse.y * inverseMass;
}
}
for (const circle of this.circles) {
for (const wall of this.walls) {
const wallVector = {
x: wall.end.x - wall.start.x,
y: wall.end.y - wall.start.y
};
const wallLengthSquared = wallVector.x * wallVector.x + wallVector.y * wallVector.y;
if (wallLengthSquared < EPSILON) {
continue;
}
const toCircle = {
x: circle.pos.x - wall.start.x,
y: circle.pos.y - wall.start.y
};
const t = Math.max(0, Math.min(1,
(wallVector.x * toCircle.x + wallVector.y * toCircle.y) / wallLengthSquared));
const closest = {
x: wall.start.x + wallVector.x * t,
y: wall.start.y + wallVector.y * t
};
const delta = {x: circle.pos.x - closest.x, y: circle.pos.y - closest.y};
const collisionRadius = circle.radius + wall.radius;
const distance = Math.hypot(delta.x, delta.y);
if (distance * distance > collisionRadius * collisionRadius) {
continue;
}
const normal = contactNormal(delta, distance, wallVector);
if (!normal) {
continue;
}
const velocityAlongNormal = circle.vel.x * normal.x + circle.vel.y * normal.y;
if (velocityAlongNormal >= 0) {
continue;
}
const restitution = -velocityAlongNormal < restThreshold ? 0 : WALL_RESTITUTION;
circle.vel.x -= normal.x * ((1 + restitution) * velocityAlongNormal);
circle.vel.y -= normal.y * ((1 + restitution) * velocityAlongNormal);
}
}
}
}
};
function contactNormal(delta, distance, wallVector) {
if (distance > EPSILON) {
return {x: delta.x / distance, y: delta.y / distance};
}
const perpendicular = {x: -wallVector.y, y: wallVector.x};
const length = Math.hypot(perpendicular.x, perpendicular.y);
if (length < EPSILON) {
return null;
}
return {x: perpendicular.x / length, y: perpendicular.y / length};
}
function addWall(x0, y0, x1, y1) {
physics.createWall({x: x0, y: y0}, {x: x1, y: y1}, WALL_RADIUS, "rgba(0, 0, 0, .78)");
}
function createOuterWalls() {
const outerGap = 50;
addWall(maze.position.x - 1, maze.position.y - outerGap,
maze.position.x - 1, maze.position.y);
addWall(maze.position.x - 1 + maze.totalWidth, maze.position.y - outerGap,
maze.position.x - 1 + maze.totalWidth, maze.totalHeight + outerGap + 11);
}
function exportMazeWalls() {
for (let y = 0; y < maze.height - 1; y++) {
for (let x = 0; x < maze.width; x++) {
const x0 = x * maze.stride + maze.position.x - maze.pathGap / 2;
const y0 = y * maze.stride + maze.position.y - maze.pathGap / 2;
const x1 = x0 + maze.stride;
const y1 = y0 + maze.stride;
const value = maze.cell(x, y).value;
if (value === 0) {
addWall(x0, y1, x1, y1);
addWall(x0, y0, x0, y1);
addWall(x1, y0, x1, y1);
} else if (value === 1) {
addWall(x1, y0, x1, y1);
} else if (value === 2) {
addWall(x0, y0, x0, y1);
addWall(x1, y0, x1, y1);
} else if (value >= 17 && value <= 19) {
addWall(x0, y1, x1, y1);
addWall(x0, y0, x0, y1);
} else if (value >= 20 && value <= 23) {
addWall(x0, y0, x0, y1);
} else if (value >= 24 && value <= 27) {
addWall(x0, y1, x1, y1);
}
}
}
}
function drawMaze() {
const xStart = maze.position.x;
const yStart = maze.position.y;
ctx.fillStyle = "#071016";
ctx.fillRect(xStart, yStart, maze.totalWidth, (maze.height - 1) * maze.stride - maze.pathGap);
for (let y = 0; y < maze.height - 1; y++) {
for (let x = 0; x < maze.width; x++) {
const cell = maze.cell(x, y);
const cellX = xStart + x * maze.stride;
const cellY = yStart + y * maze.stride;
ctx.fillStyle = cell.value && CELL_VISITED ? "rgba(160, 220, 240, .62)" : "rgba(0, 0, 0, .78)";
ctx.fillRect(cellX, cellY, maze.pathWidth, maze.pathWidth);
if (cell.value && CELL_PATH_S) {
ctx.fillRect(cellX, cellY + maze.pathWidth, maze.pathWidth, maze.pathGap);
}
if (cell.value && CELL_PATH_E) {
ctx.fillRect(cellX + maze.pathWidth, cellY, maze.pathGap, maze.pathWidth);
}
}
}
if (maze.generating && maze.stack.length > 0 &&
maze.stack[maze.stack.length - 1].y < maze.height - 1) {
const current = maze.stack[maze.stack.length - 1];
ctx.fillStyle = "#ffffff";
ctx.fillRect(xStart + current.x * maze.stride, yStart + current.y * maze.stride,
maze.pathWidth, maze.pathWidth);
}
}
function drawWalls() {
ctx.save();
ctx.lineWidth = WALL_RADIUS * 2;
ctx.lineCap = "round";
ctx.strokeStyle = "rgba(0, 0, 0, .78)";
for (const wall of physics.walls) {
ctx.beginPath();
ctx.moveTo(wall.start.x, wall.start.y);
ctx.lineTo(wall.end.x, wall.end.y);
ctx.stroke();
}
ctx.restore();
}
function drawCircles() {
for (const circle of physics.circles) {
ctx.beginPath();
ctx.arc(circle.pos.x, circle.pos.y, circle.radius, 0, Math.PI * 2);
ctx.fillStyle = circle.fill;
ctx.fill();
ctx.strokeStyle = circle.frame;
ctx.lineWidth = 1;
ctx.stroke();
const speed = Math.hypot(circle.vel.x, circle.vel.y);
if (circle.radius > 2) {
ctx.beginPath();
if (speed > EPSILON) {
ctx.moveTo(circle.pos.x, circle.pos.y);
ctx.lineTo(circle.pos.x + circle.vel.x / speed * circle.radius,
circle.pos.y + circle.vel.y / speed * circle.radius);
} else {
ctx.arc(circle.pos.x, circle.pos.y, .5, 0, Math.PI * 2);
}
ctx.strokeStyle = circle.frame;
ctx.stroke();
}
}
}
function drawInfo() {
const x = maze.position.x + maze.totalWidth + 40;
let y = maze.position.y + 30;
ctx.fillStyle = "rgba(110, 0, 0, .86)";
ctx.font = "18px system-ui, sans-serif";
ctx.textBaseline = "top";
ctx.fillText("Maze size:", x, y);
ctx.fillText(`${maze.width}, ${maze.height}`, x + 190, y);
y += 22;
ctx.fillText("Maze cells:", x, y);
ctx.fillText(String(maze.cells.length), x + 190, y);
y += 22;
if (maze.generating) {
ctx.fillText("Generation delay:", x, y);
ctx.fillText(`${maze.generationDelay.toFixed(2)} s`, x + 190, y);
}
y += 52;
ctx.font = "24px system-ui, sans-serif";
ctx.fillStyle = "rgba(110, 0, 0, .9)";
ctx.fillText(maze.generating ? "Generating maze" : "Drop circles with mouse", x, y);
y += 52;
ctx.font = "18px system-ui, sans-serif";
ctx.fillText("Circle count:", x, y);
ctx.fillText(String(physics.circles.length), x + 200, y);
}
let mazePhysicsReady = false;
let pointerActive = false;
let pointerPosition = {x: 0, y: 0};
let spawnTimer = 0;
const keys = new Set();
function reset() {
physics.reset();
createOuterWalls();
maze.reset();
mazePhysicsReady = false;
spawnTimer = 0;
}
function pointerToCanvas(event) {
const rect = canvas.getBoundingClientRect();
return {
x: (event.clientX - rect.left) * WIDTH / rect.width,
y: (event.clientY - rect.top) * HEIGHT / rect.height
};
}
function dropCircles() {
for (let i = 0; i < 3; i++) {
physics.createCircle(pointerPosition, CIRCLE_RADIUS);
}
}
canvas.addEventListener("pointerdown", (event) => {
pointerActive = true;
pointerPosition = pointerToCanvas(event);
canvas.setPointerCapture(event.pointerId);
if (!maze.generating) {
dropCircles();
}
});
canvas.addEventListener("pointermove", (event) => {
pointerPosition = pointerToCanvas(event);
});
canvas.addEventListener("pointerup", () => {
pointerActive = false;
});
canvas.addEventListener("pointercancel", () => {
pointerActive = false;
});
window.addEventListener("blur", () => {
pointerActive = false;
keys.clear();
});
window.addEventListener("keydown", (event) => {
if (event.key === "Enter") {
reset();
}
if (event.key === "ArrowLeft" || event.key === "ArrowRight") {
event.preventDefault();
keys.add(event.key);
}
});
window.addEventListener("keyup", (event) => {
keys.delete(event.key);
});
resetButton.addEventListener("click", reset);
function frame(timestamp) {
if (!frame.lastTimestamp) {
frame.lastTimestamp = timestamp;
}
const dt = Math.min((timestamp - frame.lastTimestamp) / 1000, 0.1);
frame.lastTimestamp = timestamp;
if (keys.has("ArrowLeft")) {
maze.generationDelay -= dt;
}
if (keys.has("ArrowRight")) {
maze.generationDelay += dt;
}
maze.generationDelay = Math.max(0, maze.generationDelay);
const becameReady = maze.generate(dt);
if (becameReady || (!maze.generating && !mazePhysicsReady)) {
exportMazeWalls();
mazePhysicsReady = true;
}
if (!maze.generating && pointerActive) {
spawnTimer += dt;
if (spawnTimer >= 0.05) {
spawnTimer = 0;
dropCircles();
}
} else {
spawnTimer = 0;
}
physics.update(dt);
ctx.clearRect(0, 0, WIDTH, HEIGHT);
drawMaze();
if (!maze.generating) {
drawWalls();
}
drawCircles();
drawInfo();
requestAnimationFrame(frame);
}
reset();
requestAnimationFrame(frame);
})();
</script>
</body>
</html>
Dabei ist mir noch aufgefallen, dass sich Kreise nicht nur überschneiden, sondern sogar durch Wände rutschen können... fast schon gespenstisch.