Best Z ordering method for tile-based, cocos2D-iPhone games?

Question

I want to make isometric, tile-based, iPhone games with cocos2D.

Sprites need to be drawn on-top of other sprites that are "behind" it. I'm looking for the best way to do this.

I'd like to avoid the painter's algorithm because it involves sorting all the sprites every frame which is expensive.

The Z buffer algorithm is supported by the GPU and cocos2D so this is what I'd like to use, but there is a problem. Some sprites, like buildings for example, occupy multiple tiles. Assigning a Z value to such sprites is difficult.

These are the options I've thought of:

1. Comparing two buildings and determining which one is "in-front" is easy. So buildings can be sorted then assigned a Z value based on the sort order. This wouldn't be any different from the painter's algorithm. The OpenGl ES Z buffer wouldn't be necessary.
2. Assign a Z value to each building based purely on its location on the map (without knowledge of where other buildings are). I'm finding this difficult. I think it is possible, but I haven't been able to come up with a formula yet.
3. Use multiple sprites for images that occupy more than one tile, so all sprites will be exactly the same size. Z orders can then be easily assigned based on what tile the sprite is occupying. The problem with this solution is that it makes the game logic much more complicated. All operations on a single building will have to be repeated for each sprite the building is made-up of. I'd like to treat each object as a single entity.
4. Modify the cocos2D code to allow sprites to have multiple Z values at different points. If a sprite can have multiple Z values based on what tile a particular part of the sprite falls on, then calculating a Z value for that section is easy. I won't need to compare the sprite to any other sprites. I believe this is possible by using multiple quads for each sprite. The problem with this is that it is a bit complicated for me since I am new to OpenGL ES and cocos2D. I don't completely understand how all of the internal data structures work. Although it seems like the most elegant solution if a formula cannot be found.

I will up-vote any suggestions or references to helpful resources.

Answer 1

For #2, you can compute the Manhattan distance of the center of the object and use this value as the z-value of that object. It will work as long as you avoid very long objects in your map like 5x1 object or worse. But if you really need a long object to be placed in a tiled map, managing the z-order of objects in the map by setting a z-value using a formula is impossible.

To prove this:
1.) Place two 2x2 objects in a map horizontally and leave a unit tile between them.
2.) Place a 3x1 object between them. Let's name the 2x2 objects to A and B, and the 3x1 object to C.
3.) If you just rotate C(not changing its position), z-order of A and B interchange.

-If B is now in front, some objects behind B will be in front of A because of just the rotation of C. And it's costly to know which objects in back of both A and B previously will become in front of A after C's rotation.