Best Way to do Z-Ordering?

BlitzMax Forums/BlitzMax Programming/Best Way to do Z-Ordering?

therevills

(Posted 2010) [#1]

Hi All,

Ive currently got the following for Z-Ordering:

Sprite.bmx

Type TSprite
	Field x#, y#

	Method Compare:Int(other:Object)
	 	Local s:TSprite = TSprite(other)
	 	If y = s.y Return Super.Compare(other)
	 	Return y - s.y
	End Method
End Type

Monster.bmx

Type TMonster Extends TSprite
	Global list:TList

	Function CreateMonster:TMonster(gi:TGameImage, x:Float, y:Float)
		Local m:TMonster = New TMonster
		If list = Null list = CreateList()
		m.x = x
		m.y = y
		list.AddLast m
		GameScreen.level.objectList.AddLast m
		Return m
	End Function
End Type

Hero.bmx

Type THero Extends TSprite
	Global list:TList

	Function CreateHero:THero(gi:TGameImage, x:Float, y:Float)
		Local h:THero = New THero
		If list = Null list = CreateList()
		h.x = x
		h.y = y
		list.AddLast h
		GameScreen.level.objectList.AddLast h
		Return h
	End Function
End Type

Gamescreen.bmx

Type TGamescreen Extends TScreen
	Field level:TLevel

	Method Update()
		level.update()
	End Method

	Method Draw()
		level.draw()
	End Method

End Type

Level.bmx

Type TLevel
	Field objectList:TList

	Function Create:TLevel(levelNumber:Int)
		Local level:TLevel = New TLevel
		
		level.objectList = CreateList()
		Return level
	End Function

	Method update()
		THero.UpdateAll()
		TMonster.UpdateAll()
		SortList objectList
	End Method

	Method draw()
		For Local s:TSprite = EachIn objectList
			s.draw()
		Next
	End Method

You see I have currently got 3 lists:
* Tlevel.objectList
* TMonster.list
* THero.list

Runnable Code:

SuperStrict

Graphics 800, 600

Global objectList:TList = CreateList()

For Local i:Int = 1 To 20
	TMonster.CreateMonster(Rand(0, 800), Rand(0, 600))
	THero.CreatHero(Rand(0, 800), Rand(0, 600))
Next

Repeat
	TMonster.UpdateAll()
	SortList objectList
	
	Cls
	For Local s:TSprite = EachIn objectList
		s.draw()
	Next
	Flip
Until AppTerminate()

Type TSprite
	Field x:Float, y:Float
	Field dx:Float, dy:Float
	
	Method Compare:Int(other:Object)
	 	Local s:TSprite = TSprite(other)
	 	If y = s.y Return Super.Compare(other)
	 	Return y - s.y
	End Method
	
	Method Draw()
		
	End Method
End Type


Type TMonster Extends TSprite
	Global list:TList

	Function CreateMonster:TMonster(x:Float, y:Float)
		Local m:TMonster = New TMonster
		If list = Null list = CreateList()
		m.x = x
		m.y = y
		m.dx = Rnd(-1, 1)
		m.dy = Rnd(-1, 1)
		list.AddLast m
		objectList.AddLast m
		Return m
	End Function

	Function UpdateAll()
		If Not list Return
		For Local m:TMonster = EachIn list
			m.Update()
		Next
	End Function
	
	Method Update()
		x:+dx
		y:+dy
		If x < 0 dx = -dx
		If x > 800 dx = -dx
		If y < 0 dy = -dy
		If y > 600 dy = -dy
	End Method
	
	Method Draw()
		SetColor 255, 0, 0
		DrawRect x - 25, y - 25, 50, 50
		SetColor 0, 0, 0
		Plot x, y
		SetColor 255, 255, 255
	End Method	
End Type

Type THero Extends TSprite
	Global list:TList

	Function CreatHero:THero(x:Float, y:Float)
		Local m:THero = New THero
		If list = Null list = CreateList()
		m.x = x
		m.y = y
		m.dx = Rnd(-1, 1)
		m.dy = Rnd(-1, 1)
		list.AddLast m
		objectList.AddLast m
		Return m
	End Function

	Function UpdateAll()
		If Not list Return
		For Local m:THero = EachIn list
			m.Update()
		Next
	End Function
	
	Method Update()
		x:+dx
		y:+dy
	End Method
	
	Method Draw()
		SetColor 0, 255, 0
		DrawRect x - 25, y - 25, 50, 50
		SetColor 0, 0, 0
		Plot x, y
		SetColor 255, 255, 255
	End Method	
End Type

When creating a hero or monster I add them to the Tlevel.objectlist and their own list. I update them via their own lists, but only draw them via the TLevel.objectList. The z-ordering is done via the sortList and compare methods in Max.

I was wondering if this is the best way of doing this or should I be doing this another way?

Thanks!

Last edited 2010

Muttley

(Posted 2010) [#2]

Avoid overriding Compare for sorting, it also affects removing objects from lists (there's a big discussion about this floating around), and you may end up removing the wrong object.

therevills

(Posted 2010) [#3]

I have seen that, but doing this line seems to fix that issue:

 	If y = s.y Return Super.Compare(other)

If I shouldnt use Compare, then what should I use?

Czar Flavius

(Posted 2010) [#4]

Use a custom compare function, which you send as a parameter to Sort. That way, you can even have multiple compare functions!

therevills

(Posted 2010) [#5]

@Muttley, I guess you are talking about this thread :)

http://www.blitzbasic.co.nz/Community/posts.php?topic=87418

@Czar

Something like this?

SortList list, True, ZOrderSort

Function ZOrderSort:Int( o1:Object, o2:Object )
	Return TSprite(o1).y-TSprite(o2).y
End Function

Czar Flavius

(Posted 2010) [#6]

Yes, like that! :D

If you are ok to guarantee that only TSprites are in the list, you can use it like that. A safer, more generic solution is like this:

Function ZOrderSort:Int(o1:Object, o2:Object)
	Local s1:TSprite = TSprite(o1)
	Local s2:TSprite = TSprite(o2)
	If s1 And s2
		Return s2.y - s1.y
	Else
		Return o1.Compare(o2)
	End if
End Function

The else statement is a fail-safe comparison. If an "o" does not cast to a TSprite, but you try to get the y anyway, it will crash.

Jesse

(Posted 2010) [#7]

I don't know if you know this but you know you can do all using a single list. if you don't know, it's quite a bit of less code to type and less to keep track of:

SuperStrict

Graphics 800, 600

Global objectList:TList = CreateList()

For Local i:Int = 1 To 20
	TMonster.CreateMonster(Rand(0, 800), Rand(0, 600))
	THero.CreatHero(Rand(0, 800), Rand(0, 600))
Next
Local ms:Int
Repeat
	TSprite.UpdateAll()
	SortList objectList
	
	Cls
	Tsprite.drawAll()
	SetColor 255,255,255
	DrawText ms,20,20
	Flip
Until AppTerminate()

Type TSprite
	Field x:Float, y:Float
	Field dx:Float, dy:Float
	
	Method draw() Abstract
	Method update() Abstract
		
	Method Compare:Int(other:Object)
	 	Local s:TSprite = TSprite(other)
	 	If y = s.y Return Super.Compare(other)
		
	 	Return y - s.y
	End Method
	
	Function UpdateAll()
		For Local m:Tsprite = EachIn objectlist
			m.Update()
		Next
	End Function
	
	Function drawAll()
		For Local m:Tsprite = EachIn objectList
			m.draw()
		Next
	End function
	
End Type


Type TMonster Extends TSprite

	Function CreateMonster:TMonster(x:Float, y:Float)
		Local m:TMonster = New TMonster
		m.x = x
		m.y = y
		m.dx = Rnd(-1, 1)
		m.dy = Rnd(-1, 1)
		objectList.AddLast m
		
		Return m
	End Function

	Method Update()
		x:+dx
		y:+dy
		If x < 0 dx = -dx
		If x > 800 dx = -dx
		If y < 0 dy = -dy
		If y > 600 dy = -dy
	End Method
	
	Method Draw()
		SetColor 255, 0, 0
		DrawRect x - 25, y - 25, 50, 50
		SetColor 0, 0, 0
		Plot x, y
		SetColor 255, 255, 255
	End Method	
End Type

Type THero Extends TSprite

	Function CreatHero:THero(x:Float, y:Float)
		Local m:THero = New THero
		m.x = x
		m.y = y
		m.dx = Rnd(-1, 1)
		m.dy = Rnd(-1, 1)
		objectList.AddLast m
		Return m
	End Function

	Method Update()
		x:+dx
		y:+dy
	End Method
	
	Method Draw()
		SetColor 0, 255, 0
		DrawRect x - 25, y - 25, 50, 50
		SetColor 0, 0, 0
		Plot x, y
		SetColor 255, 255, 255
	End Method	
	
End Type

Last edited 2010

therevills

(Posted 2010) [#8]

Thanks Czar :)

@Jesse, yeah I know I can do that, but what about if I have multiple objects in the list (eg, monsters, heroes, projectiles, pickups etc) and I want to do a collision check on monsters with heroes, isnt it faster just to loop on the monsters list instead of the entire objectlist?

Czar Flavius

(Posted 2010) [#9]

Unless your game has thousands of objects that need to be checked several times a second, the speed cost of redundant checks on the whole list of objects isn't worth worrying about. If it is, you can optimize later. That said, it's not too complicated to maintain an "all objects" list, and seperate lists for each kind of object. You just need to remember to add and remove objects from all the right lists and the right time.

Last edited 2010

Jesse

(Posted 2010) [#10]

isnt it faster just to loop on the monsters list instead of the entire objectlist?

I tried the code I posted with 2000(1000 each) objects and it processed all the 2000 object in under 2 millisecs. all on a 2ghz core duo macbook.

Matty

(Posted 2010) [#11]

There is a very quick way to sort a list, simply by counting before displaying, no need to rearrange order within a list, I've used this a lot in B3D/blitzplus and other languages, not sure if bmax would do it but I don't see why not. It does assume however that your 'y' value is an integer or at least can be expressed as an integer with no decimal component...

Simply have an array (or a bank) with indices going from minimum value to maximum value for the y coordinate.

Loop through your objects/sprites whatever, then using the y value of the object as the index into your array store in a bank created at that array index the list of objects/sprites handles to be displayed at that y value.

Then in your display routine iterate through the array from smallest to largest displaying sprites where there is a bank handle reference containing a bank with the sprites in them.

Not sure how bmax handles cleaning up of the banks/arrays but I'm sure it can't be that hard.

therevills

(Posted 2010) [#12]

I guess you dont even have to go that far Matty:

Const ScreenWidth% = 800
Const ScreenHeight% = 600

Repeat

  Cls
  For Local i% = 0 to ScreenHeight
    For Local s:Tsprite = Eachin ObjectList
      if (int)s.y = i Then
        s.draw()
      end if;
    Next
  Next
  Flip

Until Appterminate()

LOL :D

TaskMaster

(Posted 2010) [#13]

Wow, that will go through your object list 600 times each loop. That is completely unnecessary.

Last edited 2010

_JIM	(Posted 2010) [#14]

I would sort them once per frame making sure to only sort sprites that are in the view. Worst case scenario, you could only sort them if necessary (say if one sprite moved and is touching anothers bounding box). You could even limit it to the moving sprites and "neighbours".

But optimize only when you need to. A qsort on all onscreen sprites should be fast enough for ones needs, unless you got thousands of sprites. Even then, probably the rendering would be your true bottleneck.

Htbaa

(Posted 2010) [#15]

Don't forget your sort function should either return -1, 0 or 1. Not just True or False.

therevills

(Posted 2010) [#16]

That is completely unnecessary.

@TaskMaster - I was joking!! :P

@Htbaa - I currently using the ZOrderSort which Czar provided:

SortList list, False, ZOrderSor

Function ZOrderSort:Int(o1:Object, o2:Object)
	Local s1:TSprite = TSprite(o1)
	Local s2:TSprite = TSprite(o2)
	If s1 And s2
		Return s2.y - s1.y
	Else
		Return o1.Compare(o2)
	End if
End Function

This returns s2.y - s1.y (eg 500-600), how does this return true or false?

Matty

(Posted 2010) [#17]

Hi Therevills - I'm not sure any of you understood my algorithm. Here it is in pseudocode - trust me it is very fast when there are lots of objects...

; Screen Height 600 pixels.
Dim ZBuffer(600)

Loop Through Objects Once
	Array_Index = Object.Y
	If ZBuffer(Array_Index) = 0
		Create a Bank At ZBuffer(Array_Index)
		Insert Handle To Object In Bank
	Else
		Resize Bank By An Additional 'x' bytes
		Append Handle To Object In Bank
	Endif
End Loop

; Draw Routine
Loop Through Array 1 To 600
	If ZBuffer(Array_Index) <> 0
		Iterate Through Handles In Bank At This Index and Draw Each One
		
		Free The Bank At Array_Index 		
	Endif
End Loop

; This is actually a very quick sort method

Last edited 2010

Czar Flavius

(Posted 2010) [#18]

If your game has a world larger than the screen, then you can subtract the current viewing coordinates from the objects' y coordinate.

I would use an array of lists rather than banks, personally.