next »

[Armageddon]

Hey, I'm wanting to make a 3D tile-based game and I want a sort of fog of war lighting effect from the player/light sources as depicted below.


https://pbs.twimg.com/tweet_video/CJugVZGVAAAw3Zw.mp4
https://pbs.twimg.com/tweet_video/CK68Z_hVEAAe8TT.mp4

I really need a push in the right direction though of how to go about this in Unity. Every tile would of course be a mesh/GameObject. The only solution I can come up with is to raytrace the distance to the player and calculating the percentage of brightness/material color from that. Which would be very processing intensive and slow in my mind to do that for every tile every frame.

[SelfTitled]

You could do the distance calculation in the shadder. You would have to have properties in the shader for light positions and set them via script.

[Sqorgar]

I've seen tutorials on line of sight vision using ray tracing. I forget where (RogueBasin?) but I'm sure Google has you covered.

I'd use a recursive flood fill. Maybe something like:

Code:

void lightCell( cell, lightValue )
{
    if( lightValue <= 0 ) return;
    if( !isCellLightable(cell) ) return;
    if( cell.lightValue >= lightValue ) return;

    cell.lightValue = lightValue;

    lightCell( cellAbove(cell), lightValue - 10 );
    lightCell( cellToRightOf(cell), lightValue - 10 );
    lightCell( cellBelow(cell), lightValue - 10 );
    lightCell( cellToLeftOf(cell), lightValue - 10 );
}

Each frame, you can add a decay value to the light in each cell, causing the light to naturally diminish.

Using a recursive flood fill over a large area will absolutely overflow your stack, but if you use it for relatively small areas, it should be okay.

Also, this approach is more for ambient light, as it absolutely will spill around corners and get into cracks and crevices. However, (I haven't tried this) you can manipulate the order and light value of how you visit each cell to emulate directional light. For instance, if you are projecting light to the right, don't add light to the left of the cell and can have a higher drop off (lightValue-20) for cells above and below it. You can also do diagonals. Then just do a recursive, directional light fill N+S+E+W.

[tjkopena]

One extension of the flood-fill approach that incorporates some notion of line of sight, rather than just spilling around corners, is generally called recursive shadowcasting.  One way to look at it is that it's efficiently raycasting out from the source.  It's actually a really neat algorithm, and works well, with several tuneable parameters.  There are some notes on RogueBasin about it, and I have a little writeup and simple code here:

http://www.rocketshipgames.com/blogs/tjkopena/2014/07/recursive-shadowcasting/

I think this could be applied fairly readily to the OP's task.  In my demo I modify a tile layer of shadows above everything else in the 2D world, but presumably you could darken or otherwise change the view of a floor mesh and any geometry in the tile to render its visibility.  A simple distance calculation for visible tiles would let you fade things out if desired.

Demo from my writeup, displaying a 3 state map (completely unseen/seen but not currently visible/currently visible):

[You, sir, name?]

For what it's worth, I think both of these approaches are just special cases of Dijkstra's algorithm.

[Allen Chou]

I've used the flood fill method in the past, and it worked quite well.

Here's a tech demo video of my freshman project.




And here's the prototype of the flood fill method along with code.
http://wonderfl.net/c/lqhL

This other implementation has soft shadows based on distance from the obstacles. It's basically a 2D shadow map.
http://wonderfl.net/c/foPH

The last implementation is running on the CPU. Here's the original implementation on the GPU I used as reference.
http://www.catalinzima.com/2010/07/my-technique-for-the-shader-based-dynamic-2d-shadows/

[tjkopena]

For what it's worth, I think both of these approaches are just special cases of Dijkstra's algorithm.

I don't think there's a particularly meaningful comparison, though I'd be interested to hear counter-points.

These fill approaches are just visiting each node, there's no computation of path distance (as opposed to Euclidean distance for the shading), and the edges have a very fixed implicit structure.  Unless I'm missing something, the runtime is O(V), less than Djikstra even after you account for the fixed edges to potentially drop that to O(V*log(V)) from O(E+V*log(V)).  That qualitative difference implies they're doing something very different.  On the practical side, Djikstra visits all of the nodes and computes all shortest paths, whereas basically the whole point of the recursive shadowcasting is to efficiently not visit non-visible nodes as defined by the shadows.

[You, sir, name?]

For what it's worth, I think both of these approaches are just special cases of Dijkstra's algorithm.

I don't think there's a particularly meaningful comparison, though I'd be interested to hear counter-points.

These fill approaches are just visiting each node, there's no computation of path distance (as opposed to Euclidean distance for the shading), and the edges have a very fixed implicit structure.  Unless I'm missing something, the runtime is O(V), less than Djikstra even after you account for the fixed edges to potentially drop that to O(V*log(V)) from O(E+V*log(V)).  That qualitative difference implies they're doing something very different.  On the practical side, Djikstra visits all of the nodes and computes all shortest paths, whereas basically the whole point of the recursive shadowcasting is to efficiently not visit non-visible nodes as defined by the shadows.

Dijkstra's algorithm visits each node in the graph being considered, that doesn't necessarily translate to the entire game grid (that's just one implicit graph). I'll argue Recursive shadowcasting is Dijkstra's algorithm with a different implicit graph, one with a high branching factor near the origin of the "light", diminishing with distance from the light source.

That being said,

[Sigma]

keep a plane above the map and raycast a ray from player to plane upwards, set vertex alpha of vertices around the hit region to zero, thats how i did.