Cuando de detección de colisiones se trata, nos encontramos ante una amplia gama de algoritmos que realizan dicha tarea.
Sin embargo, el problema que muchos algoritmos de deteccion de colisiones enfrentan, es la detección de colisiones con muchos objetos en escena. La mayoría de los algoritmos ofrecen un pobre rendimiento frente a dicha situación.
El algoritmo Grid-based collision ofrece una solución eficiente para éste problema y en combinación con Per-pixel, logramos detectar colisiones precisas al maximo rendimiento.
Grid-based collision explicado.
En la mayoría de los juegos la detección de colisiones forma parte de los cimientos de tu video juego. Hay situaciones en las que es mas eficiente encerrar el objeto en un cuadrilatero y utilizar deteccion de colisiones con rectangulos para evaluar si existe colision o no. (método utilizado en Programar un videojuego en Flash)
Como regla de oro, si tu objeto tiene una forma irregular, como la de una estrella es buena idea utilizar Per-Pixel collision, que evalua las colisiones pixel por pixel, generando a una detección de colisiones exacta. El problema de per-pixel collision es que limita el tamaño de tus imagenes a un número determinado de pixeles; ya que imagenes relativamente grandes, conllevan a cientos de miles de comparaciones que se encuentran negativamente relacionadas con el rendimiento de tu video juego.
Aun para empeorar el escenario, todos estos algoritmos tienen un gran problema en comun; el manejo de cantidades masivas de objetos en escena. Un juego sencillo, como el que programamos en el tutorial Como programar un videjuego en Flash, puede llegar a tener cien objetos en pantalla y si observan el codigo; constantemente se esta monitoreando si existe una colision o no entre el contenedor y los objetos que caen del techo. Para juegos mas grandes, esto produce un problema, ya que incluso monitorea si existe collision entre dos objetos que no hay manera alguna de que en un determinado momento se encuentren colisionando.
En otras palabras, porque habria de verificar si existe una colision entre dos objetos que se encuentran en los extremos de la pantalla, ya que no existe forma alguna de que estos objetos colisionen? Es aqui donde entra grid-based collision, cuya escencia basicamente es cuadricular la escena (de ahi grid-based) y evaluar si existe una collision solo con los objetos que se encuentran alrededor de una determinada entidad (un personaje por ejemplo), de esta manera podemos reducir millones de comparaciones innecesarias con otros métodos, a solo unas cuantas miles de comparaciones utilizando grid-based collision.
Grid-based + per-pixel collision:
[kml_flashembed publishmethod="static" fversion="8.0.0" movie="http://www.alanchavez.com/Tutoriales/Videojuegos/Colisiones-Avanzadas/grid-based-collision.swf" width="400" height="300" targetclass="flashmovie"]
[/kml_flashembed]
Requisitos
- Adobe Flash CS3 o superior.
- Conocimientos de Programacion Orientada a Objetos.
- Conocimiento mínimo sobre operaciones matriciales.
Preparando el ambiente de trabajo
- Crea dos archivos diferentes colisiones.fla y colision.as. Si tienes dudas de como crearlos, visita el post clases externas as3 en flash.
- Dibuja una estrella en un clip de pelicula vacío y exportalo a ActionScript con el nombre de clase Estrella. Sigue el enlace para aprender como exportar clips de pelicula a ActionScript 3.
El código
Este código copia y pegalo en el archivo colision.as
package
{
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.display.MovieClip;
import flash.display.BitmapData;
import flash.display.Bitmap;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.filters.GlowFilter;
public class GridCollision extends Sprite
{
private const CUADRICULA_TAMANO:Number = 32;
private var _estrellas:Array;
private var _cuadricula:Array;
private var _numEstrellas:int = 100;
private var _comparacionesRealizadas:int = 0;
private var bmpd1:BitmapData;
private var bmp1:Bitmap;
private var bmpd2:BitmapData;
private var bmp2:Bitmap;
public function GridCollision()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;
crearEstrellas();
crearCuadricula();
dibujarCuadricula();
enlazarEstrellasACuadricula();
evaluarCuadricula();
trace(_comparacionesRealizadas);
}
private function crearEstrellas():void
{
_estrellas = new Array();
for (var i:int = 0; i< _numEstrellas; i++)
{
//crea una estrella y la agrega al display list.
// y al array _estrellas
var estrella:Estrella = new Estrella();
estrella.x = Math.random() * stage.stageWidth;
estrella.y = Math.random() * stage.stageHeight;
//addChild(estrella);
_estrellas.push(estrella);
}
}
private function crearCuadricula():void
{
_cuadricula = new Array();
//ancho de la escena / tamano de la cuadricula = numero de columnas
for (var i:int = 0; i<=stage.stageWith/CUADRICULA_TAMANO;i++) {
_cuadricula[i] = new Array();
//alto de la escena / tamano de la cuadricula = numero de filas
for (var j:int = 0; j<=stage.stageHeight/CUADRICULA_TAMANO;j++) {
_cuadricula[i][j] = new Array();
}
}
}
private function dibujarCuadricula():void
{
//dibuja lineas para indicar filas y columnas
graphics.lineStyle(0,.5);
for (var i:int = 0; i<=stage.stageWidth; i+=CUADRICULA_TAMANO)
{
graphics.moveTo(i,0);
graphics.lineTo(i,stage.stageHeight);
}
for (i = 0; i<=stage.stageHeight; i+= CUADRICULA_TAMANO)
{
graphics.moveTo(0,i);
graphics.lineTo(stage.stageWidth,i);
}
}
private function enlazarEstrellasACuadricula():void
{
for (var i:int = 0; i<_numEstrellas; i++)
{
//dividir la posicion por el tamano de la cuadricula
//nos dice en que fila y columna esta la estrella
var estrella:Estrella = _estrellas[i] as Estrella;
var xpos:int = Math.floor(estrella.x / CUADRICULA_TAMANO);
var ypos:int = Math.floor(estrella.y / CUADRICULA_TAMANO);
_cuadricula[xpos][ypos].push(estrella);
}
}
private function evaluarCuadricula():void
{
//pasar atraves de fila y columna de la cuadricula
for (var i:int = 0; i<_cuadricula.length; i++)
{
for (var j:int = 0; j<_cuadricula[i].length; j++)
{
//examinar todos los objetos en la primera celda uno contra otro
evaluarCelda(i,j);
evaluarCeldas(i, j, i+1, j);
evaluarCeldas(i, j, i-1, j+1);
evaluarCeldas(i, j, i, j+1);
evaluarCeldas(i, j, i+1, j+1);
}
}
}
private function evaluarCelda(x:int, y:int):void
{
//verifica todas las pelotas en una celda una con la otra
var celda:Array = _cuadricula[x][y] as Array;
for (var i:int = 0; i< celda.length - 1; i++)
{
var estrellaA:Estrella = celda[i] as Estrella;
for (var j:int = i + 1; j++) {
var estrellaB:Estrella = celda[j] as Estrella;
evaluarColision(estrellaA,estrellaB);
}
}
}
private function evaluarCeldas(x1:int,y1:int,x2:int,y2:int):void
{
//asegurarse que la segunda celda existe
if (x2 < 0) return; if (x2 >= _cuadricula.length) return;
if (y2 >= _cuadricula[x2].length) return;
var celda0:Array = _cuadricula[x1][y1] as Array;
var celda1:Array = _cuadricula[x2][y2] as Array;
//verifica todas las pelotas en una celda contra las demas en otra celda
for (var i:int = 0; i {
var estrellaA:Estrella = celda0[i] as Estrella;
for (var j:int = 0; j {
var estrellaB:Estrella = celda1[j] as Estrella;
evaluarColision(estrellaA,estrellaB);
}
}
}
private function evaluarColision(estrellaA:Estrella, estrellaB:Estrella):void
{
_comparacionesRealizadas++;
bmpd1 = new BitmapData(100,100,true,0);
bmpd1.draw(estrellaA, new Matrix(1,0,0,1,32,32));
bmp1 = new Bitmap(bmpd1);
bmp1.x = estrellaA.x;
bmp1.y = estrellaA.y;
bmpd2 = new BitmapData(100,100,true,0);
bmpd2.draw(estrellaB, new Matrix(1,0,0,1,32,32));
bmp2 = new Bitmap(bmpd2);
bmp2.x = estrellaB.x;
bmp2.y = estrellaB.y;
addChild(bmp1);
addChild(bmp2);
if(bmpd1.hitTest(new Point(bmp1.x,bmp1.y),255,bmpd2,new Point(bmp2.x,bmp2.y),255))
{
bmp1.filters = [new GlowFilter()];
bmp2.filters = [new GlowFilter()];
}
}
}
}
Grid-based + Per-pixel collision a detalle
Colisión pixel a pixel
Utilizamos el método de pixel-a-pixel que viene incluído en Flash, que basicamente compara dos objetos BitmapData y determin si los pixeles de dichos objetos colisionan.
En principio, este método parece sencillo y sin mayor complejidad, pero la verdadera complejidad aparece cuando tenemos un objeto BitmapData con un mapa de bits transparente, y una figura sobre el mapa de bits, ya que tenemos que encontrar la colisión con la figura, y no con el mapa de bits.
Imaginemos este método, como dos hojas de papel transparente. Tomamos un marcador negro y dibujamos una estrella en cada hoja. Para nosotros, una colisión entre las estrellas solo ocurre cuando un borde de la estrella A, toca un borde de la estrella B, sin importar que las hojas se encuentren sobrepuestas. La escencia de la colisión pixel a pixel es la misma. Nuestro objeto BitmapData es la hoja transparente, y el mapa de bits contiene la forma y los colores de las estrellas. Un BitmapData, no es mas que un arreglo de bits rectangular y cuando creamos un objeto BitmapData, tenemos que especificar en el constructor, si el objeto soporta transparencia o no.
new BitmapData(ancho,alto,transparente,color);
El tercer parametro, es un valor Booleano (true/false,0/1) que establece la opcion de transparencia.
Si lo inicializamos como falso, el mapa de bits será completamente opaco y si se agrega al display list, será dibujado como un rectangulo opaco, del color especificado en el constructor.
Cuando el objeto es incializado como opaco (transparente = false), estamos indicando que cada pixel tendrá numeros de 24 bits en la forma 0xRRGGBB. Cada letra representa un Canal (Rojo =R, Verde = G, Azul = B) y cada canal toma un numero hexadecimal de dos digitos con un rango de valores desde 00 (0) a FF (255)
Ejemplo:
- 0xFF0000 - Rojo (Canal rojo lleno, y los canales azul y verdes vacíos).
- 0x00FF00 - Verde (Canal verde lleno, canales rojos y azul vacíos).
- 0x0000FF - Azul (Canal azul lleno, canales rojo y verde vacíos).
En un objeto BitmapData con la transparencia inicializada como true, estamos indicando que queremos pixeles de 32 bits con la forma 0xAARRGGBB, dicha forma agrega un canal adicional, conocido como canal alfa que se encarga de establecer el nivel de transparencia de nuestro mapa de bits. De igual forma, este es canal toma un número hexadecimal de 2 dígitos.
Ejemplo:
- 0x00FF0000 - Color rojo completamente transparente (alfa = 0)
- 0xFFFF0000 - Color rojo, completamente opaco (alfa = 255)
Entendiendo el funcionamiento del objeto BitmapData, podemos pasar al funcionamiento de detección de colisiones pixel a pixel.
La imagen de una estrella es un excelente ejemplo, y comunmente usado en la literatura, para probar este método debido a la naturaleza irregular de su forma. En otros lenguajes de programación, colisiones pixel a pixel es mas complicado. Los chicos de Adobe han hecho un gran trabajo al incorporar en la clase BitmapData un método llamado hitTest y toda la lógica se reduce a una línea:
if bmpd1.hitTest(new Point(bmp1.x, bmp1.y), 255, bmpd2, new Point(bmp2.x, bmp2.y),255)
Si observamos la descripción del método hitTest, encontramos que tiene la siguiente forma:
hitTest(primerPunto:Point, primerAlfaUmbral:uint, segundoObjeto:Object, segundoPunto:Point, segundoAlfaUmbra:uint);
Básicamente éste método agrupa los parametros en dos conjuntos, primero y segundo.
Necesitmos pasar un punto para ambos conjuntos, y este punto corresponde a la esquina superior izquierda del objeto BitmapData, la razón para hacerlo es que cada mapa de bits puede estar anidado con otro símbolo, o con multiples símbolos. En tal caso, pueden tener un sistema de coordenadas completamente diferentes. Al especificar un punto arbitrario, tienes la facilidad de alinear los dos sistemas de coordenadas en caso de ser necesario. Sin embargo, en este ejemplo ambos mapas de bits son dibujados directamente en la escena, asi que podemos utilizar su posición local directamente para construír el punto para cada uno.
El segundo y el último parametro, corresponde al umbral del canal alfa. Como se explico anteriormente, la transparencia de cada pixel puede variar de 0 (completamente transparente) a 255 (completamente opaco), este umbral, especifica que tan transparente debe ser el pixel para que pueda ser catalogado como una colisión. En este caso estamos pasando los parametros 255, en otras palabras, el pixel tiene que ser completamente opaco para que pueda ser detectado como una colisión.
Si regresamos al ejemplo de las hojas de papel transparente, nuestras estrellas pueden tener detalles en gris, en blanco o en rojo, pero visualmente solo será una colisión si el borde negro de la estrella A, entra en contacto con el borde negro de la estrella B.
Finalmente el parametro segundoObjeto, es un parametro tipo Object, es decir que puedes pasar Puntos, Rectangulos, o cualquier parametro que herede de BitmapData para verificar la colisión.
Colision basada en cuadricula (Grid -based collision)
Evaluar colisiones entre cientos de objetos en escena constantemente es un desperdicio innecesario de memoria y capacidad de procesamiento porque necesitamos estar comparando un objeto, con el resto de los objetos. Por ejemplo, si tuvieramos solamente 6 objetos, y queremos evaluar las combinaciones entre dos objetos; el numero de comparaciones necesarias es 
(vease Teoria Combinatoria). La formula para encontrar la combinacion entre n y r, es:
Tomando un poco de Analisis de Algoritmos, tenemos que la complejidad es 
en el peor caso. Como siempre vamos a comparar dos objetos, podemos fijar el valor de 
y la complejidad se reduce a 
De manera concreta, evaluar cantidades pequenas cantidades de objetos en escena, nos produce un numero de comparaciones muy cercano al numero de objetos analizados al cuadrado. Si tomamos en cuenta que el video juego no solamente hace comparaciones, sino que tiene dibujar imagenes, calcular raices cuadradas, mantener una maquina de estados finitos (o una tabla de decisiones), monitorear eventos, comunicaciones entre un servidor de sockets y el videojuego, etc, una pobre implementacion de colisiones nos conlleva a un rendimiento y uso ineficiente de los recursos del sistema.
Afortundamente, existe un metodo para optimizar la evaluacion de colisiones. Los cimientos del metodo parten de la idea, que dos objetos relativamente chicos que se encuentran en lados opuestos de la pantalla, no pueden estar colisionando, de tal manera que no hay necesidad de que se evalue la colision entre dichos objetos. Entonces, la manera de implementar este metodo, es dividir la pantalla en cuadrados, en el que el objeto mas grande en pantalla, debe caber perfectamente en un cuadro, en otras palabras si tu objeto mas grande es de 32 x 64 pixeles, entonces cada celda debe ser de 32 x 64 pixeles.
De esta manera, si analizamos el objeto como una particula tomando en cuenta el centro del objeto como la posicion del mismo, dicho objeto solamente puede colisionar con otros objetos si el centro de los mismos, se encuentra en alguna de las 8 celdas que rodean al objeto que estamos analizando.
En el constructor de la clase, primero creamos las estrellas mediante la funcion crearEstrella. Es exactamente la misma implementacion que utilizamos para El generador de particulas en AS3 y La programacion de un videojuego en Flash. Posteriormente creamos la cuadricula, mediante el la funcion crearCuadricula() creamos una matriz de 
donde n es el numero de filas y m el numero de columnas.
private function crearCuadricula():void
{
_cuadricula = new Array();
//ancho de la escena / tamano de la cuadricula = numero de columnas
for (var i:int = 0; i<_cuadricula.length;i++;) {
_cuadricula[i] = new Array();
//alto de la escena / tamano de la cuadricula = numero de filas
for (var j:int = 0; j<cuadricula[i].length;j++) {
_cuadricula[i][j] = new Array();
}
}
}
En esta implementacion, estamos creando celdas cuadrdas, pero las celdas pueden ser rectangulares. Recuerda que las celdas Deben contener exactamente al objeto mas grande en escena.
La funcion dibujarCuadricula solamente la escribi para ilustrar el concepto, simplemente une las linea de un lado a otro de la pantalla, a lo largo y a lo ancho.
La funcion enlazarEstrellasACuadricula() simplemente lo que hace es crear una referencia de las estrellas que hemos creado, para posteriormente calcular la posicion exacta de dichas estrellas y almacenar dichas posiciones en la matriz que creamos en el metodo crearCuadricula()
Finalmente la funcion evaluarCuadricula es la que se encarga de evaluar las celdas que se encuentran alrededor del objeto que a su vez, hace uso de la funcion evaluarColision. Es en evaluarColision, donde implementamos per-pixel collision; primero instanciando la clase BitmapData, y dibujando el contenido del clip de peliculas estrella en el objeto, para posteriormente crear un mapa de bits y utilizamos el metodo hitTest del mapa de bits para evaluar la condicion pixel a pixel.
El numero de comparaciones es aleatorio, debido a la posicion aleatoria de las estrellas en la escena. Sin embargo, en una configuracion como la mia, con 200 estrellas siendo mostradas en escena, la combinacion de colisiones basadas en cuadriculas y colisiones pixel a pixel, producen un numero entre 600 y 700 comparaciones. De no haber utilizado este metodo, y seguir haciendolo de la manera en que lo hicimos en el tutorial de programar un videojuego, hubieramos hecho un numero cercano a 40,000 comparaciones solamente para 200 objetos, y esto se repite cada vez que el objeto se mueve!
Archivos del tutorial:
Ultimos comentarios
A pesar de que los tutoriales no tienen seguimiento, con este tutorial ya se tienen las bases para empezar a pensar en TileMaps e isometria. Espero que este metodo sea de utilidad para ustedes y sus proyectos!
