Merrak's Isometric Adventures -- Drawing Order Algorithms

Dependency Problem. As is usually the case around here, the actor rendering order problem has turned out to be more difficult than originally anticipated. In the old engine, the solution was easy. Every actor and tile was the same size. Create a list of every actor and tile (what I called DrawStack) and sort the list based on (gx+gy+gz)--distance from the "camera".

Last time I wrote about this problem I mentioned that this doesn't work for the walls. Walls are different sizes. But that's okay. All I had to do was figure out which walls needed to be drawn in front of the others. This was the original dependency problem that called for the topological sort. Walls are only ordered relative to their neighbors. In the screenshot below, it is impossible for Wall1 and Wall2 to overlap. So the order those two walls are drawn in doesn't matter.

On the other hand, Wall1 must be drawn over the red floor tile. So there are multiple drawing orders that solve the problem: (W2,F,W1) or (W1,F,W2).

What I want to happen is pretty clear. If Marika is standing in the red square, she should be drawn behind Wall1 and Wall2. Otherwise, she should be drawn in front of the walls. In both cases she should be drawn in front of the floor.

But because the floor never overlaps with Wall2, I can't assume that Wall2 is placed after the floor in the drawing order (DrawStack). The floor could just as easily be placed after Wall2. So if I place Marika after the floor so that she is drawn over it, then she could also be drawn over Wall2.

What I really don't want to do is call the topological sort every time any actor changes position. I think this would be way too costly.

Topological sort is achieved by defining dependency rules, so I need to identify a new rule. The floor must always be drawn before Wall1 and Wall2. Even though the floor never overlaps Wall2, its contents might.

I'm now wrestling with a couple of potential solutions. One idea I thought of was to partition each sector into subsectors. Floors define occupiable volumes, so I loop through all the floors and start building occupiable spaces for which every point is in front of the same set of walls. I can then add rules to the dependency graph that insists the floor is always rendered before every wall in front of it and after every wall behind it.

This solution has the problem of defining the spaces, which is a tricky one but can be part of the game loading sequence where speed isn't as much of an issue. Once I have the spaces defined and the walls ordered, I won't have to do any topological sorting in-game, which was one of my concerns. I don't trust the topological sort to work efficiently enough to maintain 60 FPS.

When Good Solutions Go Bad... So I spent about a week chasing a bug. Admittedly, I could've fixed it quicker if I weren't participating in Nanowrimo this year. The feeling of accomplishment after fixing a persistent bug is soon met by the annoyance at the time wasted trying to find it.

That's why I spent as much time as I did writing the error checking routines. The extra time would pay off in less time spent chasing bugs. The system is so big and complex I can't possibly memorize the entire thing, so having the error check standing guard is helpful.

The wall renderer can't render the "Impossible Room" (like in an MC Escher drawing). This would be the consequence of a cyclic wall dependency graph. Suppose Wall 1 needed to be drawn before Wall 2, and Wall 2 needed to be drawn before Wall 3. If Wall 3 also needed to be drawn before Wall 1, it would be impossible to resolve the drawing order.

It turns out the renderer would happily try, though, because the error detection wasn't working. It looks like a problem with the topological sort algorithm on the Wikipedia page, which should raise a flag if a cycle in the graph is detected. Or maybe I misinterpreted something in the implementation. Either way, I implemented a new algorithm which works better.

So now it appears I don't really have a good solution to the original problem. In addition, sorting one actor every time it changed subsectors (every five or so tiles) caused a noticeable hiccup in the framerate. So even if I did come up with the proper way to sort floors and walls, the solution would be laggy.

Back to the drawing board, then! I realized all this time I've been solving the wrong problem. If I adhere to the level design guidelines I wrote down, the player disappearing behind a wall shouldn't ever happen. The good news about all this effort is that I ended up learning quite a bit about how OpenFL and Stencyl manages scenes, layers, and so forth. So now I have enough knowledge of the Stencyl engine to write a new layering system.

This is so amazing merrak!
I have difficulties understanding everything but is is very inspiring.
Thanks a lot for sharing!

This is so amazing merrak!
I have difficulties understanding everything but is is very inspiring.
Thanks a lot for sharing!

I agree. This is really impressive to see. I tested the prototype version of Thief of Vallas and it's amazing how you developed this engine.

Thanks for the feedback!

Here's a bit of trivia I dug up while researching sprites: There is a 'useHandCursor' boolean in the Sprite class. I haven't had time to play around with it, but it might provide a better answer to a recent question posted to the forums about setting the hand cursor when hovering over things like buttons.

... I tested the prototype version of Thief of Vallas and it's amazing how you developed this engine.

That older version was put together entirely with code blocks (Except for the Isometric Coordinate Conversion Extension, which is primarily just a set of math macros)

Victory. Who's that hiding behind the pillar? That's right, it's a properly rendered actor.

Before I got caught up with Nanowrimo, I passed the time between compiles doodling little machines. Who knows, maybe a business sim game?

Something like Vallas Engine would be overkill for an isometric factory game which has no lights or shadows and has traditional 2.5D scenes. It would also be under powered if I wanted lights and shadows, since I would need a high number of polygons to render them. Still, might be a fun project to jump into sometime if I'm looking for something different. I've certainly wasted enough time on Factory Idle.

Before I got caught up with Nanowrimo, I passed the time between compiles doodling little machines. Who knows, maybe a business sim game?

Love those!

Victory. Who's that hiding behind the pillar? That's right, it's a properly rendered actor.

Yeah! Awesome. I hope the ordering of the pillars and actors is not causing too much of computation time.

Love those!

Thanks! I have a few more. I might do something with it over the holiday if I need a lower-stress project to work on while traveling, etc.

Yeah! Awesome. I hope the ordering of the pillars and actors is not causing too much of computation time.

CPU usage time in-game is ~0.9% (desktop build on my machine). For comparison, the April version that kicked off this major re-write clocked in around 9 - 15%. 15% is about the max I ever see from one single-threaded application running on the system.

The ordering only happens once, when the scene loads. There's a foreground, middle, and background layer, and tiles are pushed to the appropriate layer. Some thanks goes to you and Justin for helping me figure out how these layers work. This is what I was working on the other night.

The level design guide I have for this game specifies the player be visible at all times, and so should the player walk behind a pillar, they would enter a new sector. So three layers should be adequate for any level that adheres to the style guide.

In theory I could have more layers and allow the player to walk behind walls within a sector. I'm not sure why I'd want to do that, but it raises a neat math question. If I create a graph with subsectors represented as nodes and overlaps between subsectors as edges, and I can show the graph is planar, then by the Four Color Theorem, four layers should be enough to render any possible room.

That question may be purely academic, though.* It's kinda hard to play the game if the player is hidden behind a bunch of walls 

* Edit: Pretty sure the answer is 'no'.

Edit 2. One of the problems with the layer solution is putting the right walls in the right layers. Walls highlighted in red are not rendering correctly because they're in the wrong layer (even if in the proper order in the 'master list').

The solution is easily described: figure out if it is possible for the player to walk in front of the wall. This is tricky to implement, though, because there isn't a clear definition of what screen coordinates it is possible for the player to occupy. Instead I have to write a function that goes through a bunch of 'if statement' checks. I'm almost certain there's a more graceful solution, but, eh, as long as it works and works quickly then I don't care so much if the code is messy.

Style Guide. The good news is that everything order related seems to work--player, tiles, walls, according to the style guide. I'm actually pretty happy with how everything came together. CPU usage is great (sub-1%), memory is reported by the booter console,

Can be improved, but eh, okay for now. So here's the next challenge. Do I really want to update the style guide to forbid the use of thick walls in doorways:

Admittedly, I didn't think about this case when I came to the conclusion three layers was all I needed. It would be very easy to expand my layer system to allow for multiple layers. The hard part is automatically figuring out what tiles go on what layers.

I think I'm getting to the point where I need to let go of Tiled as my scene editor. I moved from Stencyl's scene editor to Tiled because Tiled made it easier to draw multiple layers of Isometric tiles on top of each other. Tiled lets you set the screen coordinates origin for each layer, so that I can visualize how different layers form different floors.

But that is kind of a hack (probably the wrong word). Mixing sprites and walls is also very clunky. Tiled is meant for 2D maps, just like Stencyl's scene editor--so I really can't say Tiled was the best tool to use. What I really need is a map editor specifically designed for the kind of 3D world Vallas Engine supports. So I'm coming to the conclusion I need to write my own.

The obvious downside is this will cost time. But there would be a lot of benefits--most notably, having a user interface perfectly suited for Vallas' special features. This would let me effectively use a multi-layer rendering system, since I can place tiles myself rather than relying on a complex set of rules to figure out where they go automatically. I could also clean up the resources handler, since it doesn't have to parse Tiled's output.

I'm thinking of just building the level editor into the base game. After all, the renderer, map graph system, etc., is already implemented. As a bonus, I can ship a level editor with the desktop game so people can make and share their own maps... something I'd still like to do.

So today's report card:
Layer System: Satisfactory
Layer Rules: Needs Improvement
Plays Well With Others: Works well with Stencyl, not getting along with Tiled

This would let me effectively use a multi-layer rendering system,

This will be very interesting!! I might be able to use this myself *wink* *wink*

This would let me effectively use a multi-layer rendering system,

This will be very interesting!! I might be able to use this myself *wink* *wink*

I could call it a "dynamic layer system", since it's designed to create and remove layers in-game. A more clever programmer than me would have the code figure out exactly how many layers it needed to render any map and create that number. I don't feel like trying to solve that problem at the moment. I'm pretty sure I know what I'd be getting myself into

One long term goal is to have randomly generated maps. The way I'd do that is draw template rooms manually and then glue them together. I think I can make much more interesting rooms by hand rather than generating them, anyway.

But the layer system is still essential if I'm going to have a level editor. You can see the code if you want to: http://anorthogonaluniverse.com/misc/vallas/LayerDrawStack.hx

It's a simple idea: Just a sprite that contains two more sprites: a sprite acting as a container for walls and a second sprite acting as a container for actors. I added some methods to make managing them easier. What I call a "DrawStackWrapper" just contains either an actor or a wall (bitmapwrapper, i.e. image instance). The LDS is then just plopped into whatever Stencyl scene layer the map is configured for.

Thank you for sharing your code. That might be useful for my later 3D endeavours !

Thanks! I have a few more. I might do something with it over the holiday if I need a lower-stress project to work on while traveling, etc.

I think thise lower-stress projects in between are super important btw.

Physics Update. I now have collision detection! Since all I have is a static screenshot, I let Marika add some commentary.

I spent a while debugging the math before I found the actual culprit--Motion updated the actor grid (gx,gy,gz) coordinates, but not the grid coordinates of the collision body. So even though my actors could move, their collision bodies stayed put. That was a silly mistake, but that's the sort of thing that happens if you bounce too much between problems in a larger project.

I have a few optimizations to make and tidying up to do with the physics code. But that's pretty much it after that. Vallas Engine 0.9... done.

The next step would be to work on that level editor so I can take advantage of the layer system.

I think thise lower-stress projects in between are super important btw.

Definitely. I'm never sure where to draw the line between procrastination and a break. Nothing gets finished by hopping from project to project all the time, but burn-out is definitely a thing, too. I don't have any deadlines or financial constraints on this project, but it'd still be nice to finish it.

On the other hand, drawing all those little machines is fun 

I usually have an "A", "B", and sometimes a "C" project going in my free time. Because of the tight deadline, Nanowrimo has taken over the top priority slot. But I've also just crossed 32,768 words (out of 50,000).