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.