Public Group

# Line of sight on 2D tilemap

This topic is 2186 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've been trying to do a line of sight code for a 2D tilemap, but it seems to eat lot of performance in some cases. Anyone have ideas how to improve it or am I doing it in the wrong direction?

Here's the code

 bool CGame::TargetBehindWall(int x, int y, int w, int h, int targX, int targY, int sight) { int collision[3]; int distX, distY; int OX, OY, TX, TY, stepX, stepY; bool visible = false; bool left, right, up, down; bool tooFar; left = right = up = down = false; int sightx, sighty; sightx = sighty = sight; int C_STEP = TILE_SIZE + 1; TX = targX; TY = targY; OX = x + w / 2; OY = y + h / 2; distX = abs(OX - TX) / C_STEP; distY = abs(OY - TY) / C_STEP; tooFar = false; if((distX > sightx) || (distY > sighty)) tooFar = true; if(!tooFar) { visible = true; if(TX > OX) { stepX = distX; left = true; } else { stepX = -distX; right = true; } if(TY > OY) { stepY = distY; up = true; } else { stepY = -distY; down = true; } for(int i=0;i<C_STEP;i++) { TestMapCollision(OX,OY,collision); if(collision[0] == 1) { left = right = up = down = false; visible = false; return true; } OX = OX + stepX; OY = OY + stepY; } } if((left)||(right)||(up)||(down)) return false; return true; } 

 void CGame::TestMapCollision(int sX, int sY, int *r) { int tx, ty; bool floor = false; tx = sX / TILE_SIZE; ty = sY / TILE_SIZE; if(!Map.OutOfBounds(tx,ty)) { if(!Map.Collide(tx,ty)) floor = true; } else { r[0] = 1; r[1] = (tx * TILE_SIZE); r[2] = (ty * TILE_SIZE); return; } if(!floor) { r[0] = 1; r[1] = (tx * TILE_SIZE); r[2] = (ty * TILE_SIZE); return; } r[0] = 0; } 

I modified it a bit for this post, there might be a mistake Edited by NukeCorr

##### Share on other sites

My totally random guess is that you're generating every pixel position along the line and checking for tile collisions. This would mean that you're testing the same tile for collisions many times. I would suggest using a line rasterisation algorithm like http://en.wikipedia.org/wiki/Bresenham's_line_algorithm or http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm to generate the exact set of tiles that you need to check. Wu's algorithm is a bit more conservative, e.g. Bresenham's algorithm would assume that you can see between two obstacles in a diagonal line but Wu's would not.

On top of that, you could go a step further and break your map up into areas. If you break it up into convex polygons (like a navmesh) you can assume that any two points within the same polygon can see each other. If you break it up into areas and portals (like PVS) you can assume that certain areas/rooms cannot see each other at all. But that level wouldn't be required unless your maps are huge.

• 9
• 23
• 10
• 19