Tiled Shadow Maps | Hacker News Reader

Tiled Shadow Maps

jasonnall.com

114 pointsgfosco32 comments

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

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.

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

For line of sight you couldn't cache, no, but for static lighting you certainly could.

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)

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.

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)

This works, but gives you no indication of whether the tile is partially visible or not, much less how visible. An accurate indication of this would require many more rays and a lot of processing.

Right.

I was thinking about whether there could be a way to apply your technique, without having to do the polar + cartesian conversions.

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

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

This is an interesting problem, good luck!

Here's where I'd start:

1. See what resolution you need to get the level of grays you want. Your example shows 29x29 pixels for a cell be for it's resampled down. (2900%) so 841 possible shades of grey, (minus the artifacts from converting to polar and back. (the stair stepped edges)) but if you only need 12 shades of grey, render it at 400%, 4x4 pixels and add up the results for each cell. (But with shadow maps, you need a larger render to reduce the effects of the polar conversion.)

2. See if your shadow map approach or ray casting (or this http://www.redblobgames.com/articles/visibility/ ?) is faster to get this type of result: http://www.jasonnall.com/polar/images/Scale.png With your shadow mapping you are processing every pixel several times. With ray casting you can optimize and and only process what the player sees, and you don't have the polar conversion artifacts.

I'm betting on ray casting/ this http://www.redblobgames.com/articles/visibility/ and I bet there's a quick test for partially occluded cells, then chop in half and get the percentage exposed. Yeah, it may be more work to figure out, and not worth it. But you can still super sample only the the partially exposed cells 4x4 for 12 shades, 5x5 for 25 shades etc... and just render what you see instead of everything.

Thanks for reading!

You can get pretty good results with just a little trigonometry. For example, in the diagram below, the ratio of angles A/(A+B) tells you how shaded the blue tile should be. You can apply this method recursively.

http://i.imgur.com/0rz69.png

I hadn't thought of that! Thank you for sharing!

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.

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!

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.

I don't deny that simple 2d operations would be faster nor do I claim this to be a fast solution, I simply wrote the idea as it came to me and I have taken no time to implement it yet nor to compare it with other techniques in any detail. As always, thank you for reading and for your thoughts.

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

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.

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

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.

Thanks!

What are the games featured in the screenshots?

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

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

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

Thanks for looking. :)

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.

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!

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

Reply on news.ycombinator.com