Grid-Based Lighting

[lithander]

I'm trying to figure out a clever way to simulate light-propagation, shadowing and LOS on square grids.

As long as I only care for a boolean result (e.g. is whether a field is visible from another field) it's straight forward calculate using raycasting.
I just use the Bresenham Line Algorithm to trace the fields from start to max-range. All clear fields covered by the line are lit. as soon as an occluding field is hit I abort the raycast. Doing this for all the fields on the edge of the field-of-view I can easily find all visible/lighted fields.

This basic version that is working flawlessly but what if I need more specific information on how visible a field is? If you consider a blocked field casting a shadow a lot of fields are neither fully lit nore fully in shadow but "cut in half". Imagine tracing a line but with anitaliasing - there will be many shades of gray. So I'd like my "visible" property be a percentage (0 - 100%) and not just a boolean (true or false).

How would you solve this problem?

To make it even more complicated: What if the light-source has a non-integer position e.g. it's not right in the center of a field but in the upper right corner. This should affect line-of-sight and light-probagation calculations but isn't handled by the algoirthm I described above.

Sorry, that the question is not specifically rogue-like related but as rogulikes tend to feature very complex grid-based simulations I figured some of you guys might have solved my problem allready! All kind of feedback/opinion is appreciated.

[Krice]

It's grid-based so make the lighting also strictly grid-based. Problem solved. I don't get those half-lit/half-visible tiles.

[Alex E]

I have light fade away with distance in "Left Field Hotel". If you want to see what it looks like I have a picture on the thread, http://roguetemple.com/forums/index.php?topic=2509.0.

On to the point. What I did was have every tile have a brightness variable. This can range from 0 to 10. If it was a 5, for example, then the tile would be half lit. If 10, it would be fully lit. So after giving the brightness to the light source, it would loop through all of the tiles and find the distance between them and the light source. Then, a brightness would be given to said looped tiles based on the distances. If a light source crosses another light source, then the surrounding tiles' light would combine and become more bright. To find the distance from the light source and the tiles around it, I used the pythagorean theorem (a*a+b*b=c*c). Let's say that the light source is 10. Well the tile two tiles to the right is two tiles away, right? 10(light source)-2(distance) would be 8. So the tile would have a brightness of 8. If a wall is in the way of the tiles, then the brightness would not change.

I'm not sure about having non-integer based lighting. Light wouldn't be grid based anymore.

[XLambda]

I'm trying to figure out a clever way to simulate light-propagation, shadowing and LOS on square grids.

As long as I only care for a boolean result (e.g. is whether a field is visible from another field) it's straight forward calculate using raycasting.
I just use the Bresenham Line Algorithm to trace the fields from start to max-range. All clear fields covered by the line are lit. as soon as an occluding field is hit I abort the raycast. Doing this for all the fields on the edge of the field-of-view I can easily find all visible/lighted fields.

This basic version that is working flawlessly but what if I need more specific information on how visible a field is? If you consider a blocked field casting a shadow a lot of fields are neither fully lit nore fully in shadow but "cut in half". Imagine tracing a line but with anitaliasing - there will be many shades of gray. So I'd like my "visible" property be a percentage (0 - 100%) and not just a boolean (true or false).

How would you solve this problem?

To make it even more complicated: What if the light-source has a non-integer position e.g. it's not right in the center of a field but in the upper right corner. This should affect line-of-sight and light-probagation calculations but isn't handled by the algoirthm I described above.

Sorry, that the question is not specifically rogue-like related but as rogulikes tend to feature very complex grid-based simulations I figured some of you guys might have solved my problem allready! All kind of feedback/opinion is appreciated.

For the first problem, I think you should look at libtcod code. I know jice has several implementations of this in there.

But I kind of agree with Krice - unless it has some impact on the mechanics, avoid non-digital lighting.


EDIT: Ah, I forgot, there's also an article about this on doryen.

[lithander]

Thanks for the replies.

If you don't see the point in having non-integer positions in a gridbased game let's ignore my second question. Even with integer coordinates for both lightsource and occluders there will be partially occluded fields and when you chose to ignore that in your calculations it will have an impact on gameplay. Let's just assume my reasons to want that feature are valid and focus on a possible solution.

I'm not asking for a easy-to-use solution. I just want to avoid reinventing the wheel here. If someone has solved it sufficiently there's no point in doing it again imho.

@Mosenzov: Your screenshot looks cool! But allowing lights to fade away with distance is not my current problem. Once you've settled on a formula to calculate the intensity based on distance it's pretty easy to calculate for any field that is not partially occluded. It's the degree of occlusion that I'm trying to calculate.

@XLambda: Thanks for the tip about libtcod library. I'll dig into that and see what I can find.

EDIT: There's a nice sample included in the libtcod repository that shows off different Field-of-View algorithms. They differ greatly in result and just from looking at it I have a hard time saying which one works best. A player wouldn't be able to predict the results of whatever algorithm you chose without you visualizing it someway. It might be against roguelike traditions but the samples only reenforce my opinion that it'd be better to consider partially occluded fields. (if you consider intensity and distance, why not occlusion?)

[kraflab]

I don't do what you want to do, but the way I do lighting could easily achieve the results you want, so let me describe the situation:

A single time, I run a script which takes a tile and separates it into a number of subpoints.  For example, I might take only the center of a tile, or maybe I take 9 points forming a border that runs around the tile and the middle of the tile.  At any rate, pick some source points in the tile.  Then pick destination points.  I think I just use the center as a destination, which makes lighting non-symmetric, but you can do whatever you want.  Then draw a line from each source point to each destination point, and form an array of movements on the grid that form that line, i.e. x, y, x, x, y...

If the line from a source point to a destination point has a different path than one previously used, add that path to a list of all possible light paths from tile a to tile b.  Then do this for every possible tile destination you want.  Now you have a set of lists of routes for light to take to get from tile a to tile b.  I store these in an input file so the calculation is actually never done within the game itself.

To see if a tile is lit, take all paths and stop if one of them reaches the source.

Now, for you, you could do the exact same thing, but check all paths and count the fraction of paths that make it.  This will give you a fractional visibility value that will reflect how much the tile is blocked by walls or other possible obstructions.

This may not be the best way to do it, but it's trivial to write and takes no computation time (at least using my parameters).

[lithander]

Kraflab, if I understood you correctly you suggest to use raycasting approach but on a sup-cell precision. Shoot a lot more rays and for each cell count the number of passing rays that are occluded and compare them with the number of passing rays that reach the cell unobstructed. Kinda like supersampling in rendering.

But I fear I can't afford to calculate so many raycasts. I'm working in Flash and AS3 code execution is still pretty slow. I got maps that are multiple screens big with many moving light sources and recalculating the lightgrid is allready taking a noticable performance hit. :/

Seems like this problem doesn't have a simple solution, yet! Bad news for the project at work but might provide some hours entertainment in my spare time! If I find something I'll let you know. (I don't want to imply that all roguelikes benefit from having antialiased field of views but it doesn't hurt to have the option, I guess)

[kraflab]

If it's important to you and you cannot find a fast enough solution, you may have to consider switching to a faster language.  Good luck at any rate though

[st33d]

Perhaps you want to actually do a grid based version of polygon shadow casting. Here's a tutorial on the subject:

http://forums.tigsource.com/index.php?topic=8803.0

It doesn't actually involve a load of hit and hope raycasts. There are already less vertices to consider around the light source than firing out 100 odd rays.

The actual brightness of a tile referred to in the original post isn't actually realistic. Light doesn't fade, it gets absorbed. Your best bet would be to track the slices of light that get through then perhaps colour based on coverage.

Though after all that effort, I really doubt the player is going to care or notice the difference between that and one of the standard LOS algorithms with a few hard coded tweaks.

[loom_weaver]

Full raycasting can be quite expensive assuming you need to incorporate all the tiles between the origin and the one you're checking.

A different technique, which is the one I'm using, is to represent what is visible to the player on an offscreen panorama.  For full 3D you need a two dimensional array but for 2D you can get away with a 1D array:

Initially nothing is obstructed:

Code: [Select]

0     PI/2    PI     3/2PI   2PI
00000000000000000000

If an obstacle occluded 25% of your view to the north:

Code: [Select]

0     PI/2    PI     3/2PI   2PI
11100000000000000111


You can make the array as large as you want to gain more resolution.

Next thing you do is do a spiral iteration from the origin outwards.  For each tile you're checking you calculate the angle (where in the array to start filling) and how wide it should fill (depending on the radius).

Now if what you're about to fill is already completely filled with 1's then the tile is fully occluded.  If the space is all 0's then it's fully visible.  Anything in between will give you a percentage i.e. an alpha value.  Once you determined the alpha of your tile, then you fill in corresponding area in the array with 1's if it's an obstacle.

I think this method will give you a decent FoV with anti-aliasing.  Since you are using a grid then you can pre-calculate the distances and the angles as they'll always be the same.  This is really fast too because now you only need some multiplies and integer operations and checking between any two tiles is now a constant time operation because any tiles in between have already been accounted for.

To do your grid-based lighting you store an alpha for every tile that you want to check.  Initially reset all values to 0.  Then repeat the above algorithm using each light source as a center and update the alpha value if it's greater than the current value.

[lithander]

Awesome. Two more approaches to solve shadows/FoV/LoS in 2D. How many are there? I've one on my mind that's not yet mentioned. Started implementing it yesterday and if everything works out I'll post it here.

@st33d: The solution you linked reminds me of the Stencil Shadows technique that was used in 3D games (like Doom3) before shadowmapping took over. In a game I made 2 years ago I used a geometrical approach, too. But that game wasn't grid based and I really aimed for some fancy shadow FX there. (http://www.newgrounds.com/portal/view/549686)
The problem I see is that you have to render the polygons to evaluate them by picking pixels. Pretty expensive if this is the only reason to render polygons, but allright if you do that anyway and the resulting buffer is easily accessible. I sampled the light-buffer in Rune-Hunt for gameplay reasons. To check mathematically if a cell on your grid intersects with the Shadow-Polygons sounds expensive too, so probably not the best approach unless you aim for the visuals, too.

@loom_weaver:

That's clever. A bit like a depth-buffer but thanks to the spiral iteration you don't even need that. Though I've a hard time to picture an iteration that visits the cells exactly in the correct distance-sorted order so that for each current cell all potentially occluding cells have allready been visited. Do you happen to have a game/demo that shows this in action?


Btw: Both of you implied that Raycasts is an inefficient strategy. But I don't think it's that bad. For a light with an effective radius of 10 cells (diameter = 20 cells) I have to shoot 4x20 rays. Each raycast aborts as soon as it hits an opaque cell. If diagonal movement is allowed each ray touches at max 10 cells. So you have to access your grid up to 800 times. If you use Bresenhams line algorithm you don't need floating point math or any other fancy calculations. I think for simple, boolean cases (is this cell part of the FoV or not?) Raycasting is pretty efficient.
My personal tests showed that to get really pleasing results you have to use combine to styles of raycasts: Only if a cell can be reached by a ray allowing diagonal movements AND by a ray that may only move vertical/horizontal it is considered visible. I'll post an example when I get home so you can judge the quality for yourself. Personally I feel like it pretty much matches human expectations. It just doesn't work to calculate the amount of light received for partially-occluded cells.

[lithander]

A first result on my quest:

Interactive Demo - Field of View on a Grid

So far all implemented algorithms use raycasting and don't handle partially-lit cells correctly. For now it's either lit or dark. (I'll use those as a reference to verify the anti-aliased FoV against)

"Narrow" means that the ray's can move diagonally whereas "Wide" does not not allow diagonal steps so it's wider as all cells are connected side-by-side.
Then there's "Narrow AND Wide" which basically means that both types of rays are shot and only if both reach a cell unoccluded the cell is considered to be within the Field of View.
Lastly there's a mode that aims to show the difference between "Narrow and Wide" by color coding those cells that differ between those modes.

I don't have a metric to say which mode works best. And I don't know how they compare to what is implemented in libtcod but I guess the results are plausible enough.

[lithander]

I've managed to implement the behavior I was looking for: light-source has a non-integer position and cells can be partially lit.



The code needs some cleaning up but it's functional, yay! In the end I settled on a recursive solution not discussed above. To calculate a cells occlusion it first querys the occlusion of those two neighbours that the light would have to pass through. Because occluders are at least one cell in size the occlusion of each cell can be fully described as a circular sector (defined by two angles) with the light source in the center. By intersecting the neighbours sectors with my current cells largest possible sector I get it's occlusion. The recursive setup calculates the occlusion by querying each cell twice - but calculations have to be made only the first visit. So complexity scales linearly with the size of the potential lit area.

Sadly I've got no IDE with a profiler at home so I'm not sure how much of an performance hit the trigonometrical calculations (atan2!) and the function-call heavy implementation are. But at least I got a working prototype!

Looks cooler in motion so here's an interactive Flash-Demo

[requerent]

Looks nice- do you have source up anywhere? I've been thinking about making a roguelike graphics library that uses tweening and animation to move objects between tiles. I hadn't considered lighting yet, and your little demo is very pretty.

[loom_weaver]

Pretty neat.  How is your game going to take advantage of it though?  Are you planning to animate the glyphs as they move from one tile to another?