Реализация Raycaster в PixiJS с обнаружением столкновений Vertex

Введение

Значительная задача, которую я выполнил: реализовать функцию, необходимую для правильного управления столкновениями в моем игровом движке.

В отличие от большинства игровых движков, которые используют векторы, PixiJS обрабатывает bounds только в виде прямоугольных проекций. Если в 2D это не является проблемой, то для нужд игры такой подход остается очень ограниченным. Изображение выше иллюстрирует поведение raycast на bounds наших объектов.

Проблема

Однако в 3D этот подход создает серьезную проблему. Когда DisplayObject поворачивается, его bounds остается простым статичным прямоугольником.

Вот пример:

Поэтому мне пришлось потратить несколько дней на изучение математики и тригонометрии, чтобы реализовать эту функциональность.

Эта функция будет иметь решающее значение для того, чтобы актер мог воспринимать свое окружение и взаимодействовать с объектами в зависимости от их расстояния и высоты. Этот raycast также будет использоваться системой FOW (Туман войны), отображая определенные участки карты и элементы в зависимости от обнаруженных им столкновений.

Это очень сложная тема, которую я затрагиваю лишь поверхностно. Тем не менее, я надеюсь, что эта статья сможет вдохновить вас на ваш собственный проект.

Интеграции

Чтобы упростить свой подход, я создал Class Helper в рамках своей архитектуры. Эти Class Helper хранятся в файлах `.h.ts` и экспортируют исключительно объекты 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[] = [];
}

Инициализация создает количество сегментов, указанное в качестве параметра. В моем случае квадранта из 8 сегментов оказалось более чем достаточно. Эта конфигурация также облегчает отладку, поскольку позволяет присваивать этим сегментам 8 различных цветов.

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

Следует отметить создание точек, которые служат сегментами. Обычно нужны только точки диагоналей, поскольку прямоугольник не имеет мертвых зон на своих горизонтальной и вертикальной осях. Поэтому можно игнорировать их в зависимости от процента квадранта, что позволяет пропускать вертикальные и горизонтальные лучи для генерации полигонов только по диагоналям.

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

Далее идет метод intersect, который принимает только DisplayObject в качестве параметров. Мы передаем ему все DisplayObject, по которым raycast должен будет итерировать.

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

Мне также пришлось адаптировать функцию PixiJS для обнаружения пересечений и сбора дополнительных данных. Код представлен ниже, он не сильно отличается от исходного метода.

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

Наконец, после того как Pixi обнаружил пересечения между двумя объектами, можно уточнить локальное обнаружение, чтобы проверить, касаются ли наши диагональные сегменты объектов.

Заметки по оптимизации:

Объекты окружения используют классические квадратные bounds. Действительно, при наличии нескольких тысяч сущностей обнаружение столкновений, основанное на всех сегментах без оптимизированной структуры, привело бы к очень серьезным проблемам с производительностью. Вероятно, было бы предпочтительнее использовать web workers или shaders для оптимизации такого рода вычислений, а не возлагать их на CPU.

Вот почему только диагонали DisplayObject raycaster будут обрабатывать обнаружение полигональных столкновений, что дает прирост точности в 50%. Для достижения 100% точности необходимо, чтобы объекты окружения также были полигонами, что не является обязательным для моего текущего движка. За исключением, возможно, диагональных ограждений, которые потенциально могут вызвать проблемы... будущее покажет.

Таким образом, этот метод IntersectsShape должен будет перебирать каждую точку vertex, чтобы проверить, находятся ли эти точки внутри 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;
	}
}

Финальный рендер

Метод segmentIntersects — это то место, где выполняются самые сложные вычисления. Мне потребовалось два дня интенсивной работы, чтобы сделать его функциональным, но результат очень удовлетворительный. Как видно на этом gif, я теперь могу взаимодействовать со своим окружением и связывать с ним теги и информацию благодаря Raycasting.

Этот простой инструмент предлагает множество интересных функций для использования.