Pan-Maciek · October 16, 2019 20:06
diff --git a/grid.js b/grid.js
 class Grid {
  constructor(width, height, resolution) {
    const cols = this.cols = ceil(width / resolution)
    const rows = this.rows = ceil(height / resolution)
    this.resolution = resolution
    this.data = Array.from({ length: rows }, () => Array.from({ length: cols }, () => []))
    this.neighbors = function* (obj) {
      const x = floor(obj.x / this.resolution), y = floor(obj.y / this.resolution)
      for (var oy = -1; oy <= 1; oy++) {
        for (var ox = -1; ox <= 1; ox++) {
          if (x + ox >= 0 && x + ox < cols && y + oy >= 0 && y + oy < rows)
            for (let neighbor of this.data[y + oy][x + ox]) {
              if (neighbor != obj) yield neighbor
            }
        }
      }
    }
  }
  vecToCell({ x, y }) { return this.data[floor(y / this.resolution)][floor(x / this.resolution)] }
  add(obj) { this.vecToCell(obj).push(obj) } // obj size <= resolution

  move(obj, vec) {
    const old_cell = this.vecToCell(obj)
    vecApplyAdd(obj, vec)
    for (let n of this.neighbors(obj)) {
      if (circle_circle_collision_test(obj, n)) {
        // HANDLE COLLISION LOGIC
        const v = unitVec(makeVec(n, obj)) // basic collision resolution ignoring velocity change, pushing into other circles etc
        obj.x = n.x + (obj.r + n.r) * v.x
        obj.y = n.y + (obj.r + n.r) * v.y
        obj.color = n.color = '#f00'
      }
    }
    const new_cell = this.vecToCell(obj)
    if (old_cell !== new_cell) {
      remove(old_cell, obj)
      new_cell.push(obj)
    }
  }
 }
diff --git a/index.html b/index.html
 <!DOCTYPE html>
 <html>

 <head>
  <title>Grid based collision detection</title>
 </head>

 <body>
  <script src="grid.js"></script>
  <script src="main.js"></script>
 </body>

 </html>
diff --git a/main.js b/main.js
 const canvas = document.createElement('canvas')
 const size = canvas.width = canvas.height = 500
 document.body.append(canvas)
 const { min, max, ceil, floor, PI, hypot, abs } = Math
 const c = canvas.getContext('2d')

 function* range2d(x, y) {
  for (var xi = 0; xi < x; xi++)
    for (var yi = 0; yi < y; yi++)
      yield { x: xi, y: yi }
 }

 function circle_circle_collision_test(c1, c2) {
  const { x: x1, y: y1, r: r1 } = c1
  const { x: x2, y: y2, r: r2 } = c2
  return hypot(x1 - x2, y1 - y2) < r1 + r2
 }

 const vecLen = ({ x, y }) => hypot(x, y)
 const makeVec = (A, B) => ({ x: B.x - A.x, y: B.y - A.y })
 const scale = ({ x, y }, s) => ({ x: x * s, y: y * s })
 const unitVec = A => scale(A, 1 / vecLen(A))
 const remove = (array, obj) => array.splice(array.indexOf(obj), 1)
 const vecApplyAdd = (A, { x, y }) => { A.x += x; A.y += y }


 const grid = new Grid(size, size, 50)
 const cs = Array.from({ length: 10 }, () => ({ x: Math.random() * size, y: Math.random() * size, r: 10 + 15 * Math.random() }))
 cs.forEach(c => grid.add(c))

 function drawCircle({ x, y, r, color }) {
  c.beginPath()
  c.strokeStyle = color
  c.arc(x, y, r, 0, 2 * PI)
  c.closePath()
  c.stroke()
 }

 function drawGrid() {
  for (let { x, y } of range2d(grid.cols, grid.rows)) {
    c.fillStyle = grid.data[y][x].length ? '#bf4040' : ((x + y) % 2 ? '#f1f1f1' : '#ccc')
    c.fillRect(x * grid.resolution, y * grid.resolution, grid.resolution, grid.resolution)
  }
 }

 function draw() {
  drawGrid()
  cs.forEach(c => {
    drawCircle(c)
    c.color = '#000'
  })
 }
 draw()

 window.addEventListener('keydown', e => {
  if (e.key == 'w') grid.move(cs[0], { x: 0, y: -5 })
  if (e.key == 's') grid.move(cs[0], { x: 0, y: 5 })
  if (e.key == 'a') grid.move(cs[0], { x: -5, y: 0 })
  if (e.key == 'd') grid.move(cs[0], { x: 5, y: 0 })
  draw()
 })
	class Grid {
	constructor(width, height, resolution) {
	const cols = this.cols = ceil(width / resolution)
	const rows = this.rows = ceil(height / resolution)
	this.resolution = resolution
	this.data = Array.from({ length: rows }, () => Array.from({ length: cols }, () => []))
	this.neighbors = function* (obj) {
	const x = floor(obj.x / this.resolution), y = floor(obj.y / this.resolution)
	for (var oy = -1; oy <= 1; oy++) {
	for (var ox = -1; ox <= 1; ox++) {
	if (x + ox >= 0 && x + ox < cols && y + oy >= 0 && y + oy < rows)
	for (let neighbor of this.data[y + oy][x + ox]) {
	if (neighbor != obj) yield neighbor
	}
	}
	}
	}
	}
	vecToCell({ x, y }) { return this.data[floor(y / this.resolution)][floor(x / this.resolution)] }
	add(obj) { this.vecToCell(obj).push(obj) } // obj size <= resolution

	move(obj, vec) {
	const old_cell = this.vecToCell(obj)
	vecApplyAdd(obj, vec)
	for (let n of this.neighbors(obj)) {
	if (circle_circle_collision_test(obj, n)) {
	// HANDLE COLLISION LOGIC
	const v = unitVec(makeVec(n, obj)) // basic collision resolution ignoring velocity change, pushing into other circles etc
	obj.x = n.x + (obj.r + n.r) * v.x
	obj.y = n.y + (obj.r + n.r) * v.y
	obj.color = n.color = '#f00'
	}
	}
	const new_cell = this.vecToCell(obj)
	if (old_cell !== new_cell) {
	remove(old_cell, obj)
	new_cell.push(obj)
	}
	}
	}
	<!DOCTYPE html>
	<html>

	<head>
	<title>Grid based collision detection</title>
	</head>

	<body>
	<script src="grid.js"></script>
	<script src="main.js"></script>
	</body>

	</html>
	const canvas = document.createElement('canvas')
	const size = canvas.width = canvas.height = 500
	document.body.append(canvas)
	const { min, max, ceil, floor, PI, hypot, abs } = Math
	const c = canvas.getContext('2d')

	function* range2d(x, y) {
	for (var xi = 0; xi < x; xi++)
	for (var yi = 0; yi < y; yi++)
	yield { x: xi, y: yi }
	}

	function circle_circle_collision_test(c1, c2) {
	const { x: x1, y: y1, r: r1 } = c1
	const { x: x2, y: y2, r: r2 } = c2
	return hypot(x1 - x2, y1 - y2) < r1 + r2
	}

	const vecLen = ({ x, y }) => hypot(x, y)
	const makeVec = (A, B) => ({ x: B.x - A.x, y: B.y - A.y })
	const scale = ({ x, y }, s) => ({ x: x * s, y: y * s })
	const unitVec = A => scale(A, 1 / vecLen(A))
	const remove = (array, obj) => array.splice(array.indexOf(obj), 1)
	const vecApplyAdd = (A, { x, y }) => { A.x += x; A.y += y }


	const grid = new Grid(size, size, 50)
	const cs = Array.from({ length: 10 }, () => ({ x: Math.random() * size, y: Math.random() * size, r: 10 + 15 * Math.random() }))
	cs.forEach(c => grid.add(c))

	function drawCircle({ x, y, r, color }) {
	c.beginPath()
	c.strokeStyle = color
	c.arc(x, y, r, 0, 2 * PI)
	c.closePath()
	c.stroke()
	}

	function drawGrid() {
	for (let { x, y } of range2d(grid.cols, grid.rows)) {
	c.fillStyle = grid.data[y][x].length ? '#bf4040' : ((x + y) % 2 ? '#f1f1f1' : '#ccc')
	c.fillRect(x * grid.resolution, y * grid.resolution, grid.resolution, grid.resolution)
	}
	}

	function draw() {
	drawGrid()
	cs.forEach(c => {
	drawCircle(c)
	c.color = '#000'
	})
	}
	draw()

	window.addEventListener('keydown', e => {
	if (e.key == 'w') grid.move(cs[0], { x: 0, y: -5 })
	if (e.key == 's') grid.move(cs[0], { x: 0, y: 5 })
	if (e.key == 'a') grid.move(cs[0], { x: -5, y: 0 })
	if (e.key == 'd') grid.move(cs[0], { x: 5, y: 0 })
	draw()
	})