碰撞检测

学习Canvas碰撞检测技术，掌握各种碰撞检测算法和碰撞响应处理方法。碰撞检测是判断物体是否相交的技术，是游戏开发和物理模拟的核心技术。

碰撞检测基础

什么是碰撞检测

碰撞检测判断两个物体是否接触或重叠，是物理交互的基础。

碰撞检测类型

基础碰撞检测

点与圆

function pointInCircle(px, py, cx, cy, radius) {
  const dx = px - cx
  const dy = py - cy
  return dx * dx + dy * dy <= radius * radius
}

点与矩形

function pointInRect(px, py, rx, ry, rw, rh) {
  return px >= rx && px <= rx + rw &&
         py >= ry && py <= ry + rh
}

圆与圆

function circleCollision(c1, c2) {
  const dx = c2.x - c1.x
  const dy = c2.y - c1.y
  const distance = Math.sqrt(dx * dx + dy * dy)
  return distance < c1.radius + c2.radius
}

矩形与矩形（AABB）

function rectCollision(r1, r2) {
  return r1.x < r2.x + r2.width &&
         r1.x + r1.width > r2.x &&
         r1.y < r2.y + r2.height &&
         r1.y + r1.height > r2.y
}

碰撞检测演示

高级碰撞检测

圆与矩形

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
}

线段与圆

function lineCircleCollision(x1, y1, x2, y2, cx, cy, radius) {
  const dx = x2 - x1
  const dy = y2 - y1
  const fx = x1 - cx
  const fy = y1 - cy
  
  const a = dx * dx + dy * dy
  const b = 2 * (fx * dx + fy * dy)
  const c = fx * fx + fy * fy - radius * radius
  
  let discriminant = b * b - 4 * a * c
  
  if (discriminant < 0) return false
  
  discriminant = Math.sqrt(discriminant)
  
  const t1 = (-b - discriminant) / (2 * a)
  const t2 = (-b + discriminant) / (2 * a)
  
  if (t1 >= 0 && t1 <= 1) return true
  if (t2 >= 0 && t2 <= 1) return true
  
  return false
}

线段与线段

function lineLineCollision(x1, y1, x2, y2, x3, y3, x4, y4) {
  const denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1)
  
  if (denom === 0) return false
  
  const ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom
  const ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom
  
  return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1
}

多边形碰撞（SAT）

分离轴定理（SAT）是检测凸多边形碰撞的通用方法。

class SATPolygon {
  constructor(vertices) {
    this.vertices = vertices
  }
  
  getAxes() {
    const axes = []
    for (let i = 0; i < this.vertices.length; i++) {
      const p1 = this.vertices[i]
      const p2 = this.vertices[(i + 1) % this.vertices.length]
      
      const edge = { x: p2.x - p1.x, y: p2.y - p1.y }
      const normal = { x: -edge.y, y: edge.x }
      
      const length = Math.sqrt(normal.x * normal.x + normal.y * normal.y)
      normal.x /= length
      normal.y /= length
      
      axes.push(normal)
    }
    return axes
  }
  
  project(axis) {
    let min = Infinity
    let max = -Infinity
    
    this.vertices.forEach(v => {
      const proj = v.x * axis.x + v.y * axis.y
      min = Math.min(min, proj)
      max = Math.max(max, proj)
    })
    
    return { min, max }
  }
}

function satCollision(poly1, poly2) {
  const axes = [...poly1.getAxes(), ...poly2.getAxes()]
  
  for (const axis of axes) {
    const proj1 = poly1.project(axis)
    const proj2 = poly2.project(axis)
    
    if (proj1.max < proj2.min || proj2.max < proj1.min) {
      return false
    }
  }
  
  return true
}

碰撞响应

圆与圆碰撞响应

function resolveCircleCollision(c1, c2) {
  const dx = c2.x - c1.x
  const dy = c2.y - c1.y
  const distance = Math.sqrt(dx * dx + dy * dy)
  
  if (distance === 0) return
  
  const nx = dx / distance
  const ny = dy / distance
  
  const overlap = c1.radius + c2.radius - distance
  
  c1.x -= nx * overlap * 0.5
  c1.y -= ny * overlap * 0.5
  c2.x += nx * overlap * 0.5
  c2.y += ny * overlap * 0.5
  
  const dvx = c1.vx - c2.vx
  const dvy = c1.vy - c2.vy
  const dvn = dvx * nx + dvy * ny
  
  if (dvn > 0) return
  
  const restitution = 0.8
  const impulse = -(1 + restitution) * dvn / (1 / c1.mass + 1 / c2.mass)
  
  c1.vx += impulse * nx / c1.mass
  c1.vy += impulse * ny / c1.mass
  c2.vx -= impulse * nx / c2.mass
  c2.vy -= impulse * ny / c2.mass
}

碰撞响应演示

空间分区优化

网格分区

class SpatialGrid {
  constructor(cellSize, width, height) {
    this.cellSize = cellSize
    this.cols = Math.ceil(width / cellSize)
    this.rows = Math.ceil(height / cellSize)
    this.grid = new Map()
  }
  
  clear() {
    this.grid.clear()
  }
  
  getKey(x, y) {
    const col = Math.floor(x / this.cellSize)
    const row = Math.floor(y / this.cellSize)
    return `${col},${row}`
  }
  
  insert(obj) {
    const key = this.getKey(obj.x, obj.y)
    if (!this.grid.has(key)) {
      this.grid.set(key, [])
    }
    this.grid.get(key).push(obj)
  }
  
  getNearby(obj) {
    const col = Math.floor(obj.x / this.cellSize)
    const row = Math.floor(obj.y / this.cellSize)
    const nearby = []
    
    for (let i = -1; i <= 1; i++) {
      for (let j = -1; j <= 1; j++) {
        const key = `${col + i},${row + j}`
        const cell = this.grid.get(key)
        if (cell) {
          nearby.push(...cell)
        }
      }
    }
    
    return nearby
  }
}

const grid = new SpatialGrid(50, 800, 600)

function checkCollisionsWithGrid(objects) {
  grid.clear()
  objects.forEach(obj => grid.insert(obj))
  
  const checked = new Set()
  const collisions = []
  
  objects.forEach(obj => {
    const nearby = grid.getNearby(obj)
    
    nearby.forEach(other => {
      if (obj === other) return
      
      const key = obj.id < other.id ? `${obj.id}-${other.id}` : `${other.id}-${obj.id}`
      if (checked.has(key)) return
      checked.add(key)
      
      if (circleCollision(obj, other)) {
        collisions.push([obj, other])
      }
    })
  })
  
  return collisions
}

四叉树

class QuadTree {
  constructor(bounds, capacity = 4) {
    this.bounds = bounds
    this.capacity = capacity
    this.objects = []
    this.divided = false
    this.children = null
  }
  
  subdivide() {
    const { x, y, width, height } = this.bounds
    const hw = width / 2
    const hh = height / 2
    
    this.children = [
      new QuadTree({ x, y, width: hw, height: hh }, this.capacity),
      new QuadTree({ x: x + hw, y, width: hw, height: hh }, this.capacity),
      new QuadTree({ x, y: y + hh, width: hw, height: hh }, this.capacity),
      new QuadTree({ x: x + hw, y: y + hh, width: hw, height: hh }, this.capacity)
    ]
    
    this.divided = true
  }
  
  insert(obj) {
    if (!this.contains(obj)) return false
    
    if (this.objects.length < this.capacity) {
      this.objects.push(obj)
      return true
    }
    
    if (!this.divided) {
      this.subdivide()
    }
    
    return this.children.some(child => child.insert(obj))
  }
  
  contains(obj) {
    return obj.x >= this.bounds.x &&
           obj.x < this.bounds.x + this.bounds.width &&
           obj.y >= this.bounds.y &&
           obj.y < this.bounds.y + this.bounds.height
  }
  
  query(range, found = []) {
    if (!this.intersects(range)) return found
    
    this.objects.forEach(obj => {
      if (obj.x >= range.x && obj.x < range.x + range.width &&
          obj.y >= range.y && obj.y < range.y + range.height) {
        found.push(obj)
      }
    })
    
    if (this.divided) {
      this.children.forEach(child => child.query(range, found))
    }
    
    return found
  }
  
  intersects(range) {
    return !(range.x > this.bounds.x + this.bounds.width ||
             range.x + range.width < this.bounds.x ||
             range.y > this.bounds.y + this.bounds.height ||
             range.y + range.height < this.bounds.y)
  }
}

射线检测

class Ray {
  constructor(x, y, dx, dy) {
    this.x = x
    this.y = y
    this.dx = dx
    this.dy = dy
  }
  
  castToCircle(cx, cy, radius) {
    const fx = this.x - cx
    const fy = this.y - cy
    
    const a = this.dx * this.dx + this.dy * this.dy
    const b = 2 * (fx * this.dx + fy * this.dy)
    const c = fx * fx + fy * fy - radius * radius
    
    let discriminant = b * b - 4 * a * c
    
    if (discriminant < 0) return null
    
    discriminant = Math.sqrt(discriminant)
    
    const t1 = (-b - discriminant) / (2 * a)
    const t2 = (-b + discriminant) / (2 * a)
    
    const t = t1 >= 0 ? t1 : (t2 >= 0 ? t2 : null)
    
    if (t === null) return null
    
    return {
      x: this.x + this.dx * t,
      y: this.y + this.dy * t,
      distance: t
    }
  }
  
  castToRect(rx, ry, rw, rh) {
    let tmin = 0
    let tmax = Infinity
    
    const axes = [
      { origin: rx, size: rw, rayOrigin: this.x, rayDir: this.dx },
      { origin: ry, size: rh, rayOrigin: this.y, rayDir: this.dy }
    ]
    
    for (const axis of axes) {
      const invD = 1 / axis.rayDir
      let t0 = (axis.origin - axis.rayOrigin) * invD
      let t1 = (axis.origin + axis.size - axis.rayOrigin) * invD
      
      if (invD < 0) [t0, t1] = [t1, t0]
      
      tmin = Math.max(tmin, t0)
      tmax = Math.min(tmax, t1)
      
      if (tmax < tmin) return null
    }
    
    return {
      x: this.x + this.dx * tmin,
      y: this.y + this.dy * tmin,
      distance: tmin
    }
  }
}

碰撞层

class CollisionLayer {
  constructor() {
    this.layers = new Map()
    this.matrix = new Map()
  }
  
  createLayer(name) {
    this.layers.set(name, [])
  }
  
  addToLayer(name, obj) {
    if (!this.layers.has(name)) {
      this.createLayer(name)
    }
    this.layers.get(name).push(obj)
  }
  
  setCollision(layer1, layer2, collides = true) {
    const key = layer1 < layer2 ? `${layer1}-${layer2}` : `${layer2}-${layer1}`
    this.matrix.set(key, collides)
  }
  
  shouldCollide(layer1, layer2) {
    if (layer1 === layer2) return true
    const key = layer1 < layer2 ? `${layer1}-${layer2}` : `${layer2}-${layer1}`
    return this.matrix.get(key) || false
  }
  
  checkCollisions() {
    const collisions = []
    const layerNames = Array.from(this.layers.keys())
    
    for (let i = 0; i < layerNames.length; i++) {
      for (let j = i; j < layerNames.length; j++) {
        if (!this.shouldCollide(layerNames[i], layerNames[j])) continue
        
        const objects1 = this.layers.get(layerNames[i])
        const objects2 = this.layers.get(layerNames[j])
        
        objects1.forEach(obj1 => {
          objects2.forEach(obj2 => {
            if (obj1 === obj2) return
            if (circleCollision(obj1, obj2)) {
              collisions.push([obj1, obj2])
            }
          })
        })
      }
    }
    
    return collisions
  }
}