Haga su juego Explotar con efectos de partículas y árboles cuaternarios

Spanish (Español) translation by Elías Nicolás (you can also view the original English article)

¿Así que quieres explosiones, fuego, balas o hechizos mágicos en tu juego? Los sistemas de partículas producen grandes efectos gráficos sencillos para incrementar un poco su juego. Usted puede wow el jugador aún más haciendo partículas interactuar con su mundo, rebotando fuera del medio ambiente y otros jugadores. En este tutorial vamos a implementar algunos efectos de partículas simples, ya partir de aquí vamos a pasar a hacer que las partículas reboten fuera del mundo de ellos.

También optimizaremos las cosas implementando una estructura de datos llamada árbol cuaternario. Arbol cuaternario le permiten comprobar las colisiones mucho más rápido de lo que podría sin uno, y son fáciles de implementar y entender.

Nota: Aunque este tutorial está escrito usando HTML5 y JavaScript, debería ser capaz de usar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos.

Para ver las demostraciones en el artículo, asegúrese de leer este artículo en Chrome, Firefox, IE 9 o cualquier otro navegador que admita HTML5 y Canvas.

Observe cómo las partículas cambian de color a medida que caen, y cómo rebotan en las formas.

¿Qué es un sistema de partículas?

Un sistema de partículas es una forma sencilla de generar efectos como el fuego, el humo y las explosiones.

Creas un emisor de partículas, y esto lanza pequeñas "partículas" que puedes mostrar como píxeles, cajas o pequeños mapas de bits. Siguen la física newtoniana simple y cambian de color a medida que se mueven, dando como resultado efectos dinámicos, personalizables y gráficos.

El inicio de un sistema de partículas

Nuestro sistema de partículas tendrá algunos parámetros personalizables:

Cuántas partículas muestra cada segundo.
Cuánto tiempo una partícula puede "vivir".
Los colores que cada partícula tendrá en la transición .
La posición y el ángulo de las partículas que se generan.
¿Qué tan rápido irán las partículas cuando se reproducen?
¿Cuánta gravedad deben afectar las partículas?

Si cada partícula produjera exactamente lo mismo, sólo tendríamos una corriente de partículas, no un efecto de partícula. Permítanos también permitir la variabilidad configurable. Esto nos da algunos parámetros más para nuestro sistema:

Cuánto puede variar su ángulo de lanzamiento.
Cuánto puede variar su velocidad inicial.
Cuánto de su vida puede variar.

Terminamos con una clase del sistema de partículas que comienza así:


function ParticleSystem(params) {
  //Default parameters
	this.params = {
		//Where particles spawn from
		pos : new Point(0, 0),
		
		//How many particles spawn every second
		particlesPerSecond : 100,

		//How long each particle lives (and how much this can vary)
		particleLife: 0.5,
		lifeVariation: 0.52,

		//The gradient of colors the particle will travel through
		colors: new Gradient([ new Color(255, 255, 255, 1), new Color(0, 0, 0, 0) ]),

		//The angle the particle will fire off at (and how much this can vary)
		angle: 0,
		angleVariation: Math.PI * 2,

		//The velocity range the particle will fire off at
		minVelocity : 20,
		maxVelocity : 50,

		//The gravity vector applied to each particle
		gravity: new Point(0, 30.8),

		//An object to test for collisions against, and bounce damping factor
		//for said collisions
		collider : null,
		bounceDamper: 0.5
	};

	//Override our default parameters with supplied parameters
	for (var p in params) {
		this.params[p] = params[p];
	}

	this.particles = [];
}

Haciendo el flujo del sistema

Cada marco necesitamos hacer tres cosas: crear nuevas partículas, mover las partículas existentes, y dibujar las partículas.

Creación de partículas

Crear partículas es bastante simple. Si estamos creando 300 partículas por segundo, y ha sido 0.05 segundos desde el último cuadro, creamos 15 partículas para el marco (que promedia a 300 por segundo).

Debemos tener un bucle simple que se parece a esto:


var newParticlesThisFrame = this.params.particlesPerSecond * frameTime;
for (var i = 0; i < newParticlesThisFrame; i++) {
	this.spawnParticle((1.0 + i) / newParticlesThisFrame * frameTime);
}

Nuestra función spawnParticle() crea una nueva partícula basada en los parámetros de nuestro sistema:


ParticleSystem.prototype.spawnParticle = function(offset) {
	//We want to fire the particle off at a random angle and a random velocity
	//within the parameters dictated for this system
	var angle = randVariation(this.params.angle, this.params.angleVariation);
	var speed = randRange(this.params.minVelocity, this.params.maxVelocity);
	var life = randVariation(this.params.particleLife, this.params.particleLife * this.params.lifeVariation);

	//Our initial velocity will be moving at the speed we chose above in the 
	//direction of the angle we chose
	var velocity = new Point().fromPolar(angle, speed);

	//If we created every single particle at "pos", then every particle 
	//created within one frame would start at the same place.  
	//Instead, we act as if we created the particle continuously between 
	//this frame and the previous frame, by starting it at a certain offset
	//along its path.
	var pos = this.params.pos.clone().add(velocity.times(offset));

	//Contruct a new particle object from the parameters we chose
	this.particles.push(new Particle(this.params, pos, velocity, life));
};

Elegimos nuestra velocidad inicial desde un ángulo y velocidad aleatorios. A continuación, utilizamos el método fromPolar() para crear un vector de velocidad cartesiana a partir de la combinación ángulo / velocidad.

La trigonometría básica produce el método fromPolar:


Point.prototype.fromPolar = function(ang, rad) {
	this.x = Math.cos(ang) * rad;
	this.y = Math.sin(ang) * rad;

	return this;
};

Si necesita un poco de trigonometría un poco, toda la trigonometría que estamos utilizando se deriva del Unit Circle.

Movimiento de Partículas

El movimiento de partículas sigue las leyes newtonianas básicas. Las partículas tienen una velocidad y posición. Nuestra velocidad actúa sobre la fuerza de la gravedad, y nuestra posición cambia proporcionalmente a la gravedad. Finalmente necesitamos seguir la vida de cada partícula, de lo contrario las partículas nunca morirían, terminaríamos teniendo demasiadas y el sistema se pararía. Todas estas acciones se producen proporcionalmente al tiempo entre fotogramas.


Particle.prototype.step = function(frameTime) {
	this.velocity.add(this.params.gravity.times(frameTime));
	this.pos.add(this.velocity.times(frameTime));
	this.life -= frameTime;
};

Dibujo de las Partículas

Finalmente tenemos que dibujar nuestras partículas. La forma en que implementa esto en su juego variará mucho de una plataforma a otra, y lo avanzado que desea que sea la representación. Esto puede ser tan simple como colocar un solo píxel de color, para mover un par de triángulos para cada partícula, dibujado por un sombreado de GPU complejo.

En nuestro caso, aprovecharemos la API de lienzo para dibujar un pequeño rectángulo para la partícula.


Particle.prototype.draw = function(ctx, frameTime) {
	//No need to draw the particle if it is out of life.
	if (this.isDead())
		return;

	//We want to travel through our gradient of colors as the particle ages
	var lifePercent = 1.0 - this.life / this.maxLife;
	var color = this.params.colors.getColor(lifePercent);
	
	//Set up the colors
	ctx.globalAlpha = color.a;
	ctx.fillStyle = color.toCanvasColor();

	//Fill in the rectangle at the particle's position
	ctx.fillRect(this.pos.x - 1, this.pos.y - 1, 3, 3);
};

La interpolación de color depende de si la plataforma que está utilizando proporciona una clase de color (o formato de representación), si proporciona un interpolador para usted y cómo desea abordar todo el problema. Escribí una clase pequeña del gradiente que permite la interpolación fácil entre los colores múltiples, y una clase pequeña del color que proporciona la funcionalidad para interpolar entre cualesquiera dos colores.


Color.prototype.interpolate = function(percent, other) {
	return new Color(
		this.r + (other.r - this.r) * percent,
		this.g + (other.g - this.g) * percent,
		this.b + (other.b - this.b) * percent,
		this.a + (other.a - this.a) * percent);
};


Gradient.prototype.getColor = function(percent) {
	//Floating point color location within the array
	var colorF = percent * (this.colors.length - 1);

	//Round down; this is the specified color in the array 
	//below our current color
	var color1 = parseInt(colorF);
	//Round up; this is the specified color in the array 
	//above our current color
	var color2 = parseInt(colorF + 1);

	//Interpolate between the two nearest colors (using above method)
	return this.colors[color1].interpolate(
			(colorF - color1) / (color2 - color1),
			this.colors[color2]
		);
};

¡Aquí está nuestro sistema de partículas en acción!

Rebote de Partículas

Como se puede ver en la demostración anterior, ahora tenemos algunos efectos básicos de partículas. Sin embargo, carecen de interacción con el entorno que los rodea. Para hacer que estos efectos formen parte de nuestro mundo de juego, vamos a hacer que reboten fuera de las paredes a su alrededor.

Para empezar, el sistema de partículas tomará ahora un colisionador como parámetro. Será tarea del colisionador decirle a una partícula si se ha estrellado contra cualquier cosa. El método step() de una partícula ahora se parece a esto:


Particle.prototype.step = function(frameTime) {
	//Save our last position
	var lastPos = this.pos.clone();

	//Move
	this.velocity.add(this.params.gravity.times(frameTime));
	this.pos.add(this.velocity.times(frameTime));


	//Can this particle bounce?
	if (this.params.collider) {
		
		//Check if we hit anything
		var intersect = this.params.collider.getIntersection(
					new Line(lastPos, this.pos)
				);
		if (intersect != null) {
			//If so, we reset our position, and update our velocity 
			//to reflect the collision
			this.pos = lastPos;
			this.velocity = intersect.seg.reflect(this.velocity).times(this.params.bounceDamper);
		}
	}

	this.life -= frameTime;
};

Ahora cada vez que la partícula se mueve, le preguntamos al colisionador si su trayectoria de movimiento ha "colisionado" a través del método getIntersection(). Si es así, reajustamos su posición (de modo que no esté dentro de lo que intersectó), y reflejamos la velocidad.

Una implementación básica de "colisionador" podría tener este aspecto:


//Takes a collection of line segments representing the game world
function Collider(lines) {
	this.lines = lines;
}

//Returns any line segment intersected by "path", otherwise null
Collider.prototype.getIntersection = function(path) {
	for (var i = 0; i < this.lines.length; i++) {
		var intersection = this.lines[i].getIntersection(path);
		if (intersection)
			return intersection;	
	}

	return null;
};

¿Notó un problema? Cada partícula necesita llamar a collider.getIntersection() y luego cada llamada getIntersection debe comprobar contra cada "pared" en el mundo. Si tiene 300 partículas (tipo de un número bajo) y 200 paredes en su mundo (no es razonable tampoco), está realizando 60.000 pruebas de intersección de líneas! Esto podría retrasar su juego, especialmente con más partículas (o mundos más complejos).

Detección más rápida de colisiones con árboles cuaternarios

El problema con nuestro colisionador simple es que comprueba cada pared para cada partícula. Si nuestra partícula está en el cuadrante de la parte superior derecha de la pantalla, no deberíamos perder el tiempo comprobando si se estrelló contra paredes que sólo están en la parte inferior o izquierda de la pantalla. Así que idealmente queremos recortar cualquier control de intersecciones fuera del cuadrante superior derecho:

Sólo comprobamos si hay colisiones entre el punto azul y las líneas rojas.

Eso es sólo una cuarta parte de los cheques! Ahora vamos más allá: si la partícula está en el cuadrante superior izquierdo del cuadrante superior derecho de la pantalla, sólo debemos comprobar aquellas paredes en el mismo cuadrante:

El Árbol cuaternario le permiten hacer exactamente esto! En lugar de probar contra todas las paredes, dividir paredes en los cuadrantes y sub-cuadrantes que ocupan, por lo que sólo hay que comprobar algunos cuadrantes. Puede pasar fácilmente de 200 cheques por partícula a sólo 5 o 6.

Los pasos para crear un árbol cuaternario son los siguientes:

Comience con un rectángulo que llena toda la pantalla.
Tome el rectángulo actual, cuente cuántas "paredes" caen dentro de él.
Si tiene más de tres líneas (puede elegir un número diferente), divida el rectángulo en cuatro cuadrantes iguales. Repita el paso 2 con cada cuadrante.
Después de repetir los pasos 2 y 3, se termina con un "árbol" de rectángulos, con ninguno de los rectángulos más pequeños que contienen más de tres líneas (o lo que usted eligió).

Construyendo un árbol cuaternario. Los números representan el número de líneas dentro del cuadrante, siendo el rojo demasiado alto y necesitando subdividirlo.

Para construir nuestro árbol cuaternario tomamos un conjunto de "muros" (segmentos de línea) como un parámetro, y si demasiados están contenidos dentro de nuestro rectángulo, subdividimos en rectángulos más pequeños, y el proceso se repite.


QuadTree.prototype.addSegments = function(segs) {
	for (var i = 0; i < segs.length; i++) {
		if (this.rect.overlapsWithLine(segs[i])) {
			this.segs.push(segs[i]);
		}
	}

	if (this.segs.length > 3) {
		this.subdivide();
	}
};

QuadTree.prototype.subdivide = function() {
	var w2 = this.rect.w / 2,
	    h2 = this.rect.h / 2,
	    x = this.rect.x,
	    y = this.rect.y;

	this.quads.push(new QuadTree(x, y, w2, h2));
	this.quads.push(new QuadTree(x + w2, y, w2, h2));
	this.quads.push(new QuadTree(x + w2, y + h2, w2, h2));
	this.quads.push(new QuadTree(x, y + h2, w2, h2));

	for (var i = 0; i < this.quads.length; i++) {
		this.quads[i].addSegments(this.segs);
	}

	this.segs = [];
};

Puede ver la clase completa del árbol cuaternario aquí:


/**
 * @constructor
 */
function QuadTree(x, y, w, h) {
	this.thresh = 4;
	this.segs = [];
	this.quads = [];

	this.rect = new Rect2D(x, y, w, h);
}

QuadTree.prototype.addSegments = function(segs) {
	for (var i = 0; i < segs.length; i++) {
		if (this.rect.overlapsWithLine(segs[i])) {
			this.segs.push(segs[i]);
		}
	}

	if (this.segs.length > this.thresh) {
		this.subdivide();
	}
};

QuadTree.prototype.getIntersection = function(seg) {
	if (!this.rect.overlapsWithLine(seg))
		return null;

	for (var i = 0; i < this.segs.length; i++) {
		var s = this.segs[i];
		var inter = s.getIntersection(seg);
		if (inter) {
			var o = {};
			return s;
		}
	}

	for (var i = 0; i < this.quads.length; i++) {
		var inter = this.quads[i].getIntersection(seg);
		if (inter)
			return inter;
	}

	return null;
};

QuadTree.prototype.subdivide = function() {
	var w2 = this.rect.w / 2,
	    h2 = this.rect.h / 2,
	    x = this.rect.x,
	    y = this.rect.y;

	this.quads.push(new QuadTree(x, y, w2, h2));
	this.quads.push(new QuadTree(x + w2, y, w2, h2));
	this.quads.push(new QuadTree(x + w2, y + h2, w2, h2));
	this.quads.push(new QuadTree(x, y + h2, w2, h2));

	for (var i = 0; i < this.quads.length; i++) {
		this.quads[i].addSegments(this.segs);
	}

	this.segs = [];
};

QuadTree.prototype.display = function(ctx, mx, my, ibOnly) {

	var inBox = this.rect.containsPoint(new Point(mx, my));

	ctx.strokeStyle = inBox ? '#FF44CC' : '#000000';

	if (inBox || !ibOnly) {
		ctx.strokeRect(this.rect.x, this.rect.y, this.rect.w, this.rect.h);
		for (var i = 0; i < this.quads.length; i++) {
			this.quads[i].display(ctx, mx, my, ibOnly);
		}
	}

	if (inBox) {
		ctx.strokeStyle = '#FF0000';
		for (var i = 0 ; i < this.segs.length; i++) {
			var s = this.segs[i];
			ctx.beginPath();
			ctx.moveTo(s.a.x, s.a.y);
			ctx.lineTo(s.b.x, s.b.y);
			ctx.stroke();
		}
	}
};

La prueba para la intersección con un segmento de línea se realiza de una manera similar. Para cada rectángulo hacemos lo siguiente:

Comience con el rectángulo más grande en el árbol cuaternario.
Compruebe si el segmento de línea intersecta o está dentro del rectángulo actual. Si no lo hace, no se moleste en hacer más pruebas en este camino.
Si el segmento de línea cae dentro del rectángulo actual o lo cruza, compruebe si el rectángulo actual tiene algún rectángulo hijo. Si lo hace, vuelva al Paso 2, pero usando cada uno de los rectángulos hijos.
Si el rectángulo actual no tiene rectángulos hijos, pero es un nodo hoja (es decir, sólo tiene segmentos de línea como hijos), pruebe el segmento de línea de destino con esos segmentos de línea. Si se trata de una intersección, devuelva la intersección. ¡Hemos terminado!

Buscando un árbol cuaternario. Comenzamos en el rectángulo más grande y buscamos pequeños y pequeños, hasta finalmente probar segmentos de línea individuales. Con el árbol cuaternario, sólo realizamos cuatro pruebas de rectángulo y dos pruebas de línea, en lugar de probar contra todos los 21 segmentos de línea. La diferencia sólo crece más dramática con conjuntos de datos más grandes.


QuadTree.prototype.getIntersection = function(seg) {
	if (!this.rect.overlapsWithLine(seg))
		return null;

	for (var i = 0; i < this.segs.length; i++) {
		var s = this.segs[i];
		var inter = s.getIntersection(seg);
		if (inter) {
			var o = {};
			return s;
		}
	}

	for (var i = 0; i < this.quads.length; i++) {
		var inter = this.quads[i].getIntersection(seg);
		if (inter)
			return inter;
	}

	return null;
};

Una vez que pasamos un objeto QuadTree a nuestro sistema de partículas como el "colisionador", obtenemos una búsqueda rápida. Echa un vistazo a la demostración interactiva a continuación - utilizar el ratón para ver qué segmentos de línea el quadtree necesitaría probar en contra!

Coloque el cursor sobre un (sub-)cuadrante para ver qué segmentos de línea contiene.

Alimento para el pensamiento

El sistema de partículas y el árbol cuaternario presentados en este artículo son sistemas de enseñanza rudimentarios. Algunas otras ideas que quizás quiera considerar al implementarlas usted mismo:

Es posible que desee mantener objetos además de segmentos de línea en el quadtree. ¿Cómo lo expandirías para incluir círculos? ¿Cuadrícula?
Es posible que desee una forma de recuperar objetos individuales (para notificarles que han sido golpeados por una partícula), mientras sigue recuperando segmentos reflectantes.
Las ecuaciones físicas sufren de discrepancias que las ecuaciones de Euler se acumulan con el tiempo con tasas de cuadros inestables. Si bien esto no suele importar para un sistema de partículas, ¿por qué no leer sobre las ecuaciones de movimiento más avanzadas? (Eche un vistazo a este tutorial, por ejemplo.)
Hay muchas maneras de almacenar la lista de partículas en la memoria. Un arreglo es el más simple pero puede no ser la mejor opción dado que las partículas se quitan a menudo del sistema y otras nuevas se insertan a menudo. Una lista enlazada puede encajar mejor, pero tiene mala localidad de caché. La mejor representación de las partículas puede depender del marco o el lenguaje que está utilizando.