El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

La detecció de col·lisions és una part fonamental en el desenvolupament de videojocs, ja que permet determinar quan dos o més objectes dins del joc entren en contacte. Aquesta informació és crucial per a la simulació de respostes físiques realistes, com ara rebotar, empènyer o destruir objectes. En aquesta secció, explorarem els conceptes bàsics de la detecció de col·lisions, les tècniques més comunes i com implementar-les en un motor de videojocs.

Conceptes Bàsics

Què és una Col·lisió?

Una col·lisió es produeix quan dos objectes ocupen el mateix espai en un moment determinat. En els videojocs, això es tradueix en la intersecció de les formes geomètriques que representen els objectes.

Tipus de Col·lisions

Col·lisions entre Rigid Bodies: Objectes sòlids que no es deformen.
Col·lisions entre Partícules: Objectes petits que poden representar elements com pols o aigua.
Col·lisions entre Soft Bodies: Objectes que es poden deformar, com ara roba o cossos humans.

Tècniques de Detecció de Col·lisions

Bounding Volumes

Els volums de delimitació són formes geomètriques simples que envolten un objecte més complex per simplificar la detecció de col·lisions. Els tipus més comuns són:

Bounding Box (Caixa de Delimitació): Una caixa rectangular que envolta l'objecte.
Bounding Sphere (Esfera de Delimitació): Una esfera que envolta l'objecte.
Bounding Capsule (Càpsula de Delimitació): Una càpsula que envolta l'objecte.

Exemple de Bounding Box en Pseudocodi

function checkCollision(box1, box2):
    if (box1.maxX < box2.minX or box1.minX > box2.maxX):
        return false
    if (box1.maxY < box2.minY or box1.minY > box2.maxY):
        return false
    if (box1.maxZ < box2.minZ or box1.minZ > box2.maxZ):
        return false
    return true

Algoritmes de Detecció de Col·lisions

Algoritme de Separating Axis Theorem (SAT)

El SAT és un mètode per determinar si dos polígons convexos estan col·lisionant. La idea és projectar els polígons en un eix i veure si les projeccions es superposen.

Exemple de SAT en Pseudocodi

function SATCollision(poly1, poly2):
    axes = getAxes(poly1) + getAxes(poly2)
    for axis in axes:
        projection1 = projectPolygon(poly1, axis)
        projection2 = projectPolygon(poly2, axis)
        if not overlap(projection1, projection2):
            return false
    return true

Grids i Quadtrees

Per a jocs amb molts objectes, utilitzar una estructura de dades com un grid o un quadtree pot millorar l'eficiència de la detecció de col·lisions.

Exemple de Quadtree en Pseudocodi

class Quadtree:
    def __init__(self, level, bounds):
        self.level = level
        self.bounds = bounds
        self.objects = []
        self.nodes = []

    def split(self):
        subWidth = self.bounds.width / 2
        subHeight = self.bounds.height / 2
        x = self.bounds.x
        y = self.bounds.y

        self.nodes.append(Quadtree(self.level + 1, Rect(x + subWidth, y, subWidth, subHeight)))
        self.nodes.append(Quadtree(self.level + 1, Rect(x, y, subWidth, subHeight)))
        self.nodes.append(Quadtree(self.level + 1, Rect(x, y + subHeight, subWidth, subHeight)))
        self.nodes.append(Quadtree(self.level + 1, Rect(x + subWidth, y + subHeight, subWidth, subHeight)))

    def insert(self, obj):
        if self.nodes:
            index = self.getIndex(obj)
            if index != -1:
                self.nodes[index].insert(obj)
                return

        self.objects.append(obj)

        if len(self.objects) > MAX_OBJECTS and self.level < MAX_LEVELS:
            if not self.nodes:
                self.split()

            i = 0
            while i < len(self.objects):
                index = self.getIndex(self.objects[i])
                if index != -1:
                    self.nodes[index].insert(self.objects.pop(i))
                else:
                    i += 1

Implementació en Motors de Videojocs

Unity

Unity proporciona components com Collider i Rigidbody per facilitar la detecció de col·lisions. Els col·liders poden ser de diferents formes, com ara caixes, esferes o malles personalitzades.

Exemple en C# per Unity

void OnCollisionEnter(Collision collision)
{
    if (collision.gameObject.tag == "Enemy")
    {
        // Accions a realitzar en cas de col·lisió amb un enemic
    }
}

Unreal Engine

Unreal Engine utilitza components com UPrimitiveComponent i URigidBodyComponent per gestionar col·lisions. També ofereix funcions com OnComponentHit per detectar col·lisions.

Exemple en C++ per Unreal Engine

void AMyActor::NotifyHit(UPrimitiveComponent* MyComp, AActor* Other, UPrimitiveComponent* OtherComp, bool bSelfMoved, FVector HitLocation, FVector HitNormal, FVector NormalImpulse, const FHitResult& Hit)
{
    if (Other->ActorHasTag("Enemy"))
    {
        // Accions a realitzar en cas de col·lisió amb un enemic
    }
}

Exercicis Pràctics

Exercici 1: Implementar una Bounding Box

Implementa una funció que comprovi si dues caixes de delimitació estan col·lisionant. Utilitza les coordenades mínimes i màximes de cada caixa.

Solució

def check_collision(box1, box2):
    if (box1['maxX'] < box2['minX'] or box1['minX'] > box2['maxX']):
        return False
    if (box1['maxY'] < box2['minY'] or box1['minY'] > box2['maxY']):
        return False
    if (box1['maxZ'] < box2['minZ'] or box1['minZ'] > box2['maxZ']):
        return False
    return True

box1 = {'minX': 0, 'maxX': 2, 'minY': 0, 'maxY': 2, 'minZ': 0, 'maxZ': 2}
box2 = {'minX': 1, 'maxX': 3, 'minY': 1, 'maxY': 3, 'minZ': 1, 'maxZ': 3}

print(check_collision(box1, box2))  # Ha de retornar True

Exercici 2: Implementar un Quadtree

Implementa un quadtree per gestionar la detecció de col·lisions en un espai 2D amb molts objectes.

Solució

class Quadtree:
    def __init__(self, level, bounds):
        self.level = level
        self.bounds = bounds
        self.objects = []
        self.nodes = []

    def split(self):
        subWidth = self.bounds['width'] / 2
        subHeight = self.bounds['height'] / 2
        x = self.bounds['x']
        y = self.bounds['y']

        self.nodes.append(Quadtree(self.level + 1, {'x': x + subWidth, 'y': y, 'width': subWidth, 'height': subHeight}))
        self.nodes.append(Quadtree(self.level + 1, {'x': x, 'y': y, 'width': subWidth, 'height': subHeight}))
        self.nodes.append(Quadtree(self.level + 1, {'x': x, 'y': y + subHeight, 'width': subWidth, 'height': subHeight}))
        self.nodes.append(Quadtree(self.level + 1, {'x': x + subWidth, 'y': y + subHeight, 'width': subWidth, 'height': subHeight}))

    def insert(self, obj):
        if self.nodes:
            index = self.get_index(obj)
            if index != -1:
                self.nodes[index].insert(obj)
                return

        self.objects.append(obj)

        if len(self.objects) > MAX_OBJECTS and self.level < MAX_LEVELS:
            if not self.nodes:
                self.split()

            i = 0
            while i < len(self.objects):
                index = self.get_index(self.objects[i])
                if index != -1:
                    self.nodes[index].insert(self.objects.pop(i))
                else:
                    i += 1

    def get_index(self, obj):
        index = -1
        vertical_midpoint = self.bounds['x'] + (self.bounds['width'] / 2)
        horizontal_midpoint = self.bounds['y'] + (self.bounds['height'] / 2)

        top_quadrant = (obj['y'] < horizontal_midpoint and obj['y'] + obj['height'] < horizontal_midpoint)
        bottom_quadrant = (obj['y'] > horizontal_midpoint)

        if obj['x'] < vertical_midpoint and obj['x'] + obj['width'] < vertical_midpoint:
            if top_quadrant:
                index = 1
            elif bottom_quadrant:
                index = 2
        elif obj['x'] > vertical_midpoint:
            if top_quadrant:
                index = 0
            elif bottom_quadrant:
                index = 3

        return index

Conclusió

La detecció de col·lisions és un aspecte crucial en el desenvolupament de videojocs, ja que permet simular interaccions realistes entre objectes. Hem explorat diversos mètodes i tècniques per detectar col·lisions, des de volums de delimitació fins a algoritmes més avançats com el SAT i estructures de dades com els quadtrees. A més, hem vist com implementar aquestes tècniques en motors de videojocs populars com Unity i Unreal Engine. Amb aquests coneixements, estàs preparat per abordar la detecció de col·lisions en els teus propis projectes de videojocs.

Detecció de Col·lisions

Conceptes Bàsics

Què és una Col·lisió?

Tipus de Col·lisions

Tècniques de Detecció de Col·lisions

Bounding Volumes

Exemple de Bounding Box en Pseudocodi

Algoritmes de Detecció de Col·lisions

Algoritme de Separating Axis Theorem (SAT)

Exemple de SAT en Pseudocodi

Grids i Quadtrees

Exemple de Quadtree en Pseudocodi

Implementació en Motors de Videojocs

Unity

Exemple en C# per Unity

Unreal Engine

Exemple en C++ per Unreal Engine

Exercicis Pràctics

Exercici 1: Implementar una Bounding Box

Solució

Exercici 2: Implementar un Quadtree

Solució

Conclusió

Física de Videojocs

Mòdul 1: Introducció a la Física en Videojocs

Mòdul 2: Cinemàtica i Dinàmica

Mòdul 3: Col·lisions i Respostes

Mòdul 4: Física de Rigid Bodies

Mòdul 5: Física de Partícules

Mòdul 6: Física Avançada

Mòdul 7: Implementació en Motors de Videojocs

Mòdul 8: Projecte Final