TileWorld - Ray Casting in a Grid

TileWorld.as

// TileWorld.as - Lee Grey, November 2011

package com.lgrey.game.tileEngine 
{
	import com.lgrey.vectors.LGVector2D;
	import flash.display.BitmapData;
	
	public class TileWorld 
	{
		protected var _worldMap:BitmapData;
		
		public function TileWorld() 
		{	
		}
		
		public function get worldMap():BitmapData 
		{
			return _worldMap;
		}
		
		public function set worldMap(value:BitmapData):void 
		{
			_worldMap = value;
		}
		
		//Ray casting technique described in paper:
		//A Fast Voxel Traversal Algorithm for Ray Tracing - John Amanatides, Andrew Woo
		//http://www.cse.yorku.ca/~amana/research/grid.pdf
		
		public function castRay( p1Original:LGVector2D, p2Original:LGVector2D, tileSize:int = 32 ):LGVector2D
		{
			//INITIALISE//////////////////////////////////////////

			// normalise the points
			var p1:LGVector2D = new LGVector2D( p1Original.x / tileSize, p1Original.y / tileSize);
			var p2:LGVector2D = new LGVector2D( p2Original.x / tileSize, p2Original.y / tileSize);
		
			if ( int( p1.x ) == int( p2.x ) && int( p1.y ) == int( p2.y ) ) {
				//since it doesn't cross any boundaries, there can't be a collision
				return p2Original;
			}
			
			//find out which direction to step, on each axis
			var stepX:int = ( p2.x > p1.x ) ? 1 : -1;  
			var stepY:int = ( p2.y > p1.y ) ? 1 : -1;

			var rayDirection:LGVector2D = new LGVector2D( p2.x - p1.x, p2.y - p1.y );

			//find out how far to move on each axis for every whole integer step on the other
			var ratioX:Number = rayDirection.x / rayDirection.y;
			var ratioY:Number = rayDirection.y / rayDirection.x;

			var deltaY:Number = p2.x - p1.x;
			var deltaX:Number = p2.y - p1.y;
			//faster than Math.abs()...
			deltaX = deltaX < 0 ? -deltaX : deltaX;
			deltaY = deltaY < 0 ? -deltaY : deltaY;

			//initialise the integer test coordinates with the coordinates of the starting tile, in tile space ( integer )
			//Note: using noralised version of p1
			var testX:int = int(p1.x); 
			var testY:int = int(p1.y);

			//initialise the non-integer step, by advancing to the next tile boundary / ( whole integer of opposing axis )
			//if moving in positive direction, move to end of curent tile, otherwise the beginning
			var maxX:Number = deltaX * ( ( stepX > 0 ) ? ( 1.0 - (p1.x % 1) ) : (p1.x % 1) ); 
			var maxY:Number = deltaY * ( ( stepY > 0 ) ? ( 1.0 - (p1.y % 1) ) : (p1.y % 1) );
	
			var endTileX:int = int(p2.x);
			var endTileY:int = int(p2.y);
			
			//TRAVERSE//////////////////////////////////////////
	
			var hit:Boolean;
			var collisionPoint:LGVector2D = new LGVector2D();;
			
			while( testX != endTileX || testY != endTileY ) {
				
				if (  maxX < maxY ) {
				
					maxX += deltaX;
					testX += stepX;
					
					if ( _worldMap.getPixel( testX, testY ) != 0 ) {
						collisionPoint.x = testX;
						if ( stepX < 0 ) collisionPoint.x += 1.0; //add one if going left
						collisionPoint.y = p1.y + ratioY * ( collisionPoint.x - p1.x);	
						collisionPoint.x *= tileSize;//scale up
						collisionPoint.y *= tileSize;
						return collisionPoint;
					}
				
				} else {
					
					maxY += deltaY;
					testY += stepY;
	
					if ( _worldMap.getPixel( testX, testY ) != 0 ) {
						collisionPoint.y = testY;
						if ( stepY < 0 ) collisionPoint.y += 1.0; //add one if going up
						collisionPoint.x = p1.x + ratioX * ( collisionPoint.y - p1.y);
						collisionPoint.x *= tileSize;//scale up
						collisionPoint.y *= tileSize;
						return collisionPoint;
					}
				}
		
			}
			
			//no intersection found, just return end point:
			return p2Original;
		}
		
	}

}