Z Ordering

Monkey Forums/Monkey Programming/Z Ordering

Raz	(Posted 2012) [#1]

I am thinking of making a game using an overhead perspective (not top down, slightly at an angle like Zelda 3). I will need to do some sort of Z Ordering, but I am not entirely sure how I would go about doing this with multiple types of object?

Has anyone tackled this yet? Any thoughts?

Ta :)

Raz	(Posted 2012) [#2]

My initial thought is...

maybe I can almost scan each row of the game area for all types of object and draw them as required. As I go I could tag each item as drawn. And reset it at the start of each frame. To me this seems like quite of processing, but (as I have done many times before) maybe I am just under estimating just how much processing can be done in a 60th of a second.

Gerry Quinn

(Posted 2012) [#3]

Do you mean isometric tiles?

If so, the following may be all you need:

from bottom to top
from back to front
from left to right
draw tile or object
next
next
next

(assuming view is from overhead, front and right)

siread

(Posted 2012) [#4]

Import mojo
Import diddy

Class TDrawOb Implements IComparable
	Global glist:ArrayList<TDrawOb>
	
	Field x:Float, y:Float, z:Float
	Field img:Image
	Field frame:Int
	Field level:Int			' 0 ground, 1 shadows, 2 objects, 3 gui
	Field alph:Float		' Alpha
	Field rot:Int			' Rotation
	Field col:String		' HTML style colour normally white "FFFFFF"
	Field sclx:Float		' Scale
	Field scly:Float
	
	Function AddImage(obimg:Image, obx:Float, oby:Float, obz:Float = 0, frm:Int = 0, lvl:Int = 0, 
alph:Float = 1.0, rot:Int = 0, col:String = "FFFFFF", sclx:Float = 1.0, scly:Float = 1.0)

		If Not glist Then glist = New ArrayList<TDrawOb>
		
		Local ob:TDrawOb = New TDrawOb
		
		ob.x = obx
		ob.y = oby
		ob.z = obz
		ob.img = obimg
		ob.frame = frm
		ob.level = lvl
		ob.alph = alph
		ob.rot = rot
		ob.col = col
		ob.sclx = sclx
		ob.scly = scly
		
		glist.AddLast(ob)
	End
	
	Function RenderAll()
		If Not glist Then Return
		
		glist.Sort()
		
		For Local ob:TDrawOb = EachIn glist
			SetHexColour(ob.col)
			SetAlpha(ob.alph)
			DrawImage(ob.img, ob.x, ob.y-ob.z, ob.rot, ob.sclx, ob.scly, ob.frame)	
		Next
		
		glist.Clear()
		
		SetAlpha(1.0)
		SetColor(255,255,255)
	End
	
	Method Compare:Int(O:Object)
		' Images are initially sorted according to their level (ground, shadows, objects etc)
		If TDrawOb(O).level < level Then Return 1 
		If TDrawOb(O).level > level Then Return -1 
		
		' Then sort them according to their y co-ordinate
		If TDrawOb(O).y < y Then Return 1 
		If TDrawOb(O).y > y Then Return -1
		
		' If y coord is equal then sort by height
		If TDrawOb(O).z < z Then Return 1 
		If TDrawOb(O).z > z Then Return -1
		
		Return 0
	End

End

' Functions for setting colour using HTML style string
Function SetHexColour(col:String)
	If col.Length < 6 Then Return
	
	Local r:Int, g:Int, b:Int
	r = HexToDecimal(col[0..2])
	g = HexToDecimal(col[2..4])
	b = HexToDecimal(col[4..6])
	
	SetColor(r, g, b)
End

Function HexToDecimal:Int(token:String)
	Local val:Int = 0
	Local hex:String = token.ToUpper()
	
	For Local i:Int = 0 Until hex.Length()
		val *=16
		
		If hex[i] >= 48 And hex[i] <= 57
			val += (hex[i]-48)
		Else
			val += (hex[i]-55)
		End
	Next
	
	Return val
End

siread

(Posted 2012) [#5]

Personally I would add all the objects that you want to draw to a list, then sort the list according to their Y co-ordinates, top to bottom. Finally iterate through the list to draw them. Of course you will need to make sure your hot spots are set to the bottom of the images with SetHandle().

You are welcome to use this code if you like (it requires the Diddy mod for IComparable). All you do is instead of using DrawImage() in your code you use TDrawOb.AddImage() passing the image, co-ords, setting alpha, scale etc. Then you just call TDrawOb.RenderAll() to sort and draw the images. You can even give the objects height by passing a value for z. Just remember to create a shadow for the object too. ;)

[code]
Import mojo
Import diddy

Class TDrawOb Implements IComparable
Global glist:ArrayList<TDrawOb>

Field x:Float, y:Float, z:Float
Field img:Image
Field frame:Int
Field level:Int ' 0 ground, 1 shadows, 2 objects, 3 gui
Field alph:Float ' Alpha
Field rot:Int
Field col:String ' Colour normally white "FFFFFF"
Field sclx:Float ' Scale
Field scly:Float

Function AddImage(obimg:Image, obx:Float, oby:Float, obz:Float = 0, frm:Int = 0, lvl:Int = 0,
alph:Float = 1.0, rot:Int = 0, col:String = "FFFFFF", sclx:Float = 1.0, scly:Float = 1.0)

If Not glist Then glist = New ArrayList<TDrawOb>

Local ob:TDrawOb = New TDrawOb

ob.x = obx
ob.y = oby
ob.z = obz
ob.img = obimg
ob.frame = frm
ob.level = lvl
ob.alph = alph
ob.rot = rot
ob.col = col
ob.sclx = sclx
ob.scly = scly

glist.AddLast(ob)
End

Function RenderAll()
If Not glist Then Return

glist.Sort()

For Local ob:TDrawOb = EachIn glist
SetHexColour(ob.col)
SetAlpha(ValidateMinMaxFloat(ob.alph, 0, 1.0))
DrawImage(ob.img, ob.x, ob.y-ob.z, ob.rot, ob.sclx, ob.scly, ob.frame)
Next

glist.Clear()

SetAlpha(1.0)
SetColor(255,255,255)
End

Method Compare:Int(O:Object)
' Images are initially sorted according to their level (ground, shadows, objects etc)
If TDrawOb(O).level < level Then Return 1
If TDrawOb(O).level > level Then Return -1

' Then sort them according to their y co-ordinate
If TDraw

Raz	(Posted 2012) [#6]

Thanks Siread, that's really helpful :) It sounds very similar to the XNA Spritebatch system. I am hoping sorting this sorting won't become too CPU hungry!

siread

(Posted 2012) [#7]

Yeah, that might be an issue if you are drawing lots of images as the sort is done every render. My game only has 5-10 sprites on screen at once so it's not a problem.

You could probably separate the sort from the render by doing all of your AddImage commands at the end of OnUpdate and doing just one sort there (remembering to clear the list before you start adding). Then call RenderAll (without the sorting or list clearing) during OnRender.

Jesse

(Posted 2012) [#8]

I don't know how Diddy sorting but all of the objects don't need to be sorted every frame. Sort everything only once then just sort only the ones that moved and only from it's current position to where it moved to. Sorting should be minimal and fast once the first sort is done.

Samah

(Posted 2012) [#9]

ArrayList uses quicksort, so yes, sorting a list with minor modifications should be fast.

Raz	(Posted 2014) [#10]

Dragging up an old thread, but relevant :)

ArrayList uses quicksort, so yes, sorting a list with minor modifications should be fast.

Are there limits to how big an ArrayList can be? Are there realistic limits to how big a list can be when sorting?

'This file was edited with Jungle IDE
Import diddy

Class TestApp Extends DiddyApp

	Field testScreen:TestScreen
	
	Method Create:Void()
	
		SetUpdateRate(60)
		
		testScreen = New TestScreen()
		
		drawFPSOn = True
		
		Start(testScreen)
	
	End
End

Class TestScreen Extends Screen
	
	Field iterateTime:Int
	Field sortTime:Int
	Field drawList:ArrayList<TestItem>
	
	Method New()
	
		name = "Test Screen"
		
		drawList = New ArrayList<TestItem>
		
		For Local x:Int = 0 Until 100
			For Local y:Int = 0 Until 100
				Local tTest:TestItem = New TestItem(x * TestItem.W, y * TestItem.H, Rnd(0, 50))
				drawList.AddLast(tTest)
			Next
		Next
		
		Print "What"
		
	End
	
	Method Start:Void()
	
	End
	
	Method Render:Void()
	
		Cls()
		
		iterateTime = Millisecs()
		For Local tT:TestItem = EachIn drawList
			tT.Render()
		Next
		
		iterateTime = Millisecs() -iterateTime
		
		SetColor(255, 255, 255)
		DrawText("Draw Time  : " + iterateTime, 16, 32)
		DrawText("Sort Time  : " + sortTime, 16, 48)
		
	End
	
	Method Update:Void()
	
		If KeyHit(KEY_SPACE)
			For Local tT:TestItem = EachIn drawList
				If Rnd() < 0.5
					tT.y += TestItem.H
				Else
					tT.y -= TestItem.H
				End
			Next
			
			sortTime = Millisecs()
			drawList.Sort()
			sortTime = Millisecs() -sortTime
			Print sortTime
			
		Else
		
			sortTime = Millisecs()
			drawList.Sort()
			sortTime = Millisecs() -sortTime
			
		End
		
	End

End

Class TestItem Implements IComparable

	Const W:Int = 16
	Const H:Int = 16

	Field x:Int
	Field y:Int
	Field z:Int
	
	Method New(x:Int, y:Int, z:Int)
		Self.x = x
		Self.y = y
		Self.z = z
	End
	
	Method Render:Void()
		If x >= 0 And x < DeviceWidth()
			If y - z >= 0 And y - z < DeviceHeight()
				' Would Normally Draw Here
				SetColor(255, 0, 0)
				DrawRect(x, y - z, W, H)
			EndIf
		EndIf
	End
	
	' return 0 if Self is equal to o, a negative number if Self < o, and a positive number if Self > o
	Method Compare:Int(o:Object)
		Return y - TestItem(o).y
	End
	
	' return true if o is Self, or if Compare(o) would normally return 0
	Method Equals:Bool(o:Object)
		Return o = Self Or y = TestItem(o).y
	End

End

Function Main()
	New TestApp()
End

It appears to me that sorting is taking the same time each frame, regardless of whether there were any changes or not. Am I missing something?

Ideally I would like to store every drawable item in a list and sort by the Y position to draw the items at the back first.

Cheers :)
-Chris

muddy_shoes

(Posted 2014) [#11]

>Are there limits to how big an ArrayList can be?

Memory.

>Are there realistic limits to how big a list can be when sorting?

Sure. Bigger lists take longer to sort. The realistic limit depends on your application, the sort implementation and your comparison function. Are you really going to have a game with 10,000 objects on screen though? :)

>It appears to me that sorting is taking the same time each frame, regardless of whether there were any changes or not. Am I missing something?

Quicksort will end up running over the list whether you've made changes or not. An already sorted list might do a bit less swapping but the cost of the partition/comparison operations may well swamp that. If you want to stick with your current method while avoiding a sort overhead when no changes have occurred then you'll need to only call sort when you've made a change.

As a side note, from your example it looks like Diddy's quicksort implementation isn't smart about data sets with lots of shared values. This is causing performance to be generally bad for your data because you're setting all the y positions to 16 pixel boundaries.

Nobuyuki

(Posted 2014) [#12]

If you have a really enormous amount of objects to sort, may I be allowed to toot my own horn for a sec and point out that Timsort tends to runs faster on pre-ordered data, and I've ported over a Monkey implementation of it on straight arrays. According to the original creator of the implementation: "It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays."

Comparing best and worst case performance:

'         Timsort       Quicksort
'Worst:   O(n log n)    O(n^2)
'Best:    O(n)          O(n log n)

Because of the mostly-sorted order advantage, Timsort's ideal for sorting Z-Order data. You can run this algorithm on every update and have a much faster sort speed than Quicksort, particularly if your objects don't change draw order much between updates (as is the case in the majority of update cycles, even with small changes to a camera rotation).

maltic

(Posted 2014) [#13]

I would recommend using Timsort too.

Temporal coherence tends to trigger Quicksort's WORST case performance quite often, but alternatively brings out the best in Timsort. You may also be surprised to find that Insertion Sort will probably be the best for Y-Ordering since it will usually be O(n) with almost no overhead, no auxiliary memory needed, and excellent cache coherence.

muddy_shoes

(Posted 2014) [#14]

Not to point out the fly in the punchbowl but I'm not that convinced of TimSort's real advantage here. As I've pointed out to Nobuyuki before, his comparison with Diddy's implementation of quicksort makes his version of TimSort look much better than it would against an implementation without some of the overhead Diddy has.

I've taken Raz's test code and altered it a little to provide some comparison between TimSort and a tweaked version of Diddy's QuickSort. It's runnable at these links: Flash and HTML5

What I've changed:

* There are now 20,000 items being sorted, just to get reasonable times.
* I altered the render to make the visualisation clearer.
* The drawlist is now perturbed on each frame according to two settings:
DisturbRatio dictates the percentage of items that get moved (0-100)
DisturbAmount dictates how much they move on average (1-10)
* On alternate frames I switch between sort mechanisms and the displayed time is the average over 10 frames, which means it takes 2secs to get a clear value after changing settings.
* Fixed diddy's repeat values problem and made it use generic comparators as TimSort. I didn't put in the switch to Insertion sort based on partition size that often gets added for speed though.

Up and Down changes the ratio. Left and Right changes the amount.

So, when it starts with no disturbance you see the huge advantage that TimSort has. Which is great, except that it is pretty trivial to just not sort the list if nothing changes. It's also noticeable that we're sorting 20,000 items and quicksort isn't exactly taking a huge amount of time anyway.

Now up the ratio and see what happens to that advantage. It basically disappears if anything much moves at all. If stuff moves a lot it's worse.

I'm not saying that TimSort is useless, but I don't see it offering much here (at least on HTML5 and Flash, other targets may well vary. GLFW quicksort performance is terrible, for example.)

maltic

(Posted 2014) [#15]

I am seeing Timsort perform a lot better when there is a small amount of change frame-to-frame. As I predicted. I think in most games (except really busy ones) you might have a handful of units moving between frames, and perhaps two or three of them swapping Y positions. Especially in an RPG. As such I think your examples are disingenuous in that they don't reflect reality at all.

Obviously the more random the movement is, and the more of it there is, the better Quicksort does. But Timsort dominates when there is little change between frames (what I believe would be typical of most RPG games). For my own interest, could you try adding Insertion Sort to your example?

I think the best option (if possible) is some kind of bucket sort, where you keep an array of entities in every position on the tile map, and draw them in order.

muddy_shoes

(Posted 2014) [#16]

I don't know what browser you're look at but that's not what I see, which is part of the problem with duelling algorithms via big O theorising.

Disingenuous? I'm reflecting Raz's own test. If you arbitrarily state your "reality" is 100,000 items and 100 move per frame then TimSort has an advantage, so what? Is that any actual game either? Even if it was, would you use any kind of full sweep sort to implement that at all? I hope not.

I uploaded new versions with 1% disturbance steps so you can find it less "disingenuous" if you like. What's the advantage at 1%? I'm seeing TimSort about 6x faster. Amazing! Except the real world time advantage is 5ms and we're sorting 20,000 objects, which we never would be in any reasonable game. Change it to a thousand items and it's a fraction of a millisecond gap. This is not a meaningful difference.

And no, I won't be adding an Insertion Sort. Why would you want to see which sort is better on such a ridiculously unrealistic and misleading test anyway?

maltic

(Posted 2014) [#17]

@muddy_shoes I am using the latest version of Chrome on Windows 8.1.

You seem to be taking this very personally. Of course my opinions are arbitrary, that's pretty much categorically what opinions are. I made that clear. I also offered some sound reasoning for my opinions: Whether or not you agree is up to you, I offer all my advice without a disclaimer. However you may wish to consider what I am saying instead of taking it as an attack--which it isn't. Sorry if I caused offence :(. I'm just trying to help people by sharing what I think might be useful knowledge. I might be wrong, but I'm not forcing anyone to listen!

I think in most games (except really busy ones) you might have a handful of units moving between frames, and perhaps two or three of them swapping Y positions. Especially in an RPG.

(what I believe would be typical of most RPG games)

As such I think your examples are disingenuous in that they don't reflect reality at all.

In my experience a millisecond or two extra is a huge advantage, given you only get 10-20 per frame. Also, My recommendations are not based on Big Oh notation. In fact I am recommending Insertion Sort, which is worst case O(n^2), because I have gathered from experience and empirical testing that it works very well in this situation: temporal coherence is king, as I keep saying.

muddy_shoes

(Posted 2014) [#18]

I'm not taking it personally, I'm just annoyed at characterising my input as disingenuous when it's based on what the person asking the question put forward and intentionally allows anyone to derive an understanding of where the real world performance balance lies. I don't generally have a lot of patience for people pushing solutions with little attention paid to the actual problem.

You feel free to recommend switching to a sort (with what available implementation?) to someone based on what? Not on their question, on their given test code or on knowledge of their actual game, but based on your own assessment that they'll be moving a handful of units in some large total? What is that total to make it a noticeable sort time? 5000 elements takes about a millisecond, and the difference is about 0.6ms in HTML5 on my pitiful laptop. Enough to be worth it? Do you think that's a typical number of game units and a typical platform?

Let's say you do. Let's say that Raz had even come forward with exactly that number. Let's imagine that his post above was then "I'm moving about 50 units every frame out of 5000 that I keep in a big ArrayList that I sort every frame. When I don't move them the sort seems to still take as long. What's up with that?". Is a reasonable response to that question "You should use TimSort/InsertionSort."? Really?

If Raz is doing that then I put it to you that the answer, even if you decide not to address his question but to address his entire design, isn't to change sort, it's to change datastructure. The fact is that you don't know what he is doing. He could well be intending to have 500 units and they all move like buggery half the time and all stop dead the other half. You have no idea. He's not writing your RPG.

Nobuyuki

(Posted 2014) [#19]

Sorry that I wasn't able to figure out how to work the demo to test it myself. Time target at 60fps is 16.6 ms, right? Under these test conditions and what you've mentioned earlier, a change ratio of 1% over each frame could shave off ~1ms for a screen containing 4000 objects (I'm extrapolating from the numbers given in a previous post). If Timsort's 6x faster than Quicksort under the previous conditions as you say, even if that gap narrows at 4000 objects it is a non-trivial difference. Order sorting's an expensive operation! I can reasonably imagine a scenario where 4000 objects needing sorting could be blitted at once, and necessary for a number of frames. I can even imagine a scenario where 20,000 objects would be sorted -- depending on laziness of culling, even with off-screen culling you could easily find yourself in a situation where you'd need to sort that many objects on an isometric tilemap. But then I guess that starts getting into speed issues in other places, too.

But in any case I would say the speed difference is non-trivial, and furthermore with the absence of quicksort from Monkey's standard library I don't see why implementing timsort would be any more difficult than implementing an efficient version of quicksort (which I'm assuming you can't just rip out of diddy and get comparable results to the existing timsort implementation, even now). You can say that you don't see the advantage, muddy, but you pointed the speed differences out yourself, so there must be some other caveat that I'm not seeing which lends to your skepticism.

Oh, and if you'd like to lend me some of that code to make it a fairer test than the one I devised, I'd be more than happy to add it to the test examples that come with monkey-timsort.

maltic

(Posted 2014) [#20]

I answered the question as I read it. I guess your interpretation is more valid than everyone else's, and as a result everything they say doesn't answer the question.

I am thinking of making a game using an overhead perspective (not top down, slightly at an angle like Zelda 3)

RPG-like game.

Ideally I would like to store every drawable item in a list and sort by the Y position to draw the items at the back first.

Y-Ordering.

So when you say "it's based on what the person asking the question put forward". I can honestly say the same thing! I may be wrong in my interpretation, but that only makes my answer as valid or invalid as yours.

Now, let me dissect your post a little, as I feel you are doing me some small injustice, and spreading some misinformation:

"I'm not taking it personally, I'm just annoyed at characterising my input as disingenuous when it's based on what the person asking the question put forward and intentionally allows anyone to derive an understanding of where the real world performance balance lies. I don't generally have a lot of patience for people pushing solutions with little attention paid to the actual problem."

This is you simply making an assertion. I made the assertion that I think real world performance lies with leveraging temporal coherence. Why is it OK for you to deride my opinion, but propound your own? Surely it is more useful for the OP, and anyone else looking for answers, to have both posts available. I don't think there is much value is you arbitrating on whose answer is more valid. Do you think the casual poster doesn't have enough brainpower to decide which answer is most relevant to their needs?
I never said your input was disingenuous, I said the test scenario was. I think you are making some useful points, and I also believe you are genuinely trying to spread the truth as you see it.

"You feel free to recommend switching to a sort (with what available implementation?)"
Insertion Sort takes about 5 minutes to implement. Here is my code, feel free to use, break, change, or ignore it as best suits you. It was made just for this post:

Class Sort
	Function InsertionSort:Void(arr:Int[])
		For Local i:= 1 Until arr.Length
			Local v:Int = arr[i]
			Local pos:Int = i
			While pos > 0 And v < arr[pos - 1]
				arr[pos] = arr[pos - 1]
				pos -= 1
			Wend
			arr[pos] = v
		Next
	End
End

"and the difference is about 0.6ms in HTML5 on my pitiful laptop"
0.6ms is 3.6% of a typical frame. You could probably put a bit more eye candy on screen. Every little bit helps!

It's also actually a realistic scenario to be Y-ordering 10000+ elements. You could be doing a Sweep and Prune type collision detection. You could have a lot of colliding particles, for example. This kind of analysis and discussion is definitely of value, even if it doesn't directly answer OPs question. As you say though: "You have no idea. He's not writing your RPG." So I may as well post anything I think might help.

"You should use TimSort/InsertionSort"
I remember my posts being a little longer than once sentence. I also remember giving some reasons for my suggestions.

"it's to change datastructure"
I already proposed that.

I think the best option (if possible) is some kind of bucket sort, where you keep an array of entities in every position on the tile map, and draw them in order.

muddy_shoes

(Posted 2014) [#21]

Spin all you want, maltic. I addressed the question, which was about quicksort behaviour and then, when TimSort was brought up as some blanket "just do this" solution, actually bothered to test against the provided example. I post runnables that allow looking at a range of possible scenarios and give the damning assessment that "I'm not that convinced of TimSort's real advantage here". For this I'm told I'm being disingenuous (Oh no, the test scenario is, not me? That's not how it works) and have to read how off track my thinking is to doubt you because your RPG is somehow what's under discussion. No thanks - filed under "waste of breath".

maltic

(Posted 2014) [#22]

Look, you can't make "damning assessments" and expect people not the challenge them. Science wouldn't get anywhere if that were the case. Nobody would get anything out of it. I'm also not making an RPG, by the way. I just assumed the OP might be.

"Oh no, the test scenario is, not me? That's not how it works"
My exact words were,

I think your examples are disingenuous

I'm not trying to attack you! I don't even know you outside of a pseudonym! Just calm down and be magnanimous. We're all just trying to help people here.

muddy_shoes

(Posted 2014) [#23]

1. "Damning assessment". You think I mean that literally? I see why maybe we have a problem.
2. I am calm enough. Stop inferring tone.
3. Look up the word "disingenuous" and consider how it possibly applies to human communications. Did the examples come from the ether? If you say something and I call it a lie am I somehow only referring to the words and you're completely separate from them?

maltic

(Posted 2014) [#24]

Nobody is going to get anything meaningful out of two anonymous people arguing semantics over the internet, and that includes us. Pun not intended.

Raz	(Posted 2014) [#25]

Thanks for everyone's responses, it's interesting to read and I appreciate your time.

Here's a bit more detail in what I was attempting. While not an RPG game, yes it is THAT style of view. Originally Siread suggested that I add all draw operations to a list that gets sorted, drawn and then cleared each frame. On the logic that Quicksorts are not expensive if there hasn't been much change, I was just considering that I add all potentially drawable objects to a list and go from there. Objects would not be randomly darting around the level, so I figured any changes in position would take minimal effort if I maintained the list compared to reordering a potentially erratic list of draw commands each frame. I would be submitting draw requests from many different lists of items, so I think this would quite easily cause the list to start out considerable jumbled up.

My example of 10,000 items was to exaggerate for the sake of performance monitoring.

SLotman

(Posted 2014) [#26]

Why would you need Z-Ordering/sorting on a Zelda like map? Have you heard of tilemaps?
That's what every 2D zelda game uses, alas, almost every 2D game uses it, and needs no sorting whatsoever.

You just make a for loop, draw the static tiles (stored on a 2D array), then draw everything that moves on top. Simple as that.

Raz	(Posted 2014) [#27]

Slotman : There is a simple element of 3d to it. Like I have tree/rock formation tiles but I want the player to be able to walk behind them. Also I want the active objects to be correctly ordered as well.

Nobuyuki

(Posted 2014) [#28]

@Raz
thanks for your time. Also... "Active objects", I haven't heard that one in a while ;)

@muddy_shoes
my offer is still open. I'm sure people could benefit from a Comparator<T> compatible quicksort, and some people might prefer it anyway, so like I said before I'd be more than happy to include it as a test (or at the very least use it to improve the usefulness of my test)

@SLotman
tilemaps bake-in their layering, sure, but this presumes you have an object that you can split up into multiple layers to fake the perspective ordering. This is annoying at best and not practical at worst. Ordering of sprites is a different story altogether. Tilemaps with height data that sprites can use (particularly 3/4 isometric but also with orthagonal maps) require either a sorting algorithm to re-arrange the sprite and tilemap layers around for proper occlusion (particularly between sprites), or a series of occlusion layers at each height to obscure sprites.

Raz	(Posted 2014) [#29]

Oh wow, I didn't realise you were THAT Nobu :D

Yup, active objects, background obstacles, quick backgrounds, the lot :)

Raz	(Posted 2014) [#30]

For what it's worth, I've been messing around with Siread's original suggestion and am using the equivalent of sprite batches now. Even when rendering around 3000 objects, 50 or which move I am getting really good draw and sort speeds. :) My initial worry way back then was the amount of garbage iterating through lists would create, specifically because I was targeting Xbox but that's irrelevant now, seeing as it's an array list and also, I'm not really too fussed about the Xbox anymore!

Instead of sorting through layers I am just assigning draw commands to individual layers of my choosing. So right now I've got:

backgroundLayer
foregroundLayer
effectsLayer
guiLayer

and on a per layer basis I am saying whether I want the stuff sorted or not (useful for the background tile and gui layers). Thinking about it, I can add other checks to the layers, like whether it scrolls and maybe even set layer scissors as well (does Diddy handle scissor scaling when using a virtual res as well?)

Thanks again everyone :)