Android Game Development: Which data structure to use?

Question

I am making a game for Android. I am kind of trying to keep the game a secret so I cannot reveal too much about it, so bear with me. Basically it runs in real-time (so I will be implementing a thread to update objects' coordinates) and its style is kind of like Duck Hunt; you have to hit objects that move around on the screen.However, the game has been lagging slightly from time to time (running on a Samsung Galaxy S, which is one of the higher-end devices) so I believe I need to use a better data structure.

Basically I am storing these objects in a doubly linked list instead of in an array because I wanted the maximum number of objects on the screen to be dynamic. In other words, I have a reference to the head and tail objects and all the game objects are connected just as a typical linked list would. This provides the following problems:

1. Searching if an object intersects with a given coordinate (by touching the screen) takes O(n) time (worst case scenario) because I have to traverse from head to tail and check the hitbox of each object.
2. Collision checking between two objects takes O(n^2) time (again, worst case scenario) because for every object I have to check if its hitbox intersects with that of all other objects in the linked list.

Another reason why I chose linked list is because I basically have two linked lists: one for active objects (i.e. objects that are on the screen) and one for inactive objects. So let's say that there will be at most 8 objects on the game screen, if the active linked lists would have 5 objects, the inactive list will have 3 objects. Using two linked list makes it so that whenever an object becomes inactive, I can simply append it to the inactive linked list instead of dereferencing it and waiting for the garbage collector to reclaim memory. Also, if I need a new object, I can simply take an object from the inactive linked list and use it in the active linked list instead of having to allocate more memory to create a new object.

I have considered using a multi-dimensional array. This method involves dividing up the screen into "cells" in which an object can lie. For example, on a 480x800 screen, if the object's height and width are both 80 pixels, I would divide the screens into a 6x10 grid, or in the context of Java code, I would make GameObject[6][10]. I could simply divide the coordinates (on the screen) of an object by 80 to get its index (on the grid), which could also provide an O(1) insertion. This could also make searching by coordinate O(1) as I could do the same thing with the touch coordinates to check the appropriate index.

Collision checking might still take O(n^2) time because I still have to go through every cell in the grid (although this way I only have to compare with at most 8 cells that are adjacent to the cell I am examining currently).

However, the grid idea poses its own problems:

1. What if the screen has a resolution other than 480x800? Also, what if the grid cannot be evenly divided into 6x10? This might make the program more error prone.
2. Is using a grid of game objects expensive in terms of memory? Considering that I am developing for a mobile device, I need to take this into consideration.

So the ultimate question is: should I use linked list, multi-dimensional array, or something else that I haven't considered?

Below is an idea of how I am implementing collision:

private void checkForAllCollisions() {
 GameObject obj1 = mHead;

 while (obj1 != null) {
        GameObject obj2 = obj1.getNext();
            while (obj2 != null) {
                //getHitBox() returns a Rect object that encompasses the object
                Rect.intersects(obj1.getHitBox(), obj2.getHitBox());
                //Some collision logic
            }
            obj1 = obj1.getNext();
        }
}

Answer 1

Common data structures for better collision-detection performance are quadtrees (in 2 dimensions) and octrees (3 dimensions).

If you want to stick with a list - is there a reason you're using LinkedList and not ArrayList? I hope you are currently using the built-in linked list implementation...

---

A Samsung Galaxy S has 512 MB of RAM - don't worry about taking up too much memory with a single data structure (yet). You'd have to have a relatively high number of relatively heavy objects before this data structure starts sucking significant amounts of RAM. Even if you have 1000 GameObject instances, and each instance in the data structure (including the associated weight of storing an instance in said data structure) was 10,000 bytes (which is pretty honking big) that's still only 9.5 megabytes of memory.

Answer 2

So I definitely think that there's something we need to firstly consider.

1.) LL vs. Array

You said that you used a LL instead of an array because of the dynamic property the LL gives you. However, I would like to say that you can make using an array dynamic enough by doubling the size of it after it has filled up, which will give you O(1) runtime of insert amortized (given that the array is being unkept/unsorted). However, there will be a scenario where every now and then an insert can take O(n) since you must copy the data appropriately. So, for live games such as this, I believe the LL was a good choice.

2.) Your consideration of memory in terms of game objects.

This depends heavily on the structure of each GameObject, which you have not provided enough detailed information about. If each GameObject only contains a couple of ints or primitive types, chances are that you can afford the memory. If each GameObject is very memory costly and you are using a very large grid, then it will definitely cost tons of memory, but it will depend on both the memory usage of each GameObject as well as the size of the grid.

3.) If the resolution is different than 480x800, don't worry. If you are using a 6x10 grid for everything, consider using a density multiplier like so:

float scale = getContext().getResources().getDisplayMetrics().density;

and then getWidth() and getHeight() should be multiplied by this scale to get the exact width and height of the device that's using your app. You can then divide these numbers by the 6 and 10. However, note that some grids may look ugly on some devices, even if they are scaled correctly this way.

4.) Collision Handling

You mentioned that you were doing collision handling. Although I cannot say which is the best way to handle this in your situation (I'm still kind of confused how you're actually doing this based on your question), please keep in mind these alternatives:

a.) Linear Probing b.) Separate Chaining c.) Double Hashing

which are all admittedly hash collision handling strategies, but may be implementable given your game (which, again, you would know more about since you have kept some info back). However, I will say that if you use a grid, you may want to do something along the lines of linear probing or create 2 hash tables all together (if appropriate, but this seems to take away the grid-layout you're trying to achieve, so, again, your discretion). Also note that you may use a tree of some sort (like a quadtree) to get faster collision detection. If you don't know about quadtrees, check them out here. A good way to think of one is dividing a square picture into separate pixels at the leaves and storing the average colors at the parent nodes for pruning. Just a way to help you think of quadtrees meaningfully.

Hoped that helped. Again, maybe I'm misunderstanding something because of the vague nature of your question, so let me know. I'd be happy to help.