**Sorting Stumper.** Drawing order has been the number one problem since the beginning of this thread. But it's pretty much solved (for my purposes, at least). Why come back to it?

While the wall ordering problem has been solved, actors provide an additional challenge: they move. Because of that, their images can't be clipped--at least, not efficiently.

The most obvious solution would be to draw each wall on its own layer, then draw the actor on the appropriate layer so that it is behind/in front of the right walls. However, there's a catch: The walls aren't drawn in order from farthest to nearest because such a sorting doesn't exist. That was the reason why I needed the local dependency-based sorting.

The dependency-base sorting (topological sort) is a great solution for cases where you need to sort planes of different sizes. See the 17 September post on

Topological Sort. The drawback, though, is that walls that don't overlap on the screen may not be sorted in the way you'd expect. They're not sorted at all, so their placement in the draw order may as well be random.

Once the walls are sorted, I can clip out the parts that aren't drawn and obtain a tiling. At this point, the draw order of the walls is irrelevant because all of the overlaps have been discarded. But that still doesn't solve the actor order problem because there's no way to define how "far from the screen" a wall is. This problem is discussed more thoroughly in the post I linked above. Bottom line, though, is that the proposed solution won't work.

**So, what now?** It's a nice warm day today, so I sat outside with a pad of paper and sketched out a couple of algorithms. This is my typical workflow. Interestingly enough, I've done more "programming" on paper than in front of a computer.

My current sorting routine constructs three layers: background, "midground" (call it the "stage"), and foreground. The stage layer is where all the actors are, with most walls in the background and a few in the foreground. Assigning a wall to a layer is a bit of a challenge. Crucial to this process is an "occupiable volume (OV)", which is any three-dimensional subspace that an actor can occupy. If a wall opens up to an OV, then it should go in the stage layer. If a wall doesn't open up to an OV, it should go in the foreground layer. Since, in each layer, actors are drawn on top of walls, the background layer is mostly for cases where the actor goes behind a wall.

This solution works with a catch: No part of an OV should be behind a wall. I didn't think this would be a limiting factor at first, but then I started drawing maps. In my screenshot at the top of this post you can see that even a simple doorway can't be constructed.

I could put the wall in the foreground layer, but then if Marika was standing on the tile 32 pixels down, she would be drawn behind the wall--even though she should be in front of it.

I don't think this idea is a total lost cause. It just needs some refinement.

Here are a few pages out of today's notes book. I'm trying to solve three problems:

1. Determine how many layers are needed

2. Determine what layer to assign each wall

3. Determine what layer to assign each OV

I thought I had it on my first idea. It's similar to the dependency sort in that I'm using the overlaps. It'd be worth defining some new vocabulary here. For a three dimensional solid (or a planar wall in 3D space), let's refer to the polygon that's drawn on screen as the "On-Screen Projection" (OSP). The OSP for any wall will be a quadrilateral, and for any 3D volume a hexagon.

Consider a vector drawn orthogonal to the screen, projecting from pixel (sx,sy) and into the scene. This vector may cross through any number of walls. For every (sx,sy) coordinate in a wall's OSP, I want to compute the maximum possible number of wall intersections between the screen and the wall.

For example, for the pixel on the floor just under Marika's right foot, the intersection number is 1. A vector from that pixel on the screen to that point in the floor passes through the wall. The vector to some points on the floor pass through 0 walls, and some, like the aforementioned point, pass through 1. So the maximum number is 1.

This number can be computed by counting the number of overlapping OSPs. An alternative solution, looping through every pixel and every wall, would take far too long. (Cubic order).

The wall's layer is set equal to the max number of intersections, with Layer 0 being top-most. So for a simple scene, here are the layer assignments:

Seems okay. Unfortunately, I thought of a situation where this wouldn't work.

The problem is that the little half-wall's (W4) OSP doesn't overlap with anything. So it would be assigned layer 0. But then Marika (or any actor, for that matter) would be drawn in front of W4. Since W1 is also assigned Layer 0, she would be drawn in front of W1 as well.

To further refine the idea, I came up with a way to assign layers to occupiable volumes. The collision detection uses OVs, so this framework is already established. An OV is defined by projecting a floor wall upward until it hits a ceiling (or goes off the map). All OVs are three-dimensional rectangular solids, and so their on-screen projections will be hexagons. Because they have OSPs, I can assign them a layer. Then I can use the occupiable volume's layer to compute the wall layers for the walls behind them.

Hopefully this works

Just so that there's some more pictures to look at, I got the light editor up and running. I can now add lights using the map editor--the first real feature that Tiled never provided.