Sorting a List by depth

Monkey Forums/Monkey Programming/Sorting a List by depth

Vinians

(Posted 2011) [#1]

Hi friends!
I'm creating a game and all is working fine, but now I need to sort the List object by a field called Z. It possible to sort a list easly or I need to work at base linked list class ? Thanks !

DruggedBunny

(Posted 2011) [#2]

Have a look at this thread (I had to do this recently)...

Vinians

(Posted 2011) [#3]

NIce but its uses Diddy module, I'm not using it yet because I'm creating my own framework thats only use mojo. List class doesnt have this method..

muddy_shoes

(Posted 2011) [#4]

The first post in that thread shows how to extend the standard monkey List to enable sorting of custom classes.

GfK	(Posted 2011) [#5]

For Local i:= 0 To 1000

What's that all about??

muddy_shoes

(Posted 2011) [#6]

What's that all about??

It's a For loop incrementing i from 0 to 1000. The usage is in the language reference under "Numeric For loop".

impixi

(Posted 2011) [#7]

:= Implicitly sets the variable's type. ie Monkey automagically determines the variable's type based on the number used. In the code above, that's shorthand for:

For Local i:Int = 0 to 1000

GfK	(Posted 2011) [#8]

It's a For loop incrementing i from 0 to 1000.

*sigh* I know that! ;)

It was the colon that I didn't understand.

muddy_shoes

(Posted 2011) [#9]

Apologies for my lack of psychic powers.

therevills

(Posted 2011) [#10]

@Vinians - you dont have to use the entire Diddy module just the collections part.

BTW I dont like the := I like to define the variable type myself ;)

Samah

(Posted 2011) [#11]

@Vinians: NIce but its uses Diddy module, I'm not using it yet because I'm creating my own framework thats only use mojo. List class doesnt have this method..

Import diddy.collections

That's it. That will only import collections.monkey and assert.monkey, and only the parts that are actually used.

matty

(Posted 2011) [#12]

My preference with sorting lists of sprites by z-order is usually as follows (assuming this is what this is about):

Create an array of lists of size equal to the display height.
Run through your set of sprites to draw and insert/append their image reference to the list at the relevant array index, where the array index is equal to the z-depth on the screen. This requires a single pass through your list of objects.

Then in your OnRender routine run through the array from top to bottom (0 to graphics height - 1) and draw all the sprites in the associated list at each index. This also requires only a single pass through your array of lists.It is very simple, and has always seemed quite fast..have been doing this method for many many years.

muddy_shoes

(Posted 2011) [#13]

I'd imagine that most games likely to be built on Monkey would be counting z-ordered elements in the dozens rather than hundreds or thousands, so almost any approach is likely to be fast enough. However, if you're building something where you need to access that ordered list a lot and/or you have a larger number of screen elements then it could be worth looking into something based on a tree.

Happily enough, the Monkey map implementation is backed with a Red-Black tree. It wouldn't take much to put a wrapper around it to provide a display list class that kept everything in z-order. Depending on how much z movement is going on, it would probably be considerably faster than a solution based on lists being sorted on demand.

Vinians

(Posted 2011) [#14]

@therevills I will try to use diddy's collection, but how fast is it? Its fast like List or more ? The sort method is fast? I need to know about it because I will need to sort Z a lot because In my next game I will use this same framework to create a isometric game that use depth a lot sorting by -y position as if it was Z. One more question, diddy collection works with all platforms that monkey export?

@matty Very interesting your solution, but it is a bit complex for me right now, unless you created a tutorial for us! It would be valuable to many beginners like me.

@muddy_shoes Perhaps "class map" would be the solution, but I would have to change much in my current engine, but if I do not get any other way I have to try

muddy_shoes

(Posted 2011) [#15]

The real-world performance of sorting algorithms (outside of their general big-O performance characteristics) and the data structure being used will depend on the usage patterns and the specifics of the implementation and platform involved. So, in order to get any idea you have to start with that information.

* Which target(s) are you talking about?
* How many screen items are you intending to have?
* How many unique Z values do you expect and how spread out will the objects be? In other words, will you have lots of items with the same Z value?
* In any given update interval, how many additions, removals, item searches and list traversals do you expect to be doing?

muddy_shoes

(Posted 2011) [#16]

Here are some timings to illustrate the lack of an easy answer. I've set up a test that does the following:

* Creates a set of test objects that wrap an integer value. I've chosen a thousand objects as representing a pretty ambitious monkey game for rendering output. (Actually, I'd say that it was enormously ambitious, but it illustrates an extreme)
* The values are picked from a limited set of possibilities. This simulates different z "resolutions".
* For each list type, the values are added, one by one, the list is traversed a number of times, sorted - if the list requires an explicit sort - and then the values are removed, one by one. This test is repeated several times and an average time recorded.

Four "lists" are used: Diddy's ArrayList, the Monkey List, a Monkey IntMap used to store Monkey Lists of objects at a z-value and OrderedList, which is my own implementation of a tree-backed collection.

Okay, so here are some numbers for Chrome:

Num. sorted items: 1000
Num. unique values: 8

DiddyList- avg(ms): 2.67
IntMap- avg(ms): 2.33
MonkeyList- avg(ms): 0.74
OrderedList- avg(ms): 1.85

Num. sorted items: 1000
Num. unique values: 240

DiddyList- avg(ms): 3.17
IntMap- avg(ms): 2.92
MonkeyList- avg(ms): 3.09
OrderedList- avg(ms): 2.38

Num. sorted items: 1000
Num. unique values: 10000

DiddyList- avg(ms): 2.78
IntMap- avg(ms): 5.3
MonkeyList- avg(ms): 6.29
OrderedList- avg(ms): 3.1

So we have three cases that cover some possibilities of our game design. The scenarios are 8, 240 and 10000 unique z values, which covers plenty of ground between something like a platformer with large amounts of depth-sorted scenery through to some sort of pseudo-3D craziness.

The first thing to note about this is that as the number of unique slots increases, the best and worst solutions swap around. MonkeyList clearly wins with lots of things on the same z plane and clearly loses when everything is spread around and the reverse is true for the Diddy list. The second thing to note is that the real-world time differences are actually tiny. Sure, 4ms is a decent chunk of time if you're pushing for 60fps, but if you are optimising at that level then expecting to pick the perfect solution before you've even started the game is a bit unrealistic.

But lets say you look at those number and think that scenario B is most like your intentions and so you can expect all the solutions to be the same. How true is that across different platforms and targets? Well lets just try that scenario on a different browser:

Firefox

Num. sorted items: 1000
Num. unique values: 240

DiddyList- avg(ms): 13.34
IntMap- avg(ms): 20.37
MonkeyList- avg(ms): 5.87
OrderedList- avg(ms): 9.46

Oops, if you went with the IntMap, you're suffering now! We should definitely use the MonkeyList, right?

Well, let's take a look at Flash and Android:

Flash:

Num. sorted items: 1000
Num. unique values: 240

DiddyList- avg(ms): 28.71
IntMap- avg(ms): 4.83
MonkeyList- avg(ms): 11.5
OrderedList- avg(ms): 3.6

Android:

09-05 09:49:44.313: INFO/[Monkey](7271): Num. sorted items: 1000
09-05 09:49:44.313: INFO/[Monkey](7271): Num. unique values: 240
09-05 09:49:44.313: INFO/[Monkey](7271): DiddyList- avg(ms): 280.09
09-05 09:49:44.313: INFO/[Monkey](7271): IntMap- avg(ms): 74.23
09-05 09:49:44.313: INFO/[Monkey](7271): MonkeyList- avg(ms): 171.22
09-05 09:49:44.313: INFO/[Monkey](7271): OrderedList- avg(ms): 45.2

Oops again.

therevills

(Posted 2011) [#17]

Hey Muddy any chance you could share your test code?

One thing to note is that with the Diddy's Arraylist is that you dont have to use an iterator which creates a new object every time you use an EachIn.

therevills

(Posted 2011) [#18]

muddy_shoes

(Posted 2011) [#19]

@therevills - The point wasn't to demonstrate that one thing was better or worse than another. The point was exactly the opposite, to show that any of the solutions could be the "best" depending on how and where they are used.

The traversals aren't really a major performance component of the timings above and GC isn't a big issue either, but if you want me to repeat something using the preferred method, I'm happy to oblige. What is the preferred technique? The enumerator or using the list count and the get methods?

therevills

(Posted 2011) [#20]

I would just like to test on my phone using your code... that Android test worries me a tad ;)

Vinians

(Posted 2011) [#21]

Nice! I'm using Monkey List by now, and with this tests will be easy for us to know what type to use with our projects. Fix it! Thanks a lot!

muddy_shoes

(Posted 2011) [#22]

with this tests will be easy for us to know what type to use with our projects

Well, that was a waste of time...

@therevills - I'll separate the relevant code in a bit, but there's nothing special about it. It just does what it says above: add, traverse, sort, remove.

Vinians

(Posted 2011) [#23]

Information is never a waste of time, anyway for me it was important information for the use of ordered lists often involves a large number of objects to any change in velocity influences.
Thanks anyway.

muddy_shoes

(Posted 2011) [#24]

So, to provide a bit more insight and to perhaps reduce therevills' panic, here are breakdown times by activity on my ZTE Blade Android phone.

Num. sorted items: 1000
Num. unique values: 240

DiddyList
Insert - avg(ms): 4.1
Remove - avg(ms): 156.2
Sort - avg(ms): 31.8
Traverse - avg(ms): 8.5

IntMap
Insert - avg(ms): 28.6
Remove - avg(ms): 32.7
Sort - avg(ms): 0.0
Traverse - avg(ms): 33.9

MonkeyList
Insert - avg(ms): 4.2
Remove - avg(ms): 145.4
Sort - avg(ms): 8.2
Traverse - avg(ms): 11.6

OrderedList
Insert - avg(ms): 20.0
Remove - avg(ms): 15.8
Sort - avg(ms): 0.0
Traverse - avg(ms): 11.5

As you can see, it's the removal that really causes pain for the non-tree based collection classes, basically because they involve a search. So, as long as you aren't constantly fiddling with the list contents, you're probably fine. As expected, the tree-based collections pay up-front on the cost of insertion in return for cheap search/removal and no need to explicitly sort the contents.

The code to run the test on the diddy list is below. Note that the Dalvik VM will run generally run code more quickly over time, so running the test for ten loops will result in slower average times than a hundred.

Import mojo
Import diddy.collections

Class Sprite Implements IComparable
  Field z:Int
  
  Method New(z:Int)
      Self.z = z 
  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 z - Sprite(o).z
  End

  ' return true if o is Self, or if Compare(o) would normally return 0
  Method CompareBool:Bool(o:Object)
    Return o = Self Or z = Sprite(o).z
  End
End

Global processTime:Int
Function StartTiming()
    processTime = Millisecs()
End

Function EndTiming(times:StringMap<IntObject>,id:String)
    processTime = Millisecs() - processTime
    Local time:IntObject = times.Get(id)
    time = time + processTime
    times.Set(id,time)
End

Function Main()
	Local a:App = New App
    Local testItems:List<Sprite> = New List<Sprite>
    Local numTestLoops:Int = 100
    Local numTestItems:Int = 1000
    Local zLevels:Int = 240
    Local numTraversals = 10
    Local times:StringMap<IntObject> = New StringMap<IntObject>()
    
    times.Set("Insert",New IntObject(0))
    times.Set("Traverse",New IntObject(0))
    times.Set("Sort",New IntObject(0))
    times.Set("Remove",New IntObject(0))
    
    For Local t:Int = 0 Until numTestLoops
    
        Seed = Millisecs()    
        testItems.Clear()
        For Local i:Int = 0 Until numTestItems
            testItems.AddLast(New Sprite(Rnd() * zLevels))
        End
            
        Local l:ArrayList<Sprite> = New ArrayList<Sprite>
      
        StartTiming()
        
        ' add items here
        For Local item:Sprite = Eachin testItems
            l.AddLast(item)
        End
        
        EndTiming(times,"Insert")
        StartTiming()
        
        For Local i:Int = 0 Until numTraversals
            Local dummy:Int
            For Local j:Int = 0 Until l.Size
                dummy = l.Get(j).z
            End
        End
        
        EndTiming(times,"Traverse")
        StartTiming()
        
        l.Sort()    
        
        EndTiming(times,"Sort")
        StartTiming()
        
        For Local item:Sprite = Eachin testItems
            l.Remove(item)
        End
        
        EndTiming(times,"Remove")
                
    End
    
    Print "Num. sorted items: " + numTestItems
    Print "Num. unique values: " + zLevels
    Print ""
    For Local key:String = Eachin times.Keys()
        Print key +"- avg(ms): " + Float(times.Get(key))/numTestLoops
    End
    
    Error ""
End

Foppy

(Posted 2011) [#25]

Instead of sorting a list in real time it can be faster to use a method as proposed by Matty above (create an array that corresponds to vertical lines on the screen and put references to objects in that array based on their vertical position). However I would not repeat that operation each frame, but instead maintain the array as the game progresses.

In other words you have two things:

1) Some list of creatures

This is your main list of creatures. You use this list to update the creatures from, as usual.

2) Some array or list representing vertical positions on the screen

In this array you have references to the objects in list 1. When you update an object (in list 1) and its vertical position changes, you update the array in point 2 to reflect this change. This might mean you remove the reference in one spot of the array to add it to another spot, for example one row up or down.

You use the array to draw the objects in the correct order.

This means you are updating the drawing-array when necessary and never have to perform a full sort on the array.

Another solution (that I am using in a game I am working on) is to not have the extra array, but work only with the list in point 1. Instead of using a monkey List, create you own linked list by adding "previous" and "next" pointers to the creatures themselves. Now you can maintain the creature list in depth-sorted order, switching creatures around when they pass each other vertically on screen. A disadvantage of this approach might be: what to do if you now add "bullets" or any other type that should have its sprites depth-sorted with the other objects? So you might need to base the different objects on the same base class and then make the list of the base class type.