next »

[Marvin Fröhlich]

Now, once we touched on the trees: is there any way I could access the list of Nodes located in a selected part of space (say, limited by a cube in XYZ space or a rectangular on the XZ plane)?
 This might prove kind of handy when recounting the behavior of gameObjects for some games - in most RPGs or shooters it is enought to check on the objects within some radius from the player and not burden the processor with objects (NPCs etc.) on the other side of the map.
 I just thought it would be nice to use the virtualUniverse's graphics index tree for this purpose rather than create a paralell one... Plus, it would be much easier, memory efficient... and probably has been coded before

 Say, Id'l like to get a list of all Nodes (of some specific type, say only OBJModels or my own type extending Node) within 10 units radius from the viewport / player location. How can that be easily done?

This cannot be retrieved from the scenegraph itself and must be done in a parallel datastructure or a special node type (see below). OcTrees exactly do this.

Ah, that's always the same problem : graphics and non-graphics objects. So our scenegraph should contain non-graphics objects as well ?
We don't use octrees or what to render a scene, do we, Marvin ?

No, we don't. And it is not possible. Well, there could be an OcTreeGroup or something like that. It would then be a bit less performant for node adding/removing (search the right place to add the node from the Tree's root and balance the tree, if necessary), but would allow the node-in-range-test in O(log n). This test could also be extended by a type check, that wouldn't cost more than a simple instanceof test for each positively range-checked node.

Marvin

[Tom Rubaj]

Ah, that's always the same problem : graphics and non-graphics objects. So our scenegraph should contain non-graphics objects as well ?
We don't use octrees or what to render a scene, do we, Marvin ?

 Well, I suppose it would suffice for my needs to extend the Node class so that some of the objects (nodes) I'd be adding to the scenegraph would have all the qualities of both graphics node and a game object. I do that with a class extending TransformGroup, the instances of which have a complete set of nodes (shape3Ds, OBJModels or anything else) representing separate game objects added to them.

 It's kind of fun because you can easily manipulate objects with commands like:
 ((HumanHeadExtendsGameObjectNodeExtendsNode)(rootBranchWrapper.getChild("scene.human1.head"))).shake()
 plus, you almost don't have to switch from graphical objects picking to game objects picking (you just recurently loop over pickedNode.getParent() until you come across something that is instanceOf GameObjectNode).

 Aaanyway, back to the topic:
 Guess I could just create an alternative View looking down on the area around the player and extract all the nodes that are instances of that class-extending-node-and-representing-gameObject-at-the-same-time and run some gameObject-behavior specyfic methods on them ("runAnAnimation", "greetThePlayer", "moveInPlayersDirection" etc.) but such solution does sound a bit.. barbaric.

 Ok, I'll do some more serious reading on the trees and if I come up with anything worth mention, I'll report back.

[Marvin Fröhlich]

((HumanHeadExtendsGameObjectNodeExtendsNode)(rootBranchWrapper.getChild("scene.human1.head"))).shake()
 plus, you almost don't have to switch from graphical objects picking to game objects picking (you just recurently loop over pickedNode.getParent() until you come across something that is instanceOf GameObjectNode).

Using PickingLibrary you can just set your GameObject's pickHost property to 'true' and the PickResult will provide you exectly this instance.

Marvin

['n ddrylliog]

Anyway, please continue dumping your thoughts here Thomas. Ideas are welcome and that's interesting. As I'm working on several game projects, I'm always searching for a better way...

[Patheros]

that wouldn't cost more than a simple instanceof test

I've been told instanceof operations are slow and you should avoid calling them frequently. I don't actualy have any data on this, but I think i'm going to run a test as soon as I have free time to verify this claim.

['n ddrylliog]

that wouldn't cost more than a simple instanceof test

I've been told instanceof operations are slow and you should avoid calling them frequently. I don't actualy have any data on this, but I think i'm going to run a test as soon as I have free time to verify this claim.

OK, waiting for your benches..

[Marvin Fröhlich]

I've been told instanceof operations are slow and you should avoid calling them frequently. I don't actualy have any data on this, but I think i'm going to run a test as soon as I have free time to verify this claim.

Some weeks ago I ran a test expeacially for the instanceof thing. And I measured, that it doesn't cost (much) more than a simple int type identifyer check. But please verify my tests. Sometimes one test the wrong way.

Marvin

[horati]

I just ran some tests and discovered that it takes a little while longer than I expected to execute an instance of check but still extremely fast.

Code:

public class Test
{
        public static class A { }
        public static class B { }
        public static class C { }
        public static class D { }

        public static void main( String[] args )
        {
                Object[] array = new Object[ 100000 ];
                for( int i = 0; i < array.length; i++ )
                {
                        double num = Math.random();
                        if( num < 0.25 )
                                array[ i ] = new A();
                        else if( num < 0.5 )
                                array[ i ] = new B();
                        else if( num < 0.75 )
                                array[ i ] = new C();
                        else
                                array[ i ] = new D();
                }

                int countA = 0;
                double start = System.currentTimeMillis();
                for( int i = 0; i < 1000; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A )
                                        countA++;
                        }
                }
                double end = System.currentTimeMillis();
                int ops = 1000 * array.length;
                double seconds = ( end - start ) / 1000.;
                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op", seconds / ops * 1000000000 );
        }
}

indicated that instanceof tests take approximately 10 ns on my computer (2.16 GHz Intel CPU).

['n ddrylliog]

So it's perfect.

[Patheros]

Heres a more extensive test case

Code:

import java.lang.reflect.Type;

public class Test
{
public static class TestBase{
private final int ID;
TestBase(){
ID = this.getClass().hashCode();
}
public int getID() {
return ID;
}
}

private static int A_ID = new A().getID();

        public static class A extends TestBase{ }
        public static class B extends TestBase{ }
        public static class C extends TestBase{ }
        public static class D extends TestBase{ }
        public static class A1 extends A { }
        public static class A2 extends A1 { }
        public static class A3 extends A2 { }
        public static class A4 extends A3 { }
        public static class A5 extends A4 { }
        public static class A6 extends A5 { }
        public static class A7 extends A6 { }
        public static class A8 extends A7 { }
        public static class A9 extends A8 { }
        public static class A10 extends A9 { }
        public static class AA extends A3 { }
        public static class AB extends A3 { }
        public static class AC extends A3 { }
        public static class AD extends A3 { }

        public static final int NUM_OF_ITT = 1000;
       
        public static void main( String[] args )
        {
                TestBase[] array = new TestBase[ 100000 ];
                for( int i = 0; i < array.length; i++ )
                {
                        int num = (int)(Math.random() * 18.0);
                        switch(num){
                        case 0 : array[i] = new A(); break;
                        case 1 : array[i] = new B(); break;
                        case 2 : array[i] = new C(); break;
                        case 3 : array[i] = new D(); break;
                        case 4 : array[i] = new A1(); break;
                        case 5 : array[i] = new A2(); break;
                        case 6 : array[i] = new A3(); break;
                        case 7 : array[i] = new A4(); break;
                        case 8 : array[i] = new A5(); break;
                        case 9 : array[i] = new A6(); break;
                        case 10 : array[i] = new A7(); break;
                        case 11 : array[i] = new A8(); break;
                        case 12 : array[i] = new A9(); break;
                        case 13 : array[i] = new A10(); break;
                        case 14 : array[i] = new AA(); break;
                        case 15 : array[i] = new AB(); break;
                        case 16 : array[i] = new AC(); break;
                        case 17 : array[i] = new AD(); break;
                        }
                }
                test(array);
                System.out.println();
                test(array);
                System.out.println();
                test(array);
        }
           
       
        private static void test(TestBase[] array) {

int count;
                double start;
                double end;
                int ops;
                double seconds;
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ].ID == A_ID)
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof B )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof AA )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A1 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A2 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A3 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A4 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A5 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A6 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A7 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A8 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A9 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
               
                count = 0;
                start = System.currentTimeMillis();
                for( int i = 0; i < NUM_OF_ITT; i++ )
                {
                        for( int j = 0; j < array.length; j++ )
                        {
                                if( array[ j ] instanceof A10 )
                                        count++;
                        }
                }
                end = System.currentTimeMillis();
                ops = NUM_OF_ITT * array.length;
                seconds = ( end - start ) / (double)NUM_OF_ITT;
//                System.out.printf( "%d ops in %f seconds\n", ops, seconds );
//                System.out.printf( "%f ops per second\n", ops / seconds );
                System.out.printf( "%f ns per op\n", seconds / ops * 1000000000 );
        }
}

[Patheros]

running the above test instanceof seems to perform 1 to 5 times slower than a simple integer compare. The thing to note is that the simple integer compare wont work for parent classes. Checking the id on A2 won't equal the id of A. I think the test needs to be more specific to the desired implementation to be accurate.

[Marvin Fröhlich]

running the above test instanceof seems to perform 1 to 5 times slower than a simple integer compare. The thing to note is that the simple integer compare wont work for parent classes. Checking the id on A2 won't equal the id of A. I think the test needs to be more specific to the desired implementation to be accurate.

I haven't run the new test yet. I will do it this evening.
But I think, it is very specific to some situations in xith. Any time I traverse the scenegraph (RenderAtom collection, frustum culling, picking, etc.) these checks are performed and have to be as cheap as possible.

Marvin

[horati]

I did not realize we were talking about something that needs to be absolutely as cheap as possible because it O(really big).  I thought the original discussion started around "should I use instanceof or not?" to which the answer is yes.  If we're talking about O( frame * triangles ) or something of similar magnitude, then you should replace instanceof checks with numeric comparisons as Pantheros suggested or with

Code:

if( o.getClass() == TestClass.class )

whereever possible.  Due to ClassLoader isolation, the above should always be safe and is more expressive than an integer comparison.  In the deep hierarchy provided in the test case, performance must have been similar to

Code:

if( TestClass.class.isAssignableFrom( o.getClass() ) )

Please give this a test to ensure that it performs as well as simple integer comparison.  It should since it is just a memory address comparison, which is of course an integer.  In fact, it is possible that it will outperform int comparison on 64-bit platforms because it uses the natural word size of the CPU (unless using 32-bit JVM on 64-bit platform).

BTW, good test Panth.  I'm normally a big picture guy so I don't usually bother at that level of detail any more.

[Marvin Fröhlich]

o.getClass() == TestClass.class doesn't do the same. But I will try it with int type ids then.

Marvin

[horati]

o.getClass() == TestClass.class doesn't do the same. But I will try it with int type ids then.

If you have a method

Code:

public abstract int getMyType();
...
@Override public int getMyType()
{
    return MAGIC_NUMBER_1;
}
...
@Override public int getMyType()
{
    return MAGIC_NUMBER_2;
}

then it does.  And since it performs an == test, it doesn't even utilize the dynamic dispatch required by the polymorphic implementation above.  Remember, dynamic dispatch methods cannot be inlined and require a few extra pointer operations, and your whole purpose was "squeeze out that last 0.1% inside the biggest O loops".

Did I misunderstand the integer comparison you were talking about?  I have been running on low sleep lately.