Implementacja Raycastera w PixiJS z Wykrywaniem Kolizji Vertex

Wprowadzenie

Podjąłem się sporego wyzwania: zaimplementowania kluczowej funkcji do prawidłowego zarządzania kolizjami w moim silniku gry.

W przeciwieństwie do większości silników gier, które używają wektorów, PixiJS obsługuje jedynie bounds w postaci prostokątnych rzutów.
O ile nie stanowi to problemu w 2D, o tyle to podejście jest bardzo ograniczone w kontekście potrzeb gry.
Powyższy obrazek ilustruje zachowanie raycasta na bounds naszych obiektów.

Problem

Jednakże w 3D to podejście stanowi znaczący problem.
Gdy DisplayObject obraca się, jego bounds pozostaje prostym, statycznym prostokątem.

Oto przykład:

Dlatego musiałem poświęcić kilka dni na studiowanie matematyki i trygonometrii, aby zaimplementować tę funkcjonalność.

Ta funkcja będzie kluczowa, aby aktor mógł postrzegać swoje otoczenie i wchodzić w interakcje z obiektami w zależności od ich odległości i wysokości.
Ten raycast posłuży również systemowi FOW (Fog of War), wyświetlając określone części mapy i elementy w zależności od wykrytych kolizji.

Jest to temat, który poruszam jedynie pobieżnie, ponieważ jest bardzo złożony.
Mam jednak nadzieję, że ten artykuł zainspiruje Cię do własnego projektu.

Integracje

Aby uprościć moje podejście, stworzyłem Class Helper w ramach mojej architektury.
Te Class Helper są przechowywane w plikach `.h.ts` i eksportują wyłącznie obiekty 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[] = [];
}

Inicjalizacja tworzy liczbę segmentów wskazaną w parametrze.
W moim przypadku kwadrant składający się z 8 segmentów okazał się więcej niż wystarczający.
Taka konfiguracja ułatwia również debugowanie, ponieważ pozwala na przypisanie 8 różnych kolorów do tych segmentów.

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

Warto zauważyć tworzenie punktów, które służą jako segmenty.
Normalnie, potrzebne byłyby tylko punkty przekątnych, ponieważ prostokąt nie ma martwego punktu na osiach poziomej i pionowej.
Możliwe jest więc ich ignorowanie w zależności od procentu kwadrantu, co pozwala pominąć promienie pionowe i poziome, aby generować poligony tylko na przekątnych.

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 = [...

Następnie pojawia się metoda intersect, która akceptuje w parametrach wyłącznie DisplayObject.
Dostarczamy jej wszystkie DisplayObject, na których raycast będzie musiał iterować.

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

Musiałem również dostosować funkcję z PixiJS, aby wykrywać przecięcia i zbierać dodatkowe dane.
Kod przedstawiono poniżej; nie różni się on znacząco od oryginalnej metody.

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

Wreszcie, gdy Pixi wykryje przecięcia między dwoma obiektami, możliwe jest dopracowanie lokalnego wykrywania, aby sprawdzić, czy nasze ukośne segmenty dotykają obiektów.

Notatka dotycząca optymalizacji:

Obiekty środowiskowe wykorzystują klasyczne kwadratowe bounds.
Rzeczywiście, przy wielu tysiącach obiektów, wykrywanie kolizji oparte na wszystkich segmentach bez zoptymalizowanej struktury prowadziłoby do bardzo poważnych problemów z wydajnością.
Prawdopodobnie lepiej byłoby użyć web workers lub shaders, aby zoptymalizować ten typ obliczeń, zamiast zlecać je do zarządzania CPU.

Dlatego tylko przekątne DisplayObject raycastera będą obsługiwać wykrywanie kolizji poligonalnych, oferując w ten sposób 50% wzrost precyzji.
Aby osiągnąć 100% precyzji, obiekty środowiskowe musiałyby również być poligonami, co nie jest niezbędne dla mojego obecnego silnika.
Z wyjątkiem być może ukośnych ogrodzeń, które potencjalnie mogłyby stanowić problem...
przyszłość pokaże.

Ta metoda IntersectsShape będzie musiała więc iterować po każdym z punktów vertex, aby sprawdzić, czy te punkty znajdują się wewnątrz bounds 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;
	}
}

Końcowy render

Metoda segmentIntersects to ta, w której wykonywane są najbardziej złożone obliczenia.
Uruchomienie jej zajęło mi dwa dni intensywnej pracy, ale wynik jest bardzo zadowalający.
Jak widać na tym gifie, mogę teraz wchodzić w interakcje z moim otoczeniem i przypisywać tagi oraz informacje dzięki Raycastingowi.

To proste narzędzie oferuje wiele interesujących funkcji do wykorzystania.