Collision detection is a fundamental aspect of video game physics, ensuring that objects within the game environment interact realistically. This module will cover the basic principles, methods, and algorithms used to detect collisions between objects in a game.
Key Concepts
-
Bounding Volumes: Simplified shapes used to approximate the geometry of objects for collision detection.
- Axis-Aligned Bounding Box (AABB): A box aligned with the coordinate axes.
- Bounding Sphere: A sphere that encompasses the object.
- Oriented Bounding Box (OBB): A box that can rotate with the object.
-
Spatial Partitioning: Techniques to divide the game world into manageable sections to optimize collision detection.
- Grid-based Partitioning: Dividing the world into a grid.
- Quadtrees/Octrees: Hierarchical tree structures that subdivide space.
-
Collision Detection Algorithms: Methods to determine if and when objects collide.
- Brute Force: Checking every object against every other object.
- Sweep and Prune: Sorting objects along an axis and checking for overlaps.
- Bounding Volume Hierarchies (BVH): Using a tree of bounding volumes.
Bounding Volumes
Axis-Aligned Bounding Box (AABB)
An AABB is a box aligned with the coordinate axes. It is defined by its minimum and maximum corners.
class AABB:
def __init__(self, min_point, max_point):
self.min_point = min_point
self.max_point = max_point
def intersects(self, other):
return (self.min_point[0] <= other.max_point[0] and self.max_point[0] >= other.min_point[0] and
self.min_point[1] <= other.max_point[1] and self.max_point[1] >= other.min_point[1] and
self.min_point[2] <= other.max_point[2] and self.max_point[2] >= other.min_point[2])Bounding Sphere
A bounding sphere is defined by a center point and a radius.
class BoundingSphere:
def __init__(self, center, radius):
self.center = center
self.radius = radius
def intersects(self, other):
distance = ((self.center[0] - other.center[0]) ** 2 +
(self.center[1] - other.center[1]) ** 2 +
(self.center[2] - other.center[2]) ** 2) ** 0.5
return distance < (self.radius + other.radius)Spatial Partitioning
Grid-based Partitioning
Dividing the game world into a grid can help reduce the number of collision checks.
class Grid:
def __init__(self, cell_size):
self.cell_size = cell_size
self.cells = {}
def add_object(self, obj, position):
cell = self.get_cell(position)
if cell not in self.cells:
self.cells[cell] = []
self.cells[cell].append(obj)
def get_cell(self, position):
return (int(position[0] // self.cell_size),
int(position[1] // self.cell_size),
int(position[2] // self.cell_size))
def get_nearby_objects(self, position):
cell = self.get_cell(position)
nearby_objects = []
for dx in range(-1, 2):
for dy in range(-1, 2):
for dz in range(-1, 2):
nearby_cell = (cell[0] + dx, cell[1] + dy, cell[2] + dz)
if nearby_cell in self.cells:
nearby_objects.extend(self.cells[nearby_cell])
return nearby_objectsQuadtrees/Octrees
Quadtrees and octrees are hierarchical data structures that subdivide space into smaller regions.
class Quadtree:
def __init__(self, boundary, capacity):
self.boundary = boundary
self.capacity = capacity
self.points = []
self.divided = False
def subdivide(self):
# Subdivide the boundary into four quadrants
pass
def insert(self, point):
if not self.boundary.contains(point):
return False
if len(self.points) < self.capacity:
self.points.append(point)
return True
if not self.divided:
self.subdivide()
return (self.northeast.insert(point) or
self.northwest.insert(point) or
self.southeast.insert(point) or
self.southwest.insert(point))Collision Detection Algorithms
Brute Force
The brute force method checks every object against every other object.
def brute_force_collision(objects):
collisions = []
for i in range(len(objects)):
for j in range(i + 1, len(objects)):
if objects[i].intersects(objects[j]):
collisions.append((objects[i], objects[j]))
return collisionsSweep and Prune
The sweep and prune algorithm sorts objects along an axis and checks for overlaps.
def sweep_and_prune(objects):
objects.sort(key=lambda obj: obj.min_point[0])
active_list = []
collisions = []
for obj in objects:
active_list = [o for o in active_list if o.max_point[0] >= obj.min_point[0]]
for active_obj in active_list:
if obj.intersects(active_obj):
collisions.append((obj, active_obj))
active_list.append(obj)
return collisionsBounding Volume Hierarchies (BVH)
BVH uses a tree of bounding volumes to reduce the number of collision checks.
class BVHNode:
def __init__(self, bounding_volume, left=None, right=None):
self.bounding_volume = bounding_volume
self.left = left
self.right = right
def build_bvh(objects):
if len(objects) == 1:
return BVHNode(objects[0].bounding_volume)
mid = len(objects) // 2
left = build_bvh(objects[:mid])
right = build_bvh(objects[mid:])
bounding_volume = combine_volumes(left.bounding_volume, right.bounding_volume)
return BVHNode(bounding_volume, left, right)
def bvh_collision(node1, node2):
if not node1.bounding_volume.intersects(node2.bounding_volume):
return []
if node1.left is None and node2.left is None:
return [(node1, node2)]
collisions = []
if node1.left is not None:
collisions.extend(bvh_collision(node1.left, node2))
collisions.extend(bvh_collision(node1.right, node2))
if node2.left is not None:
collisions.extend(bvh_collision(node1, node2.left))
collisions.extend(bvh_collision(node1, node2.right))
return collisionsPractical Exercises
Exercise 1: Implement AABB Collision Detection
Implement the intersects method for the AABB class and test it with different AABB objects.
Solution:
class AABB:
def __init__(self, min_point, max_point):
self.min_point = min_point
self.max_point = max_point
def intersects(self, other):
return (self.min_point[0] <= other.max_point[0] and self.max_point[0] >= other.min_point[0] and
self.min_point[1] <= other.max_point[1] and self.max_point[1] >= other.min_point[1] and
self.min_point[2] <= other.max_point[2] and self.max_point[2] >= other.min_point[2])
# Test cases
aabb1 = AABB([0, 0, 0], [1, 1, 1])
aabb2 = AABB([0.5, 0.5, 0.5], [1.5, 1.5, 1.5])
aabb3 = AABB([2, 2, 2], [3, 3, 3])
print(aabb1.intersects(aabb2)) # Should return True
print(aabb1.intersects(aabb3)) # Should return FalseExercise 2: Implement Bounding Sphere Collision Detection
Implement the intersects method for the BoundingSphere class and test it with different bounding spheres.
Solution:
class BoundingSphere:
def __init__(self, center, radius):
self.center = center
self.radius = radius
def intersects(self, other):
distance = ((self.center[0] - other.center[0]) ** 2 +
(self.center[1] - other.center[1]) ** 2 +
(self.center[2] - other.center[2]) ** 2) ** 0.5
return distance < (self.radius + other.radius)
# Test cases
sphere1 = BoundingSphere([0, 0, 0], 1)
sphere2 = BoundingSphere([1, 1, 1], 1)
sphere3 = BoundingSphere([3, 3, 3], 1)
print(sphere1.intersects(sphere2)) # Should return True
print(sphere1.intersects(sphere3)) # Should return FalseConclusion
In this section, we covered the fundamental concepts and methods of collision detection in video games. We explored bounding volumes, spatial partitioning techniques, and various collision detection algorithms. By understanding and implementing these techniques, you can ensure realistic interactions between objects in your game environment. In the next module, we will delve into collision resolution, where we will learn how to handle collisions once they are detected.
Physics of Video Games
Module 1: Introduction to Physics in Video Games
Module 2: Kinematics and Dynamics
- Uniform Rectilinear Motion (URM)
- Uniformly Accelerated Rectilinear Motion (UARM)
- Newton's Laws
- Circular Motion
Module 3: Collisions and Responses
Module 4: Rigid Bodies Physics
- Introduction to Rigid Bodies
- Rigid Bodies Simulation
- Interactions between Rigid Bodies
- Constraints and Joints