Implémentation d'un Raycaster dans PixiJS avec une Détection des Collisions de Vertex

Introduction

Un défi de taille que j'ai relevé : implémenter une fonctionnalité essentielle à la bonne gestion des collisions dans mon moteur de jeu.

Contrairement à la plupart des moteurs de jeu qui utilisent des vecteurs, PixiJS gère uniquement les bounds sous forme de projections rectangulaires.
Si cela n'est pas problématique en 2D, cette approche reste très limitée pour les besoins d'un jeu.
L'image ci-dessus illustre le comportement d'un raycast sur les bounds de nos objets.

Le problème

Cependant, en 3D, cette approche pose un problème significatif.
Lorsqu'un DisplayObject subit une rotation, son bounds demeure un simple rectangle statique.

Voici un exemple :

J'ai donc dû consacrer plusieurs jours à l'étude des mathématiques et de la trigonométrie pour implémenter cette fonctionnalité.

Cette fonctionnalité sera essentielle pour qu'un acteur puisse percevoir son environnement et interagir avec les objets en fonction de leur distance et de leur hauteur.
Ce raycast servira également au système de FOW (Fog of War), affichant certaines portions de la carte et des éléments en fonction des collisions qu'il détecte.

Il s'agit d'un sujet que je n'aborde que sommairement, car il est très complexe.
J'espère néanmoins que cet article pourra vous inspirer pour votre propre projet.

Intégrations

Afin de simplifier mon approche, j'ai créé une Class Helper au sein de mon architecture.
Ces Class Helper sont stockées dans des fichiers `.h.ts` et exportent exclusivement des objets 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[] = [];
}

L'initialisation construit le nombre de segments indiqué en paramètre.
Dans mon cas, un quadrant de 8 segments s'est avéré plus que suffisant.
Cette configuration facilite également le débogage, car elle permet d'assigner 8 couleurs distinctes à ces segments.

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 );

Il convient de noter la création des points qui servent de segments.
Normalement, seuls les points des diagonales seraient nécessaires, car un rectangle ne présente pas d'angle mort sur ses axes horizontal et vertical.
Il est donc possible de les ignorer en fonction du pourcentage du quadrant, ce qui permet de sauter les rayons verticaux et horizontaux pour générer des polygones uniquement sur les 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 = [...

Vient ensuite la méthode intersect, qui accepte uniquement des DisplayObject en paramètres.
On lui fournit tous les DisplayObject sur lesquels le raycast devra itérer.

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 ) );
					}
				}
			}
		}

J'ai également dû adapter une fonction de PixiJS pour détecter les intersections et collecter des données supplémentaires.
Le code est présenté ci-dessous, il ne diffère pas significativement de la méthode d'origine.

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 ),
	};
}

Enfin, une fois que Pixi a détecté les intersections entre deux objets, il est possible d'affiner la détection locale pour vérifier si nos segments diagonaux touchent les objets.

Mémo d'optimisation :

Les objets de l'environnement utilisent des bounds carrés classiques.
En effet, avec plusieurs milliers d'entités, une détection de collisions basée sur tous les segments sans une structure optimisée entraînerait de très sérieux problèmes de performance.
Il serait probablement préférable d'utiliser des web workers ou des shaders pour optimiser ce type de calcul, plutôt que de le faire gérer par le CPU.

C'est pourquoi seules les diagonales du DisplayObject raycaster géreront la détection de collision polygonale, offrant ainsi un gain de précision de 50 %.
Pour atteindre 100 % de précision, il faudrait que les objets de l'environnement soient également des polygones, ce qui n'est pas indispensable pour mon moteur actuel. À l'exception peut-être des clôtures diagonales, qui pourraient potentiellement poser problème...
l'avenir nous le dira.

Cette méthode IntersectsShape devra donc itérer sur chacun des points du vertex pour vérifier si ces points se trouvent à l'intérieur des bounds des 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;
	}
}

Rendu final

La méthode segmentIntersects est celle où sont effectués les calculs les plus complexes.
Il m'a fallu deux jours de travail intense pour la rendre fonctionnelle, mais le résultat est très satisfaisant.
Comme on peut le constater dans ce gif, je peux désormais interagir avec mon environnement et y associer des tags et des informations grâce au Raycasting.

Ce simple outil offre de multiples fonctionnalités intéressantes à exploiter.