1
\$\begingroup\$

I'm trying to write a 2D isometric scene. Rendering order is complex, since both tilemaps and sprites are different concepts. Rendering one of the 2 before the other will draw the scene incorrectly.

Tiles and Sprites both have some common data that can be used as render information. I thought of creating an extra object which simply holds the coordinates and texture data. However, this also meant having to couple a tile or sprite to a render info object. (something I haven't figured out). This adds complexity. However, I thought this way I could abstract over any renderable object.

This tutorial defines tiles as any other sprite and then uses a topology algorithm to sort the scene every frame.

I was actually thinking of using the pigeon hole algorithm by sorting the render info objects on their depth property.

How is this usually done? I can't wrap my head around it.

Bear in mind that I have no actual z-depth to work with. Everything relies on the artificial depth from the x and y coordinates.

\$\endgroup\$
  • 2
    \$\begingroup\$ The tutorial seems to cover it - I don't get how your case differs. It is also detailed with the explanations and the source code. So what exactly is the problem? \$\endgroup\$ – antont May 4 '14 at 23:40
  • \$\begingroup\$ @antont Because that solution tends to be pretty heavy, especially the bigger your maps and sprite count is. Surely there is an alternative or something that is commonly used which is not described in the tutorial? \$\endgroup\$ – Sidar May 5 '14 at 12:58
  • \$\begingroup\$ Ah yes, re-reading your question I get it better now. Don't know it offhand but my suspicion is the same, I bet good solutions for this are known. \$\endgroup\$ – antont May 5 '14 at 14:50
3
\$\begingroup\$

The artificial depth from x and y is worth exactly as much as a the one from perspective projection, meaning all normal depth operations apply to it. There are essentially two possibilities for solving your problem: Keeping the static tiles in an already sorted structure and using the depth buffer.

Sorting and Redrawing

pros:

  • lower graphics memory consumption
  • works with transparent tiles and sprites

cons:

  • more CPU pressure
  • likely more GPU pressure

Since the tiles' draw order won't change over the course of the scene, you can sort just the sprites and then keep track of the next tile and sprite each, picking between the two using your comparison function. Since the order of the sprites is somewhat consistent over time, you can base the order on the previous one and pick an algorithm that performs well with almost sorted lists.

If you have access to the stencil buffer it might be better to draw front to back, if no pixels are transparent. This depends on the complexity of your shader though, as far as I know.

If you have a lot of overdraw through tiles this algorithm is not very efficient, but you can make sure your tile map is composited with not much of it by culling e.g. invisible front faces when building the game.

Depth Buffering

pros:

  • lowest CPU pressure
  • likely lowest GPU pressure

cons:

  • higher graphics memory consumption
  • doesn't work as well with transparent tiles or sprites

Since the artificial depth computed from x and y is "real", you can write it to the z-buffer as normal. Then, after drawing the map (or parts of it, if it's too large) keep that clean image in a texture and each frame copy it to the back buffer and draw unordered sprites on top.

The depth check function in the GPU will automatically (and relatively efficiently) sort everything correctly, just like when rendering 3D graphics. This doesn't work on transparent pixels though, so it may not be an option in every case.

Hybrid Solution

pros:

  • relatively low CPU and GPU pressure
  • works with transparent sprites

cons:

  • higher graphics memory consumption
  • doesn't work with transparent tiles

You can combine an opaque tile map that is drawn once with transparent tiles if you sort the latter and then draw back to front over the clean map. This still takes advantage of the fastest solution for static maps but allows some more flexibility on the art side.

It's also possible to separate opaque and transparent sprites and draw the former first, without sorting.

Other Thoughts

  • If you have large (possibly static) obstructions that hide part of the map, consider using occlusion culling to avoid rendering sprites in that area. This works just like in 3D, with the exception that the bounding checks are easier because the view doesn't rotate.

  • If you use a cache of twice the screen size in each direction, you can always just replace half of it when scrolling beyond the cached area and draw it in one go to the back buffer using texture wrapping.

    If you don't render with "nearest pixel" mode you have to make the image slightly larger to consistently avoid texture bleeding around the edges, but I don't know what the impact of a non-power-of-two texture is in practice. This should be a non-issue if the viewport already has a non-power-of-two size though.

\$\endgroup\$
  • \$\begingroup\$ As of right now I'm aiming for a single tile layer with dynamically elevated tile heights ( like so : 1.bp.blogspot.com/-WoGz4ctA25g/T5CVYy4MlpI/AAAAAAAABbo/…). So I've simply made sure every tile is a sprite so I can mingle them with any other sprite. Although the con of this setup is that a tiles become more bloated due to all the sprite properties they inherit and anything super. I might actually consider going full 3D because the more I think about it, it makes more sense. But I absolutely love the 2D flair and don't want to loose that. \$\endgroup\$ – Sidar May 8 '14 at 10:31
  • \$\begingroup\$ Thanks for the info btw. Ill take some time to look further into it. \$\endgroup\$ – Sidar May 8 '14 at 10:32
  • \$\begingroup\$ an algorithm that performs well with almost sorted lists I'm using pigeonhole algorithm. And it works brilliantly actually. But not sure how intensive it is. But I can see it being memory intensive at some point because of all the buckets that are created. \$\endgroup\$ – Sidar May 8 '14 at 10:38
  • \$\begingroup\$ @Sidar If you never move anything from the midpoint of a tile then the pigeon hole algorithm should be viable, but a better option might be organizing your scene in such a way that it updates when sprites move between tiles and has a persistent ready-to-render structure, like a grid of the tiles. If you reuse (doubly) linked list items this can be done fairly efficiently. \$\endgroup\$ – Tamschi May 8 '14 at 15:07
  • \$\begingroup\$ It only updates the order if the depth of a sprite has changed. I'm also keeping track of a grid but you can't place a sprite in between when you're rendering the grid first. So I just have a list of buckets where all my sprites go into, and only one of the buckets update when a depth changes(tiles as well as any other sprite). And in what way should I use a doubly linked list exactly? \$\endgroup\$ – Sidar May 9 '14 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.