Hey! I use both! (but yeah, as a part of something else is where they have practical application)
I’m going to be a nit-picking bastard and say that bubble sort has its uses. In games it’s actually a really neat approach to sorting particles, as you can just run a fixed number of iterations every frame and the intermediate results are good enough to draw without looking completely wrong.
Actually hold on there princec, I think LinkedList is perfect for games that want to preserve order yet need to add/remove items quickly.
Come on… if the performances of a list are the bottleneck of your game, then I guess it’s already running at 200 fps. You can stop optimizing now.
I always like TreeMap for that kind of usage.
LinkedList might look superficially like O(1) removal/insertion should you happen to be iterating through it… but underneath the hood you forget about the complexity of the memory subsystem, not to mention the potentially catastrophic effects that trashing your caches has on every other aspect of whatever you’re iterating through or doing at the same time.
You can absolutely guarantee to get vastly better performance by using a double-buffered ArrayList, and copying from one to the other etc. And surprisingly in considerably less RAM too. Win-win.
Cas 
Why double buffered?
Assuming you basically iterate through the whole thing once per game loop, you’re potentially adding and removing fairly large numbers of objects. A double buffer where you scan through the front buffer, adding objects that are still alive and new objects to the back buffer, means that there’s no associated penalty inserting or removing elements from the list which involve copying all subsequent elements each time. It’s nice and cache friendly too, operating on a pair of sequential blocks of RAM.
Feel free to correct me if I’m wrong because I’ve been using this technique for a while and if there’s a better way I’d like to know!
Cas
I’d only do that if the order of elements is important. If not, I’d use a Bag. But that’s just from a design point of view, because it better maps to your intented use of the datastructure. Whether that means it’s best in your case is a different matter. As long as it’s not comsuming vast amounts of CPU cycles, stick with what works.
The order of elements is almost always important.
Cas
The order of elements in the same z-index is almost never important.
Generally speaking, from one frame to the next, you want everything to be processed in exactly the same order as last time. WRT the OP’s original design question about in-game objects.
Cas
I always just use pure arrays.
Sun…ehrm…Oracle did an amazing job of forcing us to write our own collections for performance.
… and they wrote a language in which that can be easily done.
Everyone, thank you so much for the comments.
True, what I plan to do on my game so far is not really heavy, yet. I do want to put some effects. I’m thinking about using images instead of drawing from Graphics object(I use Java2D by the way)… thought this might not be the correct way to handle effects. I have to research over effects soon. I haven’t touched anything about particle system, but I would like to take a look if you don’t mind.
Regarding order,
I will have a class that holds all game objects separated according to their type. Player reference to a Player object, enemy objects in a Bag, PlayerBullet objects in another Bag, and so on…
Basically, I won’t specify the index or the order when I add game objects, but they would be in order I add them. The order would start messing up when I remove elements from bag because they would switch out with the last element. Also, I loop backwards, so that I can remove an element and not miss it while iterating. (I remove within game object’s update() method)I don’t think the order within each type will matter since I’m not doing collision detection or any interactions between same types.
The order they are drawn is determined in Sprite class with planes. These planes stored in Hashtable with Integer index corresponding to Image objects are always in the same order every frame after spitting it out to array and sorting. I do iterate this Hashtable every frame to populate the array with keys(Integer).
I will have a code like this…
updateAll(double deltaTime){
player.update(deltaTime);
for (int i = enemyManager.size(); i >= 0; i--)
enemyManager.get(i).update(deltaTime);
// so on...
}
I didn’t have a LinkedList as a choice since I thought its functionality doesn’t suit my need. Reasons being, also mentioned in other posts, random indexing and memory storing references to next objects while I don’t depend on a LinkedList.
@princec
Pardon me for my lack of understanding. Is it like for example…
- You have a main ArrayList listA(front buffer).
- When you iterate it every frame, create a temporary ArrayList listB.
- Whenever it requires you to add or remove game object, you would add into listB.
- Then copyOf listB into listA?
If this is trying to avoid extras of shifting elements, you would have to specify the size of the listB initially, right? How would this work?
It’s true that I could make this work without having to worry much like this. However, I want to learn to use the right data structure more efficiently. I do need to read more.
What I meant is… I actually read that they’re not touching collections because of backwards compatibility. So, while they could make it a lot better, they do not, so it’s up to us to do it. :clue:
ArrayList<Entity> entities0 = new ArrayList<Entity>(), entities1 = new ArrayList<Entity>();
.
.
.
for (int i = 0; i < entities0.size(); i ++) {
Entity e = entities0.get(i);
if (e.isActive()) {
e.process();
}
if (e.isActive()) {
entities1.add(e);
}
}
ArrayList<Entity> temp = entities0;
entities0 = entities1;
entities1 = temp;
entities1.clear();
Two things to note that look unusual at first:
- Two checks to isActive() are required.
- The size of entities0 can increase during processing (spawn a bullet, etc); that is why we do not use an iterator and dynamically check the size every loop iteration.
Cas
God damn it! Why did I not think about that before?! You have no idea what you’ve done to me now! Now I’m stuck with experimenting with multithreading for another week or so! Damn it!!!
Cas: Pure curiosity. Why the choice to spawn in the current active list rather than the next?