Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (562)
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 detection efficiency  (Read 3484 times)
0 Members and 1 Guest are viewing this topic.
Offline dcco

Senior Newbie





« Posted 2010-11-08 23:27:06 »

Hello, this is my first post here.

So I've been trying to program a 2d side scroller platformer on java by myself and it's going okay so far (though programming slopes and moving platforms were horrific) but I've decided that perhaps attempting something like this without any sort of feedback from others may not be the best idea, so I decided tojoin this place to ask questions.

On to my problem. What's happening right now is that my application occasionally gets sort of choppy. It runs okay, but I'd like the frame rate to be about as consistent as Cave Story, because even though it's playable as is, I'm a bit of a perfectionist. The choppiness is NOT what's affecting my collision, I have a special timer system built so that the game will either catch up or not move at all if too much lag builds up, so it's not like im having problems with characters clipping through platforms or anything.

My main problem is that, in my hunt to remove the occasionally choppiness/random game freezes, i've been going through (attempting to) optimize my code (i don't know much about code optimization unfortunately), and one of the things i got to is the way my collision system for objects works.

What I've done is I've created two arrays about the size of the room in pixels divided by 16 (so one average screen is about 40x40), one of them being an int array, the other one being a string array. what i'm doing is at the beginning of my collision loop I index the number of objects overlapping with a certain room tile in the integer array, and in the string array, i concatenate on the object id by converting it to two characters (0-65535, which should cover any number of objects that should get on screen). Then, during collision checking, each object reads off the list of objects from within every tile it overlaps and does collision checks with them. In this way, if I have some 200+ objects somewhere, they won't ALL be doing collision checks with ALL of them (since that many checks a loop seemed like just a little too much)

But I'm wondering if their is another, more efficient way of being able to only do collision checks with relevant objects that might be faster.

Of course, I'm worried that this might actually only marginally be affecting my frame rate, and that the occasional freezing and choppiness might be caused by something else, so any general advice on optimizing is helpful too, as well as possibly advice on

- Loop Structure/Threading (particularly, should I make another thread for key inputs or something similar to that?)
- Graphics Rendering (Right now I'm mostly just using h.drawImage(), but is there some graphics library that would improve my performance? (Portability is important))
- Swing? (I'm using a JApplet right now, but would Swing or something else be faster? Or would it just be overkill)
- This one's a little embarassing, but Building (I'm using Eclipse and so far I haven't been able to turn even a Hello World project into a .jar file)
- Anything else that might possibly be the source of my strange skipping
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #1 - Posted 2010-11-09 04:47:51 »

Use a profiler. It will tell you where the time is spent.

Also, try "-verbose:gc".

A broad collision phase is good. But why are you using strings for that? Lists are easier to use, manipulating them is faster, and they also produce less garbage (since you can actually manipulate them - strings are immutable).

弾幕 ☆ @mahonnaiseblog
Offline dcco

Senior Newbie





« Reply #2 - Posted 2010-11-09 14:20:47 »

All right, thanks for your recommendation to use lists, I was using strings just because for some reason when I started coding, I had this thing against using non primitive data types and I guess I didn't bother to look up to see if there were any more suitable data types other than a string, so yeah, i'll try to use lists instead then.

I tried to set up a profiler, but unfortunately, the ones I've found seem to require a working build and I still don't know how to make one for an applet.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cylab

JGO Ninja


Medals: 49



« Reply #3 - Posted 2010-11-09 15:04:06 »

Just make it work as an application. If you use Netbeans, you have a build-in profiler and a Profile button to start the current application and profile it.

Mathias - I Know What [you] Did Last Summer!
Offline dcco

Senior Newbie





« Reply #4 - Posted 2010-11-09 15:09:02 »

Well actually, I use Eclipse not Netbeans, but I will try it out just to see the pofiler  Wink and converting the applet into an application doesn't look too difficult so I'll try that too, thanks a lot guys, I'll edit this post with results
Offline Tobias

Junior Member


Projects: 1



« Reply #5 - Posted 2010-11-09 19:16:33 »

Eclipse has a profiler if you are willing to bat out of hell. I use Netbeans for profiling, and Eclipse for everything else.

Mad Skills Motocross
Turborilla - independent game developer
Offline ewjordan

Junior Member





« Reply #6 - Posted 2010-11-09 21:09:14 »

The VisualVM profiler is quite nice, it's one of the few that I've found that tends to work on most systems without major amounts of pain: https://visualvm.dev.java.net/
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #7 - Posted 2010-11-09 23:27:04 »

Netbeans' profiler is probably the best one you can get for free. I highly recommend it.

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





« Reply #8 - Posted 2010-11-09 23:41:40 »

As far as profiling I personally didn't have much success as profiling itself used so much time it was useless and inaccurate (used Eclipse TPTP, or whatever is called)

If profiling doesn't work for you, you can always turn off feature by feature and see the impact on the FPS. For example turn off collision detection and see FPS difference.
Offline dcco

Senior Newbie





« Reply #9 - Posted 2010-11-10 05:29:16 »

If profiling doesn't work for you, you can always turn off feature by feature and see the impact on the FPS. For example turn off collision detection and see FPS difference.
The main thing is that my frame rate fluctuates a LOT (one moment it'll be at 1-10ms per frame, and then suddenly itll jump to 200ms impreceptibly) and it actually changes so quickly that i cant read it.

Yeah, I guess I'll try netbeans profiler to see if profiling helps, but right now Im having problems with getting it to run in the Netbeans IDE. It seems as if it doesnt taking to running applets very well for some reason and converting my applet to an application is harder than it seems.
fakeedit: (okay so now I can get it to build correctly on Netbeans (I just added a main method, but the applet isnt showing up?)

If push comes to shove though, I will try turning things off and maybe slowing down the speed at which i read the frame rate or decreasing my sensitivity.

Thank you everyone for replying to my topic guys.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cylab

JGO Ninja


Medals: 49



« Reply #10 - Posted 2010-11-10 08:56:21 »

Do yourself a favor and make yourself comfortable with profilers. It will pay off in the end (like making oneself comfortable with debuggers - I never understand the folks that refuse to use one and cluttering their whole code with debug-messages like "worked up to line 123").

Mathias - I Know What [you] Did Last Summer!
Offline princec

JGO Kernel


Medals: 379
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #11 - Posted 2010-11-10 10:54:11 »

Debuggers are actually a massive pain in the arse when you're writing psuedo-realtime code. It's often more helpful to see a stream of printouts or an overlay text string instead.

Cas Smiley

Offline cylab

JGO Ninja


Medals: 49



« Reply #12 - Posted 2010-11-10 11:40:46 »

You know about conditional and non-blocking but logging breakpoints?

Mathias - I Know What [you] Did Last Summer!
Offline princec

JGO Kernel


Medals: 379
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #13 - Posted 2010-11-10 11:41:44 »

They are many many clicks of irritation and twiddling away, compared to a s-o-p-ctrl-space Wink

Cas Smiley

Offline cylab

JGO Ninja


Medals: 49



« Reply #14 - Posted 2010-11-10 11:53:23 »

*sigh* Wink

Mathias - I Know What [you] Did Last Summer!
Offline philfrei
« Reply #15 - Posted 2010-12-03 07:32:39 »

http://www.eclipse.org/forums/
The "newcomers" forum would be an excellent start for your Eclipse questions, though I could try and help if you spell out where you run into trouble trying to export to JARs. I think I finally got a pretty good handle on it, have posted Applets and emailed JARs that folks can click and run. Also have some success with WARs.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline philfrei
« Reply #16 - Posted 2010-12-03 08:31:42 »

A couple questions and comments.

It is probably easier to debug an application than an applet. Conversion back and forth is not so hard if you do it right. There is a java tutorial on structuring for conversion.
http://download.oracle.com/javase/tutorial/deployment/applet/developingApplet.html

I don't understand your distinction between JApplet and Swing. JApplet is a Swing component, yes? Or is this part of what you are refering to in terms of trying to code this as an App instead of Applet?

One thing I'm doing with my game is using a util.Timer to control the frame rate. Objects are "registered" with the Timer for position updates, and the JPanel being displayed is registered to receive the repaints. Then, I can forego doing a repaint in the various ActionListeners, MouseListeners, KeyListeners, etc. These routines JUST do the needed state changes. (Got to keep things clean to avoid concurrency issues.) The Timer cranks out update orders and repaints every 40 ms like clockwork (one has some leeway with the actual rate) and things like click&drag are fine in terms of response and smoothness. I don't know if others are using this model or if there are problems with it that I just haven't run into yet. But it seems a lot steadier and cleaner than a classic "game loop".

The type of collision checking you are doing I've seen described as "cell-space partitioning" or "bin-space partitioning" and it's supposed to be pretty efficient. I don't know enough about your game nor about the various other collision detection tools (BSP trees, quad-trees) to know if they would be better in your situation.

You understand that Strings are NOT primitive data types in Java, yes? Concatenations and substring operations are not very efficient if there is a way to accomplish the same thing with ints. And, as oNyx suggests, you might be better off using Lists, even if they are lists of strings, than doing concatenations. There are some very fast data structures for collections--check out something like Horstmann's "Core Java" chapter on Collections to cherry pick the best for a given situation. I haven't read this yet, but it should cover the same material.
http://download.oracle.com/javase/tutorial/collections/index.html

If you are trying to store a bunch of objects, e.g., all the objects in a quadrant, perhaps an ArrayList<yourobjtype>. Store the objects themselves (or more precisely, pointers to their heap locations), not their names. That is more direct.
http://download.oracle.com/javase/tutorial/extra/generics/intro.html

I had some success using jconsole.exe for profiling. I had a heavily multithreaded app and it was great for tracing the lifetime of the various threads. Interesting insights into garbage collection too. Sometimes garbage collection can disrupt timing, but I haven't done anything of sufficient complexity to test this yet.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #17 - Posted 2010-12-03 22:42:43 »

All right, thanks for your recommendation to use lists, I was using strings just because for some reason when I started coding, I had this thing against using non primitive data types and I guess I didn't bother to look up to see if there were any more suitable data types other than a string, so yeah, i'll try to use lists instead then.

I tried to set up a profiler, but unfortunately, the ones I've found seem to require a working build and I still don't know how to make one for an applet.
FYI, a String in Java is not a primitive data type, it's an object as well. You tell by it starting with a capital letter (yay for consistent naming conventions). The only primitives are what you would expect: int/double/boolean/char/etc. If it can't be represented by one number then it's not a primitive.

See my work:
OTC Software
Offline JL235

JGO Coder


Medals: 10



« Reply #18 - Posted 2010-12-12 22:36:31 »

For the record I am pretty certain the NetBeans profiler is just JVisualVM under the hood. Either way I second that both are excellent.

The choppiness you report sounds to me like excessive garbage collection. This could be from the amount of strings your creating, iterators or from other unwanted internal objects within your data structures (the hashmap is particularly bad for this).

I would second using JVisualVM, but I would look for two things. First it can show you a graph of memory usage and in this you should see it slowly going up and then down when a GC occurres. Check for how often a GC is happening. If it's happening a lot then this is (probably) the cause of your choppiness and can be prevented by just making less objects. My second suggestion is to work out which objects you need to create less of, and to do this you should profile your memory usage. It should give you a count of the number of objects created for each type.

Btw if you search JavaGaming.org you can find several existing topics around describing different strategies on handling collision detection. There is one I wrote here which works well for me.

Offline cylab

JGO Ninja


Medals: 49



« Reply #19 - Posted 2010-12-12 23:35:26 »

Just to nitpik - its more the other way around: visualvm is a downstripped netbeans...

Mathias - I Know What [you] Did Last Summer!
Offline fletchergames

Senior Member





« Reply #20 - Posted 2010-12-13 13:10:35 »

Even without a profiler, you can find out if your collision detection code is the problem.  Go to your collision detection method, comment out all the code, and just return false (or null or whatever if there's a return value for no collisions).  Then run the game and see if the problem happens again.

When I have choppiness problems, it's usually the case that some of my images have suddenly stopped being hardware accelerated.  You should probably look into making sure they're accelerated.  Does the choppiness start right after you load some images?

People always think that sort of problem is caused by the garbage collector, but that's never been the case for me.

You profile your own screen drawing method by using System.nanoTime() at the beginning and the end of the method.  You just need to output the time spent during the method to the screen.  If it jumps tremendously when the choppiness occurs, then the paint method is the problem.

A profiler just tells you the total amount of time spent in each method, thread, etc.  It doesn't tell you anything about a method suddenly taking much longer than it had previously.
Offline JL235

JGO Coder


Medals: 10



« Reply #21 - Posted 2010-12-13 17:40:27 »

People always think that sort of problem is caused by the garbage collector, but that's never been the case for me.
It's typically always the case for me.

Also bear in mind that although it might not be the GC at all to blame, by proving it's not this you've eliminated it from your list of things to check.

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.

radar3301 (10 views)
2014-09-21 23:33:17

BurntPizza (28 views)
2014-09-21 02:42:18

BurntPizza (18 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (27 views)
2014-09-20 20:14:06

BurntPizza (29 views)
2014-09-19 03:14:18

Dwinin (46 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!