Merrak's Isometric Adventures -- Drawing Order Algorithms

mdotedot

  • *
  • Posts: 1364
That is a scary one: " Now it's just a matter of defining the right problem to solve. "
Totally relate to this. Sometimes we debug for hours only to find we are looking in the wrong direction and even breaking more stuff!
Hope you can find your problem!

@Vaibhav Sangwan
I can really talk only about my own stuff, but these kind of non-core engines/libraries are hard to make and to maintain.
If Stencyl would support it natively it requires a complete redesign of almost all aspects of Stencyl. So I don't think this will make it into the Stencyl-core anytime soon.

But that will not stop us from playing with it and maybe even make it available to the community to play with  ;D


Hanging out in the Chat:  http://www.stencyl.com/chat/

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.

merrak

  • *
  • Posts: 1823
That is a scary one: " Now it's just a matter of defining the right problem to solve. "
Totally relate to this. Sometimes we debug for hours only to find we are looking in the wrong direction and even breaking more stuff!
But that will not stop us from playing with it and maybe even make it available to the community to play with  ;D

It occurred to me that the best way to view an "occupiable volume" may not be to think of it as an empty space. Rather, I should think of it like a canvas to draw on--just like how walls are thought of. Then why not sort the OVs along with the walls? This seems like a more natural way to view the problem.

But in my own notes I found where I had already looked at it this way. Back in November I attempted to sort the OVs with the walls. I got the "Escher Drawing" warning.


I dismissed the whole approach then, but now I think I was too quick to do so. The warning suggests the sorting problem can't be solved. That doesn't make sense, though. I just came up with another idea to make it work. A couple things are different this time around: I know more about topological sorting for one. Second, I have a better grasp of what an "occupiable volume" is. I think I had the wrong geometry in my original attempt.

It feels awesome to have such isometric engines(soon which will be 3d I guess :) ) in a mostly 2d maker community.
Why not make it a part of Stencyl?

mdotedot said the same thing I was thinking. As of now, Vallas Engine is sitting at 32,759 lines of code. Any time there's a Stencyl update or an OpenFL update, all that code needs to be checked and updated. It's one of the reasons I stuck with Stencyl 3.4 for so long, despite having access to the 3.5 beta. I also had to write my own map editor.

There's also a lot of research that goes into these kinds of projects. I don't know how m.e. spends his time, but more than half of mine is spent researching relevant math, algorithms, programming techniques, and API documentation.

One of the greatest things about Stencyl is that the engine is right there to look at, modify, or even replace. So these kinds of projects are possible. But I think the Stencyl team itself made the right call picking one thing (2D) and working to be the best at it.

mdotedot

  • *
  • Posts: 1364
Luckilly I have not so much lines of code (yet). But that is just my code. The HaXe library is way bigger. I'm not sure how many lines.

The most time spend is actually on the Demo programs. I want to remain closest to the way Stencyl is doing stuff.
That sometimes isn't the way how the 3D engine works.

@Escher: I remember this. Unsolvable? Not with the mathmagician doing his tricks! :D
Hanging out in the Chat:  http://www.stencyl.com/chat/

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.

merrak

  • *
  • Posts: 1823
@Escher: I remember this. Unsolvable? Not with the mathmagician doing his tricks! :D

Well the good news is that I managed to revise the visible wall sorting code so that it sorts both walls and Occupiable Volumes. The test maps successfully constructed without generating the "Escher Error". If it works*, I'll be much more pleased with this solution than last week's version. Sorting everything at once seems like a more graceful solution than a two stage process: sorting the walls, then sorting the OV's in a separate step.

* And now, the catch: While I was able to test and make sure the walls are still in the right order, I wasn't able to test if the the OVs are. The sector viewer utility and the game's actual renderer use slightly different routines. The game renderer (called "SectorDrawStack") is still programmed to expect the old "Foreground / Midground / Background" layer structure. I'll have to modify SectorDrawStack to interpret the new graph.

As is the usual case around here, getting the graph up and running took a lot more effort than I originally thought. Here's the math problem I wasn't expecting: If I have two OVs in a map, how to determine which one is in front?

This is a more difficult problem to solve than determining whether one wall is in front or behind another. That's because walls are 2D and OVs are 3D rectangular solids. Because OVs are 3D and the screen is 2D, I can't reverse-project a pixel on the screen to a point in the OV--the solution to the wall-wall comparison problem.

Eventually I figured out I can view an OV as a box made up of six walls, and use the wall-wall comparison algorithm against those. Since OVs cannot overlap, if any "wall" of OV 1 is in front of any "wall" of OV 2, then the same must be true of any point in OV 1 vs. OV 2. At least, that's the going conjecture. It holds for all the test rooms I sketched out.

merrak

  • *
  • Posts: 1823
Sorting Stumper--Update. I finally got the "Water Room" to render correctly. Here it is with the proper rendering order: Floor -> Marika -> Wall


There are about seven layers in this sector. Moving the actor to the correct subsector ("Occupiable Volumes") was already implemented as part of the collision detection system. So that part came together easily. I just had to get the walls and OVs into the correct layers, which proved to be a bit more challenging than I originally thought. (This is usually the case...)

This is only the first correct room, so I'm not convinced yet that I won't find a few more bugs... but this is a good sign. I can move on to the next thing.

The Water Room is a pretty complicated room. It's not one of the most complicated, but it is far from the simpler test cases I've been using. It has 43 visible walls and 4 OV's. These 47 structures are organized in a graph which is the dependency graph. I figured out Mathematica has a neat feature where it will construct a graph from its adjacency matrix. Being able to look at the graph made it much easier to debug everything.

This is the graph. It's how Vallas Engine (well, the renderer and collision detection parts) sees the room.


The nodes labelled 44 - 47 represent the OV's. The rest represent walls. It's a directed graph where the direction indicates which structure is to be rendered in front of the other. The depth of a node will be the layer the structure should be rendered on.

So if you're writing a walls-based isometric renderer (as opposed to the usual tile-based), here is a general algorithm that will handle rendering order.

Code: [Select]
1. Create a graph. Add one node for each quadrilateral (representing a wall) or hexagon (representing an OV).

2. For each node A and for each node B, determine if their polygons overlap
    2A. If the polygons overlap, determine whether the corresponding 3D structure of A is in front of B, or behind, or neither.
    2B. If A is in front of B, then connect node A to node B.
    2C. If B is in front of A, then connect node B to node A.

3. Write the topological sorting of this graph. I used Kahn's algorithm for this. If the graph is cyclic, return "Fail" (This is what I call the "Escher Error", since the endless staircase will trigger this problem)

4. Compute the depth of each node. I used (ref 1) as a guide, but not the code presented. (ref 2) also is a good reference... a bit better if you haven't seen much graph theory and want a deeper explanation of what's going on.

5. Compute the depth of the deepest node. Call it D

6. Create D number of layers.

7. Draw each wall on the layer N, where N is the depth of its corresponding node.

8. Draw each sprite occupying an OV on the layer N.

Note that 2A, 2B, and 2C are not trivial problems. They are problems I've discussed elsewhere in the thread, though. I spent more time debugging the code handling these three steps than any other part of the process.

Now I have a solution I'm happy with. It's one graph that handles everything rendering related. This solution feels more "graceful" than the previous--the two phase process that felt clunky.

This was one of the final "big problems" in the core engine that I knew I'd have to solve, so it's good to get this one out of the way.

While I'm still working on the map editor and a few other design tools, I've slowly started moving onto the game itself. I worked out more details on a storyline that I think will do well for the episodic format I'm planning on. I've made some further adjustments to the overall map, features list, and stats tables. No release date, but I expect to be done before the heat death of the universe.

References.

(1) https://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph
(2) https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

« Last Edit: April 19, 2018, 10:38:41 pm by merrak »