How to calculate FOV with four-walled tiles?

I'm working on a 2D tile-based game. I'm trying to calculate FOV and I've implemented walls so they don't take up an entire tile. Instead, they just take up a side of each tile. Similar to:

``````class Tile {
bool northWall;
bool westWall;
}
``````

Most of the algorithms I've been looking at expect walls to take up a full tile, and the check to see if a tile is blocking tiles behind it is trivial. I'm having trouble wrapping my head around this. I've got an implementation of Recursive Shadowcasting right now, but not sure how to write my is_blocked() function. Can anyone give me some advice?

-

Given that your walls are not cells, you will need a way to identify occluders as you raymarch. The easiest way to do this would be, as you step from one cell to the next, check whether there is a wall on the boundary you are crossing from tile A to tile B, and store the result for use.

Let's look at three different approaches to clarify this for you.

Recursive shadowcasting, your current algorithm. You can never have "matchstick" (infinitesimally thin) walls. Why? Because the order in which the algorithm iterates through cells is not the same direction the ray would come from in a geometrically-correct lighting model, that is, it's an octant-based approximate. Recursive shadowcasting is a simplification of the problem, and by breaking some of the fundamental requirements for that "shortcut", the algorithm simply won't work. So although you may place individual walls at first, these edge-walls must, before the algorithm is run, be connected in loops. Otherwise, due to the direction in which the algorithm iterates, it will simply miss some walls altogether. Essentially the problem is one of quantisation and resolution -- the walls becomes 0-dimensional from certain angles and thus cannot be detected by the algorithm.

2D DDA raycasting. This is what is used in Wolfenstein and Doom, only it looks much fancier. Cast a ray along every possible path, using DDA, after selecting your angular resolution, eg. if you want one ray per degree, use 360 rays. You can use matchstick walls if you want to, but there is a caveat: While this method is geometrically correct in terms of ray direction, due to resolution limits of the underlying grid, it may miss matchstick walls at distances relatively far out from the viewer, as the rays diverge.

Back-projection. You will never lose matchstick walls, because instead of evaluating the lighting based on a grid, you are evaluating every vertex of every polygon (or edge in the case of your matchstick walls) in that space, and backprojecting them to the light source. Note however this will require you to construct actual polygons as lists of edges if you want to do the occlusion correctly, because you will need to intersect rays that are cast back from each vertex, with potential occluder that lie in front of them (i.e. between them and the light source). The biggest problem here is that arbitrary geometry leads to potentiall high complexity of the area to be evaluated for lighting, unless of course you still use a grid as your guide for vertex placement.

My advice? Use recursive shadowcasting if you are at all willing to accept using cells, because it's a shortcut that relies on this to work at all and is simple to implement and understand. Use raycasting if you can accept some loss of accuracy out at a certain distance from the light source. If all other methods fail and you need the highest possible degree of accuracy, use vertex-based back-projection.

-
Wouldn't this miss out on North Walls in octants 1, 2, 5, 6 and West Walls in octants 3, 4, 7, and 8? I might be misunderstanding, but I'm not sure your answer is very clear. – bifflechips Jan 10 '12 at 16:30
@bifflechips See my edit for clarification. – Arcane Engineer Jan 10 '12 at 17:59
I would prefer to stick with "matchstick" walls, as I'm planning on allowing the player to destroy them. I ended up implementing a modified version of the algorithm explained in these articles, which I believe is a form of back-projection. I might give raycasting a try in the future, but this works for now. Thanks! – bifflechips Jan 10 '12 at 21:11