Comparative study of field of view algorithms for 2D grid based worlds

[Hvilela]

Hi Guys,

Even though I'm a gamer and a game developer I have to admit I never developed (or even played) a rogue like game. I'm here cause I'm trying to implement the x-com gameplay and for this I need to implement fog of war / field of view.

My researches lead me to this article (http://www.robotacid.com/flash/red_rogue/shadow_casting/fov.pdf), that lead me to Roguebasin, that finally lead me here.

My first problem is that the link for the algorithm called DIAMOND (http://www.geocities.com/temerra/los_rays.html) is broken and I just can't find it, so I have no idea about how to implement it. It has another name? Were can I find an article about it?
I guess it's Ray Casting (http://roguebasin.roguelikedevelopment.org/index.php/Ray_casting) but I'm not sure.

My second problem is that each algorithm has his flaws, and (for my case, at least) that flaws are unacceptable. After a fast look I realized that a logic AND between the SHADOW and DIAMOND (the tile is visible if it's considered unblocked by both algorithms) would result in a better result.
The easiest way to imagine the result is to "sum" both shadows.

Let's take a look in each case:
Adjacent to the pillar behavior: Just like SHADOW, a nice V shaped shadow.
Away form the pillar behavior: The sum of the algorithms create a nice V shaped shadow. Better than any of the algorithms alone.
Corner peeking: Not allowed, just like SHADOW.
Inverted corner peeking: Not allowed, just like DIAMOND, making the corner peeking symmetric.
Diagonal Wall: Blocks view, like DIAMOND. What is the expected result for me, cause I allow diagonal movement but only when the 3 tiles involved are unblocked.

Symmetry: As long it's not implemented yet, I did not calculate the symmetry, but at least in the corner peeking special case it's symmetric.

Performance: My idea is to call SHADOW, and cast the rays (DIAMOND) only for the tiles considered visible. On the worst case it would roughly be the sum of the cost of both algorithms, what is in most of cases it's still faster than DIGITAL.

I would like to hear opinions about that.

[Hvilela]

I created an image to illustrate the result of SHADOW and DIAMOND.

[requerent]

http://blog.pixelpracht.net/?p=340

From a recent post here that would probably be useful to you. It includes source and an interactive flash demo.

[Hvilela]

Thank you for the reply. But I need to be sure:
Diamond == Ray Casting ?

[requerent]

I'm not really sure what DIAMOND is. The link I sent you shows a pretty clear example of what ray-casting is.

In your first DIAMOND image, more than one ray should be blocked by the pillar, which would produce a cone, pending on how many rays are cast. In your example, it looks like you've got something of the order of 80 rays. The pillar would block at least 8 or so rays

DIAMOND looks like it calculates lines between all light obstructing objects and just places shadows on those lines where pertinent. This isn't quite ray-casting.

[george]

I think you'll want to look at these:

http://doryen.eptalys.net/2009/04/the-fov-graal/

http://doryen.eptalys.net/2009/01/in-search-of-the-fov-graal/

http://doryen.eptalys.net/2009/01/optimized-diamond-raycasting/

[Hvilela]

The fist link do not explain how to implement it, the diagonal walls result are not what I expect and it do not show the results for "away the pillar".

The second has no usefull information.

The third would be great if the link to the source wans't broken.

[XLambda]

The third would be great if the link to the source wans't broken.

I just checked it, the file it links to is still in the libtcod source. It's just not hosted on googlecode anymore.

Normally I'd tell you to just download the libtcod source (which is located here). However, because I'm feeling generous today, here's a straight link to fov_diamond_raycasting.c!

[Hvilela]

Thanks man!