Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Collision performance  (Read 4200 times)
0 Members and 1 Guest are viewing this topic.
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Posted 2005-06-14 05:59:05 »

I've never previously worried about collision performance, however recently I've become picky about it.
If I have about 500 objects, all doing collision checks it is quit costly.

My frame rate may be alright on an A63 3000+ OC'd, however not everyone has an overclocked high end CPU.
This is where the trouble comes in.
Basically if the method returns (NONE, NONE), it detect no collision and nothing further is done.

Is my code in any way optimal as a collision routine?


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
public Compass[] directionOfCollision(Entity entity)
   {
      Compass[] direction = new Compass[] {Compass.NONE, Compass.NONE}; //Compass is an enum
     
      float
         entXMin = entity.bounds.x,
         entYMin = entity.bounds.y,
         entXMax = entity.bounds.x + entity.bounds.width,
         entYMax = entity.bounds.y - entity.bounds.height;
      float
         xMin = bounds.x,
         yMin = bounds.y,
         xMax = bounds.x + bounds.width,
         yMax = bounds.y - bounds.height;
     
      if(entXMin >= xMin)
         direction[0] = Compass.WEST;
      else if(entXMax <= xMax)
         direction[0] = Compass.EAST;
     
      if(entYMin <= yMin)
         direction[1] = Compass.NORTH;
      else if(entYMax >= yMax)
         direction[1] = Compass.SOUTH;
     
      return direction;
   }

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #1 - Posted 2005-06-14 08:25:30 »

Have you run a profiler over you app? 500 isn't really that many checks for a simple AABB->AABB test (although that new'd array isn't going to help).

I wonder if you're doing something daft like checking against every other object each time and duplicating the tests..?

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #2 - Posted 2005-06-14 08:57:59 »

With Mustang builds the array should be built on the stack rather than the heap, so it wouldn't make a difference AFAIK.

Basically you're saying that I really can't optimise this any further?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

« JGO Spiffy Duke »


Medals: 435
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #3 - Posted 2005-06-14 09:43:44 »

You really, really, don't want to be creating a new array every time you call the code!!

In fact a far more sensible way to do it would be to have 8 enums in your compass and return one as a simple return value (or null for no collision).

Cas Smiley

Offline kevglass

« JGO Spiffy Duke »


Medals: 212
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #4 - Posted 2005-06-14 11:56:29 »

Sorry, I didn't quite get the initial post, is that 500 objects checking against each other or against a single environment?

Kev

Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #5 - Posted 2005-06-14 15:11:56 »

Both, environment and each other.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline kevglass

« JGO Spiffy Duke »


Medals: 212
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #6 - Posted 2005-06-14 15:44:02 »

Thats a fair few calculations, some sort of spatial partioning appropriate for your game might be worth while at this point?

Kev

Offline Ask_Hjorth_Larsen

Junior Devvie




Java games rock!


« Reply #7 - Posted 2005-06-14 16:24:54 »

Let's say that we check for collisions between n entities.  First, if you determine that Q doesn't collide with P, then be sure not to waste time by determining that P doesn't collide with Q. This will cut time in half. Total time taken will now be the base time of checking two entities against each other, times

½n(n-1).

Next, if you have n+m bodies dispersed on the map, such that n of them are in the left half while m are in he right one, you may associate all entities with which half of the map they are located in. When you perform collision detection, it will now take time

½n(n-1) + ½m(m-1)

instead of

½(m+n)(m+n-1) .

Of course there will be some inconvenience with updating the whereabouts of each entity whenever it moves, and also you may have to use mutually overlapping submaps in order to avoid trouble when entities overlap more than one area. You can further perform subdivisions of the map into cubes or squares such that large numbers of objects can be tracked this way, effectively converting the square of a sum into the sum of squares. Tracking requires extra time proportional to n. Feel free to comment critically, since I'm not the Master of Algorithms.
Offline Raghar

Junior Devvie




Ue ni taete 'ru hitomi ni kono mi wa dou utsuru


« Reply #8 - Posted 2005-06-14 16:52:49 »

Is my code in any way optimal as a collision routine?

I can't see any optimality in that.

Why are you using two variables when one would do?
So you seem to have typical (a-1) * (a/2) problem. There are numerous things that could speed it up. Because it's a commonly encountered problem there are various and not optimal solution on the net.
xxxxxxx
xxxxxx
xxxxx
xxxx
xxx
xx
x
12150 tests
Is what you want to do. So we can just guess if you are doing that.
Basically for colision you are using just code if((center - center2)^2 > ((size + size2)^2)) test for detailed colision.   
Also you are returning for some reason two results It might be benefical to return just one.

You should download that little testing program that I used, and look at performance details. IIRC it did detection test between 10000 moving objects by closest point of aproach. Or was it 100000?

Of course you could do also something smarter and use quadtree. Or you could use Spanish moss algorithm.



It's funny when you are seeing the message about some other post and you'd hastily click the "post".
Offline Vorax

Senior Devvie


Projects: 1


System shutting down in 5..4..3...


« Reply #9 - Posted 2005-06-14 17:43:11 »

Quote
      Compass[] direction = new Compass[] {Compass.NONE, Compass.NONE}; //Compass is an enum

Ouch.

Also, why even have this method?  With the array creation, math and call overhead, it would be faster just to do a full bounds check with short circuiting on failures.  Your doing half the tests and all the math for it anyway.

Or kill the array and return an int representing the directions.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #10 - Posted 2005-06-14 18:07:23 »

With Mustang builds the array should be built on the stack rather than the heap, so it wouldn't make a difference AFAIK.

Are you sure. Mind explaining what you think is going on?

Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #11 - Posted 2005-06-15 02:54:53 »

Escape analysis.
Basically anything short lived is placed into cache rather than main memory.
This is why I don't believe the cost of creating the enum array is anything larger than a basic cache allocation.

With Mustang builds the array should be built on the stack rather than the heap, so it wouldn't make a difference AFAIK.

Are you sure. Mind explaining what you think is going on?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline princec

« JGO Spiffy Duke »


Medals: 435
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #12 - Posted 2005-06-15 08:54:27 »

Escape analysis or not it's still extremely daft Smiley

Cas Smiley

Offline Mark Thornton

Senior Devvie





« Reply #13 - Posted 2005-06-15 09:06:56 »

Escape analysis.
While there are plans to do this in Mustang, I didn't think it had been added to a public build yet.
Offline tom
« Reply #14 - Posted 2005-06-15 12:11:37 »

Escape analysis.
Basically anything short lived is placed into cache rather than main memory.
This is why I don't believe the cost of creating the enum array is anything larger than a basic cache allocation.

Yes, but you are returning the array from the function. First, we don't know you're not passing the array around. Second, how can you be sure that the compiler will class it as short lived. It might give up when it leaves the function.

But I don't know anything about how it would be implemented, so please correct me if I'm wrong.

Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #15 - Posted 2005-06-15 14:15:44 »

It's only used once when it's returned, that is right after it is returned. It ends right there. However the array's scope is within the game loop.
It isn't passed into any methods.

Escape analysis.
Basically anything short lived is placed into cache rather than main memory.
This is why I don't believe the cost of creating the enum array is anything larger than a basic cache allocation.

Yes, but you are returning the array from the function. First, we don't know you're not passing the array around. Second, how can you be sure that the compiler will class it as short lived. It might give up when it leaves the function.

But I don't know anything about how it would be implemented, so please correct me if I'm wrong.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline abies

Senior Devvie





« Reply #16 - Posted 2005-06-22 19:34:18 »

I would rather expect escape analysis to work if you would allocate that array in ecompassing function and pass it to subroutine - where it would not escape. Checking your caller how value you return is used is outside scope of 'trivial' escape analysis, I'm afraid.

Artur Biesiadowski
Offline Mark Thornton

Senior Devvie





« Reply #17 - Posted 2005-06-23 10:20:41 »

I would rather expect escape analysis to work if you would allocate that array in ecompassing function and pass it to subroutine - where it would not escape. Checking your caller how value you return is used is outside scope of 'trivial' escape analysis, I'm afraid.
It is possible when the called method is inlined as it then reverts to the simple case.
Offline abies

Senior Devvie





« Reply #18 - Posted 2005-06-23 17:43:14 »

It is possible when the called method is inlined as it then reverts to the simple case.
In case of inlining, imaginary compiler can even detect that it is just a function with multiple return value disguised as array and just update 2 caller-allocated variables directly - no need to pretend it is an array.

Anyway, I'm going into Cas mode here - I'll believe when I see this in action.

Artur Biesiadowski
Offline princec

« JGO Spiffy Duke »


Medals: 435
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #19 - Posted 2005-06-23 20:46:16 »

I'm not holding my breath for this to appear in the next 12 months... but stranger things have happened at sea...

Cas Smiley

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (37 views)
2014-12-15 09:26:44

Mr.CodeIt (31 views)
2014-12-14 19:50:38

BurntPizza (62 views)
2014-12-09 22:41:13

BurntPizza (99 views)
2014-12-08 04:46:31

JscottyBieshaar (60 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (77 views)
2014-11-29 21:32:03

toopeicgaming1999 (138 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (38 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!