3. Creating a "Fog of War" / Line-of-sight effectWarning: Long content! But I wanted to document what I did in case anyone is looking to implement something similar--or just learn some gamedev-related math. Hopefully this is helpful information for someone down the road!
I've created enough animations that I think the task is doable--but certainly not in one go. So that I don't burn out on drawing the same character 1,000 times, I switched brain hemispheres again and started working on solving a programming problem.Thief of Vallas
has changed in numerous ways since I first picked up Stencyl, but one thing has always remained constant--it's a game of exploration. but, it's hard to make mysterious levels if the entire screen is visible at once
So, here's the goal: A "fog of war" and line-of-sight effect (see screenshot above)
And, the rules:
1. Places Marika has never seen are completely black (areas outside of her vicinity, or behind walls)
2. If Marika has been to a place on the map, but can't see it (too far away, or behind a wall), then structures of the level will be visible--but grayed out, dark, etc.
3. If Marika can see an area, she'll see the structures and mobile actors
Keeping a record of where Marika has been will be easy. The hardest challenge will be to determine which tiles are behind walls. There are a lot of algorithms out there for this computation. There's also the RayCastAPI, which would've made this task much easier. But I decided to build from the ground up. There are a number of reasons for this, which will be mentioned later.
This is the basic procedure:
For each tile at row r, column c
For each wall within a certain radius (the maximum distance the player can see)
Compute the polygon (quadrilateral) "shadow" from r, c to the wall
For each tile at row r', column c',
If tile at r', c' is inside the quadrilateral "shadow", then flag it as "hidden"
In effect, there is a list stored at every row and column that lists the all the tiles within the max radius of sight that are hidden behind a wall. This list is generated when the level is loaded, and needs only be read in the draw loop--saving valuable time in the "Drawing" loop.
These polygons are also why I didn't want to use the RayCastAPI. In my "Isometric Engine", you're seeing the image of the actor, not the actor itself (Draw Image of [Actor] block). The original actors stay in their starting positions, invisible. They could be used. However, I want to save these polygons for future use. When I'm ready to implement shadows, I'll have the polygonal generation procedures in place... and the same code can be used to determine the hidden tiles and draw the polygonal shadows.Analyzing the walls
There are two steps that must be performed to compute the polygonal shadow. First, we must determine if the wall is facing the "light source". (Which, in this case, is the player). Only the walls facing the light need to have a shadow cast.
This is a quick calculation. We'll take the dot product of two vectors: n
, which is normal to the face of the wall, and <u,v>
, the vector pointing from the player (r,c) to the coordinate of the start of the wall (r',c'). This vector is <r'-r,c'-c>
The face normals are simple, because the tiles lie on a rectangular grid. The normal for the north face is <0,-1>
, south face <0,1>
, east face <1,0>
, and west face <-1,0>
If the dot product is negative, then the wall faces the player/light, and we need to cast a shadow against it.Computing the polygon "shadow"
Once we know the wall casts a shadow, we can construct the polygonal shadow it casts. The simplest method is a quadrilateral (more on why we want that later). The figure below shows the shadow.
Let's call the coordinates of the wall (r1,c1) and (r2, c2). To determine the other two points of the shadow, we simply need to take the vectors pointing from the player's position--(r,c) to (r1,c1) and (r,c) to (r2,c2). We extend these vectors outside of the max radius of sight.
The vector from (r,c) to (r1,c1) is <r-r1,c-c1>
. If M is the max radius of sight, then we extend it and get another coordinate for the polygon. Repeat for the other wall coordinate, and here is our polygon:
(r1,c1), (r2,c2), (r + M(r2-r),c + M(c2-c)), (r + M(r1-r),c+M(c2-c))Is a tile inside this shadow?
There are a number of ways to determine if a point is inside a polygon--ray casting is a possibility. There's also the winding number
But, since the polygonal shadows are quadrilaterals, there's an even simpler approach(source)
. For each side of the polygon, we compute
(R - Ri) * (Ci+1 - Ci) - (Ri+1 - Ri) * (C - Ci)
If all four sides have the same sign, then the point is inside the quadrilateral.Wrapping it up
That's pretty much all we need to implement the basic algorithm outlined at the beginning. Save the polygons for future use--shadows!
Here are the results: