游戏开发：碰撞检测 - 从入门到实践详解

class AABB {
    constructor(x, y, width, height) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }

    // 检测两个AABB是否重叠
    static intersects(a, b) {
        return a.x < b.x + b.width &&
               a.x + a.width > b.x &&
               a.y < b.y + b.height &&
               a.y + a.height > b.y;
    }

    // 获取重叠区域
    static overlap(a, b) {
        const x = Math.max(a.x, b.x);
        const y = Math.max(a.y, b.y);
        const width = Math.min(a.x + a.width, b.x + b.width) - x;
        const height = Math.min(a.y + a.height, b.y + b.height) - y;
        if (width > 0 && height > 0) {
            return { x, y, width, height };
        }
        return null;
    }

    // 检测点是否在AABB内
    containsPoint(px, py) {
        return px >= this.x && px <= this.x + this.width &&
               py >= this.y && py <= this.y + this.height;
    }
}

class Circle {
    constructor(x, y, radius) {
        this.x = x;
        this.y = y;
        this.radius = radius;
    }

    // 检测两个圆是否重叠
    static intersects(a, b) {
        const dx = a.x - b.x;
        const dy = a.y - b.y;
        const distSq = dx * dx + dy * dy;
        const radiusSum = a.radius + b.radius;
        return distSq < radiusSum * radiusSum;
    }

    // 获取圆心距离
    static distance(a, b) {
        const dx = a.x - b.x;
        const dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    // 检测点是否在圆内
    containsPoint(px, py) {
        const dx = px - this.x;
        const dy = py - this.y;
        return dx * dx + dy * dy < this.radius * this.radius;
    }
}

function circleRectCollision(circle, rect) {
    // 找到矩形上离圆心最近的点
    const closestX = Math.max(rect.x, Math.min(circle.x, rect.x + rect.width));
    const closestY = Math.max(rect.y, Math.min(circle.y, rect.y + rect.height));

    const dx = circle.x - closestX;
    const dy = circle.y - closestY;

    return (dx * dx + dy * dy) < (circle.radius * circle.radius);
}

class PixelCollision {
    /**
     * 检测两个精灵的像素级碰撞
     * @param {ImageData} imgA - 精灵A的像素数据
     * @param {number} ax - A的X坐标
     * @param {number} ay - A的Y坐标
     * @param {ImageData} imgB - 精灵B的像素数据
     * @param {number} bx - B的X坐标
     * @param {number} by - B的Y坐标
     */
    static check(imgA, ax, ay, imgB, bx, by) {
        // 先做AABB检测，快速排除
        if (ax >= bx + imgB.width || bx >= ax + imgA.width ||
            ay >= by + imgB.height || by >= ay + imgA.height) {
            return false;
        }

        // 计算重叠区域
        const overlapX = Math.max(ax, bx);
        const overlapY = Math.max(ay, by);
        const overlapW = Math.min(ax + imgA.width, bx + imgB.width) - overlapX;
        const overlapH = Math.min(ay + imgA.height, by + imgB.height) - overlapY;

        // 逐像素检测
        for (let y = 0; y < overlapH; y++) {
            for (let x = 0; x < overlapW; x++) {
                const pixelAX = (overlapX - ax) + x;
                const pixelAY = (overlapY - ay) + y;
                const pixelBX = (overlapX - bx) + x;
                const pixelBY = (overlapY - by) + y;

                const alphaA = imgA.data[((pixelAY * imgA.width) + pixelAX) * 4 + 3];
                const alphaB = imgB.data[((pixelBY * imgB.width) + pixelBX) * 4 + 3];

                if (alphaA > 0 && alphaB > 0) return true;
            }
        }
        return false;
    }
}

class SpatialGrid {
    constructor(cellSize, width, height) {
        this.cellSize = cellSize;
        this.cols = Math.ceil(width / cellSize);
        this.rows = Math.ceil(height / cellSize);
        this.grid = new Array(this.cols * this.rows);
        this.clear();
    }

    clear() {
        for (let i = 0; i < this.grid.length; i++) {
            this.grid[i] = [];
        }
    }

    getCell(x, y) {
        const col = Math.floor(x / this.cellSize);
        const row = Math.floor(y / this.cellSize);
        if (col < 0 || col >= this.cols || row < 0 || row >= this.rows) return -1;
        return row * this.cols + col;
    }

    insert(obj) {
        const minCol = Math.floor(obj.x / this.cellSize);
        const maxCol = Math.floor((obj.x + obj.width) / this.cellSize);
        const minRow = Math.floor(obj.y / this.cellSize);
        const maxRow = Math.floor((obj.y + obj.height) / this.cellSize);

        for (let row = minRow; row <= maxRow; row++) {
            for (let col = minCol; col <= maxCol; col++) {
                const idx = row * this.cols + col;
                if (idx >= 0 && idx < this.grid.length) {
                    this.grid[idx].push(obj);
                }
            }
        }
    }

    query(obj) {
        const result = new Set();
        const minCol = Math.floor(obj.x / this.cellSize);
        const maxCol = Math.floor((obj.x + obj.width) / this.cellSize);
        const minRow = Math.floor(obj.y / this.cellSize);
        const maxRow = Math.floor((obj.y + obj.height) / this.cellSize);

        for (let row = minRow; row <= maxRow; row++) {
            for (let col = minCol; col <= maxCol; col++) {
                const idx = row * this.cols + col;
                if (idx >= 0 && idx < this.grid.length) {
                    for (const other of this.grid[idx]) {
                        if (other !== obj) result.add(other);
                    }
                }
            }
        }
        return result;
    }
}

class QuadTree {
    constructor(bounds, maxObjects = 10, maxLevels = 5, level = 0) {
        this.bounds = bounds;
        this.maxObjects = maxObjects;
        this.maxLevels = maxLevels;
        this.level = level;
        this.objects = [];
        this.nodes = [];
    }

    clear() {
        this.objects = [];
        for (const node of this.nodes) {
            node.clear();
        }
        this.nodes = [];
    }

    split() {
        const { x, y, width, height } = this.bounds;
        const hw = width / 2;
        const hh = height / 2;
        const nextLevel = this.level + 1;

        this.nodes = [
            new QuadTree({ x: x + hw, y: y, width: hw, height: hh }, this.maxObjects, this.maxLevels, nextLevel),
            new QuadTree({ x: x, y: y, width: hw, height: hh }, this.maxObjects, this.maxLevels, nextLevel),
            new QuadTree({ x: x, y: y + hh, width: hw, height: hh }, this.maxObjects, this.maxLevels, nextLevel),
            new QuadTree({ x: x + hw, y: y + hh, width: hw, height: hh }, this.maxObjects, this.maxLevels, nextLevel)
        ];
    }

    getIndex(obj) {
        const indices = [];
        const { x, y, width, height } = this.bounds;
        const midX = x + width / 2;
        const midY = y + height / 2;

        const top = obj.y < midY;
        const bottom = obj.y + obj.height > midY;
        const left = obj.x < midX;
        const right = obj.x + obj.width > midX;

        if (top && right) indices.push(0);
        if (top && left) indices.push(1);
        if (bottom && left) indices.push(2);
        if (bottom && right) indices.push(3);

        return indices;
    }

    insert(obj) {
        if (this.nodes.length > 0) {
            const indices = this.getIndex(obj);
            for (const idx of indices) {
                this.nodes[idx].insert(obj);
            }
            return;
        }

        this.objects.push(obj);

        if (this.objects.length > this.maxObjects && this.level < this.maxLevels) {
            if (this.nodes.length === 0) {
                this.split();
            }
            while (this.objects.length > 0) {
                const o = this.objects.pop();
                const indices = this.getIndex(o);
                for (const idx of indices) {
                    this.nodes[idx].insert(o);
                }
            }
        }
    }

    retrieve(obj) {
        const result = [...this.objects];
        if (this.nodes.length > 0) {
            const indices = this.getIndex(obj);
            for (const idx of indices) {
                result.push(...this.nodes[idx].retrieve(obj));
            }
        }
        return result;
    }
}

class CollisionResponse {
    // AABB碰撞分离
    static resolveAABB(a, b) {
        const overlapX = Math.min(a.x + a.width - b.x, b.x + b.width - a.x);
        const overlapY = Math.min(a.y + a.height - b.y, b.y + b.height - a.y);

        if (overlapX < overlapY) {
            if (a.x < b.x) { a.x -= overlapX / 2; b.x += overlapX / 2; }
            else { a.x += overlapX / 2; b.x -= overlapX / 2; }
        } else {
            if (a.y < b.y) { a.y -= overlapY / 2; b.y += overlapY / 2; }
            else { a.y += overlapY / 2; b.y -= overlapY / 2; }
        }
    }

    // 弹性碰撞（圆形）
    static elasticCollision(a, b, restitution = 1) {
        const dx = b.x - a.x;
        const dy = b.y - a.y;
        const dist = Math.sqrt(dx * dx + dy * dy);

        if (dist === 0) return;

        const nx = dx / dist;
        const ny = dy / dist;

        const dvx = a.vx - b.vx;
        const dvy = a.vy - b.vy;
        const dvn = dvx * nx + dvy * ny;

        if (dvn > 0) return; // 正在远离

        const j = -(1 + restitution) * dvn / 2;
        a.vx += j * nx;
        a.vy += j * ny;
        b.vx -= j * nx;
        b.vy -= j * ny;

        // 分离
        const overlap = (a.radius + b.radius) - dist;
        if (overlap > 0) {
            a.x -= nx * overlap / 2;
            a.y -= ny * overlap / 2;
            b.x += nx * overlap / 2;
            b.y += ny * overlap / 2;
        }
    }
}

<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>碰撞检测综合演示</title>
    <style>
        * { margin: 0; padding: 0; box-sizing: border-box; }
        body { background: #0a0a1a; display: flex; flex-direction: column; align-items: center; justify-content: center; min-height: 100vh; font-family: 'Segoe UI', sans-serif; color: #fff; }
        canvas { border: 2px solid #2a2a4a; border-radius: 8px; }
        .controls { margin-top: 12px; display: flex; gap: 10px; flex-wrap: wrap; justify-content: center; }
        button { padding: 6px 16px; border: 1px solid #4a90d9; background: transparent; color: #4a90d9; border-radius: 6px; cursor: pointer; font-size: 13px; transition: all 0.2s; }
        button:hover { background: #4a90d922; }
        button.active { background: #4a90d9; color: #fff; }
    </style>
</head>
<body>
    <canvas id="gameCanvas" width="800" height="600"></canvas>
    <div class="controls">
        <button id="btnAABB" class="active">AABB碰撞</button>
        <button id="btnCircle">圆形碰撞</button>
        <button id="btnMixed">混合碰撞</button>
        <button id="btnSpatial">空间分区</button>
    </div>
    <script>
        class CollisionDemo {
            constructor() {
                this.canvas = document.getElementById('gameCanvas');
                this.ctx = this.canvas.getContext('2d');
                this.width = 800;
                this.height = 600;
                this.mode = 'aabb';
                this.objects = [];
                this.collisionPairs = [];
                this.quadTree = null;
                this.lastTime = 0;
                this.mouseX = 400;
                this.mouseY = 300;
                this.dragging = null;

                this.setupInput();
                this.setupButtons();
                this.generateObjects();
            }

            setupInput() {
                this.canvas.addEventListener('mousemove', (e) => {
                    const rect = this.canvas.getBoundingClientRect();
                    this.mouseX = (e.clientX - rect.left) * (this.width / rect.width);
                    this.mouseY = (e.clientY - rect.top) * (this.height / rect.height);
                    if (this.dragging) {
                        this.dragging.x = this.mouseX - this.dragging.offsetX;
                        this.dragging.y = this.mouseY - this.dragging.offsetY;
                    }
                });
                this.canvas.addEventListener('mousedown', (e) => {
                    for (const obj of this.objects) {
                        const dx = this.mouseX - obj.x - obj.width / 2;
                        const dy = this.mouseY - obj.y - obj.height / 2;
                        if (Math.abs(dx) < obj.width / 2 && Math.abs(dy) < obj.height / 2) {
                            this.dragging = obj;
                            this.dragging.offsetX = this.mouseX - obj.x;
                            this.dragging.offsetY = this.mouseY - obj.y;
                            break;
                        }
                    }
                });
                this.canvas.addEventListener('mouseup', () => { this.dragging = null; });
            }

            setupButtons() {
                const modes = { btnAABB: 'aabb', btnCircle: 'circle', btnMixed: 'mixed', btnSpatial: 'spatial' };
                for (const [id, mode] of Object.entries(modes)) {
                    document.getElementById(id).addEventListener('click', () => {
                        this.mode = mode;
                        document.querySelectorAll('button').forEach(b => b.classList.remove('active'));
                        document.getElementById(id).classList.add('active');
                        this.generateObjects();
                    });
                }
            }

            generateObjects() {
                this.objects = [];
                const count = this.mode === 'spatial' ? 80 : 20;
                for (let i = 0; i < count; i++) {
                    const size = 15 + Math.random() * 30;
                    const isCircle = this.mode === 'circle' || (this.mode === 'mixed' && Math.random() > 0.5);
                    this.objects.push({
                        x: 50 + Math.random() * (this.width - 100),
                        y: 50 + Math.random() * (this.height - 100),
                        width: size,
                        height: size,
                        radius: size / 2,
                        vx: (Math.random() - 0.5) * 150,
                        vy: (Math.random() - 0.5) * 150,
                        isCircle: isCircle,
                        color: isCircle ? '#4a90d9' : '#e94560',
                        colliding: false,
                        mass: size * size
                    });
                }
            }

            start() {
                this.lastTime = performance.now();
                requestAnimationFrame((t) => this.loop(t));
            }

            loop(currentTime) {
                const dt = Math.min((currentTime - this.lastTime) / 1000, 0.1);
                this.lastTime = currentTime;
                this.update(dt);
                this.render();
                requestAnimationFrame((t) => this.loop(t));
            }

            update(dt) {
                // 更新位置
                for (const obj of this.objects) {
                    if (obj === this.dragging) continue;
                    obj.x += obj.vx * dt;
                    obj.y += obj.vy * dt;

                    // 边界反弹
                    if (obj.x < 0) { obj.x = 0; obj.vx = Math.abs(obj.vx); }
                    if (obj.x + obj.width > this.width) { obj.x = this.width - obj.width; obj.vx = -Math.abs(obj.vx); }
                    if (obj.y < 0) { obj.y = 0; obj.vy = Math.abs(obj.vy); }
                    if (obj.y + obj.height > this.height) { obj.y = this.height - obj.height; obj.vy = -Math.abs(obj.vy); }

                    obj.colliding = false;
                }

                // 碰撞检测
                this.collisionPairs = [];

                if (this.mode === 'spatial') {
                    this.detectWithSpatial();
                } else {
                    this.detectBruteForce();
                }
            }

            detectBruteForce() {
                for (let i = 0; i < this.objects.length; i++) {
                    for (let j = i + 1; j < this.objects.length; j++) {
                        const a = this.objects[i];
                        const b = this.objects[j];
                        if (this.checkCollision(a, b)) {
                            a.colliding = true;
                            b.colliding = true;
                            this.collisionPairs.push([a, b]);
                            this.resolveCollision(a, b);
                        }
                    }
                }
            }

            detectWithSpatial() {
                // 构建四叉树
                this.quadTree = new QuadTree({ x: 0, y: 0, width: this.width, height: this.height }, 5, 4);
                for (const obj of this.objects) {
                    this.quadTree.insert(obj);
                }

                // 使用四叉树检测
                const checked = new Set();
                for (const obj of this.objects) {
                    const nearby = this.quadTree.retrieve(obj);
                    for (const other of nearby) {
                        if (other === obj) continue;
                        const key = obj.id < other.id ? `${obj.id}-${other.id}` : `${other.id}-${obj.id}`;
                        if (checked.has(key)) continue;
                        checked.add(key);

                        if (this.checkCollision(obj, other)) {
                            obj.colliding = true;
                            other.colliding = true;
                            this.collisionPairs.push([obj, other]);
                            this.resolveCollision(obj, other);
                        }
                    }
                }
            }

            checkCollision(a, b) {
                if (a.isCircle && b.isCircle) {
                    const dx = (a.x + a.radius) - (b.x + b.radius);
                    const dy = (a.y + a.radius) - (b.y + b.radius);
                    const distSq = dx * dx + dy * dy;
                    const radiusSum = a.radius + b.radius;
                    return distSq < radiusSum * radiusSum;
                } else if (a.isCircle || b.isCircle) {
                    const circle = a.isCircle ? a : b;
                    const rect = a.isCircle ? b : a;
                    const cx = circle.x + circle.radius;
                    const cy = circle.y + circle.radius;
                    const closestX = Math.max(rect.x, Math.min(cx, rect.x + rect.width));
                    const closestY = Math.max(rect.y, Math.min(cy, rect.y + rect.height));
                    const dx = cx - closestX;
                    const dy = cy - closestY;
                    return (dx * dx + dy * dy) < (circle.radius * circle.radius);
                } else {
                    return a.x < b.x + b.width && a.x + a.width > b.x &&
                           a.y < b.y + b.height && a.y + a.height > b.y;
                }
            }

            resolveCollision(a, b) {
                if (a === this.dragging || b === this.dragging) return;

                if (a.isCircle && b.isCircle) {
                    // 弹性碰撞
                    const dx = (b.x + b.radius) - (a.x + a.radius);
                    const dy = (b.y + b.radius) - (a.y + a.radius);
                    const dist = Math.sqrt(dx * dx + dy * dy);
                    if (dist === 0) return;

                    const nx = dx / dist;
                    const ny = dy / dist;
                    const dvx = a.vx - b.vx;
                    const dvy = a.vy - b.vy;
                    const dvn = dvx * nx + dvy * ny;
                    if (dvn > 0) return;

                    const restitution = 0.8;
                    const j = -(1 + restitution) * dvn / (1 / a.mass + 1 / b.mass);
                    a.vx += j * nx / a.mass;
                    a.vy += j * ny / a.mass;
                    b.vx -= j * nx / b.mass;
                    b.vy -= j * ny / b.mass;

                    // 分离
                    const overlap = (a.radius + b.radius) - dist;
                    if (overlap > 0) {
                        a.x -= nx * overlap / 2;
                        a.y -= ny * overlap / 2;
                        b.x += nx * overlap / 2;
                        b.y += ny * overlap / 2;
                    }
                } else {
                    // AABB碰撞响应
                    const overlapX = Math.min(a.x + a.width - b.x, b.x + b.width - a.x);
                    const overlapY = Math.min(a.y + a.height - b.y, b.y + b.height - a.y);

                    if (overlapX < overlapY) {
                        if (a.x + a.width / 2 < b.x + b.width / 2) {
                            a.x -= overlapX / 2; b.x += overlapX / 2;
                        } else {
                            a.x += overlapX / 2; b.x -= overlapX / 2;
                        }
                        const tempVx = a.vx;
                        a.vx = b.vx * 0.8;
                        b.vx = tempVx * 0.8;
                    } else {
                        if (a.y + a.height / 2 < b.y + b.height / 2) {
                            a.y -= overlapY / 2; b.y += overlapY / 2;
                        } else {
                            a.y += overlapY / 2; b.y -= overlapY / 2;
                        }
                        const tempVy = a.vy;
                        a.vy = b.vy * 0.8;
                        b.vy = tempVy * 0.8;
                    }
                }
            }

            render() {
                const ctx = this.ctx;
                ctx.fillStyle = '#0a0a1a';
                ctx.fillRect(0, 0, this.width, this.height);

                // 四叉树可视化
                if (this.mode === 'spatial' && this.quadTree) {
                    this.renderQuadTree(ctx, this.quadTree);
                }

                // 碰撞线
                for (const [a, b] of this.collisionPairs) {
                    ctx.strokeStyle = '#e9456044';
                    ctx.lineWidth = 1;
                    ctx.beginPath();
                    ctx.moveTo(a.x + a.width / 2, a.y + a.height / 2);
                    ctx.lineTo(b.x + b.width / 2, b.y + b.height / 2);
                    ctx.stroke();
                }

                // 对象
                for (const obj of this.objects) {
                    if (obj.isCircle) {
                        ctx.fillStyle = obj.colliding ? '#ff6b6b' : obj.color;
                        ctx.beginPath();
                        ctx.arc(obj.x + obj.radius, obj.y + obj.radius, obj.radius, 0, Math.PI * 2);
                        ctx.fill();
                        if (obj.colliding) {
                            ctx.strokeStyle = '#e94560';
                            ctx.lineWidth = 2;
                            ctx.stroke();
                        }
                    } else {
                        ctx.fillStyle = obj.colliding ? '#ff6b6b' : obj.color;
                        ctx.fillRect(obj.x, obj.y, obj.width, obj.height);
                        if (obj.colliding) {
                            ctx.strokeStyle = '#e94560';
                            ctx.lineWidth = 2;
                            ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
                        }
                    }
                }

                // HUD
                ctx.fillStyle = '#fff';
                ctx.font = '13px monospace';
                ctx.textAlign = 'left';
                const modeNames = { aabb: 'AABB碰撞', circle: '圆形碰撞', mixed: '混合碰撞', spatial: '空间分区' };
                ctx.fillText(`模式: ${modeNames[this.mode]}`, 10, 20);
                ctx.fillText(`对象: ${this.objects.length} | 碰撞对: ${this.collisionPairs.length}`, 10, 40);
                ctx.fillText('拖拽对象移动', 10, 580);
            }

            renderQuadTree(ctx, node) {
                ctx.strokeStyle = '#1a3a5a';
                ctx.lineWidth = 0.5;
                ctx.strokeRect(node.bounds.x, node.bounds.y, node.bounds.width, node.bounds.height);
                for (const child of node.nodes) {
                    this.renderQuadTree(ctx, child);
                }
            }
        }

        // 四叉树（简化版用于演示）
        class QuadTree {
            constructor(bounds, maxObjects, maxLevels, level = 0) {
                this.bounds = bounds;
                this.maxObjects = maxObjects;
                this.maxLevels = maxLevels;
                this.level = level;
                this.objects = [];
                this.nodes = [];
            }
            clear() { this.objects = []; this.nodes.forEach(n => n.clear()); this.nodes = []; }
            split() {
                const { x, y, width, height } = this.bounds;
                const hw = width / 2, hh = height / 2, nl = this.level + 1;
                this.nodes = [
                    new QuadTree({ x: x + hw, y, width: hw, height: hh }, this.maxObjects, this.maxLevels, nl),
                    new QuadTree({ x, y, width: hw, height: hh }, this.maxObjects, this.maxLevels, nl),
                    new QuadTree({ x, y: y + hh, width: hw, height: hh }, this.maxObjects, this.maxLevels, nl),
                    new QuadTree({ x: x + hw, y: y + hh, width: hw, height: hh }, this.maxObjects, this.maxLevels, nl)
                ];
            }
            getIndex(obj) {
                const midX = this.bounds.x + this.bounds.width / 2;
                const midY = this.bounds.y + this.bounds.height / 2;
                const indices = [];
                const top = obj.y < midY, bottom = obj.y + obj.height > midY;
                const left = obj.x < midX, right = obj.x + obj.width > midX;
                if (top && right) indices.push(0);
                if (top && left) indices.push(1);
                if (bottom && left) indices.push(2);
                if (bottom && right) indices.push(3);
                return indices;
            }
            insert(obj) {
                if (this.nodes.length > 0) {
                    for (const idx of this.getIndex(obj)) this.nodes[idx].insert(obj);
                    return;
                }
                this.objects.push(obj);
                if (this.objects.length > this.maxObjects && this.level < this.maxLevels) {
                    if (this.nodes.length === 0) this.split();
                    while (this.objects.length > 0) {
                        const o = this.objects.pop();
                        for (const idx of this.getIndex(o)) this.nodes[idx].insert(o);
                    }
                }
            }
            retrieve(obj) {
                let result = [...this.objects];
                if (this.nodes.length > 0) {
                    for (const idx of this.getIndex(obj)) result = result.concat(this.nodes[idx].retrieve(obj));
                }
                return result;
            }
        }

        const game = new CollisionDemo();
        // 给对象添加ID
        game.generateObjects = function() {
            this.objects = [];
            const count = this.mode === 'spatial' ? 80 : 20;
            for (let i = 0; i < count; i++) {
                const size = 15 + Math.random() * 30;
                const isCircle = this.mode === 'circle' || (this.mode === 'mixed' && Math.random() > 0.5);
                this.objects.push({
                    id: i,
                    x: 50 + Math.random() * (this.width - 100),
                    y: 50 + Math.random() * (this.height - 100),
                    width: size, height: size, radius: size / 2,
                    vx: (Math.random() - 0.5) * 150, vy: (Math.random() - 0.5) * 150,
                    isCircle, color: isCircle ? '#4a90d9' : '#e94560',
                    colliding: false, mass: size * size
                });
            }
        };
        game.generateObjects();
        game.start();
    </script>
</body>
</html>

/**
 * 碰撞检测系统
 * 管理碰撞检测、响应和事件分发
 */
class CollisionSystem {
    /**
     * @param {Object} config - 配置
     * @param {number} [config.cellSize=100] - 空间分区网格大小
     * @param {number} [config.width=800] - 世界宽度
     * @param {number} [config.height=600] - 世界高度
     */
    constructor(config = {}) {
        this.cellSize = config.cellSize || 100;
        this.width = config.width || 800;
        this.height = config.height || 600;
        this.spatialGrid = new SpatialGrid(this.cellSize, this.width, this.height);
        this.collisionLayers = new Map();
        this.collisionCallbacks = [];
    }

    /**
     * 注册碰撞回调
     * @param {string} layerA - 层A名称
     * @param {string} layerB - 层B名称
     * @param {Function} callback - 碰撞回调 (a, b, collisionInfo) => void
     */
    onCollision(layerA, layerB, callback) {
        this.collisionCallbacks.push({ layerA, layerB, callback });
    }

    /**
     * 检测并处理所有碰撞
     * @param {Array} objects - 游戏对象数组
     * @param {number} dt - 帧间隔时间
     */
    detect(objects, dt) {
        // 重建空间分区
        this.spatialGrid.clear();
        for (const obj of objects) {
            this.spatialGrid.insert(obj);
        }

        // 检测碰撞
        const checked = new Set();
        for (const obj of objects) {
            const nearby = this.spatialGrid.query(obj);
            for (const other of nearby) {
                const key = obj.id < other.id ? `${obj.id}-${other.id}` : `${other.id}-${obj.id}`;
                if (checked.has(key)) continue;
                checked.add(key);

                const collision = this.testCollision(obj, other);
                if (collision) {
                    this.dispatchCallback(obj, other, collision);
                }
            }
        }
    }

    /**
     * 测试两个对象的碰撞
     * @private
     */
    testCollision(a, b) {
        if (a.shape === 'circle' && b.shape === 'circle') {
            return this.testCircleCircle(a, b);
        }
        return this.testAABB(a, b);
    }

    testAABB(a, b) {
        if (a.x < b.x + b.width && a.x + a.width > b.x &&
            a.y < b.y + b.height && a.y + a.height > b.y) {
            const overlapX = Math.min(a.x + a.width - b.x, b.x + b.width - a.x);
            const overlapY = Math.min(a.y + a.height - b.y, b.y + b.height - a.y);
            return { overlapX, overlapY, normal: overlapX < overlapY ? 'x' : 'y' };
        }
        return null;
    }

    testCircleCircle(a, b) {
        const dx = a.x - b.x;
        const dy = a.y - b.y;
        const dist = Math.sqrt(dx * dx + dy * dy);
        const radiusSum = a.radius + b.radius;
        if (dist < radiusSum) {
            return { distance: dist, overlap: radiusSum - dist, nx: dx / dist, ny: dy / dist };
        }
        return null;
    }

    dispatchCallback(a, b, info) {
        for (const cb of this.collisionCallbacks) {
            if ((a.layer === cb.layerA && b.layer === cb.layerB) ||
                (a.layer === cb.layerB && b.layer === cb.layerA)) {
                cb.callback(a, b, info);
            }
        }
    }
}

// 简单的CCD：射线检测
function sweepTest(startX, startY, endX, endY, obstacle) {
    const steps = Math.ceil(Math.sqrt((endX-startX)**2 + (endY-startY)**2) / 2);
    for (let i = 0; i <= steps; i++) {
        const t = i / steps;
        const x = startX + (endX - startX) * t;
        const y = startY + (endY - startY) * t;
        if (pointInRect(x, y, obstacle)) return t;
    }
    return null;
}