Stencyl 3.4.0 is now out. Get it now!

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

merrak

  • *
  • Posts: 1418
I definitely appreciate the support  :D If anyone's willing to post a flyer or two then I'll invest more time into polishing it.  But the full desktop game may be a further ways out. To render in any appreciable screen size for a desktop game, I'll need hardware support. I do have a fallback for software-only rendering in large scale, but there are some upcoming features in Stencyl that should let me expand on what I have.

In the meantime, I'm tossing a couple of other ideas around. I really should do something with the original 6-color tileset. Completing a couple of small-scale projects with this engine would be a good way to see what really works and what needs revision before attempting something larger scale.

Speaking of which, I'm now this far:


Other than the "trim" on the tops of the walls, it may not look much different than earlier screenshots. But there is one important difference. That scene is put together with about 15 individual images, rather than one large image. In addition, the images are sorted from front-most to back-most--so I have proper z-order. If you read some of my earlier posts, you may have caught that I was on the route to abandoning z-order. After all, if I follow my own level design parameters, z-order isn't an issue. But that's not actually true. While the player should be in view, other moving actors don't necessarily have to be.

So I split the walls so that each wall has its own dedicated image. The really nice thing about this is that I don't need to replace "DrawStack" to render them. I can integrate my new tile system with the current rendering method for actors.

For anyone who hasn't seen me use that word, "DrawStack" is the rendering process I've been using since Page 1. It's based on an idea I read in a post by captaincomic (but maybe not the actual code, which I never saw but was posted to StencylForge). A more recent example would be Isotiles (I'm assuming, based on what rob1221 wrote about his strategy in that post).

"DrawStack" is a very effective strategy for rendering isometric graphics in Stencyl. But there is a limit to its reach, and that appears to be a 2.5D game world with "hundreds" of tiles. I have a 3D world with "thousands" of tiles, albeit with 2.5D rendering. That difference in the order of magnitude of tile count is the catch.

The scene shown has 24 walls, and roughly 15 or so visible. (The invisible walls are the ones behind pillars, under floors, etc. They're present for shadow computational purposes, collisions, etc., but not rendered). If I throw in some moving actors, then the number of elements "DrawStack" is managing is now one order of magnitude less than the limit, as opposed to one above. Dropping two orders of magnitude is a significant improvement, leaving much more computing power free for lighting effects, smarter AI, etc.

So, advice for anyone making an isometric game with Stencyl-- The "DrawStack" method works very well until your number of actors reaches "thousands". After that point, I suggest you have a plan in mind on how to combine them.

« Last Edit: July 10, 2017, 11:04:43 pm by merrak »

merrak

  • *
  • Posts: 1418
Renderer Result. Here it is.


The two blemishes on the left and right are to be expected, since I haven't yet defined the geometries for the invisible walls.

Moving the light to a position in front of the pillar:


And two lights:


merrak

  • *
  • Posts: 1418
So I'm finally at the fun part :D But also it's the annoying part... chasing down all the little bugs that only occur under specific circumstances. I spent the better part of this afternoon and evening chasing down a bug that turned out to be a problem in one of the most essential functions: projecting a point onto a plane. If you read the part about AABB projection (the linear algebra that is involved in shadow projection), there's an evil nuance. Projection doesn't work on a coordinate plane. What are the coordinate planes? They're the back of the back-most walls in the image below.


It's a non-issue if the light source is inside the scene. But if the light is outside, a shadow needs to be projected against the back wall into the room.

But having fixed that, it was time to start adding features! Here's a single-light source. Where did the door go?  :o


One reason I put so much time into the lighting system is that a large part of the game is based on the idea of hiding things in shadows. I want the player to be surprised, but I want it to feel fair, too. Enemies shouldn't just come out of nowhere, and I want to use shadows to put the player on guard.

Also... colored lights!


Most of the windows in Temple of Idosra are green, so I'd like to have a greenish tint.

And speaking of windows, there's now directional lighting. Got a flashlight?


merrak

  • *
  • Posts: 1418
I've been (slowly) going through the rest of the tileset from Temple of Idosra and configuring the tile geometries. This is an incredibly tedious process. Setting the image offsets, in particular, is frustrating.

To explain what that is, imagine a regular 2D tile or actor located at (x,y) in your scene. The image starts drawing at (x,y). This gets more complicated when your scene is 3D, since you have to project a point to 2D space and use that as the anchor point for the tile's image.

When things go wrong, well, this is the single most frequently posted image in this thread:


But it's also the most frequently recurring problem. It's made worse when structures are different sizes.


What's going wrong is this: I have a tile (stairs) located at (x, y, z). The steps themselves are defined by a sloping plane with four vertices. One of the vertices is (x0, y0, z0). To figure out where to draw the steps, I project (x0, y0, z0) to screen coordinates (Sx, Sy). I then add an x offset and y offset and draw the image at the resulting point. The offset is not easily calculated, because it depends on where that first plane vertex is--which is unique to the tile's geometry.

At least z-ordering is working. I never really talked about how that works, but I had to change strategies. My first solution assumed every actor and tile was the same size, so images could be sorted based on their (x + y + z) coordinate sum.

The new solution sorts walls (2D planes), not tiles (3D structures). Basically, I loop through all walls and compute the intersection of their respective on-screen polygons (compute Sx,Sy for all four vertices). The intersection is computed using the same Sutherland-Hodgman implementation I used for the shadows. If there is an intersection, I just need to pick a (x,y,z) point in the intersection and compare the depths using the (x + y + z) approach. Once again it's critical that all walls be convex quadrilaterals. An easy way to guarantee that is to make all walls rectangles (in grid coordinates)--hence the necessity of the "growing squares" algorithm.

The downside is that I couldn't get the built-in Array sort to work, since I have to compare each wall to every other wall. That's a lot of comparisons (quadratic time). While I only need to sort visible walls, there's still potential trouble in a complex room.

Sorting walls only needs to happen once, but sorting moving actors would have to occur every frame. What I might end up doing is partitioning the map's graph into three sub-sectors: visible, partially visible, and hidden. The first and third sub-sectors have simple rules. If a moving actor is in the "visible" sub-sector, then draw it. If it is in the "hidden" sub-sector, then don't draw it.  The "partially visible" sub-sector will be the pain to deal with. I'd prefer to find a way to use the painter's algorithm, since it's simple. The alternative would be to deal with more image clipping.

Edit. Here's what the scene is supposed to look like.


I used an red-orangeish light, which would be more appropriate for deeper areas away from the windows. The shadow follows the stairs rather nicely. This is a significant improvement over previous versions of the renderer, which were unable to work with any plane not parallel to a coordinate plane. This room has 77 walls, with about 30 visible. The Spring 2017 version of the engine (0.9.0, featured in March-May) would've used about 300-400 images to render this scene.

« Last Edit: July 20, 2017, 12:23:34 pm by merrak »

merrak

  • *
  • Posts: 1418
Goat Goal. There are two significant problems left to solve, then I can say I'm done with the renderer and move on to the next stage  :D These two problems are the "moving lights problem" and the "goat problem".

The "goat problem" is casting a non-planar shadow. Here's the goat. He's non-planar and he knows it.


He's based on the Spokane Goat of Riverfront Park. And here's the problem-- All tiles are rectangular solids and have six planes. The three forward-facing ones are labelled according to the coordinate plane they're parallel to: "XZ" for left, "YZ" for right, and "XY" for top.


These three planes are the ones called "tile faces". It's worth pointing out that "tile faces" are significantly different than "wall faces" and "wall planes"--the latter two of which deal with the geometry of the scene. Walls don't have to fit into the above template. "Tile faces" refer to the three images (or six, if I have to draw the back of a tile for some reason). Images that don't fit entirely into one "tile face" have always been a challenge to render--particularly when it comes to  clipping issues. The infamous stairs:


Stairs, however, are (mostly) planar. Since I'm not worried about casting shadows of individual steps, stairs come out looking pretty nice. The goat, however, is not even close to planar. But I can only cast shadows against planes.

I implemented Solution 1 and got promising early results. Basically, I cast the shadow against each of the three "tile planes" making up the goat. This results in a planar shadow. For each pixel in the shadow, I then reverse the projection back to the original image and see if it hits a pixel on the tile's image--in this case, the goat. This works pretty well if the light is hitting the XZ and YZ faces of the goat straight-on. But it falls flat in most other scenarios.

The best solution I can think of is to "simulate" a cylinder by storing the entire image of the goat in one plane, then rotating it so that its normal vector points "as directly as possible" to the light (while still remaining orthogonal to the floor). If you have a calculus background, you probably know where the phrase "as directly as possible" is taking us--a good old-fashioned optimization problem. This has the potential to be an ugly problem. On the plus side, vector function optimization is usually taught in Calculus III in US universities--and I'll be teaching that course next Fall semester  8) So I'll have a better 'real world' example to pique interest than the usual textbook examples. So, Solution 2 to follow sometime later.

Anyway, here's the only decent looking screenshot I got out of my first solution. The careful observer will notice a few quirks with the goat, but it's a step in the right direction.


And, for comparison, the same room in version 0.9.0


What a difference 0.0.6 of an engine makes..

merrak

  • *
  • Posts: 1418
Per-Pixel Perplexion. Let's speed up per-pixel image manipulation fifteen-fold.


One of the biggest bottlenecks in this project has always been updating images (BitmapData). Whether using elementary routines or the Image API, working with images has consumed more CPU time than anything else.(or even everything else combined).

My initial tests using the Image API were disappointing, but adequate. Basically, I could re-draw the entire 384x320 scene every frame and get either about 17 FPS or 25 FPS. The better number was achieved by writing the raw code myself, where as 17 FPS was achieved using blocks. Using blocks introduces some code I don't need (propertyChanged calls, for example), but even 25 FPS isn't great. But, I don't need to re-draw the entire scene every frame. Even if I fill the entire scene with tiles, the image is diamond-shaped, so I'll never need to update the corners. Plus, every wall is its own image, so I only need to re-draw walls that are updated. If no shadows move, and no light sources move, no updates are necessary.

I figured if I re-drew one fourth of the scene every frame, I should get a reasonable frame rate. This would be enough to allow moving lights in tight corridors, but moving sprites could not cast shadows and larger rooms would need to be approached with greater caution. Also, I'd need to re-think how to achieve 720p or 1080p resolution.

I recently stumbled upon hxPixels in this thread. I did a quick test comparing the Image API's draw pixels routines to the hxPixels routines and found a significant improvement in performance.

The test produces the image above, which is a screenshot I loaded into memory and then manipulated. Here's the code for the two approaches: The chosen method is ran multiple times every frame and FPS is recorded.

Code: [Select]
    // ImageAPI Method
    public static function drawtest1( )
    {
        DLit.lock( );
        for ( x in 0...384 )
        {
            for ( y in 0...320 )
            {
                imageSetPixel( DLit, y, x, imageGetPixel( DLit, x, y ) );
            }
        }
        DLit.unlock( );
    }

    // Pixels Method
    public static function drawtest2( )
    {
        var DPixels:Pixels = DLit;

        for ( x in 0...384 )
        {
            for ( y in 0...320 )
            {
                DPixels.setPixel( y, x, DPixels.getPixel( x, y ) );
            }
        }

        DPixels.applyToBitmapData( DLit );
    }

And results:

Repetitions     Pixels         Image API     hxPixels
Per Frame       Per Frame

   1x             122 880         24.8         60.0+
   2x             245 760         12.6         60.0+
   3x             368 640          8.4         60.0+
   4x             491 520          6.2         56.2
   5x                              ---         51.6
   ..
   10           1 228 800          ---         35.6
   ..
   15           1 843 200          ---         25.0

 720p (7.5)       921 600                     ~45.0
1080p (16.9)    2 073 600                     ~20.0


It's worth pointing out a few things. First, hxPixels is tagged "experimental", and was the first image manipulation package I found. There may be other, better ones. There may be unforeseen problems with hxPixels and Stencyl. Also, I'm only comparing per-pixel manipulations. Still, this is a promising first result. So far it looks like I can do a lot more in software than I was originally thinking. Being able to manipulate 921,000 pixels per frame is more than enough for 720p. The worst case scenario for my renderer is drawing a large, open room with flickering lights, since that would necessitate re-drawing every single wall on every frame. Even that wouldn't require drawing the entire screen... and I'd probably push something like that to a shader, anyway.

So, the "moving lights problem" is looking up.

Goat Problem Update.

As expected, the solution to the optimization problem in Goat Goal was ridiculous. The goal is to find the direction to point the goat's plane toward so that it points "as close as possible" to the light. The way to quantify that is to consider the direction the goat is facing (its normal vector) and the light's direction vector. The magnitude of the cross product of the two vectors gives the area of the quadrilateral formed by the two vectors. By minimizing the area, the vectors are "as parallel as possible".

Every so often "Stencyl 3D" comes up as a subject of conversation. To help illustrate the difference one extra "D" makes, here's the 3D solution: http://anorthogonaluniverse.com/misc/vallas/3dformula.txt

I worked out a 2D solution by projecting the light source onto the same plane the sprite occupies (the floor). I'll post the solution when I get it finished, but the math behind it is much more approachable without a Calculus background.

rob1221

  • *
  • Posts: 9029
Every so often "Stencyl 3D" comes up as a subject of conversation. To help illustrate the difference one extra "D" makes, here's the 3D solution: http://anorthogonaluniverse.com/misc/vallas/3dformula.txt
:o :o :o

merrak

  • *
  • Posts: 1418
Every so often "Stencyl 3D" comes up as a subject of conversation. To help illustrate the difference one extra "D" makes, here's the 3D solution: http://anorthogonaluniverse.com/misc/vallas/3dformula.txt
:o :o :o

I left out a lot of the details because the solution isn't going to work, but it's based off of Rodrigues' Rotation Formula. Apply the formula to get Nrot(t) -- rotation of the "Sprite Plane"'s normal vector by angle t.

Then compute A(t) = | L x Nrot(t) |, where L is the light's direction vector, x denotes cross product, and | | magnitude.

A(t) is the area of the parallelogram I described. The calculus starts out like a straight-forward textbook exercise. Compute A'(t) and solve A'(t) = 0 for t, but that's where it gets ugly. A' was too complicated to solve exactly (Mathematica hung up on it), so I approximated A(t) using a second-order power series approximation. Call it P(t). So that formula is the solution to P'(t) = 0. After I saw the formula I didn't bother verifying if it solved the problem. Mathematica hung up trying to simplify it, which is the sign it is time to throw in the towel :P