Public Group

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

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

## Recommended Posts

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?

##### Share on other sites

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)

##### Share on other sites

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?

##### Share on other sites

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

##### Share on other sites

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

Edited by TheChubu

##### Share on other sites

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);
}

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 13
• 9
• 9
• 15
• ### Forum Statistics

• Total Topics
634072
• Total Posts
3015341
×