Implementación de un Raycaster en PixiJS con Detección de Colisiones de Vértices

Introducción

Un gran desafío que asumí: implementar una funcionalidad esencial para la correcta gestión de colisiones en mi motor de juego.

A diferencia de la mayoría de los motores de juego que utilizan vectores, PixiJS solo maneja los bounds en forma de proyecciones rectangulares.
Si bien esto no es problemático en 2D, este enfoque es muy limitado para las necesidades de un juego.
La imagen de arriba ilustra el comportamiento de un raycast sobre los bounds de nuestros objetos.

El problema

Sin embargo, en 3D, este enfoque plantea un problema significativo.
Cuando un DisplayObject rota, su bounds sigue siendo un simple rectángulo estático.

Aquí un ejemplo:

Por lo tanto, tuve que dedicar varios días al estudio de las matemáticas y la trigonometría para implementar esta funcionalidad.

Esta funcionalidad será esencial para que un actor pueda percibir su entorno e interactuar con los objetos según su distancia y altura.
Este raycast también se utilizará en el sistema de FOW (Fog of War), mostrando ciertas porciones del mapa y elementos en función de las colisiones que detecta.

Este es un tema que solo abordo de manera somera, ya que es muy complejo.
Sin embargo, espero que este artículo pueda inspirarte para tu propio proyecto.

Integraciones

Para simplificar mi enfoque, creé una Class Helper dentro de mi arquitectura.
Estas Class Helper se almacenan en archivos `.h.ts` y exportan exclusivamente objetos Pixi.

ts
export class RayCasterHelper extends Container3d {
	public rays:Sprite3d[] = [];
	public raysVirtual:Graphics[] = [];
	public raysDistance:number[] = [];
	public boundsDebugs:Graphics[] = [];
	public raysTextDistance:Text3d[] = [];
	public rayLength:number = 900;
	public raySize:number = 12;
	public inCircleRadius:number = 10;
	public quadrans:number = 8;
	public shapes:CollisionShape[] = [];
}

La inicialización construye el número de segmentos indicado como parámetro.
En mi caso, un cuadrante de 8 segmentos resultó ser más que suficiente.
Esta configuración también facilita la depuración, ya que permite asignar 8 colores distintos a estos segmentos.

ts
public initialize( renderer:Renderer ) {
		this.clear();
		const colors = [0x00ff00, 0xff0000, 0x0000ff, 0xffff00, 0x00ffff, 0xff00ff, 0x333444, 0xffffff];
		for ( let i = 0, l = this.quadrans; i < l; i++ ) {
			const color = colors[i % colors.length];
			const edges = [
				new Point( this.inCircleRadius, 0 ),
				new Point( this.inCircleRadius + this.rayLength, 0 ),
			];
			const ray = new Graphics();
			ray.lineStyle( this.raySize, color, 1 );
			ray.moveTo( this.inCircleRadius, 1 );
			ray.drawPolygon( edges );
			ray.endFill();

			const raySprite = new Sprite3d( renderer.generateTexture( ray ) );
			this.rays.push( raySprite );
			this.shapes[i] = new CollisionShape( raySprite, edges );

			raySprite.proj.euler.z = ( Math.PI * 2 / this.quadrans ) * i;
			this.raysDistance.push( 0 );

Cabe destacar la creación de los puntos que sirven como segmentos.
Normalmente, solo los puntos de las diagonales serían necesarios, ya que un rectángulo no presenta un punto ciego en sus ejes horizontal y vertical.
Por lo tanto, es posible ignorarlos en función del porcentaje del cuadrante, lo que permite omitir los rayos verticales y horizontales para generar polígonos únicamente en las diagonales.

ts
for ( let i = 0, l = this.quadrans; i < l; i++ ) {
			const color = colors[i % colors.length];

			// continue if is horizontal or vertical
			if( i % 2 === 0 ) continue;
			const edges = [...

Luego viene el método intersect, que solo acepta DisplayObject como parámetros.
Se le proporcionan todos los DisplayObject sobre los que el raycast deberá iterar.

ts
public intersects( worlds:Container3d[] ) {
		const { rays, quadrans, intersectedMap, intersectedObjectsMap, closestMap } = this;

		intersectedMap.clear();
		intersectedObjectsMap.clear();
		closestMap.clear();

		for ( let i = 0, l = quadrans; i < l; i++ ) {
			const ray = rays[i];
			const b1 = ray.getBounds( true, this._cacheRectangle1 );
			for ( const object of worlds ) {
				const b2 = object.getBounds( true, this._cacheRectangle2 );
				const intersect = intersects( b1, b2 );
				if ( intersect ) {
					const rayshape = this.shapes[i];
					if ( rayshape.intersectsShape( b2 ) ) {
						intersectedMap.set( i, ( intersectedMap.get( i ) ?? [] ).concat( object ) );
						intersectedObjectsMap.set( object, ( intersectedObjectsMap.get( object ) ?? [] ).concat( i ) );
					}
				}
			}
		}

También tuve que adaptar una función de PixiJS para detectar intersecciones y recopilar datos adicionales.
El código se presenta a continuación, no difiere significativamente del método original.

ts
/** return the intersection between two rectangles if any */
function intersects( source:Rectangle, other:Rectangle ) {
	let x0_1 = source.x < other.x ? other.x : source.x;
	let x1_1 = source.right > other.right ? other.right : source.right;
	if ( x1_1 <= x0_1 ) {
		return null;
	}
	let y0_1 = source.y < other.y ? other.y : source.y;
	let y1_1 = source.bottom > other.bottom ? other.bottom : source.bottom;
	if ( y1_1 <= y0_1 ) {
		return null;
	}

	// Compute the intersection distance
	const dx = x0_1 - x1_1;
	const dy = y0_1 - y1_1;
	const distance = Math.sqrt( dx * dx + dy * dy );

	// Return the intersection details
	return {
		x: x0_1,
		y: y0_1,
		x2: x1_1,
		width: x1_1 - x0_1,
		height: y1_1 - y0_1,
		distance: distance,
		inRatioXY: Math.abs( dx / dy ),
	};
}

Finalmente, una vez que Pixi ha detectado las intersecciones entre dos objetos, es posible refinar la detección local para verificar si nuestros segmentos diagonales tocan los objetos.

Nota de optimización:

Los objetos del entorno utilizan bounds cuadrados clásicos.
De hecho, con varios miles de entidades, una detección de colisiones basada en todos los segmentos sin una estructura optimizada causaría problemas de rendimiento muy serios.
Probablemente sería preferible usar web workers o shaders para optimizar este tipo de cálculo, en lugar de que lo gestione la CPU.

Por eso, solo las diagonales del DisplayObject raycaster gestionarán la detección de colisiones poligonales, ofreciendo así una ganancia de precisión del 50 %.
Para alcanzar el 100 % de precisión, los objetos del entorno también tendrían que ser polígonos, lo cual no es indispensable para mi motor actual.
Con la excepción quizás de las vallas diagonales, que podrían potencialmente plantear un problema...
el futuro lo dirá.

Este método IntersectsShape deberá, por lo tanto, iterar sobre cada uno de los puntos del vértice para verificar si estos puntos se encuentran dentro de los bounds de los DisplayObject.

ts
intersectsShape( rec:Rectangle ) {
		const edges = this.edges;

		for ( let i = 0; i < edges.length; i++ ) {
			const edge = edges[i];
			const point = edge.intersectsRectangle( rec );
			if ( point ) {
				return true;
			}
		}

		return false;
	}

class Segment {
	public p1: Point;
	public p2: Point;
	constructor( p1 = new Point(), p2 = new Point() ) {
		this.p1 = p1;
		this.p2 = p2;
	}

	intersects( edge: Segment, asSegment = true, point = new Point() ) {
		const a = this.p1;
		const b = this.p2;
		const e = edge.p1;
		const f = edge.p2;

		const a1 = b.y - a.y;
		const a2 = f.y - e.y;
		const b1 = a.x - b.x;
		const b2 = e.x - f.x;

		const c1 = ( b.x * a.y ) - ( a.x * b.y );
		const c2 = ( f.x * e.y ) - ( e.x * f.y );
		const denom = ( a1 * b2 ) - ( a2 * b1 );

		if ( denom === 0 ) {
			return null;
		}

		point.x = ( ( b1 * c2 ) - ( b2 * c1 ) ) / denom;
		point.y = ( ( a2 * c1 ) - ( a1 * c2 ) ) / denom;

		if ( asSegment ) {
			const uc = ( ( f.y - e.y ) * ( b.x - a.x ) - ( f.x - e.x ) * ( b.y - a.y ) );
			const ua = ( ( ( f.x - e.x ) * ( a.y - e.y ) ) - ( f.y - e.y ) * ( a.x - e.x ) ) / uc;
			const ub = ( ( ( b.x - a.x ) * ( a.y - e.y ) ) - ( ( b.y - a.y ) * ( a.x - e.x ) ) ) / uc;

			if ( ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1 ) {
				return point;
			} else {
				return null;
			}
		}

		return point;
	}

	intersectsRectangle( rect: Rectangle ) {
		const rectEdges = [ //TODO: will need optimize with a cache pool of points
			new Segment( new Point( rect.left, rect.top ), new Point( rect.right, rect.top ) ),
			new Segment( new Point( rect.right, rect.top ), new Point( rect.right, rect.bottom ) ),
			new Segment( new Point( rect.right, rect.bottom ), new Point( rect.left, rect.bottom ) ),
			new Segment( new Point( rect.left, rect.bottom ), new Point( rect.left, rect.top ) )
		];

		for ( const rectEdge of rectEdges ) {
			if ( this.intersects( rectEdge, true ) ) {
				return true;
			}
		}
		return false;
	}
}

Resultado final

El método segmentIntersects es donde se realizan los cálculos más complejos.
Me tomó dos días de intenso trabajo para hacerlo funcional, pero el resultado es muy satisfactorio.
Como se puede ver en este gif, ahora puedo interactuar con mi entorno y asociarle etiquetas e información gracias al Raycasting.

Esta sencilla herramienta ofrece múltiples funcionalidades interesantes para explotar.