• Advertisement
Sign in to follow this  

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

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

If you intended to correct an error in the post then please contact us.

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.

 

jZaAhkl.png

 

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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);
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement