Whats the ideal way to rewrite my game?

[overeasy]

I am looking for performance gains out of my 2D tile game.
How should I store a layered map? A three dimensional array? I am currently using an Array List of objects containing matrices.

Where do I store the array determining what is walkable and what isn't? Or should my 3 dimensional matrix contain objects that have this property (like they do now). Is this incredibly slow?


The main thing is my game is running fast but not completely smooth. This is not due to graphics but due to loading additional tiles when the map shifts. The lag is barely noticeable, but it shouldn't be there for such simple a game.

What is the best way to do a time step for a game without physics or simulation by a time step variable? Consider a simulate() method that can only run forward 1 step in game time.

[kappa]

best way to get performance and silk smooth 2d games in java is to use an opengl binding. I'd highly recommend you try out Slick at http://slick.cokeandcode.com its very similar to java2d and is hardware accelerated by opengl.

[ewjordan]

I am looking for performance gains out of my 2D tile game.
How should I store a layered map? A three dimensional array? I am currently using an Array List of objects containing matrices.

Much like in C, arrays are Evil, generally speaking, unless accesses to those objects occur so often that you can't afford a dynamic array (which should never be the case with a tile-map).  And even if normal arrays are a necessary evil, multi-dimensional ones are Evil-er, where the "er" adds as much Evil as there are dimensions.  I'd almost never use a plain old 3d array under any circumstances - I can think of maybe one or two edge cases, and I don't think a tile map is one of them.

I assume you're adding a matrix to your array list for each height level, right?  That sounds about right...

Where do I store the array determining what is walkable and what isn't? Or should my 3 dimensional matrix contain objects that have this property (like they do now). Is this incredibly slow?

It depends how you do it, but it shouldn't be too bad.

The main thing is my game is running fast but not completely smooth. This is not due to graphics but due to loading additional tiles when the map shifts. The lag is barely noticeable, but it shouldn't be there for such simple a game.

Have you profiled?  I can't see how...well, pretty much anything about the way you store your tile map, apart from how you deal with the graphics, could conceivably become a bottleneck, unless you're running some fantastically complicated algorithms over your tiles.  There just aren't enough tiles to make anything that you're doing per-tile become important, again, except for graphics, since there you may have thousands of pixels per tile.

When you say it's due to loading additional tiles, do you mean you're actually calling out to the disk to open/decompress/process graphics files, or are you just creating a new tile object?

One possibility occurs to me - are you copying everything in your matrix every time it shifts?  Even this shouldn't be a huge deal if your tile map is a reasonable size, but is it possible you're doing something really inefficient there, like actually copying the sprite pixels over or something?

In any case, I think we may need to see some more information or (better) code to figure out what might be slowing you down.  A layered tile map should have very little overhead apart from graphics.

What is the best way to do a time step for a game without physics or simulation by a time step variable? Consider a simulate() method that can only run forward 1 step in game time.

What exactly does your game need to do each step?  It's hard to give advice without knowing what the specific requirements are, or even the type of game.

Games published by our own members! Check 'em out!

[Darrin]

It depends. 

How much art work do you have in mbs?   

How are you loading it?   In other words are you grabbing it from a hashmap or from the HDD on map change?

Arraylists are pretty fast for small games.  Fast enough at least.  However, with huge maps, there might be some issues.

How about your timing?   Do you just need to set your calculation delay larger so you don't go negative?   In other words drop your frame rate to 30 or something like that so any hiccups are not noticed.   I typically aim for 33 fps and never drop below 20.   

[JL235]

Unless you profile your game, all anyone can make (at best) is an educated guess.

Here is my guess, a year ago I had a problem which sounds similar to what your experiencing. I made a small shoot-em-up which ran very quickly but was randomly jerky. It turned out it was because of the high amount of objects it was making on each frame. The GC would kick in once a second causing it to stutter. You should be able to see if the GC is very active using the Java Visual VM, which is located in the JDK 6 home folder at bin/jvisualvm.exe.

You can also use it for profiling, but if your using Eclipse or NetBeans you should be able to profile your game from there as well.

[ManaSink]

"Not smooth" is usually a sign of some "bursty" behavior that stalls out your game loop by forcing an iteration to run over the allotted (or reasonable) time.  For example, if you have set you game loop up to execute one fixed game step every 20 milliseconds, for a target of 50fps, then any step that runs longer than 20 milliseconds is going to feel like a stutter.  Loading images from disk disk would do it, so would a big garbage collection pause.  Switching to a time-derived step (passing an elapsed time variable) can help with this, but can be a major overhaul if you have a lot code that assumes a fixed step, and it won't help you if your  pause is a *really* big one.

I suggest:
1) Run your code through a profiler.  The netbeans one is free.  http://profiler.netbeans.org/ 
2)  Add timing calls to your main loop to capture avg, max time elapsed per loop
3)  Reduce your target framecount.  100+ fps is great for shooters, but only gives you a budget of 10 millis per frame.  25fps is a lot more forgiving.
4)  Move any heavy lifting (image IO) to a background thread.
5)  Force a low-pause garbage collector, (such as +Xincgc)
6)  If all else fails, switch your code over to a time step / as fast as possible method.  I think the Filthy Rich Clients book had some useful code, in chapter 12 - 15, http://filthyrichclients.org/

[pjt33]

1) Run your code through a profiler.  The netbeans one is free.  http://profiler.netbeans.org/ 

It's also included in recent SDKs under the name jvisualvm. I see JL235 already mentioned it under that name.

[ManaSink]

It's also included in recent SDKs under the name jvisualvm. I see JL235 already mentioned it under that name.

Why yes it is, proof I spend too much time on trailing edge VMs at work.  It also looks much more feature rich than I remember it... 

[fletchergames]

I am looking for performance gains out of my 2D tile game.
How should I store a layered map? A three dimensional array? I am currently using an Array List of objects containing matrices.

Basically, you should never use ArrayList.  In the game I'm working on, I have a class defining a layer and storing the tiles in each layer in a 2d array.  I store the layers in a HashMap for accessing a specific layer (though I think I only actually use that HashMap in the map editor).  I also store all the non-sprite layers in an array and will store all the sprite layers in a separate array when I get around to having 2 sprite layers.

However, this isn't going to affect your performance in any noticeable way.

The main thing is my game is running fast but not completely smooth. This is not due to graphics but due to loading additional tiles when the map shifts. The lag is barely noticeable, but it shouldn't be there for such simple a game.

When you switch maps, are you dumping the old map and switching to a whole new one with the player appearing somewhere else?  If so, add a loading screen.

If it's supposed to be a smooth switch when you walk to the edge of the map, split your whole map into sections.  Have the images for 9 areas loaded into memory (the area the player is in and all the areas surrounding it).  When you switch to another area, start loading the images you need for the new areas adjacent to that one in a separate thread.  By the time you get anywhere close to those new areas, the images will be loaded.

[overeasy]

"Not smooth" is usually a sign of some "bursty" behavior that stalls out your game loop by forcing an iteration to run over the allotted (or reasonable) time.  For example, if you have set you game loop up to execute one fixed game step every 20 milliseconds, for a target of 50fps, then any step that runs longer than 20 milliseconds is going to feel like a stutter.  Loading images from disk disk would do it, so would a big garbage collection pause.  Switching to a time-derived step (passing an elapsed time variable) can help with this, but can be a major overhaul if you have a lot code that assumes a fixed step, and it won't help you if your  pause is a *really* big one.

I suggest:
1) Run your code through a profiler.  The netbeans one is free.  http://profiler.netbeans.org/ 
2)  Add timing calls to your main loop to capture avg, max time elapsed per loop
3)  Reduce your target framecount.  100+ fps is great for shooters, but only gives you a budget of 10 millis per frame.  25fps is a lot more forgiving.
4)  Move any heavy lifting (image IO) to a background thread.
5)  Force a low-pause garbage collector, (such as +Xincgc)
6)  If all else fails, switch your code over to a time step / as fast as possible method.  I think the Filthy Rich Clients book had some useful code, in chapter 12 - 15, http://filthyrichclients.org/

I ran it through a profiler... what should I be looking for? Please make it easy for me to understand.

Games published by our own members! Check 'em out!

[JL235]

Open JVisualVM.
Now run your game.
Switch back to JVisualVM and select the game on the left.
Now your ready for profiling.

First thing to check for is the amount of GC going on. In JVisualVM switch to the 'Monitor' tab and then look at the top left graph. It shows CPU usage of the app and the GC. This is good GC usage:

Notice the purple line is almost entirely flat with only two peaks. The first is soon after the game started whilst the second is very minor.

This is bad GC usage:

Far more GC activity on the CPU and notice that the memory usage climbs faster and is cleared more often.

If you have GC usage similar to the second (or worse) then garbage collection will be the cause of your stuttering. Making less objects solves this issue, but which objects? If you switch to the 'Profiler' tab you can then profile the object usage. Then select Memory to start the memory profiler. After a few minutes of playing the game then select stop.

If the GC is to blame, then typically the number of 'live objects' is the value you want to sort by. As you can see I have a very high number of object arrays and java.util.ArrayLists. The object arrays are probably from the same array lists, so somewhere I am making thousands of ArrayLists (which is true, I added code to make 10,000 ArrayLists on each frame which made the game quite stuttery).

How can you fix this? Make less objects! But often you need to make thousands of bullets or explosions on screen, so one of the main ways I use is to build in mechanisms to allow reusing them. I add an initialize method to the object which is the actual constructor and a static list for the whole class. When an object is no longer used it is added to the list. When you want to create a new object you check the list first to see if there is an object you can reuse, where you call the initialize method before returning.


What about CPU? If you select CPU from the profiler you can check this too. I'd make sure to start profiling after it has started (often startup time can be quite expensive) or if you can't (like if your profiling from NetBeans) then just run the game for a long time so the startup CPU time has a very small effect on the results.

The 'self time' is the main value to sort by. It states what percentage of the total CPU usage used by the app. In this case we can see that the Game.act() method is the most expensive, so that is the method I should optimise (it's also the method that makes the 10,000 array lists). You should also look at the number of 'invocations', the number of times the method is called. If I call Game.act() only half the number of times, it should double it's performance.

For more explanation I'd Google around online. For example here.

[ManaSink]

Whoa, nice post JL235.

overeasy, can you go over some of the basics of your setup?  You mentioned that you stuff runs with a fixed step.  If you aren't using a time step variable, then you typically have something similar to the following game loop:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17

long targetFPS = 100; long maximumNanosPerFrame = TimeUnit.SECONDS.toNanos(1) / targetFPS;  // at 100 FPS, should be 10M while (running){     long frameStartTime = System.nanoTime();     updateGameLogic();     renderToScreen();     long elapsedNanosThisFrame = System.nanoTime() - frameStartTime;     long nanosTillNextFrame = maximumNanosPerFrame - elapsedNanosThisFrame;     if (nanosTillNextFrame > 0)         try {             TimeUnit.NANOSECONDS.sleep( nanosTillNextFrame );        } catch (InterruptedException ie) {             System.out.println("weird, got interrupted while sleeping.  Spurious interruption on Solaris or Linux maybe? Ignoring.");        }     else         System.out.println("Probable stutter.  Frame took too long, overrun by " + ( - nanosTillNextFrame) ); }

This code executes updates the game logic (one fixed step), renders the view, then sleeps to smooth out and throttle the framerate.  The sleep is required to smooth out the frames, so they occur at regular intervals, otherwise the game speeds up or slows down depending on what is happening at the time, or how fast the computer it is running on.  If you are using something like this to smooth out the frame timing, than you most likely cause of stuttering is something in the updateGameLogic() or renderToScreen() methods that is taking too long, and causing a single frame to stall (elapsedNanosThisFrame) and exceed the ideal time for a frame (maximumNanosPerFrame).  Another possibility is that a JVM garbage collection pause is doing the same thing.

If your game has stalled frames, then the profiler can help you figure out what is slowing things down.  If it is garbage collection, then you will have spikes of the purple line in the CPU graph and a drop in heap size when your frames stall.  If some part of your algorithm is CPU heavy, it should show up in the hot spots list.

Hope that helps.