Note: I looked all over and could not find a technique that was really fast – if I’m reinventing the wheel here, please let me know.
I assume that you’ve already mastered tile-based game techniques (or at least can fake it).
Say you’ve got a tile-based game where you want a bunch of enemies wandering around, but you don’t want the player to see them until they’re unblocked by walls to enhance the “Oh, crap!” factor. Line-of-Sight algorithms like this one work great, provided that you’re only checking a couple of objects every frame. It’s accurate and you can use it on irregularly-shaped walls.
However, bump it up to 30 checks per frame in a 28fps app, and the speed will drop straight into the basement. hitTest() is expensive. If you are working with a tile-based map in which the walls occupy one tile (i.e., are not just lines), you can simplify the wall lookup like so:
--
I realize that this function is not the most readable thing in the world, sorry about that. For an HTML version that reads better, go here.
--
AIs is an Array of enemy movieclips
tileArray is a matrix of the map’s tile representation numbers. Walls are defined as 1. The actual wall MovieClips are irrelevant here.
player is the player’s MovieClip
var wallWidth:Number = 25 //square tiles, measured in pixels
function checkVisibility ():Void //to be performed in every _root.onEnterFrame event
{
//see if any walls appear between the AIs and player
//figure out which tile the player is sitting in.
p1={x:Math.floor(player._x./wallWidth),y:M
ath.floor(player._y/wallWidth)}
for(cv=0;cv<AIs.length;cv++) //AIs is an Array of AI movieclips – we will check each one for visibility
{
bBlocked = false;
//figure out which tile this AI element is sitting in
p2={x:Math.floor(AIs[cv]._x/wallWidth),y:M
ath.floor(AIs[cv]._y/wallWidth)}
deltax = p2.x-p1.x;
deltay = p2.y-p1.y;
absdeltax = Math.abs(deltax);
absdeltay = Math.abs(deltay);
if(absdeltax > absdeltay) //mostly a horiztontal run
{
//figure out which object is furthest to the left
tp1={x:p1.x,y:p1.y}
tp2={x:p2.x,y:p2.y}
//I found that I had to switch the points around if p1 was greater than p2
if(p1.x > p2.x) {//switch 'em
tp1.x = p2.x;
tp1.y = p2.y;
tp2.x = p1.x;
tp2.y = p1.y;
deltax = tp2.x-tp1.x;
deltay = tp2.y-tp1.y;
}
adder= (deltay<<16)/deltax; //think of the lower 16 bits as a fractional part
accumy = (tp1.y<<16);
for(x = tp1.x; x<=tp2.x;x++)
{
y = accumy>>16; //this gives you a y value for each x
//tileArray is a matrix of map tiles. Walls are defined as 1.
if(tileArray[x][y] == 1) {
bBlocked = true;
break;
}
accumy +=adder;
}
}
else //mostly vertical
{
//figure out which object is furthest to the top
tp1={x:p1.x,y:p1.y}
tp2={x:p2.x,y:p2.y}
if(p1.y > p2.y) {//switch 'em
tp1.x = p2.x;
tp1.y = p2.y;
tp2.x = p1.x;
tp2.y = p1.y;
deltax = tp2.x-tp1.x;
deltay = tp2.y-tp1.y;
}
adder= (deltax<<16)/deltay; //think of the lower 16 bits as a fractional part
accumx= (tp1.x<<16);
for(y = tp1.y; y<=tp2.y;y++)
{
x = accumx>>16; //this gives you an x value for each y
if(tileArray[x][y] == 1) {
bBlocked = true;
break;
}
accumx +=adder;
}
}
if(bBlocked)
AIs[cv]._visible = false;
else
AIs[cv]._visible = true;
}
}
Because this function is only crunching integers and not performing hitTest() all over the place, it’s uber-fast. In stand-alone mode (running on personal machine and not in a browser), I’ve been able to achieve lookups on 75 objects in every frame in a 28fps movie…30-40 online in a browser, with little or no speed degradation.
This LOS algorithm is used here. The game is under development, so I already know I have a ton of work to do (i.e., not interested in critiques of game play, bugs, etc.). The function above is virtually identical to the game’s LOS algorithm – player and AI clips are in separate classes but I simplified them for this topic.