Determining draw order for isometric games and irregular shapes (Java)

Question

I'm having some unique trouble determining the order in which objects should be rendered, particularly in the case of when a player is behind a wall. I'll try and explain thoroughly, so prepare for a lot of information.

I render things back to front (as recommended here: Drawing Isometric game worlds) and that is, for the most part, simple enough. I determine what is in the back using a simple comparator:

private Comparator<Entity> spriteSorter = new Comparator<Entity>(){
    public int compare(Entity e1, Entity e2){
        if(e1.getPhysics().getY() > e2.getPhysics().getY()) return 1;
        if(e1.getPhysics().getY() < e2.getPhysics().getY())return -1;
        return 0;
    }
};

This uses the hitbox of an entity to determine its render order, and it works flawlessly for entities with a rectangular hitbox (as almost all my characters do). The actual draw call looks like this:

ArrayList<Entity> spriteList = new ArrayList<>();
    spriteList.add(player);

    for(int i = 0; i < walls.size(); i++){
        spriteList.add(walls.get(i));
    }

    Collections.sort(spriteList, spriteSorter);
        for(int i = 0; i < spriteList.size(); i++){
        spriteList.get(i).render(g);
    }

Here's where things get tricky though, all my characters use an instance of Rectangle, and their ordering works with no problem at all, but my walls (due to the nature of an isometric game) cannot use a rectangle, and thus use a Polygon that fits their size. See picture:

I have to use a Polygon because if I use a rectangle, I get a stupid unpassable space near the wall like so:

Unfortunately, due to the nature of polygons, there is no immediately apparent test to see if the player is in front or behind the wall. Line 3 seems to be a likely candidate as a test, but there are two triangles on either side of the wall that would pass the player.getPhysics.getY() > wall.getPhysics.getY() test and mark him as in front, when he could be both in front and behind the wall.

So, how can I devise a test to tell me when he is behind the diagonal lines? The nature of Shapes and Polygons in Java seems to be limiting me a lot, but I'm sure there's a way to do it. I've played with points a lot, and getCenterY() has gotten fairly close, but it's still not perfect. The problem cases that arise with all of the methods I've tried look like this:

Actually behind, rendered in front

or this:

Actually in front, rendered behind.

Any one got any ideas?

Answer 1

Suppose your character is located at (x, y) and the wall has a central line which leads from (a, b) to (c, d). Then you can use the sign of the determinant

| x a c |
| y b d | = ab + ad + cy - ay - cb - xd
| 1 1 1 |

to decide whether the triangle formed by these three points is oriented clockwise or counter-clockwise. You can compute a similar determinant for the camera instead of the character, and multiply the results. If the product is positive, then camera and character are on the same side of the wall, and you want to draw the character after the wall. If the product is negative, then camera and character are on opposite sides and you want to draw the character before the wall.

This simplification assumes your walls are lines or line segments, not rotated rectangles, but unless your player can actually move inside the wall, the difference should not matter unless the camera looks pretty much head-on onto the short side of the wall. So perhaps you want a big rectangular bounding box for the wall after all, to do rough ordering, and only use the above if the player is inside this (still passable) bounding box.

Answer 2

It's not so easy!!!. Why? Because you have others sprites involucred in the scene (Not only 2. By example, you need have 2 players + 1 wall). How do you order them for rendering? You must always work using x, y, z which determinate respectevely "front, back, behind of" position.

NOTE: After 2 (hard) months of analysis of the problem I finally found and implemented a "correct render drawing" for my new cocos2d-js game. Solution consists in mapping, for each tile (susceptible), which sprites are "front, back and behind". Once doing that you can draw them following a "recursive logic".