How do I check to see if a tile corner is visible in 2d space?

Question

I am trying to implement fog of war, and I have run into trouble. I want to check to see if the player is able to see the corners of each tile within a certain radius, however I am unsure how to check if the vision of the corners is to be obstructed or not. Is there a quick way to do this? I used a system of drawing a line and checking if the tiles the line is on are solid blocks in a rougelike, but I am unsure if this method would be suitable, as it is possible to see parts of a tile, unlike in a rougelike where it's a yes or no type thing.

For example, the black tile is obstructing the view partially of the white tile.

The red lines signify that the player is able to see the corner, while the blue signifies they can't (as the black obstructs it).

Answer 1

To flesh out Nick's answer a bit: the core concept behind the DDA algorithm (which works just as well in three dimensions) is that for each axis of your grid you keep track of the next 'crossing point' for that axis in terms of your line parameter; each step of the algorithm consists of finding which axis has the next crossing point (which is a simple compare in two dimensions), taking the appropriate step, and updating the next-crossing values for each axis.

The line here can be written as '(x,y) = (x0,y0)+t*(m,n)', where m=x1-x0 and n=y1-y0. If the dimensions of a grid cell are gx and gy, then dx — the distance (in terms of the t parameter) that it takes to cross one grid cell — can be found with a bit of quick algebra: from the pair of equations x = x0+m*t, (x+gx) = x0+m*(t+dx) we get gx = m*dx, or in other words dx=gx/m. Likewise, dy=gy/n. The algorithm keeps track of next_x (the distance to the next red point along the line) and next_y (the distance to the next blue point along the line) and updates them every time it hits another crossing, so the central loop looks something like this:

while ( cur_t < t_max) {
  if ( next_x < next_y ) {
    cell_x++;
    cur_t += next_x;
    next_y -= next_x;
    next_x = dx;
  } else {
    cell_y++;
    cur_t += next_y;
    next_x -= next_y;
    next_y = dy;
  }
  // Process the cell (cell_x, cell_y)
}

Note that this code is missing a lot of the details - it doesn't tell you how to initialize next_x and next_y, for instance. There are ways of eliminating most of the divides, making it easier to handle special cases like vertical and horizontal lines. Whether you increment or decrement cell_x and cell_y depends on which quadrant your line is in - note that for my example line, you'd actually be decreasing cell_x each tick, since m (x1-x0) is negative. You also have to decide how you're going to handle cases where your line goes precisely through the corner between cells, rather than transitioning on an edge; there are lots of small details that can go wrong, and it needs a lot of testing. Still, hopefully this will give you a picture of what the core idea of the algorithm is.

Answer 2

John Amanatides & Andrew Woo's DDA (Digital Differential Analyser) algorithm provides what you need. I'm on mobile so tedious to grab the link without closing this page. DDA is O(n *m) where n is the number of tiles to be walked along a ray/angle, and m the number of angles.

If you need to check whether smaller parts of the tile are visible further (finer detail), you can split each tile into a separate grid and perform DDA checks at that level as well.

The only substantially different alternative I can see is raycast scanning (line-line intersection checks) which is O(n * m) with n being the number of tile edges within the area of interest, and m being the number of discrete angles you test for in each circular sweep (implying that even with this approach, there still exist issues of resolution). Since there are multiple edges to each tile, DDA can be seen to be more efficient.

One final approach that comes to mind is to adapt raycasrt scanning by setting an individual ray angle up for each individual grid intersection within your limited area of interest. This way you can determine exactly where occlusion occurs within you grid (since occlusion lines always pass corners) although you would need to substantially restrict your area of interest lest the number of interstitial points defining your ray angles were to get out of hand.