Databases
StackOverflow2013
Postsdbo
POAndroid Game Development: Which data structure to use?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAndroid Game Development: Which data structure to use?
    primarykey
    data
    text
    <p>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. </p> <p>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:</p> <ol> <li>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.</li> <li>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.</li> </ol> <p>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.</p> <p>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.</p> <p>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).</p> <p>However, the grid idea poses its own problems:</p> <ol> <li>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.</li> <li>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.</li> </ol> <p>So the ultimate question is: should I use linked list, multi-dimensional array, or something else that I haven't considered?</p> <p>Below is an idea of how I am implementing collision:</p> <pre><code>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(); } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDan
    1. USDan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAndroid Game Development: Which data structure to use?
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload