Skip to content

Instantly share code, notes, and snippets.

@leegrey
Created November 11, 2011 10:15
Show Gist options
  • Save leegrey/1357669 to your computer and use it in GitHub Desktop.
Save leegrey/1357669 to your computer and use it in GitHub Desktop.
TileWorld - Ray Casting in a Grid
// 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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment