Collision Detection Algorithm

Feature Description

In the physics section, you can add an algorithm that allows you to detect collisions of different types of primitives. This will be useful in creating games, etc.

The Collision Detection Algorithm for Different Primitives

Below, I've given an implementation of a collision detection algorithm that includes axis-aligned bounding boxes (AABB) and circles.

import math

class AABB:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height

class Circle:
    def __init__(self, x, y, radius):
        self.x = x
        self.y = y
        self.radius = radius

def check_aabb_collision(box1, box2):
    """Check if two axis-aligned bounding boxes (AABB) collide."""
    if (box1.x < box2.x + box2.width and
        box1.x + box1.width > box2.x and
        box1.y < box2.y + box2.height and
        box1.y + box1.height > box2.y):
        return True
    return False

def check_circle_collision(circle1, circle2):
    """Check if two circles collide."""
    distance = math.sqrt((circle1.x - circle2.x) ** 2 + (circle1.y - circle2.y) ** 2)
    return distance < (circle1.radius + circle2.radius)

def check_aabb_circle_collision(box, circle):
    """Check if an AABB and a circle collide."""
    closest_x = clamp(circle.x, box.x, box.x + box.width)
    closest_y = clamp(circle.y, box.y, box.y + box.height)
    distance_x = circle.x - closest_x
    distance_y = circle.y - closest_y
    distance_squared = distance_x ** 2 + distance_y ** 2
    return distance_squared < (circle.radius ** 2)

def clamp(value, min_value, max_value):
    return max(min_value, min(value, max_value))

# Example in usage
if __name__ == "__main__":
    box1 = AABB(0, 0, 10, 10)
    box2 = AABB(5, 5, 10, 10)
    box3 = AABB(20, 20, 5, 5)

    circle1 = Circle(5, 5, 3)
    circle2 = Circle(15, 15, 5)

    print(check_aabb_collision(box1, box2))  # Output: True
    print(check_aabb_collision(box1, box3))  # Output: False
    print(check_circle_collision(circle1, circle2))  # Output: False
    print(check_aabb_circle_collision(box1, circle1))  # Output: True

Separating Axis Theorem (SAT) for Convex Polygons

The Separating Axis Theorem (SAT) can be used to detect collisions between any two convex shapes. Here's an extended implementation:

import numpy as np

class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices

def project_polygon(axis, polygon):
    dots = [np.dot(vertex, axis) for vertex in polygon.vertices]
    return min(dots), max(dots)

def overlap(proj1, proj2):
    return min(proj1[1], proj2[1]) >= max(proj1[0], proj2[0])

def get_axes(polygon):
    axes = []
    num_vertices = len(polygon.vertices)
    for i in range(num_vertices):
        p1 = polygon.vertices[i]
        p2 = polygon.vertices[(i + 1) % num_vertices]
        edge = p1 - p2
        normal = np.array([-edge[1], edge[0]])
        axes.append(normal / np.linalg.norm(normal))
    return axes

def check_polygon_collision(poly1, poly2):
    """Check if two convex polygons collide using the Separating Axis Theorem (SAT)."""
    axes1 = get_axes(poly1)
    axes2 = get_axes(poly2)
    
    for axis in axes1 + axes2:
        proj1 = project_polygon(axis, poly1)
        proj2 = project_polygon(axis, poly2)
        if not overlap(proj1, proj2):
            return False
    return True

# Example in usage
if __name__ == "__main__":
    poly1 = Polygon([np.array([0, 0]), np.array([2, 0]), np.array([2, 2]), np.array([0, 2])])
    poly2 = Polygon([np.array([1, 1]), np.array([3, 1]), np.array([3, 3]), np.array([1, 3])])
    poly3 = Polygon([np.array([3, 3]), np.array([5, 3]), np.array([5, 5]), np.array([3, 5])])

    print(check_polygon_collision(poly1, poly2))  # Output: True
    print(check_polygon_collision(poly1, poly3))  # Output: False

Summary

I have extended the collision detection implementation to include:

Axis-Aligned Bounding Boxes (AABB)
Circles
Convex polygons using the Separating Axis Theorem (SAT)

These algorithms, as exhibited above, can now be used to detect collisions between different types of primitives, which is useful for creating games and other applications that require physics simulations.

Uh oh!

Add a collision detection algorithm #12569

Description

Feature description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions