Tiled Shadow Maps

[kevingadd]

Interesting approach. I'd be shocked if an algorithm based on two polar transforms, plus resampling, was ever faster than more traditional raycasting based algorithms (see http://www.redblobgames.com/articles/visibility/ for one detailed example) - especially given that you can do the raycasting algorithm entirely in hardware now on pretty much any machine, including the resampling.

Maybe you could do the polar transforms in a pixel shader to make up the difference? The transform also seems to introduce a not-insignificant amount of error, which is unfortunate if you want to use visibility data for AI (in which case you want full precision at whatever your target resolution is).

[JasonSage]

Obviously a hardware accelerated implementation would be ideal if not required, which is why I was going to first implement this in a shader, if possible.

The artifacts you mention are sort-of inherent in shadow maps, and depend on the resolution of shadow map you are working with. The demonstration I did had a lot of error, but you can see at the bottom some examples of higher resolution test cases which have significantly less error.

[0x0]

Instead of converting to polar and back again, could you do something similar by "raytracing" a 2d line from each tile to the players position backwards; starting in the middle and stepping out toward the target tile in a bresenheim-type stepping, marking as shadows after touching an obstacle? If you start by stepping around the outer edges, you'd fill most of the tiles in one pass, and then you could probably interpolate or re-trace for any missing pixels?

(Edit: I guess you'll lose the nice shades-of-grey effect that the article's bitmap processing technique yields)

[JasonSage]

I assume you mean for generating the shadow map before it is scaled and pixelized? I'm not familiar with techniques for doing such a thing. You could probably step through each object and draw lines from the corners based on the angle between the player tile and the object. The approach I listed would actually save you from testing every single object—as soon as a black pixel is detected in an algorthm, it moves to the next line, meaning that the number of objects that may exist in that direction at a greater distance is completely irrelevant.

[AddZero]

Agreed. But I think you could still do the shades of grey. Just need to determine the amount a cell is occluded.

[blackhole]

My own approach to this problem would be to consider each tile as a square polygon, then simply project the vertices outward from the light source. Then you take the resulting triangles and rasterize them on to an image scaled such that each pixel represents a tile and use antialiasing (or simply rasterize them on to an image 8 times as large as you need it and scale down, which is essentially the same thing). This gives you roughly the same end result, but would allow you to hardware accelerate almost every single aspect and avoids all the artifacts of shadowmapping. Notably, by restricting each polygon to a square, the projection could be done entirely as a vertex shader, without requiring geometry shaders. This would likely be vastly more efficient due to taking advantage of hardware acceleration.

[JasonSage]

Depends on how much of this algorithm you can heft onto the hardware. I'd like to see a polar coordinate textures and operations on graphics cards in the future. Thanks for reading!

[etcet]

This kind of Field of View algorithm is integral to any roguelike and there's a variety of methods for achieving the results [0]. I'd be interested in how this algorithm holds up against the usual raycasting or shadow casting. My intuition is that it'd be slower (especially with a 1024px shadow map resolution) due to it being based on pixels rather than grid values.

[0] http://roguebasin.roguelikedevelopment.org/index.php/Field_o...

[JasonSage]

I'll take a look at the algorithm—thanks for sharing. I fully intend to update this article later to give some details on how it performs.

[darklajid]

If you're not averse to C#: Eric Lippert has a series about visibility in a rogue-like game (it's either/or, no shadows, but still a nice read) on his blog:

http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shado...

[w0utert]

Interesting approach, but like some others I'm wondering if this is the fastest and easiest way to do this kind of thing, especially since you are working with a tile based grid.

Probably a combination of 2d portals and raycasting would do the same trick, but more efficiently. I also think it would be easier to implement, and more flexible if you want to have moving obstacles. Most of this stuff is standard fare in even the simplest of 3d engines and well documented, the 2d case would actually be a simplification of those algorithms.

Nonetheless I think your solution is pretty clever and interesting, so kudos for that.

[JasonSage]

Thanks!

[ralphleon]

What are the games featured in the screenshots?

[usea]

The one on the left is Project Zomboid http://projectzomboid.com/blog/ while the one on the right is from LambdaRogue http://lambdarogue.net/

[JTxt]

Interesting idea. I have wondered about this problem too. Thanks for sharing.

[JasonSage]

Thanks for looking. :)

[RBerenguel]

Interesting way to solve the problem. Just as curiosity, have you ever checked the ascii roguelike "Brogue"? It has a kind of line-of-sight and color scales.

[JasonSage]

Nope, I'm still fairly new to the indie/rogue community, so I'm still familiarizing with a lot of it. I'll take a look. Thank you for reading!