ArrayList, Hashtable, or ... for holding in-game-objects

Performance Tuning
#1

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

#2

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.

#3

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

#4

Yeah sorry I changed my original post :stuck_out_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.

#5

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?

#6

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.

#7

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.

#8

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.

#9

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 :slight_smile: I’d recommend that solution.

#10

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

#11

I would use a uniform grid.

#12

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.

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.

#13

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:


while(list.size() > 0)
    list.remove(0);
#14

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.

#15

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:

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.

#16

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.

#17

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.

#18

Perhaps look into a quad-tree if your thinking of handling/sorting objects with spatial information?

#19

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.

#20

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 :slight_smile: