   Efficient 2D Drawing sorted system
  Hello, the problem I have here is a bit difficult for me to describe so I'll try to be as detailed as I can be. I bolded the important part for those that understand the problem without a back-story.Back-story:Right now I've created an entity management system, every entity can be drawn through its own render() function. Problem is: since it's a 2D game engine the drawing order actually matters quite a lot, so I decided to write a layer system where you could divide the drawing of the world into generic parts, eg: first the far background is rendered, then a closer background then the action layer and finally the foreground. it all worked quite well, but I noticed that sometimes entities on the same layer need to be drawn in a specific order, otherwise things don't look quite right. So I decided to add a few functions to my layers in order to allow them to change the order of the entities drawn inside each layer.The problem with my earlier system: This system works perfectly in levels where the entire world is in view, however for bigger levels it'll render a lot object that are outside the view, thus wasting a lot of time.What I need: So, what I need is: a system that allows me to draw objects separated by layers, draw those objects in a specific order on that layer that I can pre-determine in the editor, and finally skipping the objects that are outside the view.What I've come up with so far: Normally for similar problems I would use a binary tree to decide which objects are inside the view, however in this case a tree would only scramble the object drawing order in the end. A way to combat that scrambling would be to use the tree to decide which objects are drawn, and then having them in specific order. Unfortunately that would mean I have to sort them in the end according to their drawing order and knowing the order in a tree environment would be a pain in the ass. one last thing I came up with was simple checking every single object if it's inside the view or not but it also occupies a lot of processing power.Final Questions to you Have any of you battled a similar problem before? If so then what did you come up with? Do you have any other solutions apart from the ones I presented or do you know of ways to optimize the ones I have right now?I'm sorry for the monolithic wall of text, I hope some of you can help me with this.Thank to everyone who spends his/her time on this in advance.~SpliterPS: depth testing would not work since I heavily use blending for smoother edges and better looking artwork.   
  Using some spatial-partitioning scheme to quickly get a set of visible objects and then sorting the resulting set seems perfectly reasonable to me. I don't see the "pain in the ass" anywhere. Did you try it?   ;  I recently just did something like this for my engine. Using the spatial system, I quickly grab every drawable object in view. Then I just sort them each draw by looping over them once to separate the layers, then sorting each layer as it is returned. Its a lot of extra work that "can" be avoided, but the cost is still very little, and there just isn't any reason to make it faster.If you need this to be better performing, then I suggest you implement a spatial for each layer, allowing you to quickly grab every object in view without having to do the initial pass over the whole collection to separate them by layers.If you really must have even better performance, then it really depends on how you determine what the depth is for each object, how much each object moves, etc. But no need to worry about that until it actually causes performance issues. For layers that don't move (which are probably the most busy layers, like the abundance of background tiles), you can just cache the sort result for the layer, and only update it if the camera moves a certain number of pixels in any direction.Edit: Oh, and if you don't have many possible depths, you could also just push each item into a sub-collection as you put it into the collection for the layer. So for instance, if you have 5 layers, and you can have up to 10 depths per layer, you just need 50 collections. An item in layer 3 with a depth of 7 would go into collection #37, for instance.   ;  How are you storing the entities in the layers? The typical fashion is an array. For instance, layer 0, array element 0 would be the first entity to be drawn, followed by element 1 and so on. To change the order, simply swap two array elements.Maybe I'm misunderstanding your question?   ;  It seems like you're trying to perform two different query/sorting processes "which entities are visible" and "draw entities in order" in a single step.. this is what's making it so complicated.One trivial solution -- if you're using graphics hardware -- is to just assign each object a unique z value (there are 2^24 unique values in a 24bit z-buffer, which should be more than enough) and use z-buffering. Then you can render objects in whatever order you'd like, and the z-buffer will ensure that the objects in front obscure those in the back.BUT: as others have pointed out, is it really that big a problem to perform each operation in a separate pass? Two simple options for this are:1a) Determine visible objects, set a "visible" flag in each; then iterate over all objects in depth order, drawing those whose flag is set.1b) Iterate over all objects in depth order, testing each if they're onscreen; if so, draw them.2a) Determine visible objects, adding each to a sorted list (priority queue) using depth as priority; iterate over queue drawing in priority order.2b) Determine visible objects, adding each to an unsorted list; sort list (using e.g radix sort) based on depth, then iterated over sorted results drawing in order.Hopefully this gives you some ideas.. good luck!raigan   