• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# How to check if 2 points see each other on 2D tile map?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1Killerko  Members

Posted 27 March 2014 - 07:07 PM

Hi,

I have a tile map filled with 2 types of tiles walkable (0) and nonwalkable (1)... Now I have 2 points on my map, player and the exit and I need to know if they can see each other or if there is a nonwalkable tile in between them.

all I could manage to do is compute the distance between the points like this:

distance = sqrt(
(currentLevel.getExitX() - player.getX()) * (currentLevel.getExitX() - player.getX()) +
(currentLevel.getExitY() - player.getY()) * (currentLevel.getExitY() - player.getY())
);

but from this point I am kind of clueless what to do next... how do I check all the tiles that this line is crossing if they are 1 or 0?

Ideally I would make a class which I could use like checkPoints(x1, y1, x2, y2) which will return either true or false based on if there is a non walkable tile between these 2 points... so I can use it like if( checkPoints(x1, x2, y1, y2) == true ) { do something } else { do something else }

any ideas how could I do this?

### #2BCullis  Members

Posted 27 March 2014 - 07:32 PM

One possibility: calculate which squares the line of sight travel through, then iterate through the list of results and return true if they can see eachother (i.e. if there are no non-walkable tiles in the list)

Hazard Pay :: FPS/RTS in SharpDX (gathering dust, retained for... historical purposes)
DeviantArt :: Because right-brain needs love too (also pretty neglected these days)

### #3Killerko  Members

Posted 27 March 2014 - 07:47 PM

yes that sounds like something I was thinking about but the problem is how do you get the tiles the line is crossing? all I can get is the tiles of the first point and the last point (since I know them). But how do you get the rest of the tiles thats are inbetween those 2 points?

### #4ferrous  Members

Posted 27 March 2014 - 08:04 PM

You can look up bresenham line aglorithm.  It basically walks along a line drawing pixels, but for you, instead of drawing, and instead of pixels, you just walk along the line looking at tiles.

That works great as long as each thing is at the center of the tile.  If you need something a little more complicated, you can try Xiaolin Wu's line agorithm.

For more complicated stuff, you might also like this:

http://www.redblobgames.com/articles/visibility/

Edited by ferrous, 27 March 2014 - 08:06 PM.

### #5TheChubu  Members

Posted 27 March 2014 - 11:50 PM

EDIT: Dang, didn't noticed it says "Was that so hard?" lol, I didn't mean it that way

Edited by TheChubu, 27 March 2014 - 11:52 PM.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

My journals: dustArtemis ECS framework and Making a Terrain Generator

### #6Killerko  Members

Posted 28 March 2014 - 12:06 AM

thanks for the direction what to look for!

this is now doing exactly what I needed... it returns true if the tile between the 2 points equals 1 or false if there isnt anything blocking the line.

perfect! :-)

bool raytrace(int x0, int y0, int x1, int y1)
{
int dx = abs(x1 - x0);
int dy = abs(y1 - y0);
int x = x0;
int y = y0;
int n = 1 + dx + dy;
int x_inc = (x1 > x0) ? 1 : -1;
int y_inc = (y1 > y0) ? 1 : -1;
int error = dx - dy;
dx *= 2;
dy *= 2;
for (; n > 0; --n)
{
// here I can use x,y to do something with the tile, in my case I just need to check if my tile is 1
if(currentLevel.getTile(int((x+tileSize/2)/tileSize), int((y+tileSize/2)/tileSize)) == 1) return(true);
if (error > 0)
{
x += x_inc;
error -= dy;
}
else
{
y += y_inc;
error += dx;
}
}
// nothing blocking the line
return(false);
}

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.