Stencyl 3.4.0 is now out. Get it now!

Merrak's Isometric Adventures -- Fast Per-Pixel Drawing

ceosol

  • *
  • Posts: 2091
Yeah, the 7 and 0. Her left foot was in the same place.

merrak

  • *
  • Posts: 1416
3. Creating a "Fog of War" / Line-of-sight effect

Warning: 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:

Code: [Select]
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[1]:


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:







« Last Edit: June 05, 2015, 10:30:59 pm by merrak »

mdotedot

  • *
  • Posts: 1168
Hello Merrak,

Awesome read but when I need the math I will copy-paste it from you since I could never figure that out for myself without having a whole bunch of if statements!!!

You have a whole lot of work to do on those animations !! The pile of 2D animations that I remember was HUGE! You would have to do them all again and probably more isometric orientations!
Hopefully you will stay focused enough.

The animation is better, but there is still a limb going on, also the arms feel like rotating instead of a pendulum motion.

But I have to applaud you for your efforts and the way you post them on the journal!

Keep it up!

Kind regards from
M.E.
Best regards from
M.E.
Hanging out in the Chat:  http://www.stencyl.com/chat/

ceosol

  • *
  • Posts: 2091
Your rendering algorithms are applicable to many different functions. Nice work. I will be coming back to reread this, I'm sure.

ceosol

  • *
  • Posts: 2091
I'm not sure if this is useful to you. It is what I used for larger area 2.5D.

merrak

  • *
  • Posts: 1416
Hello Merrak,

Awesome read but when I need the math I will copy-paste it from you since I could never figure that out for myself without having a whole bunch of if statements!!!

You have a whole lot of work to do on those animations !! The pile of 2D animations that I remember was HUGE! You would have to do them all again and probably more isometric orientations!
Hopefully you will stay focused enough.

The animation is better, but there is still a limb going on, also the arms feel like rotating instead of a pendulum motion.

But I have to applaud you for your efforts and the way you post them on the journal!

Keep it up!

Kind regards from
M.E.

Thanks for the tip! I was wondering whether or not I got the limp effect fixed. I think it's easier to spot these things after looking away for a bit, which is why I had to shift to another problem for a change.

I see the arm now-- I think there's an overly aggressive shadow on her arm--and her hand is rotating a bit.

I've been concentrating on the animations I can re-use in another project, if this becomes too much work. Thief of Vallas was always one of those projects I'd work on for a while, then step away and come back later... This time, I think I can do a better job picking what parts of the project to focus on first. The Isometric Engine, for instance, can be used on several projects in the future.

I've learned a good way to manage burnout is to assume it's inevitable. Start working on things that can be used multiple times, and document your work so that you can pick it up again later. Lesson two I've picked up: There's nothing wrong with taking a break, but make it easy for yourself to get back into the project--write clean, logical code, use comments, and generalize.

I'm not sure if this is useful to you. It is what I used for larger area 2.5D.

I've used atan2 quite a bit in other recent games of mine. It's definitely good to know that function! :)

For this particular application, though, I've tried to avoid it. Trigonometric functions can be computationally costly. (There's a nice overview of computational cost of basic functions here, if you're interested). In the Drawing or Update loops, I try to stick with vectors whenever I can. Vector operations are just addition/multiplication--not too expensive at all!

merrak

  • *
  • Posts: 1416
First Render

The isometric rendering engine is coming along nicely. I'm now able to show actual scenes! Below is the very first screenshot.



There are a few nuances I'm not happy with. The pillar to the right of center blends in with the back wall, for instance. However, I think that when the lighting code is complete, that will fix it.

So that the characters are not hidden from view behind tall walls, I've implemented a Diablo-style wall opacity control. Walls that block the player have their opacity reduced by 50%.

The actual game is intended to be a rogue-like, so most of the levels will be procedurally generated. For fixed levels, constructed using the scene editor, I borrowed an idea from captaincomic. Scenes are designed top-down:



The only drawback is that, since my renderer allows for multiple stories, the scene designer only lets me see one floor at a time. Different floors use different layers, but if I have multiple layers showing, there's no indication which tiles are on which layer.

It's also time to start thinking about controls. The original versions of Thief of Vallas used keyboard controls--like its inspiration, Prince of Persia. But now I'm thinking mouse control (like in Diablo I) would be better.

There are a number of reasons for this, but the biggest is that the mouse control scheme could be easily ported to a touch-control scheme. For example, in the original game, Marika could miss a ledge, but catch the edge of it and climb back up. This could easily be controlled with a swipe (tablet), or up arrow key (PC control).

I think this could be a fun tablet game if I can get the controls right. Of course, there could be a PC/Mac/Linux port, too.

Bombini

  • *
  • Posts: 771
This is so interesting and helpful!

ceosol

  • *
  • Posts: 2091
Have you tried a simple pathing "enemy"? Even on the plain gray tiles with black wall, you could try having the enemy pace back and forth. It would be neat to see it appear on a viewed tile and disappear again on a hidden tile.

merrak

  • *
  • Posts: 1416
This is so interesting and helpful!

Thanks!

Have you tried a simple pathing "enemy"? Even on the plain gray tiles with black wall, you could try having the enemy pace back and forth. It would be neat to see it appear on a viewed tile and disappear again on a hidden tile.

That's the next step :)
The walls in the original wall test were hard-coded. What's needed now is code to convert the pillars in the scene to walls (represented internally as a 3D array of vectors).

This wouldn't be too complicated if it weren't for doors. I could just use bar gates, but solid doors would give enemies something to hide behind :D Unfortunately, this means running the polygon shadow construction code for each possible state of the doors.

ceosol

  • *
  • Posts: 2091
Sorry this is a tad unsorted. It is my calculations from the 3D tests. I think I have some value in there reversed because the walls always came in upside-down :)

merrak

  • *
  • Posts: 1416
Your 3D Test is pretty impressive! It's a lot more complex than what I'm doing, since you can rotate the camera, where as I have a fixed perspective. My fixed camera spares me from all the angle calculations you have.

I wouldn't know where to begin looking for the cause of the flipped view. I always have to think twice about the screen coordinate system, since I'm so used to lower y-values corresponding to a lower vertical position--not higher. I suspect the wall glitching could be due to numerical round-off error.  But, I don't understand what is going on in screenshot 7. You either have some really big numbers, or really small.

ceosol

  • *
  • Posts: 2091
7 was for the axis flip. When you get close to zero on the z-plane, the number go crazy. I just threw that in to compensate.

I think you could still use the calculations, though. For you, Marika's "angle values" would be 0, 90, 180, 270 based on which of the four directions she was facing. In my calculations, I was generating things based on one fixed point and everything moving. Objects in your 3D space would leave many of the values in my calculations constant since the enemy/object's location would already be known to the computer.

Let's say you have an enemy.

In your top-down picture:
px and py are Marika's location.
vx and vy are the enemy's location.

y1a would be its head and y1b would be its feet (probably reversed since the calculations were mirrored).
You wouldn't need tz2, y2a or y2b because it would be counting the enemy having one edge (as opposed to the z-axis of two edges of a wall).

tz1 is the calculated distance from Marika in the 3D space. You could use the tz1 calculation to determine whether the enemy is too far into the fog to be seen (i.e. if tz1>20 = hidden)

merrak

  • *
  • Posts: 1416
I'm not sure I follow exactly what your code is doing, since I don't know what all the variables represent... other than px, py, vx, and vy that you told me. Does this compute the player's field of vision? (in this case, a cone projecting from the player's face)? It would help if I knew what vx1, vertx, and ty1 represent--since those are needed to compute tz1.

If this is the case, it's a neat idea. It could make the game too hard, though. It could also be really cool if I could get sounds to give the player clues as to what's behind them... sort of like in Doom. If nothing else, it'd be fun to play with :D

As for the calculations, there are actually 8 possible angles. The only drawback is the relative expense of the trig functions. I could squeeze a little more speed using vectors instead.

tz1 = < vertx, ty1 > . < cos(angle), sin(angle) > = < vertx, ty1 > . n
where n = <1,0> if facing east, <0,1> if facing south, etc.

The CPU usage of the game is starting to climb noticeably, and I haven't even added any real game content yet (moving enemies, AI, etc.).

The "fog", however, is already implemented. On every grid point there is a stored table of which other grid points are visible from that position. Each table stores every tile in a 5 x 5 "radius" (it's actually a square grid). Every grid point outside of this field of vision is assumed to be invisible. So, the fog is a consequence of this limitation. But--it doesn't store a separate table for each direction Marika is facing.

ceosol

  • *
  • Posts: 2091
All of the t's are for transforming 2D space into 3D.

tx and ty are both stepping stones for getting the x, y coordinates of each vertex on the screen. tz then represent the "zoom" function. I am not proposing that you have first person perspective, like what these calculations are meant to do. I am saying to repurpose the calculations. You also would not specifically need a bunch of trig functions going. Instead, have a straight calculation already set up for which of the 8 directions Marika is facing. The sin(angle) type of things would be a constant because you would not need to calculate every angle inbetween the 8 directions.

Your fog is based on the view trajectory from Marika's position. Utilizing my calculations would require using the least number of calculations to reach tz1 and x1 to see if the enemy's position fits into the fog trajectory calculations (lots of calculations in that sentence :P). x1 is the position of the enemy in relation to Marika's field of view (i.e. 0 being at the edge of sight). tz1 is the distance value from Marika. The x1 and tz1 would relate directly to the vx, vy of the top-down.