Stencyl 3.4.0 is now out. Get it now!

Merrak's Isometric Adventures -- Box2D and Simple Physics

merrak

  • *
  • Posts: 1313
What could be behind that wall??? Only one way to find out!

<a href="https://www.youtube.com/v/ZZsIlMkKkxg" target="_blank" class="new_win">https://www.youtube.com/v/ZZsIlMkKkxg</a>

All of the t's are for transforming 2D space into 3D.

I think I see what it's doing, now. For this particular game, I'm not sure if it's really necessary to do these computations just to hide the enemies. Since the "fog" generation is already implemented as a side-effect of the code that works out the walls, there's no need for an additional check (at least, at the moment. Never do know what the future has in store ;)).

But--my "fog" is binary. I could definitely see using tz1 to implement a more realistic-looking haze/fog, since you could get a smoother gradient. I'm not sure if the actual drawing of the fog would be quick enough on a Flash port... but on PC/Mac/Linux it could look really nice.

///

Today, I got the code which converts the walls in the 2D scene editor to the 3D space working. Surprisingly (very surprisingly) it even worked on my first try. This has definitely not been the case for anything else I've done. I even had all my print statements ready to fire, dreading the big debug.

However, the wall renders do need some tweaks. The polygonal "shadows" don't quite overlap correctly, which means every so often there is a tile that is visible that shouldn't be.

On the art side, Marika can now stand and walk, which means I'm getting closer to putting out an actual, playable demo. So far I have 200 animation frames completed. I'm still polishing the walk state, which is the base for most of the rest.

« Last Edit: June 12, 2015, 11:33:09 pm by merrak »

merrak

  • *
  • Posts: 1313
4. Solving the Visibility Problem

One of my goals keeping a game journal here is to collect all my research on isometric-related problems in one spot. Hopefully it's a good resource for someone down the road. However, I realized I left out one of the most important problems of all. How do you determine which actors to draw first?

The ideal solution would be to use a Z-buffering algorithm. Unfortunately, this doesn't look to be practical. Drawing each pixel one at a time appears to be a slow process, but even if it weren't, we don't have 3D models. "Isometric actors" are really 2D images drawn to look 3D--but the computer can't work out the relative depths of each pixel from the artwork alone.

Instead, we're going to use the painter's algorithm.

Here's the problem:



Two actors with unique coordinates (in the isometric coordinate system) overlap. We want to figure out which one is behind the other. The solution makes good use of linear algebra. If this is something you've never studied before, there's a great introduction on Wolfire Blog, specifically written for game developers.

One of the first problems was mapping coordinates in the isometric system ("world coordinates") to screen coordinates. This was the first problem solved. The conversion formula is, where Sx, Sy are screen coordinates, and Gx, Gy, Gz are world coordinates:

Sx = Gx - Gy,    Sy = 1/2 Gx + 1/2 Gy - Gz

In my illustration above, we have two actors that have the same Sx, Sy coordinates.

Now, here's something to think about. When converting from world coordinates to screen coordinates, we went from three dimensions to two. In effect, we deleted information. Points in the world are described with three variables... but in only two on the screen. What happened to that third piece of information?

It turns out that we really threw out the answer to the depth problem! So, we need to recover this lost information. What happened to it shouldn't be hard to visualize if you're familiar with those old big-box CRT monitors. Imagine "Actor 1" and "Actor 2" being suspended inside the monitor, at different depths. If you look at the screen straight-on, they overlap. However, one is really further back.

Both actors are on a vector that is orthogonal (perpendicular) to the screen. We just need to understand what this vector is, and then we can come up with a formula for the depth.

From the formula, since Sx = 1 * Gx - 1 * Gy, then Sx is a point on the vector <1,-1,0>. Furthermore, since Sy = 1/2 * Gx + 1/2 * Gy - 1 *  Gz, then Sy is a point on the vector <1/2,1/2,-1>.

The cross-product of these two vectors will be a vector orthogonal to the screen--thus, overlapping actors will lie on this vector, and we can compute their depth by calculating how far from the origin, along this vector, they are. The cross-product is <1,1,1>, which gives this formula for Sz: 1 * Gx + 1 * Gy + 1 * Gz, or:

Sx = Gx - Gy,    Sy = 1/2 Gx + 1/2 Gy - Gz,    Sz = Gx + Gy + Gz

Now, here's a method you can use to draw your isometric actors.

Let's suppose you have an isometric world that is 400 x 400 x 400 units. On scene creation, initialize an array of 1200 "buckets" (400 + 400 + 400). Each bucket will hold actors that are to be drawn.

When an actor is moved from coordinate (Gx, Gy, Gz) to coordinate (Gx', Gy', Gz'), remove it from bucket # Gx+Gy+Gz and add it to bucket # Gx'+Gy'+Gz'

Now, in the drawing event, loop through all 1200 buckets. Since each of these buckets is itself a list of actors, you'll need to loop through the contents of each bucket.

Sadly, this won't be a perfect solution. Here's an example of what can go wrong:



So, what went wrong? The pillar that is clipping the player is really tall. Each actor is represented in the isometric world using only a single point. But different heights along the pillar will have different Sz values. Since the actors are different sizes, there's no standard that will handle every case.

The simplest solution I can think of for now is to have all actors be the same size, and split larger ones into standard-sized chunks. The pillar, for instance, can be split in half--so that each half is the same size as any other actor. This works.



In my current implementation, I use "Draw image of actor". But, it seems like it would be possible to split each actor's image into equal-sized tiles. These tiles can be saved in the extras folder, and then assembled in the drawing loop. Each tile would have its own Sz coordinate. The smaller each tile (and hence greater number of tiles per actor), the better. For this game, though, the only large actors I can imagine needing are structural (pillars, etc.). Since they don't have nearly as many frames as moving actors, splitting them isn't difficult at all.

merrak

  • *
  • Posts: 1313
I set a goal to have a playable demo/prototype by the end of the month. So far, I think I'm actually on track--despite the fact that there have been more uphill battles than downhill. The artwork is sparse, but enough to get the point across. The isometric renderer has a growing number of features either completed, or near completion:

- Configurable screen size, tile size, height
- Line of sight calculation
- Shadow polygon calculation
- Diablo-style point-and-click movement, which can be configured for both PC and tablet ports.
- Updated "Actor State Manager": This is a variation of the Animation Manager (that ships with Stencyl) that I worked on with the previous version of Thief of Vallas. It's designed to make it easy to associate animations with actions. (e.g. the up arrow performs a jump if the player is standing, stand up if crouching, etc.).
- Debug tools

The isometric actors require a lot of tedious adjustments. Most of these result from a 3D solid being internally defined as a single point. Preventing wall clipping, for example, requires setting the artwork offset from this internal point just right. It's a pain and a half, but it could be worse without an isometric version of the debug draw mode--which is what I worked on today.

Here's the isometric debug draw showing with Stencyl's.



Purple circles are grid points in the isometric world, and cyan dots the position of actors (including walls). Marika's dot is on her knees because if it's lower, you can see her feet poking out from under a wall she is behind. There's no perfect solution to the clipping problem, but her collision box prevents her from getting close enough to the walls to cause a problem.

Stencyl's debug draw could make a neat 2D map that overlays the game play field (sort of like Doom's automap). However, I'm planning to allow for multiple floors stacked on top of each other, so a 2D map overlay wouldn't work.

You can also see how collision detection works. Since most actors move in 2D, I wrote a simpler collision detection than the one on the first page of this thread. Marika is represented by the circle, which is actually a separate actor. All of the player controls manipulate the circle. The image of Marika is positioned based on the circle's position on the 2D map.

The only drawback is this makes it tricky to implement multiple floors. The wall collision boxes are generated terrain, so the mechanic of changing floors will likely be very similar to the mechanics of the multiple block phases in letmethink's Remake of Greenie

Speaking of debug draw, here are the shadow polygons:



To implement the shadows themselves, these polygons can be rendered black and then used as a mask. These polygons are stored for every row, column. For shadows, the exact polygons to use will depend on the coordinates of the light source. This could be used for dynamic lighting (say, if Marika were holding a torch), but I'm not sure how it would look with discrete transitions.

ceosol

  • *
  • Posts: 2044
I've read about stacked map theory. From what I could tell, just make a sketch for yourself and mark off all "sectors" of the map. This means any room, passageway, stairway or upper floor that has a discernible boundary. Once you have a list of all map sectors, you can write down which sectors are visible from those points. Then you plug the sectors and visible sectors into a 2D list and you are good to go. Make any sector counted as non-visible fade out (i.e. shut off all behaviors) and any sector that Marika is currently in or has sight to be subject to whatever calculations, etc., you have going on.

FYI: I'm not claiming to have a clue of what you are doing. Just trying to help :)

merrak

  • *
  • Posts: 1313
I've never read about "stacked map theory", but what you're describing sounds very similar to how visible tiles are computed. Instead of a matrix of sectors, each tile contains a list of other tiles visible from that point.

The idea of blocking off sectors of the map in this way is a very interesting thought. I hadn't considered it before, but this could be a much better way to implement multiple floors. Instead of consistently building and deconstructing terrains, I could divide the map into, say, thirds--and have each third map to a separate floor.

The error handling in the isometric renderer is already capable of the boundary checking that would be needed to implement this. (The "ERR 0399" in the last screenshot, in fact, is the renderer catching an actor about to go out of bounds).

Certainly worth thinking about. Thanks for the tip! This was very helpful. :)

merrak

  • *
  • Posts: 1313
Just when you think you have all the bugs ironed out...



The blue dot on Marika's knee represents her position in the world... and you can see it's on the wrong row. Whoops!

Feel like making an isometric game of your own? I uploaded a small demo project you can download and build off of.



What's implemented:

- Basic implementation of the Isometric Manager (draw stack, parameter initialization, scene construction from default Stencyl scene editor and load from file)
- Isometric Position Manager
- Isometric Velocity Manager

You can download the .stencyl export on my site. You'll need to install the computation tools extension.

This is a much older version of the Isometric Manager that Thief of Vallas uses. For serious use, my recommendation would be to re-write the Isometric Manager from scratch, tailored to your own specific needs. As you can see from my screenshots in the past few posts, careful adjustment is needed to maintain the correct draw order. What works for one game may not work for another.


merrak

  • *
  • Posts: 1313
That's pretty slick! They seem pretty far along, but it's not scheduled for release until 2017.

ceosol

  • *
  • Posts: 2044
I noticed that they went with 8-way directional. It seems pretty smooth for them. Maybe forego with the plans for full movement and stick with 8-way for now.

merrak

  • *
  • Posts: 1313
I'm probably going to restrict to 8-way, but it's currently not implemented. The animations are 8-way. None of them seem to do a bad job approximating the other directions. The worst case scenarios are the odd multiples of 1/16th full rotation, which lie perfectly between two of the directions... but they seem okay.

If anything is going to necessitate restriction to 8-way, it will likely be jumping and climbing. Ledge detection in the original version of the game was complicated enough. Add to that a requirement that the angle between the player's direction and the ledge be within a certain range, and suddenly the programming gets much more complicated. Then, once it works, the resulting challenge could be too tedious.

merrak

  • *
  • Posts: 1313
5. Dynamic Lighting

The todo list for the isometric renderer is still has some major components, but the light is at the end of the tunnel! And, speaking of light, Thief of Vallas now has dynamic lighting.

Here is the static lighting.



Lighting is animation based, so tiles that do not have a "lit" state do not light up. Such is the case with the wall behind the torch. For sprites, I could probably just use tint. In fact, I'll probably have to. Marika already has over 100 frames, and I really don't want to hand-paint the various lighting states on each one. It is much easier to hand-paint lighting on the tiles, since they don't animate.

I noticed in the old Disney animated movies (the hand-painted ones--not computer animated), the backgrounds were much more elaborate than the moving characters. This will probably be the case with lighting in Thief of Vallas.

But, the best part -- lighting is now dynamic! Watch the fireball illuminate the corridors. You can even see traces of light when it is behind a wall.

<a href="https://www.youtube.com/v/LjCxd946zDM" target="_blank" class="new_win">https://www.youtube.com/v/LjCxd946zDM</a>

Marika currently has no shadow. If Marika does not see her shadow, then it's six more weeks of programming.

merrak

  • *
  • Posts: 1313
Just a couple more screenshots as I put the finishing touches on the lighting procedures. At some point, I need to start working on the actual game.

I still plan to make Thief of Vallas a rogue-like, which means auto-generating levels. An older game of mine, Caverns of Io, uses different variations of a maze generation algorithm. I'll also need to implement A*, and probably from scratch. The Stencyl A* extension uses tiles, which may be a problem since I don't use tiles in the "traditional" way.



I'm pretty happy with the lighting. I think I'm setting the mood I want, although it needs some polishing. The torch was an old asset, and is way too dim. I also need to make a proper tileset (with tiles for rounding corners, etc.) The flat tiles just don't line up correctly around bends. There's also a rather ugly gradient, but I can smooth that out with some tweaks to the light level calculator.

The bloom shader does a great job smoothing out some of the lighting. I like the fantasy/dream-like glow, although Marika herself is way too bright. I'll have to figure out how to exclude her from the bloom.



Lighting certainly makes a big difference. The look has come a long way from the first week of June.


petersdream

  • Posts: 94
Lighting certainly makes a big difference. The look has come a long way from the first week of June.

I was reading your game journal and I must say I am really impressed.
Not only you made huge progress but also you are making something really challenging.

I believe Merrak's Isometric Adventure should be used as a great example that the only limitations to Stencyl is your imagination.

My most sincere congratulations, keep up the great work.
Indie Game developer (at night). Currently working on his dream game for iOS.
@petersdreamgame



merrak

  • *
  • Posts: 1313
Thanks for the kind comments!  It certainly has been a challenge--more research than anything else. Organizing it all in one spot and demonstrating one way it can be done with Stencyl is the primary reason I wanted to keep this game journal.

At some point I really should mention the things I wish I had done different. There are a number of them that would have saved me some effort.

merrak

  • *
  • Posts: 1313
I'm still shooting for having a working prototype by the end of the month... which is quickly approaching! This goal is really more for me than anything else. The prototype simply serves to prove the concept can be realized. While interactive, it won't be a real, playable game with fun things to do. Still, it is satisfying to set a goal and achieve it... and on longer projects, the milestones matter more.  8)

So, what's left to do? There are some finishing touches that are needed--the things that don't really matter until you notice they're missing. For example, the scene initialization process can be excruciatingly slow on Flash. While there are things I haven't done yet to speed this process up, it'll always take time. Since a blank screen can be disconcerting, I made a progress indicator.



While it may not be much to look at, I'm sure it'd be missed if it weren't there. It was also surprisingly difficult to put that in. In November, I can replace it with a loading screen game.

Of course, there's error handling.



There's a good reason, too. In the future, I want to let people be able to make their own levels. This was always my own favorite part of video games. But, the isometric renderer can be finicky. No matter how many safeguards I put in, someone will find a way to break it.

When it comes to speed, Flash is most vulnerable. The frame rate stays at a nice 60 FPS on Google Chrome, but only crawls on the Adobe Flash player that ships with Stencyl. (Since I'm on Linux, I still have the old version 11 player). The renderer now detects low performance.



Here, the framerate dropped below 25 FPS. In the future, it'll be able to recommend some options to make the game playable, such as disabling the lighting I put all that work into.