Oh but we did. (edit: but maybe some people are assuming you can’t spell)
Or maybe it was just terrible 
Cas 
Gah!
</tolling bell>
Phew. Better now.
Well, a (gapless) Bag simply encapsulates array. I’ve run plenty of tests using ArrayList vs. Bag, and the performance difference is crazy, I won’t go back to using ArrayList, that’s just “code smell” in my mind.
But yes, for 99,99% of the games we’re doing here then ArrayList won’t drag your game down to 5 fps, unless you’re doing something crazy like thousands of particles per second.
An ArrayList should be able to cope with millions of particles per second, though. In fact the ArrayList won’t even be your bottleneck; it’ll be the random location of your Particles in RAM anyway.
What’s the Bag interface do then?
Cas
As an aside: If you’re talking about a very large number of particle-like things, then the CPU should be taken out of the picture (yuck, yuck).
That would depend on how the particles actually interact with whatever else is going on. Where it might be fine for trivial particle systems it’s not fine when particles have to do clever stuff like bounce off walls or fill corridors etc.
Cas
Oh, that old trick! Yeah, I use it* in the SpriteEngine in SPGL because it’s one of the few places where the order is irrelevant.
I used to use it in game code too for things like entities until I came across a series of extraordinarily difficult to trace bugs. It turns out it is nearly always important to preserve the order of those sorts of things or odd stuff happens. Worth knowing about.
Cas
- well, similar code anyway
WRT: particles. Well doing collisions on the GPU is totally doable. But, of course, the real question here is wouldn’t one be better off with each being more interesting rather than attempt to pump out of ton of them.
But really my attempted point was if any of these collections are getting large then the high level might need some rethinking.
Yeah, I’ve found that order can be important, which is why I’ve decided to split collision checks to multiple lists. The order of a list is not important, but the list that an object is allocated to is. I gave each collision object a priority enum which determines which list it gets added to. Objects like terrain that keep the player from falling out of the field have the highest priority meaning that they are considered last. Objects that I add later like moving crates and floor spikes have a low priority meaning they get called first. By this logic, objects with a high priority get the last say when considering the position of the collision objects.
My only regret is that I have to make 3 array lists per quadrant because there are 3 types of priority enums… Oh well, maybe I’ll look into that bag class! Maybe it has less fluff! ;D
Looked into Bag. Looks nice, but it isn’t a generic class. Weird… :o
Most games only do about 50-150k particles which is fairly low. I think skyrim does even less, like 1-3k. In my particle system I use arrays for emitters and effects because it is important that their locations in the array do not change. But for particles, order really does not matter much unless you have some serious physics going on.
What is the big advantage of a Bag?
Very fast removal but it can only be safely done during iteration and it will change the order of elements as items are removed.
Cas
I finally looked at the source of Bag intensively! Of course it’s significantly faster at removing elements than ArrayList! When you remove an element, it doesn’t shift each down. It places the final element in the gap that’s created from the removal process, and decrements the size. Yeeah… It makes the whole concept of a LinkedList seem stupid… :-\ Yeah, I’m definitely going to use Bag in the future!
Don’t forget that a Bag is not a List. The fundamental feature of a List is that elements remain in the order in which they are added, and this is often critically important design.
Cas
When is order important? I can only think of a few situations where it’s desirable and can’t be worked around.
- Specialized data structures (ArrayList would basically be a useless layer of abstraction)
- Queues (Circular buffers should be used instead)
- User interface related things presented to the user in list format (Then a list makes sense, but at worst they will only store tens of items)
- Everything else that’s ordered. Which I suspect is a few more use cases than you can count on one hand. Hm, seems it’s important when it’s important.
Collections doesn’t define a Bag interface, which seems an odd oversight, but it could only solidly have Iterable and add(T); once you add “remove”, you end up needing List or Set semantics in the bargain anyway.
Nope, remove works fine for Iterable: http://www.java-gaming.org/topics/implementing-and-using-an-array-backed-bag/27172/view.html
Remove on iterable is a completely different interface. But yeah I suppose that’s how you could do it for Bag too.