The almost finished player's field of view, finally

One of the most, if not the most important mechanics in our game is that the player have no vision behind walls. I've had the task of writing this code the past few weeks now, and I'm happy to say I've finally solved it. As you can imagine there have been a few problems along the way and I will explain everything here in detail.

Early mockup of the shadow system

Before I talk about anything else, I want to make this clear: what exactly was I supposed to do?

Shadow system the we decided not to use.

   In the early development of our game we discussed how exactly the lighting system should work. We talked about making the player just barely be able to see behind walls, that way the observant players wouldn't be surprised when walking around a corner and only to be shot by a guard. However this was voted against and instead we added a sneak system where if the player is sneaking he can see nearby sounds, like footsteps of patrolling guards.
   We also considered only giving vision in a cone in front of the player rather than everything around him, this was also down voted leaving me with a definite task: make everything behind walls pitch black (except for sounds when the player is in stealth).

For the prototype it was more emphasis on getting a working solution rather than a good solution, so I thought of the easiest solution I could find. At the time I worked in SDL and had only used the draw line method and nothing else, so my solution was this:

• I have the player's position.
• I take a pixel on the edge of the window and call it point.
• I take a pixel and set its position to the player's position. I move it one pixel closer towards point until it hits a wall or arrives at point. When it hits a wall a line is drawn from its position to point.

If this doesn't sound too bad, let me explicate. When the player stands inside a wall this method compare values this many times: screen width * 2 + screen height * 2. For a window with the dimensions 1024x768 this is 3944 times it has to check for walls and draw lines. If there are no walls on a map this method runs a while loop around 450 times more times, almost 2 million times each update that is. This caused the game to run significantly slower even if there wasn't even one wall on a map that was 512x512 pixels in dimensions.

For the real thing I had to figure out a much better solution, so my first thought on the problem was to draw one black shape for each wall after everything else, except sound, had been drawn. Each shape would cover the area behind the wall from the player's position.This is a simple solution in theory but it has one big flaw, if I set an opacity on each wall making them see-through there would be darker areas where two walls cast their shadows. Back then we hadn't decided whether the player could see faintly behind walls or not so I had to think of another solution were overlapping walls didn't cause darker shadows.
   I came up with an idea that there was only one big shape that was drawn. It would be defined from taking all wall edge points and see if the current point is in front of the previous and the next, if so, then it should be included, otherwise it should be discarded. I didn't think to much on this since we decided quickly on having no vision behind walls.

Now it was time to get the shadows correctly.

1. At first I created a shape with four points. The first two points were always the same, the start and end points of the wall. The third point, the point after wall end, was going to be the point on the edge of the screen which if a line was drawn between it and the player's position, it would go through the wall end. I called that point the edge end. The fourth and final point was the edge start which was similar to edge end except it went through the wall start instead.
2. I realized quickly that this wasn't enough if the shadow hit a corner. At this point I thought a lot on two different possible solutions to this specific problem. The first one being to simply extend the two edge points beyond the screen thus creating a large quadrilateral. The second one was to find the corner and set another point there. I liked the second solution better since it was a neater solution and I believed it shouldn't be too hard.
3. So I changed the shape to have five instead of four points. If the shadow didn't hit a corner, the now fourth point would have the same position as the third point, edge end. I moved the edge start to position five since the corner point had to be between the both edge points.
4. I believed I was finished here but before I could program too much I realized that the shadow could hit two corners, so back to thinking again. I had already decided on this specific solution so not much was needed to change. I added one more point to the shape and moved the edge start to position six to let the second corner come between it and the first corner. Then I got to the programming bit.

In the wall constructor I set the shadow to have six points and a fill color of black. Then I set the first two points to wall start and wall end.

   In the update I set the remaining points depending on the player's position. I first calculate the two edge points, then I use those points to calculate the corners.

To get the point on the edge of the screen was fairly straight forward. I first calculated the unity vector from the player's position to the specified wall position. I took the unity vector and calculated how many steps it had to go to reach the edge of the screen in both x and y-axis. Then I multiplied the unity vector with the smaller distance of the x and y value. Lastly I returned the walls position plus the vector, which is the position of the point on the edge of the screen.

   For example: the player's position is x = 138 and y = 88. The wall position is x = 128 and y = 128. The unity vector from the player's position to the wall position is then: -0.24 in x-axis and 0.97 in y-axis. The distance to the edge of the screen in x-axis is 128 since it's moving in a negative direction and it's x position is 128, therefor it takes 128 / 0.24 which is approximately 533.33 steps to get to the end of the screen on the x-axis. The distance to the edge of the screen in y-axis is the window height, 768, minus the wall y position; 768 - 128 = 640. Therefor it takes 640 / 0.97 which is close to 659.79 steps to get to the end of the screen in y-axis. Since the unity vector hits the end of the screen on the x-axis first I multiply the unity vector with the number of steps it takes to get to the x-axis. This gives me the vector from the wall to the edge of the screen and so I just add the wall position to the vector and ta-da, I have the edge position!

To see if there is a corner between two positions was a little bit harder. First of all I had to have the player's position as well as the two points I wanted to check since I need to know which way I should look for a corner. Secondly I tested if there even was a possibility that there was a corner between the two points, if there weren't I just returned the first parameter (the position took look for corners from). Then I tested to see if the first parameter was a corner, if it was, the second corner had the same x or y value as both the points and the other value equal to the second point. If however the first point was not a corner I tested to see if there were two corners between the two points, if there were, then it found the first corner by taking the x or y value from the first point (whichever is 0 or the screen dimensions) and the other value is set to 0 or the screen dimension depending on the player's position. If the first point was not a corner and there was only one corner between the two points, the corner had the same x or y value as the first point which ever is a 0 or screen dimensions and the other value of the other point.

That worked fine, until we added a view port. . .

Bugged shadows

What happened when we added view port to our game was that no longer was the top left corner always at point 0, 0 nor the bottom right the width and height of the screen. Since both my methods EdgePoint and GetCorner calculated everything from 0, 0 to width, height; adding the view port made everything to bug completely except when in the top left corner of the game.
   It may sound simple to change this, I certainly thought it should have been. However after several hours of not understanding why my changes didn't work I started to doubt my code. I looked deeper into SFMLs View class and it worked just as expected so there was clearly something wrong in my code but I just couldn't see it. After a week I described the problem to my programming teacher Tommi who said I shouldn't make things so complicated. He advised me to draw huge shapes that went way outside of the screen instead.

Since I had already thought some on this idea it didn't take long until I knew exactly what I should do. It was basically exactly the same as getting the point on the edge of the screen except taking the longer distance instead of the shorter one.

In the end the code looked like this:

Define m_shadow in the constructor

Update the two changing points in m_shadow

The get point method

In the GetPoint class I set the maximum value on distance to 1 million, I do this because the value can be infinite if the player is on the same x or y position which results in the shadow not drawing at all.

That was all I think! If you made it all the way please leave a comment. Also thank you for reading and stay awesome!