Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
5 replies to this topic

#1 Killerko   Members   -  Reputation: 167

Like
0Likes
Like

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.

 

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?

 

 



Sponsor:

#2 BCullis   Crossbones+   -  Reputation: 1813

Like
0Likes
Like

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
DeviantArt :: Because right-brain needs love too

#3 Killerko   Members   -  Reputation: 167

Like
0Likes
Like

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?



#4 ferrous   Members   -  Reputation: 1819

Like
2Likes
Like

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.


#5 TheChubu   Crossbones+   -  Reputation: 3952

Like
0Likes
Like

Posted 27 March 2014 - 11:50 PM

Let me Google that for you... smile.png

 

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


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


#6 Killerko   Members   -  Reputation: 167

Like
0Likes
Like

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.



PARTNERS