Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (483)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
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  
  A lot of ArrayLists. Is this good style?  (Read 856 times)
0 Members and 1 Guest are viewing this topic.
Offline Kronos

Junior Member


Medals: 1



« Posted 2013-07-13 10:06:24 »

Hello Smiley

Everytime I start coding a game I tend to use lots of ArrayLists, for example when I want to store entities. I iterate through them to check for collisions. Is this a good way to implement a game... consisting of arraylists?

How do you handle entities and so on?

I would appreciate any tipps.
THanks  Wink
Offline SHC
« Reply #1 - Posted 2013-07-13 11:28:04 »

I also use more arraylists. One ArrayList for each level's objects, one per each layer in the current level and one for each cell in the game grid for collisions and another for just destroyed ones. They perform well, I get 90-140 fps in Java2D and more than 1000 in lwjgl. Why do you bother?

Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 128
Projects: 4
Exp: 3 years



« Reply #2 - Posted 2013-07-13 12:02:20 »

I also use more arraylists. One ArrayList for each level's objects, one per each layer in the current level and one for each cell in the game grid for collisions and another for just destroyed ones. They perform well, I get 90-140 fps in Java2D and more than 1000 in lwjgl. Why do you bother?
Your fps measurements are definitely not an apt measurement for the performance/ability of ArrayLists.
Having lots of ArrayLists depends on what they are for. If the world has an ArrayList of entities, or a Player has an ArrayList of weapons, that's normal.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SHC
« Reply #3 - Posted 2013-07-13 12:21:29 »

Your fps measurements are definitely not an apt measurement for the performance/ability of ArrayLists.

I'm having my main game loop like this.

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  
28  
29  
30  
31  
32  
33  
public void gameLoop()
{
    long now = getCurrentTime();
    long gameTime = getCurrentTime();

    long frameTime = 1000 / 60;

    int fps;
    int frames;

    int lastFpsCalculated;

    while (gameIsRunning)
    {
        now = getCurrentTime();

        while (now + frameTime > gameTime)
        {
            updateGame();
            gameTime += frameTime;
        }

        renderGame();

        frames++;
        if (now - lastFpsCalculated >= 1000)
        {
            fps = frames;
            frames = 0;
            lastFpsCalculated = now;
        }
    }
}

Is there anything wrong?

Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 128
Projects: 4
Exp: 3 years



« Reply #4 - Posted 2013-07-13 13:45:18 »

I'm saying how stating your entire game's fps is not a good measurement for ArrayList performance, because it relies on everything else you've coded into the game that also lowers the fps. It's not an adequate benchmark, not even close.
Offline davedes
« Reply #5 - Posted 2013-07-13 15:01:47 »

Show some code. A lot of array lists isn't bad or inherently going to impact performance; but it depends on how you are using them. It also might be a sign of "code smell" if you are using lots of lists instead of something more appropriate, like classes and composition.

Offline ralphchapin

Junior Member


Medals: 3
Projects: 1



« Reply #6 - Posted 2013-07-14 17:14:49 »

I don't use ArrayLists much, but I may be concerned about things you're not.

I think linking all the parts of a game together will some sort of Collection is pretty much standard.  ArrayLists are simple, basic and they are very, very fast.  And they use memory efficiently.  So if the problems I list below don't threaten you, stick with them.

The first thing is they're often not the fastest solution.  Specifically, a Map of some sort can find an object by key, such as a name or an index (where there are odd gaps in the index numbering).  Linked lists ought to be faster if you want to scan a list and add or remove objects at certain points, but ArrayLists keep beating my linked lists in my benchmarks no matter how much I cheat.  I think the Array concept just fits in too well with modern CPU and cache design.  But you may want to use Maps  (HashMap and TreeMap, for starters).

However, if you are making heavy use of memory you can get memory fragmentation from anything based on large arrays.  Using arrays directly, or ArrayList, or HashMap can trigger this problem.  For example, consider creating an ArrayList and adding random value to it in an infinite loop.  It will, of course, run out of memory.  However, you will get the memory exception while there is still plenty of free memory.  Why?

As an array list grows, it runs out of space, creates a bigger array, copies the old array to it, and frees the old one.  As the arrays get large, each freed one takes up a big chuck of free memory.  The next array can't use that space because it is bigger.  So you end up filling free memory with more and more, larger and larger unusable blocks of memory.  You can end up running out of memory when 90% is still free.

The GC will work frantically to combine all these blocks into free memory, and if it has time it will merge them into big enough blocks to allocate the new, bigger arrays.  But in this example we're creating new ones too rapidly.  The GC could put the program on hold while it does this, but it in my experience it would rather throw an exception than stop a program for a second or two.

So collections that use small bits of memory can be better than collections that use arrays.  I tend to use LinkedList over ArrayList, and TreeMap over HashMap.  But do note:  if you create a large array and then leave it alone, sizewise, for the duration of a session, it won't cause this problem and will outperform anything else.

The second problem with array-based collections is that they don't shrink.  Say you have 1 million characters in your game, and each one has a list of possessions.  In 5 or 6 cases, the list may contain over 100 entries.  Often it is empty.  Usually it contains 1, 2, or 3 entries.  But the characters swap so much that each one, over the course of a game, is apt to have 100 entries at some point.  Most of your characters will end up with 100+ element arrays with 1 or 2 entries in each.  You have a huge waste of memory.  A linked list would work a lot better, even with the overhead for pointers.

So for dynamic lists, you might want something else.  I tend to use linked lists of some sort and TreeMaps most of the time.  But if your memory use is under control, stick with ArrayList and maybe HashMap.

Offline davedes
« Reply #7 - Posted 2013-07-14 17:56:12 »

ralphchapin -

For most practical purposes, especially gamedev-related, there is no need for LinkedList. If you want maximal performance and GC-optimizations, you should use something like LibGDX's Array, ObjectMap, IntMap, IntArray, IdentityMap, PooledLinkedList etc. which are tailored to low-end mobile devices. They avoid things like auto-boxing of primitive types, unnecessary allocations (i.e. enhanced for loop), allowing for identity check (==) rather than equals(), and accessing the backing array directly.

Of course, these are such minor optimizations that they probably aren't necessary in a desktop application. Having an ArrayList that is bigger than it needs to be isn't a "huge waste of memory". In a desktop application, it's usually such a small waste of memory that it isn't worth the trouble to type out the extra line for trimToSize or ensureCapacity.

Offline ralphchapin

Junior Member


Medals: 3
Projects: 1



« Reply #8 - Posted 2013-07-14 19:43:47 »

Interesting.  I've spent my life writing software that was a bit too big for the computers it ran on; I've always been running out memory even when I had a lot of it.  For some reason, when I started writing a game, I felt I had to be ready to handle seriously oversized game maps and lots of players, so I'm still overloading my computers.  (Admittedly, they're still 32 bit computers.)

Since getting on Java-Gaming, I've read a bit about LibGDX (and plan on reading more), and some of those collections look useful in a big desktop program, IntMap especially.

The oversized ArrayList is only a problem if there are a lot (100,000+) of them, or if it is a very large list.  The poster probably has a lot more memory than needed, but with lots of memory people often squander it, and I thought it would be worth noting the problems that arise when free memory does become scarce.
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #9 - Posted 2013-07-15 18:37:36 »

Incorrect data structure can sometimes explain performance issues in games, depending on how you're using the data structures, e.g. how often and how you're accessing, removing, iterating etc.

But over-optimization early on is bad. You can always swap out data structures later. Getting things to work is more important than a bit more fps.

100,000 elements should be trivial.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
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.

CopyableCougar4 (19 views)
2014-08-22 19:31:30

atombrot (30 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (24 views)
2014-08-16 06:12:11

Rayexar (63 views)
2014-08-11 02:49:23

BurntPizza (40 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (38 views)
2014-08-06 19:49:38
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!