Elysian Shadows

Alright I am writing a 2D game (with a team I know baller hey) ( 2d! so why do you want Z rendering fool! ) and I need to do Z-rendering for my game objects. Imagine a 15x15 tile grid where a game object can be anywhere on that grid we want the sprites / game objects at the bottom ( largest y value ) to be drawn last so that they overlap objects they on top of ( if you still have no idea what I am taking about check out the latest Kickle cubicle sneak peek video). We currently use an ID system for the game objects since lua allows us to spawn them whenever we want and we can have multiple over lapping objects we cannot really tie their ids to a grid meaning that we have to grab all of the game objects and sort them each frame to determine rendering order (horrible and inefficient as you might imagine), considering they can move as far as they wish each frame how could you better approach this problem. ( With a sorted pre-defined group of game objects this is really easy but ( as with my snow flakes ) that is not the case here ). Thanks.

So just draw them from bottom to top. It's much simpler and will give you much less of a headache.

First of all, I'd make a display list of all the objects that need to be drawn in order (a C++ vector, linked list, or whatever will do fine). Keep this list throughout the game, and use an algorithm to sort them each frame before rendering them in order on the list. The algorithm should be one which works well with already sorted lists, because most of the time the orders aren't gonna change a whole lot. An algorithm such as merge sort works well for already ordered lists.

http://en.wikipedia.org/wiki/Sorting_al ... Merge_sort

Ok, I counted a grand total of 3 periods in 4 wide lines of text. This was very very difficult to read and I'm not sure if there was even a question in there :P

Alright, now what you're doing actually isn't as "horrible and inefficient" as you suggest. Well....it SHOULDN'T be. Complex scenegraphs insert and reorder draw calls based on several factors several ways and multiple times per frame. You can sort lists of THOUSANDS of objects multiple times and in several different orders a few times per frame without even seeing a blip on the profiler. The key is the analysis.

What kind of data is coming in? Is it worst case data? Best case data? (Already pretty much sorted, not sorted at all, sorted within some delta range??) Will it be inserted and possibly removed every frame? Several times per frame? Every 400 frames?? These are the kinds of questions to ask that will guide you towards 1) What kind of data structure to use to hold these objects and 2) What sort will work best with the expected data set. Usually it amounts to "The data coming in is usually within SOME range of acceptability". So you can usually get away with not having to sort every single frame if you're crafty.

In the 2D case there's usually not much to be done. If the Zbuffer is an option you can just let the hardware do the footwork for you and forgo the sorting altogether.

qpHalcy0n wrote:In the 2D case there's usually not much to be done. If the Zbuffer is an option you can just let the hardware do the footwork for you and forgo the sorting altogether.

Be a bit careful here though, if you're drawing anything with transparency it will still write to the Z-buffer. This basically means that if you draw a transparent image, and then try to draw another image behind it, the parts covered by the polygon of the transparent image will not show up.

Nothing I haven't tried already except for "Complex scenegraphs insert and reorder draw calls based on several factors several ways and multiple times per frame" and I was reading the wikipedia article on scene graphs and I came across this.

The simplest form of scene graph uses an array or linked list data structure, and displaying its shapes is simply a matter of linearly iterating the nodes one by one. Other common operations, such as checking to see which shape intersects the mouse pointer (e.g., in a GUI-based applications) are also done via linear searches. For small scene graphs, this tends to suffice.

Larger scene graphs cause linear operations to become noticeably slow and thus more complex underlying data structures are used, the most popular being a tree. This is the most common form of scene graph. In these scene graphs the composite design pattern is often employed to create the hierarchical representation of group-nodes and leaf-nodes.

Group Nodes - Can have any number of child nodes attached to it. Group nodes include transformations and switch nodes.

Leaf Nodes - Are nodes that are actually rendered or see the effect of an operation. These include objects, sprites, sounds, lights and anything that could be considered 'rendered' in some abstract sense.

But maybe the bottle neck is else where thanks anyway.

Then I don't understand why you're posting?

If you know where the bottleneck is then fix it........what is the problem?

Also, I sure as HELL would NOT be quoting wikipedia on up-to-date rendering techniques. Virtually all of that information there is irrelevant except for the basic definition of what a scenegraph is. I was merely outlining that it is possible to develop a sort method that executes very very quickly.

But maybe the bottle neck is else where thanks anyway.

your response

If you know where the bottleneck is then fix it........what is the problem?

I would have preferred if you had read my post.

I was merely outlining that it is possible to develop a sort method that executes very very quickly.

I was acknowledging that in my post. Putting it frankly I didn't explain my problem and as a result I get a lot of condescending replies. I am just going to close the post and figure it out for myself. Thanks.

Well none of the replies were condescending. We're just giving you what we've got from what you gave....which wasn't much and really didn't make too much sense. (Use more punctuation )

There's plenty of people here who would be willing and able to help but you need to be a little more concise as to what you're looking for here. Ambiguity doesn't really help us in trying to give you anything worthwhile and doesn't help you in solving any problem wherever the problem may lie.