Hello 
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 
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.
I’m having my main game loop like this.
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?
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.
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.
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.
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.
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.
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.