Add a collision detection algorithm

[Andy666Fox]

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 when creating games, etc.

[ayushh0406]

Axis-Aligned Bounding Box (AABB) Collision Detection
An AABB is a rectangle whose edges are aligned with the coordinate axes. Collision detection between two AABBs is relatively straightforward:

Define Boundaries: Each rectangle is defined by its minimum and maximum x and y coordinates (or alternatively, by its top-left corner and width/height).

Check for Overlap: For two rectangles to collide, they must overlap in both the x and y axes. This can be checked with simple comparisons.

The conditions for two AABBs to intersect can be expressed as:

Rect1.x < Rect2.x + Rect2.width

Rect1.x + Rect1.width > Rect2.x

Rect1.y < Rect2.y + Rect2.height

Rect1.y + Rect1.height > Rect2.y

If all these conditions are true, the rectangles intersect.

[Rishiram20757]

function isColliding(rect1, rect2) {
return (
rect1.x < rect2.x + rect2.width &&
rect1.x + rect1.width > rect2.x &&
rect1.y < rect2.y + rect2.height &&
rect1.y + rect1.height > rect2.y
);
}

const rectA = { x: 10, y: 20, width: 50, height: 50 };
const rectB = { x: 40, y: 50, width: 50, height: 50 };

console.log(isColliding(rectA, rectB)); // becomes true if they overlap

this is just an snippet for an example

[1803053530]

1️⃣ AABB (Axis-Aligned Bounding Box):

def check_aabb(rect1, rect2): # [(x,y,w,h), ...]
return not (rect1+rect1 < rect2 or
rect2+rect2 < rect1 or
rect1+rect1 < rect2 or
rect2+rect2 < rect1)

Best for simple rectangles, O(1) time complexity

2️⃣ Circle Collision:

import math
def circle_collision(c1, c2): # [(x,y,r), ...]
dx = c2 - c1
dy = c2 - c1
return math.sqrt(dx2 + dy2) <= (c1 + c2)

Distance-based check, accurate for circular shapes

Need further tweaks? Happy to refine!

[joey-the-33rd]

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.