Rather than just explain where I ended up I'll explain the steps I took to get here.
Motivation
The player should not be able to see through walls. Why? I was going to say because it's unrealistic, but then I realized this is a 2D grid based RPG. It's unrealistic anyway, and if I shunned anything that was unrealistic there could be no magic or monsters in the game.
So perhaps the word is "unbelievable". Magic and monsters are unrealistic, but in the setting of a different world they can be believed. The world needs to be believed. As soon as the player thinks "that makes no sense" you've started losing them. A 2D grid and turn based game is on thin ice as it is in terms of immersion, if the player starts questioning the logic of the game world it all starts unraveling.
The player, being human, is familiar with how a human views a world. Therefore they expect by default that solid objects obscure things behind them. So on those grounds alone I want to make sure the player cannot see through walls. I could possibly come up with a game world based excuse such as the character has x-ray vision, but I don't think a world that is made of obviously contrived excuses can be believed.
Another reason for not allowing the player to see through walls is that I think discovery and the unknown are key parts of an RPG.
First attempt
At first I underestimated the complexity of the problem. I thought "hey this is pretty simple, all I have to do is trace a line from the middle of the player's tile to the middle of each distant tile and see if it collides with a solid tile on the way". Here is what I was thinking:
Testing whether the tile marked A is visible to the player by tracing a line from the player to tile A. All the tiles that are intersected by the line are tested. Because the line passes through the brown wall tile the test fails and tile A is considered not visible to the player.
Fortunately I did not implement this simplistic algorithm but went to google and looked up line of sight algorithms for nethack like games.
I came across this. I would usually dismiss stuff like this and keep searching but I noticed it was written in September 1989! Ancient wisdom!
http://www.fadden.co...c/fast-los.html
I didn't understand the proposed algorithm and it's probably not wise to use an algorithm over 20 years old without checking for newer improved ones anyway. But it did highlight some key problems I hadn't considered.
Take the following situation:
Player against a wall. Lines are traced from the player to each tile of the wall. Green lines are lines which go from the player to the target tile without being obstructed by another solid tile. Red lines are obstructed by other blocks on the wall itself
The player is up against a long straight wall in the example above. Now if you are up against such a wall in real life and you look to your left and right, you should be able to see the full extent of the wall. However the naive algorithm I thought of only allows the player to see the 3 nearest tiles of the wall.
How the naive algorithm would draw the wall. Only three tiles are drawn and the player does not know if the tiles in darkness are wall tiles. This is contrary to expected behavior. The player should be able to see the whole extent of the wall from where they are standing
Back to the believability of the game: The above behavior is less believable than I am willing to tolerate. The player will expect to be able to see the full extent of such a wall.
Fixing the problem
To solve the wall problem I devised an extra test for the naive algorithm. An additional trace is performed if the trace to a tile's center fails. This second trace is to the tile's edge.
If a trace line to the center of the target tile fails, a trace is attempted to the middle of the tile's edge. If that succeeds and the tile is solid then the tile is considered visible
Now all parts of the wall are visible. Hurray. There is a question remaining though about what happens if the "edge" case tile isn't solid as in the following example:
The center of tile A isn't visible to the player, but the edge is. Tile A is a non-solid. What should happen?
In terms of believability the answer to this question is not obvious. There are a number of options that are all believable enough:
1) Tile A is obscured from view (current behavior)
2) Tile A is shown in full with all it's contents
3) Tile A is shown as texture only, with a "fog of war" effect. Contents are not shown. This is to simulate that the tile is only partially visible allowing monsters, etc to effectively be hiding behind the wall.
It comes down to a choice. For now I stick with #1, but I want to eventually move to #3. Mainly because #1 is slightly flawed. An observant player knows the obscured tile is empty because if it wasn't it would be drawn solid. They can see part of the tile so they should be shown if the floor is made of stone, wood, etc. But I think it better that they can't see the contents (items, monsters).
Another problem: symmetry
Obscured regions are asymmetric. Because the diagonal lines are theoretically perfectly hitting the corners it's questionable whether they graze the tile or miss it. Due to precision error this manifests in an artifact.
Solution is to "shrink" solid area of tiles so there is a slight gap around the tiles. The traced diagonal lines now consistently miss the tile and produce no artifacts here.
This doesn't of course solve the precision error. There will still be a precision and symmetry issue, but now it will only occur where the trace line grazes the shrunken tile. The artifacts no longer occur in the very common and obvious case of pure diagonal trace lines. The artifacts are pushed back to happening in less obvious scenarios which the player is less likely to notice. That's good enough for me.
It does though allow the player to see along diagonals:
Player can see through the diagonal space between the two wall tiles
This is perhaps an advantage. A lot of roguelike games support diagonal movement and sight. I don't know whether I will. Ultimately if I don't want the player to be able to see through such gaps I could just enforce the game map so that solid blocks separated by only a diagonal aren't allowed
Flaws
The technique I use is to trace lines from the player to every tile in turn that needs to be drawn to determine if they are visible. There are better algorithms out there both in terms of performance and reducing artifacts:
http://roguebasin.roguelikedevelopment.org/index.php/Field_of_Vision
Additionally I need to consider that the line of sight and field of vision algorithm will not just be used to determine what the player can see but will be used more generally for AI purposes - ie what can the monsters see? It could also be used for lighting (ie which tiles are struck by the light from a torch). Both of these cases would increase the number of times the algorithm needed to be run and would probably require a better performing algorithm.
For now I am sticking with this simple solution, as it works kind of and I need to move on to other parts of the game. I can always come back and optimize/change this later.
Details
I have added two methods to the Map class.
public class Map
{
/// Returns whether a tile on the map is visible from another tile
public bool IsTileVisibleFrom(int tileStartX, int tileStartZ, int tileEndX, int tileEndZ);
/// Performs a line of sight test on the map
bool LineOfSightTest(int tileStartX, int tileStartZ, int tileEndX, int tileEndZ, TraceEndpointType endPointType);
enum TraceEndpointType
{
TileMiddle,
TileFarEdge,
}
}
The LineOfSightTest() method is used by the IsTileVisibleFrom() method. The IsTileVisibleFrom code is below:
public bool IsTileVisibleFrom(int tileStartX, int tileStartZ, int tileEndX, int tileEndZ)
{
if (tileStartX == tileEndX && tileStartZ == tileEndZ)
return true; //tile is visible from itself!
//calculate the x difference and z difference
float xDiff = tileEndX - tileStartX;
float zDiff = tileEndZ - tileStartZ;
//If the center of the end tile is visible from the center of the start tile then the tile is visible
if (LineOfSightTest(tileStartX, tileStartZ, tileEndX, tileEndZ, TraceEndpointType.TileMiddle))
return true;
//the center of the end tile is NOT visible from the center of the start tile.
//If the end tile is an empty space (ie floor) then it is not visible
Tile endTile = GetTile(tileEndX, tileEndZ);
if (endTile.Type == TileType.StoneFloor)
return false;
//The end tile is solid. There is one more check to make. If the edge of the tile is visible
//then the tile is visible.
if (LineOfSightTest(tileStartX, tileStartZ, tileEndX, tileEndZ, TraceEndpointType.TileFarEdge))
return true;
return false;
I won't post the LineOfSightTest() method code. It's nasty, mainly because it solves for one quadrant and for the other quadrants I swap or negate X and Z axes. Pretty common trick but it makes it a nightmare to read what's going on. This is what it does though:
Tracing a line from the player to the center of tile A. The entry and exit points of the line through each column of the grid are calculated (the red dots) and used to determine which tiles the line passes through and in which order
