Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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 15793 times)
0 Members and 1 Guest are viewing this topic.
Offline miga

Junior Member


Medals: 2
Projects: 1



« Posted 2011-12-27 06:21:35 »

Hello guys,

I came here looking for an advise on what data structure to implement on my game. I'm working on a shooter game. I am concerned with the way I'm designing this program. Briefly explaining, there will be player, player bullet, enemy, enemy bullet, and item objects. The update method in the game loop will be calling methods to update these game objects (I named the base class GameObject), detect 2 types of collisions (One is player with enemy, enemy bullet. Another one is player bullet with enemy), check if it should add an enemy on the screen, and so on.

I have a class called "ObjectManager" that holds these GameObjects. Originally, I was thinking of holding all of them in one Hashtable. As I was starting to write the code for collision detection on player's bullets, I realized putting all GameObjects together would just produce unnecessary amounts of loop. To make this operation more efficient, I thought of dividing each GameObject in the corresponding type of collection. I just don't know if I should go with ArrayList or Hashtable.

The way I handle when to throw enemies on the screen is by incrementing a counter variable every frame to check when. I prepare a ArrayList of enemy objects which holds an int to mark when to appear during game. The update method in game loop calls this method to check when to register enemies by comparing the counter with this int value each enemy contains. It would not new and just add this enemy object to the collection in ObjectManager, then remove from this ArrayList.

Here are some points I want to consider upon deciding...

Loop through to get the object and call update method every frame.
Get objects during collision detection.
Remove if the GameObjects except player go out of screen. (done within update method in each GameObject)
Remove if an enemy object dies.
Add when the player shoots. (let's say about 250'ish bullets at most?)
Add when the enemy shoots. (I would also say about 250-300 maximum)

I want to choose based on performance and efficiency. According to my test allocating both ArrayList/Hashtable with String, ArrayList seems to be faster... though I thought this hashing algorithm was supposed to be faster. Also, like Hashtable, it would make my life easier if I could use keys to fetch them and keep the size as the number of objects in it.(non-contiguous memory)

I hope my description is not so confusing. I would appreciate if anyone could throw some opinions.

Thanks

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

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #1 - Posted 2011-12-27 07:11:38 »

ArrayList and Hashtable are two completely different things. One is a list, which holds items in sequential order, and the other is a map, an item is mapped to another item. I have no idea what you mapping your GameObjects to you but this sounds like you need an ArrayList.

Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #2 - Posted 2011-12-27 07:14:20 »

Sorry for not mentioning. This is 2D. I'm not using libraries like Slick2D or anything.

Miga's Hobby Programming - http://www.migapro.com
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #3 - Posted 2011-12-27 07:19:32 »

Yeah sorry I changed my original post Tongue

Anyway, I don't really understand exactly what you are doing with that number in each enemy object and the counter but overall you need more of a HashSet instead of either.

Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #4 - Posted 2011-12-27 07:37:13 »

ra4king, thanks for the reply.

The counter variable and the int(I call registerTime) in enemy is to determine when to let enemy appear in the game. For example, an enemy would appear when the counter goes up to 200 and start moving/doing its move.

I think I have a wrong idea about Hashtable or Map class. I know a Map is like a dictionary where it looks up the key using hashcode, but I guess I don't know when is an appropriate time to use it. I have never used HashSet, so I looked it up a bit right now. Could you explain why HashSet would help?

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

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #5 - Posted 2011-12-27 07:44:15 »

A HashSet is an unordered list that that offered quick add and removal operations. since you will be adding and removing a lot and you don't really care about the order of the enemies, its perfect for what you want.

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #6 - Posted 2011-12-27 08:37:24 »

Take a look at Bag. It's super efficient for something like games.

You could borrow it from here:
http://gamadu.com/svn/artemis/trunk/src/com/artemis/utils/Bag.java

There are probably other versions around on the internets, or on this forum.

It's essentially an encapsulation for array, doesn't ensure element ordering (which you don't need in many cases).


If you're accessing a Map to look-up game objects in your game loop, then you're doing it wrong.

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

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #7 - Posted 2011-12-27 08:40:35 »

Isn't a Set most like a Bag? I have a bag implementation that just extends ArrayList and modifies the remove method to swap it with the last item and then remove it.

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #8 - Posted 2011-12-27 08:45:16 »

Isn't a Set most like a Bag? I have a bag implementation that just extends ArrayList and modifies the remove method to swap it with the last item and then remove it.
Set ensures it has at most one instance of the same object. In a Bag you can have multiple instances. Maybe Set is more appropriate for this problem though, but I'm not sure about performance.

But clever approach to implementing Bag Smiley I'd recommend that solution.

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

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #9 - Posted 2011-12-27 08:49:08 »

Oh no then Bag is faster because Set does a contains(object) check when adding an item, adding unnecessary overhead.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #10 - Posted 2011-12-27 09:19:38 »

I would use a uniform grid.
Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #11 - Posted 2011-12-28 01:42:44 »

ra4king, appel, Roquen thanks for replies.

A simple implementation like this Bag class sounds very nice for performance and it does the job I need. I tested ArrayList, HashSet, and Bag on my game. It seems like Bag performs the fastest.

I also tried the following test for HashSet, ArrayList, and Bag classes just out of curiosity.
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  
34  
35  
import java.util.*;


public class Main {

   public static void main(String[] args) {
      Random rand = new Random();
      String[] str = new String[100];
     
      for (int i = 0; i < 100; i ++)
         str[i] = String.valueOf(i);
     
      //List<String[]> a = new ArrayList<String[]>();
     //Set<String[]> a = new HashSet<String[]>();
     Bag a = new Bag();

      // Add operation
     final long start = System.nanoTime();
      for (int i = 0; i < 1000; i++){
         a.add(str);
      }
      System.out.println(System.nanoTime() - start);
     
      // Remove operation
     final long start1 = System.nanoTime();
      for (int j = 0; j < 1000; j++){
         int index = rand.nextInt(a.size());

         a.remove(index);
      }
      System.out.println(System.nanoTime() - start1);
     
   }

}


The result says that Bag > ArrayList > HashSet as Bag giving the fastest result. (Unless I'm doing this wrong)

I see that ArrayList's remove is not quick. I liked the idea of writing your own data structure. I can implement the least functionality I need.

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

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #12 - Posted 2011-12-28 01:46:34 »

Your tests arent consistent since you get a random index to remove.
The actual results should feature HashSet as the second fastest with Arraylist the slowest.
Try changing the remove test to:
1  
2  
while(list.size() > 0)
    list.remove(0);

Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #13 - Posted 2011-12-30 01:02:12 »

Thanks a lot again. I felt like I have to take a deeper look into data strictures. I'm still confused with HashSet though. I will think further to decide what I really need. Maybe modify that Bag class to suit my need better...I will see.

Thanks again for all comments.

Miga's Hobby Programming - http://www.migapro.com
Offline theagentd
« Reply #14 - Posted 2011-12-30 11:24:34 »

Performance characteristics of sets and lists are very interesting and can affect performance a lot (as you've probably noticed). I suggest you take a very quick look at this wiki page: http://en.wikipedia.org/wiki/Big_O_notation

ArrayList:
 - Adding objects is O(1) = constant time regardless of the size.
 - Getting objects is O(1).
 - Removing objects is O(n) = time depends linearly on the size of the list. Double the size and the (average) access time doubles too. Note that remove(0) is the worse case scenario as a remove forces a copy of all following objects to fill the first spot that was left empty.
 - contains(object) is O(n) since the whole list has to be traversed to check if the object is in the list.

LinkedList:
 - Adding objects is O(1)
 - Random access (getting using indices) is O(n). Getting objects in order using an iterator is O(1).
 - Removing objects is O(n) when using indices or references to remove objects. Removing objects with an iterator MIGHT/SHOULD be O(1).
 - contains(object) is O(n) since the whole list has to be traversed to check if the object is in the list.

HashSet / HashMap:
 - "This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets." - Javadoc
 - In optimal conditions: O(1) for adding, removing and getting objects, and also contains(object).
 - In worse case scenarios: O(n) for adding removing and getting objects.
 - Average is somewhere in between. I think it's O(1) on average, but the time it takes MAY increases with the size/capacity, but not linearly. The point is that doubling the size does NOT double the time it takes. It all depends on how good the hash function is at generating hashes that don't end up in the same "bucket" of the hash set/map.

Note that Big O-notation does not state how much a function costs in time, just how it scales when the amount of data is increased. Adding objects to LinkedLists is more expensive than an ArrayList as it creates a local Entry object to store references to the next and previous Entry, while an ArrayList add is just array[index] = object; plus an array range check on the index and increasing the size. Traversing a LinkedList is also slower compared to traversing an array(-list).

HashSet and HashMap are not meant for linear access, making them a pretty poor choice for storing game objects. One of the reasons for this is that they do not guarantee the ordering of objects, and this can affect how the game is played. Iterating over them is also pretty slow, with the time taken to iterate over them depending on both the capacity (the number of "buckets") and the size (the number of objects) in the hash set/map. If it all sounds interesting, I recommend reading up on them on Wikipedia:
1  
http://en.wikipedia.org/wiki/Hash_table
. HashSets are the only set that has an average time of O(1) for contains(object), so they are very fast when you need to use contains(object) often.

However, I have found that I can work around having a HashSet or HashMap almost every time I thought or were told to use one. For example, in pathfinding it is necessary to keep track of which places you have already visited. This can be done with a standard list, but we only do a few adds, LOTS of contains and a single clear on it per run. On a tiled map, each node that we traverse has 8 neighbors that have to be checked against the closed list (our ArrayList). If we have traversed 200 nodes, that 1600 checks for 8 neighbors. Simply switching to a HashSet will reduce the average number of checks from slightly under 1600 to slightly over 8. The speed-up is insanely good, but even more noticeable the longer the path we're looking for is. Doubling the number of nodes in the closed list/set will both double the number of checks calls to contain(object), and also double the number of checks each contain(object) since the list is twice as big. A HashSet seems like the perfect solution for this problem, but there is an even better solution: Simply marking a node as closed instead of having a list at all. Keeping a boolean variable in the Node object to indicate the status of the node allows us to ALWAYS get O(1) performance of the closed check (obviously), which is obviously better than an AVERAGE performance of O(1). Most problems with that can be solved with HashMap and HashSets can be solved with simple references. If anyone knows of a case where HashMaps have to be used, I'd love the hear about it!

EDIT: Kind of found one: Let's say you want to map integer ID values to an Object so you can retrieve objects based on their IDs. If the ID value is received from a network connection or something like that, it's impossible to substitute it with a reference.

Myomyomyo.
Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #15 - Posted 2012-01-03 02:36:50 »

theagentd, Thanks a lot for the detailed explanation.

Just a little conclusion within myself...

I see. I think I have my understanding of why not to use Hashtable to hold game objects. I need something that would perform iterating, adding/getting/removing frequently, and get by index well. What I had liked about Hashtable is being able to store in key-pair without worrying about size of structure, but it's not necessary. Also, easy to remove while iterating without worrying about CurrentModificationException. Though there are alternative ways to remove while iterating with other data structures.

Hashtable doesn't care about order of elements in it, so if I want to iterate it in order, I would have to allocate an array with keys, then call get() methods in loop.

On the other hand, ArrayList's downside is remove like everyone says. I would be removing a lot of player bullets in game when they goes out of screen. If I use array based structure like the Bag class above... I think I should set the size as the possible maximum number of bullets on screen. That would be more efficient than ArrayList since it's very likely that the player will be holding the shoot key long in a shooter game. I don't want the list to be shifting all elements all the time.

Miga's Hobby Programming - http://www.migapro.com
Offline theagentd
« Reply #16 - Posted 2012-01-03 04:54:23 »

Unless you have several thousand bullets at the same time, I wouldn't worry about it. The shift/copy is done using System.arraycopy(...) which is ridiculously fast.

I developed a small ArrayList alternative for a particle engine once, which proved to be very effective. However it did not keep the objects ordered, because it inserted new particles over dead particles to fill the holes that appears when particles dies. It proved to have very good performance, since the number of copied elements could be brought down to about 10% of an ArrayList. As long as ordering doesn't matter, I can share the code with you.

Myomyomyo.
Offline SwampChicken
« Reply #17 - Posted 2012-01-03 08:25:27 »

Perhaps look into a quad-tree if your thinking of handling/sorting objects with spatial information?
Offline Roquen
« Reply #18 - Posted 2012-01-03 10:49:34 »

I'd stick with learning to standing before to attempting run.  (See my previous uniform grid suggestion)  Besides, I don't see any reason to use a quad-tree from what's been said so far.  Plus what kind of quad-tree?  Region or non-region?  Explicit or implicit nodes?  Single or forest?  Choosing between all the various options can be tricky even when one is familiar with the techniques.
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #19 - Posted 2012-01-03 13:10:40 »

Just one side note I would like to make: there is almost no situation in existence, ever, that you would want to use a LinkedList. It exists mostly as a curiosity for computer science degrees as an example of a data structure that has no practical application, like the infamous bubble sorting algorithm.

Cas Smiley

Offline Roquen
« Reply #20 - Posted 2012-01-03 13:18:51 »

Hey! I use both!  (but yeah, as a part of something else is where they have practical application)
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #21 - Posted 2012-01-03 13:34:03 »

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #22 - Posted 2012-01-03 13:56:51 »

Actually hold on there princec, I think LinkedList is perfect for games that want to preserve order yet need to add/remove items quickly.

Offline AurelienRibon

Senior Newbie


Medals: 3


Toolmaker, yeah.


« Reply #23 - Posted 2012-01-03 14:08:33 »

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.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #24 - Posted 2012-01-03 14:09:50 »

Actually hold on there princec, I think LinkedList is perfect for games that want to preserve order yet need to add/remove items quickly.

I always like TreeMap for that kind of usage.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline princec

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #25 - Posted 2012-01-03 14:50:19 »

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 Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #26 - Posted 2012-01-03 16:36:41 »

You can absolutely guarantee to get vastly better performance by using a double-buffered ArrayList
Why double buffered?

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

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #27 - Posted 2012-01-03 18:27:48 »

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.

<edit> 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 Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #28 - Posted 2012-01-03 18:44:19 »

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.

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

JGO Kernel


Medals: 378
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #29 - Posted 2012-01-03 19:15:44 »

The order of elements is almost always important.

Cas Smiley

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.

Dwinin (19 views)
2014-09-12 09:08:26

Norakomi (54 views)
2014-09-10 13:57:51

TehJavaDev (63 views)
2014-09-10 06:39:09

Tekkerue (31 views)
2014-09-09 02:24:56

mitcheeb (53 views)
2014-09-08 06:06:29

BurntPizza (37 views)
2014-09-07 01:13:42

Longarmx (23 views)
2014-09-07 01:12:14

Longarmx (27 views)
2014-09-07 01:11:22

Longarmx (27 views)
2014-09-07 01:10:19

mitcheeb (35 views)
2014-09-04 23:08:59
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!