Tiled Shadow Maps

http://www.jasonnall.com/polar/

by gfosco • 14 years ago

114 32 14 years ago

jasonnall.com

JTxt2• 14 years ago

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

JasonSage13• 14 years ago

Thanks for looking. :)

0x03• 14 years ago

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)

JasonSage13• 14 years ago

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.

0x03• 14 years ago

I guess I was thinking something like this: http://roguebasin.roguelikedevelopment.org/index.php/Eliglos...

(the second example, "raycasting"). You'd work on the "native tile resolution".

I.e. you just "swipe" lines starting at the player position to the edge of the map, in a circle; as soon as you hit an obstacle tile, you stop marking the tiles ("pixels") on the line as lightened. No need to do any per-object iteration (as long as the tile map contains object references in tile positions)

AddZero• 14 years ago

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

JasonSage13• 14 years ago

"Just need to determine the amount a cell is occluded."

That's the trick isn't it? How do you determine the amount? That is more or less what I set out to figure out when this started. Sure you can do a calculus/math-based approach, but it is slow and done entirely on the CPU.

etcet• 14 years ago

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...

JasonSage13• 14 years ago

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.

kevingadd2• 14 years ago

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).

JasonSage13• 14 years ago

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.

kevingadd2• 14 years ago

If you use a raycasting method, you can rasterize a shadow map with exactly the amount of precision you need and not have any artifacts (for 2d, of course - for 3d the necessary amount of precision is hard to calculate and sometimes prohibitive).

My old game Chimaera ( http://www.luminance.org/chimaera.html ) did this - lightmap rendered at full screen resolution (1-1 mapping) in full precision, with an on-demand raycasting solution for offscreen pixels. A raycasting method also allows you to cache the shadow data for static geometry and static light sources, which can be a big win for complex scenes. (I think maybe you could cache the polar data, but it wouldn't be as easy since you can't just translate by x&y like you can with a normal 2D perspective?)

w0utert• 14 years ago

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.

JasonSage13• 14 years ago

Thanks!

darklajid• 14 years ago

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...

ralphleon2• 14 years ago

What are the games featured in the screenshots?

usea• 14 years ago

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

ralphleon2• 14 years ago

Thanks! I have a soft spot in my heart for isometric adventure games.

RBerenguel2• 14 years ago

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.

JasonSage13• 14 years ago

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!

RBerenguel2• 14 years ago

Give it a play. For me it's a "beautiful" roguelike. Like making a simpler, more straightforward Nethack and somehow adding it stunning... ascii graphics :D

blackhole2• 14 years ago

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.

JasonSage13• 14 years ago

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!

blackhole2• 14 years ago

Even if you moved the polar coordinate shift to the hardware, you're doing pixel ray operations on the texture, followed by rasterization. I do vertex operations only, which are vastly fewer in number even in a worst case scenario, and then rasterize that. I'm willing to bet that even if we implemented this on the CPU, my algorithm would still be significantly faster and more accurate. Furthermore, your algorithm would struggle to take into account soft shadows, which actually become a noticeable problem in certain situations in large tilemaps when you have very large light radii.

I think the polar coordinate transformation trick is really cool, but I feel like this is the wrong use for it. This is essentially a solved problem using polygons in 2D lighting engines already - to make it work for tiles, you simply scale down and back up to map to tiles.

I have to admit I'm sorely tempted to implement this in WebGL just to see what happens.

Tiled Shadow Maps

Related Stories