Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2] 3 4
  ignore  |  Print  
  ArrayList, Hashtable, or ... for holding in-game-objects  (Read 15285 times)
0 Members and 1 Guest are viewing this topic.
Offline ra4king

JGO Kernel


Medals: 338
Projects: 2
Exp: 5 years


I'm the King!


« Reply #30 - Posted 2012-01-03 20:32:51 »

The order of elements in the same z-index is almost never important.

Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #31 - Posted 2012-01-03 20:52:28 »

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 Smiley

Offline Cero
« Reply #32 - Posted 2012-01-03 23:09:59 »

I always just use pure arrays.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #33 - Posted 2012-01-04 00:11:28 »

Sun...ehrm...Oracle did an amazing job of forcing us to write our own collections for performance.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #34 - Posted 2012-01-04 00:13:02 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #35 - Posted 2012-01-04 00:29:27 »

Everyone, thank you so much for the comments.

@theagentd

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...

1  
2  
3  
4  
5  
6  
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..
1. You have a main ArrayList listA(front buffer).
2. When you iterate it every frame, create a temporary ArrayList listB.
3. Whenever it requires you to add or remove game object, you would add into listB.
4. 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.

Miga's Hobby Programming - http://www.migapro.com
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #36 - Posted 2012-01-04 01:06:22 »

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.
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.  Clueless

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #37 - Posted 2012-01-04 11:29:15 »

@princec
Pardon me for my lack of understanding. Is it like for example..
1. You have a main ArrayList listA(front buffer).
2. When you iterate it every frame, create a temporary ArrayList listB.
3. Whenever it requires you to add or remove game object, you would add into listB.
4. 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?
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
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:
1. Two checks to isActive() are required.
2. 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 Smiley

Offline theagentd
« Reply #38 - Posted 2012-01-04 14:17:51 »

...

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!!!

Myomyomyo.
Offline Roquen
« Reply #39 - Posted 2012-01-04 15:31:25 »

Cas: Pure curiosity.   Why the choice to spawn in the current active list rather than the next?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #40 - Posted 2012-01-04 16:01:41 »

Because a call to getEntities() has to consistently return the "current" list (eg. entities0); also, I want any entities spawned to receive a call to process() in that tick. I don't really know if there's a cleverer way of doing all this but it does work very simply and intuitively.

Cas Smiley

Offline nsigma
« Reply #41 - Posted 2012-01-04 16:07:32 »

Because a call to getEntities() has to consistently return the "current" list (eg. entities0); also, I want any entities spawned to receive a call to process() in that tick. I don't really know if there's a cleverer way of doing all this but it does work very simply and intuitively.

Cas Smiley

Couldn't you call process() as you spawn them, before adding them to the other list.  Depends where you need them ordered, I suppose - my way they'll be next to the entity that spawned them I presume?

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #42 - Posted 2012-01-04 16:18:46 »

I just tended to find that anything that monkeys with the order of things being spawned tends to produce strange unreproducible effects. So with the hard and fast rule "everything is processed in the order it was originally created", everything always works, the same way.

I have a feeling you're just trying to avoid calling .size() on the list in that loop for the sake of it Smiley

Cas Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #43 - Posted 2012-01-04 18:00:53 »

Surely this
1  
2  
3  
4  
5  
6  
7  
8  
9  
for (int i = 0; i < entities0.size(); i ++) {
   Entity e = entities0.get(i);
   if (e.isActive()) {
      e.process();
   }
   if (e.isActive()) {
      entities1.add(e);
   }
}

can be 'optimized' to
1  
2  
3  
4  
5  
6  
7  
8  
9  
for (int i = 0; i < entities0.size(); i ++) {
   Entity e = entities0.get(i);
   if (e.isActive()) {
      e.process();
      if (e.isActive()) {
         entities1.add(e);
      }
   }
}

</nitpick>

Depending on the implementation of .isActive() this can make your logic up to 3000x faster.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline theagentd
« Reply #44 - Posted 2012-01-04 18:10:12 »

Depending on the implementation of .isActive() this can make your logic up to 3000x faster.
Is isActive() supposed to try to resuscitate the entity before finally determining if it is inactive or not?! I don't see when isActive() would not simply return a boolean variable.

Myomyomyo.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #45 - Posted 2012-01-04 18:11:26 »

It was a joke Sad

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline nsigma
« Reply #46 - Posted 2012-01-04 18:22:39 »

I just tended to find that anything that monkeys with the order of things being spawned tends to produce strange unreproducible effects. So with the hard and fast rule "everything is processed in the order it was originally created", everything always works, the same way.

I have a feeling you're just trying to avoid calling .size() on the list in that loop for the sake of it Smiley

Not at all.  I don't think you'd mentioned the necessity to keep in spawned order, just to call process() on the spawned object and keep things in a consistent order.  Therefore, adding to the current list seemed a wasted operation.  I also like to keep away from changing list contents while iterating over them, even if the way you're doing it here is safe.
 

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #47 - Posted 2012-01-04 18:36:56 »

A double buffer where you scan through the front buffer, adding objects that are still alive and new objects to the back buffer
I think this is what confused some people, after you provided the actual code.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline ra4king

JGO Kernel


Medals: 338
Projects: 2
Exp: 5 years


I'm the King!


« Reply #48 - Posted 2012-01-04 18:46:52 »

What I do is not remove the Entity until after the loop terminates. In my Bag implementation, I set the index to null (my Iterable knows to skip nulls) and when the loop ends, I remove all nulls.

Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #49 - Posted 2012-01-04 19:58:28 »

Riven's small tweak is quite right, small slip of the curly brackets.

Cas Smiley

Offline theagentd
« Reply #50 - Posted 2012-01-04 20:45:30 »

It was a joke Sad
My response too... Sad

Myomyomyo.
Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #51 - Posted 2012-01-04 20:59:29 »

princec, thank you for explaining.

Very interesting. So basically, the advantage is that you don't call remove(). Also, it will keep it in the order game objects spawn.

Are you declaring entities1 at the same time with entities0, so you can add entities from other places/methods? Why not declare entities1 within every frame when you loop keeping it local? Is it to keep the capacity of array within ArrayList same as the list before?, so unless you add new objects somewhere else, the capacity of list would not have to increase? And to avoid instantiating every frame?

Miga's Hobby Programming - http://www.migapro.com
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #52 - Posted 2012-01-04 21:23:13 »

Yes. No need to keep allocating and resizing it.

Cas Smiley

Offline theagentd
« Reply #53 - Posted 2012-01-04 22:29:09 »

A small optimization to ArrayList.clear() that I thought of: Maybe not really clearing it like ByteBuffer? Yeah, you might want to clear out old references so the GC can get rid of them, but you can do this every x-th frame (maybe with a semi-random bias so the "true" clears don't sync up). That would get rid of looping through all the data each frame just to get rid of it.

Myomyomyo.
Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #54 - Posted 2012-01-04 22:39:24 »

I see. I'm thinking how I can implement this in my code. Since I have separate ArrayLists for each type of game object, I would have to prepare same number of ArrayLists I have so that I can buffer all of them. My concern is the cost of having 2 ArrayLists per type of object(enemy, enemy bullets, player bullets, and item). It's not that my program is going through a serious need of tuning, yet, but I'm trying to think of the best way. I just don't want to loop too many unnecessary times when detecting collision. There will always be a lot of player's/enemy's bullets flying around.

I do think it's a good idea to loop game objects by order of spawn especially if I decide to interact between same types of entities or if I was keeping all my entities in one list.

Miga's Hobby Programming - http://www.migapro.com
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #55 - Posted 2012-01-04 23:11:36 »

I keep all my entities in one big list, generally. Collision I do with a grid cell approach (Revenge, Droid Assault) or simple brute force (Titan Attacks, Ultratron). I do mirror certain parts of the list into sublists of types, eg. buildings, gidrahs; but only the "main" list need be "double-buffered" in this way.

Cas Smiley

Offline theagentd
« Reply #56 - Posted 2012-01-05 06:17:24 »

I see. I'm thinking how I can implement this in my code. Since I have separate ArrayLists for each type of game object, I would have to prepare same number of ArrayLists I have so that I can buffer all of them. My concern is the cost of having 2 ArrayLists per type of object(enemy, enemy bullets, player bullets, and item). It's not that my program is going through a serious need of tuning, yet, but I'm trying to think of the best way. I just don't want to loop too many unnecessary times when detecting collision. There will always be a lot of player's/enemy's bullets flying around.

I do think it's a good idea to loop game objects by order of spawn especially if I decide to interact between same types of entities or if I was keeping all my entities in one list.

Shouldn't an Object[] just be 64-bit references, so it's just 8 bytes times the size of the array? I mean, my laptop has 4GB RAM, that's enough room for 536 870 912 array elements... Even in just one megabyte you can store 131 072 elements, so you should NOT worry about memory usage. I agree with Cas, a double-buffered ArrayList is most likely the best solution.

Myomyomyo.
Offline Scarzzurs
« Reply #57 - Posted 2012-01-05 11:58:04 »

Just to chip in, I use a tactic very similar to princec:

1) Typed uniform grids for fast collision detection.
2) A long (ordered) list with all entities in the game.

This list has delayed addition and removal of entities (stored in a single queue).
Entities will have their spawn method called when they have become part of the entity list.
Entities will have their cleanup method called when they are no longer part of the entity list.
Thus entities are spawned and removed in order.

Another benefit is that the list of entities is stable throughout physics computation.
It works well under the assumption that the game objects stay in the game for a long time (several iterations).
But of course all methods have drawbacks :-)

I used to use the same approach for all games, but I'm shifting towards more modular and individual designs.
As such my game engine is starting to more and more become a game library instead...

- Scarzzurs

My games and Projects:
BlastingPixels.com,
Old website
Offline gimbal

JGO Knight


Medals: 25



« Reply #58 - Posted 2012-01-05 13:35:13 »

Just to chip in, I use a tactic very similar to princec:

1) Typed uniform grids for fast collision detection.
2) A long (ordered) list with all entities in the game.

Yup, me too. If by entity you mean a game object that animates, moves and/or can disappear from the game world.
Offline Grunnt

JGO Wizard


Medals: 66
Projects: 8
Exp: 5 years


Complex != complicated


« Reply #59 - Posted 2012-01-05 14:42:41 »

Doesn't all the adding and removing game objects generate massive amounts of garbage? I'm trying to understand the discussion here, but have a hard time understanding why - performance wise - any of these constructions should be better than a simple array, e.g. I'm usually doing something like this:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
int numberOfBullets = 10000;
Bullet[] bullets = new Bullet[numberOfBullets];

for (int i = 0; i < numberOfBullets; i++)
  bullets[i] = new Bullet();

[... snip ...]

public void update() {
for (int i = 0; i < numberOfBullets; i++)
   if (bullets[i].isActive())
      bullets[i].update();
}

Pages: 1 [2] 3 4
  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.

Riven (15 views)
2014-07-29 18:09:19

Riven (10 views)
2014-07-29 18:08:52

Dwinin (10 views)
2014-07-29 10:59:34

E.R. Fleming (28 views)
2014-07-29 03:07:13

E.R. Fleming (10 views)
2014-07-29 03:06:25

pw (40 views)
2014-07-24 01:59:36

Riven (39 views)
2014-07-23 21:16:32

Riven (27 views)
2014-07-23 21:07:15

Riven (29 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!