Be a Supporter!

As: Tile-based Los Algorithm

  • 5,717 Views
  • 5 Replies
New Topic Respond to this Topic
zoohl
zoohl
  • Member since: Mar. 22, 2005
  • Offline.
Forum Stats
Member
Level 05
Blank Slate
As: Tile-based Los Algorithm Jul. 27th, 2005 @ 11:06 AM Reply

AS:Main

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.

Nemo
Nemo
  • Member since: Jun. 13, 2003
  • Offline.
Forum Stats
Member
Level 34
Game Developer
Response to As: Tile-based Los Algorithm Jul. 27th, 2005 @ 11:16 AM Reply

That's really cool especially if it does not use any hit tests. I was looking for something like this a while ago but could not find anything so I had to trash the game I was working on. This is the first line of sight script I have seen and definitely will come to be useful for me when I do some other projects. Great script.


BBS Signature
dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to As: Tile-based Los Algorithm Jul. 27th, 2005 @ 01:11 PM Reply

nice


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
zoohl
zoohl
  • Member since: Mar. 22, 2005
  • Offline.
Forum Stats
Member
Level 05
Blank Slate
Response to As: Tile-based Los Algorithm Aug. 11th, 2005 @ 03:03 PM Reply

Hi folks, just a correction:

The above algorithm is occasionally (read: evil to debug) including adjacent wall tiles along mostly straight vertical or horizontal axises(sp?), so enemies will disappear and reappear if a player is adjacent to a wall, even if there are no walls between them. No fun tracking down that little nasty...who knew that an '=' sign would be so much trouble?

Anyway, here's the fix: in the above algorithm, there are 2 main for() loops, depending on the general angle of the line:
for(x = tp1.x; x<=tp2.x;x++)
and
for(y = tp1.y; y<=tp2.y;y++)

They should actually read:
for(x = tp1.x; x < tp2.x;x++)
and
for(y = tp1.y; y < tp2.y;y++)

Change the '<=' to just '<'

Cheers!

LeechmasterB
LeechmasterB
  • Member since: Apr. 1, 2005
  • Offline.
Forum Stats
Member
Level 17
Blank Slate
Response to As: Tile-based Los Algorithm Feb. 28th, 2006 @ 11:47 AM Reply

This is not really well coded. You should only use one for loop and it can be done ways shorter and easier. Think different! :)

Hoeloe
Hoeloe
  • Member since: Apr. 29, 2004
  • Offline.
Forum Stats
Member
Level 37
Game Developer
Response to As: Tile-based Los Algorithm Dec. 22nd, 2006 @ 10:36 AM Reply

All i get is a bunch of errors....

Error Scene=Scene 1, layer=Layer 1, frame=1:Line 7: Expected a field name after '.' operator.
p1={x:Math.floor(player._x./wallWidth),y:M

Error Scene=Scene 1, layer=Layer 1, frame=1:Line 8: '}' or ',' expected
ath.floor(player._y/wallWidth)}

Error Scene=Scene 1, layer=Layer 1, frame=1:Line 15: '}' or ',' expected
ath.floor(AIs[cv]._y/wallWidth)}

Error Scene=Scene 1, layer=Layer 1, frame=1:Line 78: Unexpected '}' encountered
}

Total ActionScript Errors: 4 Reported Errors: 4


Decima: The Last Story of Vald has a Facebook page and a development blog. Give them a look!
------------------------------

BBS Signature