PROGRAMAÇÃO EM
JOGOS DIGITAIS
Frutuoso Silva
Jogos
Detecção de colisões em 2D
1 Detecção de colisões em 2D
! Rectângulo alinhado com os eixos
(Axis-Aligned Bounding Box)
! Utilização de círculos (Bounding Sphere)
! Separating Axis Theorem
! Pixel perfect collision
Rectângulo alinhado com os eixos
! Considerando um rectângulo (rect) definido por:
! x
, y - posição do canto inferior do rectângulo;
! width,
height – largura e altura do rectângulo;
width
rect
height
y
x
2 Rectângulo alinhado com os eixos
if (rect1.x < rect2.x + rect2.width and
rect1.x + rect1.width > rect2.x and
rect1.y < rect2.y + rect2.height and
rect1.y + rect1.height > rect2.y):
#collision detected!
…
y
rect1
rect2
x
Rectângulo alinhado com os eixos
if (rect1.x < rect2.x + rect2.width and
rect1.x + rect1.width > rect2.x and
rect1.y < rect2.y + rect2.height and
rect1.y + rect1.height > rect2.y):
#collision detected!
…
y
# Falha aqui !
rect1
rect2
x
3 Rectângulo alinhado com os eixos
if (rect1.x < rect2.x + rect2.width and
rect1.x + rect1.width > rect2.x and
rect1.y < rect2.y + rect2.height and
rect1.y + rect1.height > rect2.y):
#collision detected!
…
y
# Falha aqui !
rect1
rect2
x
Rectângulo alinhado com os eixos
if (rect1.x < rect2.x + rect2.width and
rect1.x + rect1.width > rect2.x and
rect1.y < rect2.y + rect2.height and
rect1.y + rect1.height > rect2.y):
#collision detected!
…
y
# Falha aqui !
# Falha aqui !
rect1
rect2
x
4 Utilização de círculos
! Considerando um círculo definido por:
! x,
y – coordenadas do centro;
! radius – raio do círculo
raio
y
x
Utilização de círculos
dx = circle1.x - circle2.x
dy = circle1.y - circle2.y
dist = math.sqrt(dx * dx + dy * dy)
if (dist < circle1.radius + circle2.radius):
# collision detected!
y
circle1
circle2
dist
x
5 Utilização de círculos
dx = circle1.x - circle2.x
dy = circle1.y - circle2.y
dist = math.sqrt(dx * dx + dy * dy)
if (dist < circle1.radius + circle2.radius):
# collision detected!
y
circle1
dy
dist
circle2
x
dx
Utilização de círculos
dx = circle1.x - circle2.x
dy = circle1.y - circle2.y
dist = math.sqrt(dx * dx + dy * dy)
if (dist < circle1.radius + circle2.radius):
# collision detected!
y
circle1
Existe colisão !
circle2
dist
x
6 Separating Axis Theorem
! ! The Separation of Axis Theorem (SAT) is a
technique to test whether two convex polygons are
colliding.
The SAT theorem: "given two convex shapes, there
exists a line onto which their projections will be
separate if and only if they are not intersecting."
Separating Axis Theorem
! The SAT theorem: "given two convex shapes, there
exists a line onto which their projections will be
separate if and only if they are not intersecting."
Separating line
Separating Axis
7 Separating Axis Theorem
! Work with polygons not aligned with axis?
! Yes,
we only need to check as many sides as both
objects have combined
Separating line
Separating Axis
Separating Axis Theorem
! Work with polygons not aligned with axis?
! Yes,
we only need to check as many sides as both
objects have combined
Separating line
Separating Axis
8 Separating Axis Theorem
! Work for convex polygons only.
! But,
we can subdivide a concave polygon into several
convex polygons!
! More hardly to code !
Pixel perfect collision (PPC)
! Uses bit-masks to determine whether two objects collide.
https://wiki.allegro.cc/index.php?title=Pixel_Perfect_Collision
! There are many ways to code this approach, but all of
them are extremely slow compared to bounding boxes.
9 Pixel perfect collision (PPC)
! First use the bounding box method to detect a
collision
Pixel perfect collision (PPC)
! If bounding box method detects a collision
Then pixel perfect collision will evaluate
the collision between the two sprites
10 Detecção de Colisões em 3D
! Bounding Sphere
! Bounding Box
! Face to Face
Detecção de Colisões em 3D
! Bounding Sphere
11 Detecção de Colisões em 3D
! Bounding Box
Detecção de Colisões em 3D
! Face to Face
12 Detecção de Colisões em 3D
! Face to Face
13