Ray Casting en Actionscript 3 basado en Tiles

Bien, otra semana, otro tip. En este caso, es hora de un poco de ray casting. Aunque ya había hablado de esta técnica anteriormente (confundiéndola con el ray tracing ), voy a mostrar un sistema muchísimo más eficiente.

Básicamente lo que queremos es determinar si dos tiles (por convención, llamaremos así a los cuadrados que forman una teselación, o dicho de otro modo más simple, baldosas) pueden verse entre sí o si existe algún objeto que se interponga, impidiendo una línea recta de visión.

El problema en cuestión no es muy complicado y está muy relacionado con la rasterización de vectores (convertir un vector en una serie de píxeles). El problema es que el algoritmo empleado para rasterizarlos, el llamado algoritmo de Bresenham, omite algunos puntos necesarios para un buen ray casting. La siguiente imagen bastará como ejemplo, a la izquierda tenemos el algoritmo de Bresenham, a la derecha, la solución que realmente buscamos.

De todos modos, vale aclarar nuevamente que el algoritmo de Bresenham es el mejor para hacer lo que se supone que debe hacer, esto es representar un vector. Simplemente, esta representación no necesariamente visita todos los tiles que necesitamos.

Un ejemplo de uso sería el siguiente, donde usamos las flechas y el cursor para mover los tiles de inicio y destino, haciendo click en la pantalla para cambiar el mapa:



Para emplear el ray casting, primero definimos una función que dado un tile determinado (indicado como un par ordenado de columna y fila) devuelve true o false indicando si está ocupado. La clase RayCaster generará un error en caso de que hagamos hecho algo mal:

Código :

RayCaster.setFunction (customMap.isOccupied);

Luego, empleamos la función isVisible para obtener true o false dependiendo de si el tile es o no visible:

Código :

var startTileCol:int = 0;
var startTileRow:int = 0;
var endTileCol:int = 1;
var endTileRow:int = 1;
trace (RayCaster.isVisible (startTileCol, startTileRow, endTileCol, endTileRow));

La clase que se encarga del ray casting sería la siguiente:

Código :

package
{
   
   public class RayCaster
   {
      
      private static var lookUpFunction:Function;
      
      public static function setFunction (f:Function):void
      {
         lookUpFunction = f;
         
         try
         {
            // Test the function
            var b:Boolean = lookUpFunction (0, 0);
         }
         catch (e:Error)
         {
            // Error handling
            if (e.errorID == 1063) throw new Error ('RayCaster.as, setFunction failed. Reason: "Parameter count mismatch".');
            else throw new Error ('RayCaster.as, setFunction failed. Reason: "Unexpected function structure".');
         }
      }
      
      public static function isVisible (c0:int, r0:int, cf:int, rf:int):Boolean
      {
         var dc:int = cf - c0;
         var dr:int = rf - r0;
         
         var stepx:int = dc > 0? 1 : (dc == 0? 0 : -1);
         var stepy:int = dr > 0? 1 : (dr == 0? 0 : -1);
         
         var cc:int = c0; // CurrentColumn
         var cr:int = r0; // CurrentRow
         
         if (dc == dr || -dc == dr) // Special case, very simple to check
         {
            while (int (cc < cf) ^ int (stepx < 0) && cc != cf)
            {
               if (lookUpFunction (cc, cr) || lookUpFunction (cc, cr + stepy))
               // if (lookUpFunction (cc, cr)) // Replace the previous if with this one in order to get a thin line
               {
                  return false; // We cant see the target
               }
               cc += stepx;
               cr += stepy;
            }
            return !lookUpFunction (cc, cr); // Check the final tile, where the target is
         }
         else if (dc == 0 || dr == 0) // Another special case, also simple to solve, similar to the previous case
         {
            while (cc != cf || cr != rf)
            {
               if (lookUpFunction (cc, cr))
               {
                  return false;
               }
               cc += stepx;
               cr += stepy;
            }
            return !lookUpFunction (cc, cr);
         }
         else // This is the real case
         {
            var found:Boolean = false;
            
            var m:Number = dr / dc * stepx;
            var b:Number = r0 - .5 * stepy - (c0 - .5 * stepx) * m;
            
            var lr:Number = m * (cc - stepx) + b;
            lr += stepx > 0? m : 0;
            
            
            while (!found)
            {
               if (cc == cf && cr == rf)
               {
                  found = true; // We found the point
               }
               else if (lookUpFunction (cc, cr))
               {
                  return false; // There is an obstacle in the way
               }
               else
               {
                  if ((lr < cr && stepy > 0) || (lr > cr && stepy < 0))
                  {
                     cc += stepx;
                     lr += m;
                  }
                  else
                  {
                     cr += stepy;
                  }
               }
            }
         }
         return !lookUpFunction (cc, cr);
      }
   }
}

¿Sabes SQL? ¿No-SQL? Aprende MySQL, PostgreSQL, MongoDB, Redis y más con el Curso Profesional de Bases de Datos que empieza el martes, en vivo.