Skip to content

Collision Detection

:material-circle-edit-outline: 约 277 个字 :fontawesome-solid-code: 4 行代码 :material-image-multiple-outline: 4 张图片 :material-clock-time-two-outline: 预计阅读时间 3 分钟

Collision Detection

  • Collision detection is a fundamental problem in computer graphics and game development.
  • The problem is to determine whether two objects are intersecting.
  • for each pair of sprites, check wheher \(p_1 \cap p_2 \eq \emptyset ->\) No collision!!!

Rect Collision Algorithm

alt text
collidepoint:

Python
1
2
def collidepoint(self, x, y):  
    return self.left <= x <= self.right and self.top <= y <= self.bottom

Warning

The test need to be bi-directional.

colliderect:

Python
1
2
def colliderect(self, rect):  
    return self.left < rect.right and self.right > rect.left and self.top < rect.bottom and self.bottom > rect.top
Problematic indeed: checks too frequently, move-through prolems

Tyranny of numbers

Note

checking collisions for all pairs of objects is not feasible

alt text(就像时序下沿时原件的delay)

Solving all the possible problems

  • need to look for objects that don't move, and that are allowed to go through other objects
  • distant objects can be ignored
  • objects that are not visible can be ignored(off-screen objects)
  • restricted locations

Quadtree(and other sorting methods)

  • A tree data structure in which each internal node has exactly four children.

Quick test

  • Circle/ Sphere test
    alt text
    don't use sqrt function, too ecpensive(Numerical Analysis)
  • Bounding Box(a better rectangle)
  • a better collision detection algorithm(don't use corners of the rec)
  • Separating Axis Theorem:
    • if two convex shapes do not intersect, there exists a line such that the projection of the two shapes onto the line do not overlap.
  • Capsule(semicircles: a bounding test for the rec,and a circle test for the circle)

Book Recommendation

Game Programming: Algorithms and Techniques by Sanjay Madhaven

  • Swept Sphere Algorithm(use math to determine whether two moving objects will collide dynamically)
    \((B\cdot B)t^2+2(A\cdot B)t+A\cdot A-(r_p+r_q)^2=0\)

Resolve Collision

  • Bounces
  • Elastic Collisions
    alt text
    find the touching point

\(\vec{v_1}=\vec{v}-2\vec{n}(\vec{v} \cdot \vec{n})\)

Comments