Well, the map itself is a 3D grid, but the rendering is done with 2D sprites.
I'm guessing this question has been asked before, but I couldn't find anything after looking around for a while.

I'm wondering what's the best order to render the map and the objects in it. I've tried a bunch of my own ideas but always end up with characters appearing in front of objects they should be hidden behind or the other way around.
I'm trying to replicate the style found in games like Landstalker:




Note that the objects and characters can stand in between tiles.
So right now I have a 16x16x16 3D grid that I'm playing around with. The only object I have on the map is my main character which I can move around freely on the bottom part of the map.
Rendering the actual map is simple enough. I just render them from north to south, bottom to top. So it's mainly when to render the main character that's the issue.
It feels like I'm just missing something, that it's bound to be really simple, but I can't seem to figure it out for the life of me.

I'll look at the code closer later on. It seems I should be able to use it for what I want. Though since only tiles close to the character is causing issues right now, I think I could do some culling to avoid having to compare every tile with the character.

I had really hoped for something simpler though. This was done on the Genesis after all.

Actually, the character on that screenshot stands on the edge of the gray cube, overlapping two tiles, and the brown button is placed at the mid point of four tiles. So that probably won't work.

In a basic 2D Rendering Engine I find it best to use a Layer based approach.

I would have 4 layers.

Layer 0 - background this layer is drawn first.
Layer 1 - transitional
Layer 2 - transitional
Layer 3 - foreground this layer is drawn last.

All backgrounds and objects the Sprite should always be on top of should be in layer 0
The Sprite itself should initially be in layer 1 but can be moved to 2 and back depending on game events, you can use triggers for this. These layers should have their respective textures drawn first then their sprites.
All foregrounds and objects the Sprite must always be drawn underneath so they can cover or obscure the sprite should be in layer 3.

Consider a bridge, that you can both walk under or walk over. The bridge is raised up accessed by steps. And has a guide rail that should be drawn over the player.

All of the ground would be in layer 0
The sprite would be in layer 1. All textures in layer 1 are drawn before sprites.
The bridge is drawn in layer 2. Again all textures in layer 2 are drawn before sprites.
The rail is drawn in layer 3.

So the sprite could walk under the bridge in this scenario and the bridge path etc would be drawn over the sprite.

When the sprite collides with the tile at the top of the stairs it is moved to layer 2. Which tiles on the floor can be walked upon are changed you can do this by triggering a game event you probably have some mechanism like this planned so walls etc cannot be passed and doors can be locked etc that later open.
The sprite can then walk across the bridge, with the bridge being drawn beneath it. The rail is draw over the sprite. When leaving the bridge when the player collides with the tile at the bottom of the stairs trigger an event that changes the walkable floor map back.

Using the layer based approach even if you don't allow or need the sprite to move between layers you can still achieve the effects you want namely allowing the sprite to be in front of some textures and behind others.

We draw the screen from top to bottom; we draw layer 0 first, then the textures of layer 1 then the sprites of layer 1 then the textures of layer 2 then the sprites of layer 2 then layer 3.

You could implement the entire thing with 3 layers instead of 4 but then when crossing the bridge in the above scenarios instead of moving the sprite you would move the textures. It makes more sense to me to just move the one sprite though instead of moving the texture of each tile that the sprite would want to walk on.

As for implementing this system you can have two collections, one for layer 1 and one for layer 2 that contain sprites. This way when you render your layer you render all of the tiles first then render the sprites for that layer. The great thing about this approach is that you do not have to check at each tile, you just render the whole layer then all the sprites for that layer before rendering the next.

renderTexLayer( 0 ); // layer 0
renderTexLayer( 1 ); // layer 1
renderSpriteLayer( 1 ); // sprites for layer 1
renderTexLayer( 2 ); // layer 2
renderSpriteLayer( 2 ); // sprites for layer 2
renderTexLayer( 3 ); // layer 3

In your game events where a sprite moves between layers you just move the sprite from the collection for layer 1 to the collection for layer , your rendering order should take care of the rest.

I'm pretty sure I've already tried determining the front-most point, and that didn't work out the way I planned. I haven't worked on the game in a while though, so I'll try once more and determine why.

As for the layer approach, the problem here is that with this game the character can move behind the geography of the world. There's no background which the player is always in front of.

I have an algo to determine the correct position of each 'cube' in your iso grid... in my own game I was trying to improve speed so I went ahead and made a LUT from the algo.. I one limitation with the algo is that it only works if the array is a square - which ends up making a rectangle map on the screen.

here is some Basic code:
' ---- Initialize Lookup Table for Display mapping offsets and coords -----
Whalf = 36 ' change this value to change display map size (only even integers, please, not tested with odd yet) - my display map was LARGE 72x by 72y by 32z
Wsize = Whalf * 2
Woffset = Whalf * 16 '<----- the '16' here is in relation to my tile size

For x = Wsize to 0 step -1
Xabs = abs(x-Whalf) : Diff = Wsize-Xabs
For y= Xabs to Diff step 1

xloc = (x+y)*16 - Woffset : yloc = 350 + (y-x)*8 ' find screen locations

DisplayMap(CurTile,0) = x : DisplayMap(CurTile,1) = y
DisplayMap(CurTile,2) = xloc : DisplayMap(CurTile,3) = yloc

CurTile = CurTile + 1
Next
Next
CurTile = CurTile - 1 ' now CurTile is max Terrain # used in Display loop below
CursrTile = CurTile/2 ' Set the cursor position to the middle of the tile index which points to the middle of the display map on screen


The LUT is DisplayMap() and it has as many elements as there are tiles on the screen, with each element having 4 usefule values: actual X and Y pixel locations, and the X and Y offests of the 2D map array.

This routine draws the map perfectly correctly, from the upper right corner, in diagonal strips, to the lower left corner. And calculating a 'Z' coord is really easy as you just subtract an amount from the provided Y location. It really works great.