0

I have an ArrayList with 40,000 separate objects that can be drawn to the screen. Right now I have to iterate through all of them, and perform a calculation if they are showing on the screen, before I draw them with a Graphics2D object.

for (GameObject object : gameObjects) {
        if (insideScreenView(object)) {
            object.draw(g2d);
        }
    }

This doesn't take too long, but it does take about 2-5 ms. Only about 100 of these objects are showing on the screen at any given time. Meaning that I am running 39,900 iterations that aren't necessary. Is there a better way to do this, given that I know most iterations don't have to happen.

Edit: Objects are chosen to be on screen based on if an object's bounding rectangle intersects the screen via Rectangle's intersects() method.

BitNinja
  • 1,477
  • 1
  • 19
  • 25
  • Could you give us more info on how you know what objects to choose and not? – Einar May 24 '14 at 18:22
  • Only way I can see is to implement a 2nd array that contains the objects drawable on the screen. Maybe in your core game loop after you do something with the object check if `insideScreenView` if so then add it to the drawable array. – ug_ May 24 '14 at 18:23
  • Maybe if you post the insideScreenView code we can see it and see if can be improved. (P.S why insideScreenView is not a method of GameObject?) – Marco Acierno May 24 '14 at 18:28
  • Obviously, this has been widely studied in computer graphics. Search for frustrum culling... It usually requires some acceleration data structure like BVH or kd-tree. – Jaa-c May 24 '14 at 18:30
  • @MarcoAcierno `insideScreenView()` is a single call to `screenRect.intersects(object.getRect())`. Where `screenRect` is a `Rectangle` that holds the location of the in-game camera. It is implemented as-per this question: http://stackoverflow.com/questions/9997006/slick2d-and-jbox2d-how-to-draw?answertab=votes#tab-top – BitNinja May 24 '14 at 18:34
  • Can you afford an extra thread to manage half of them? – rath May 24 '14 at 18:46
  • @rath probably, how would I go about doing that though? – BitNinja May 24 '14 at 18:52
  • You keep the extra thread in stand-by and give it the arraylist. At this point, the thread will start checking the objects by starting at arraylist.size()/2, and that's where the main thread stops at (you can scale that up as much as it makes sense). Your biggest problem though would be lock contention, ie. make sure the threads don't fight over resources. If you haven't worked with threads in the past it's gonna be a bit of an uphill battle to get it right the first time, but if done right it can nearly double (or more) performance at this choke-point. – rath May 24 '14 at 19:03

1 Answers1

1

Instead of iterating ALL the game objects, you should iterate only the viewable objects.

So, how to do that?

->> METHOD 1 (slow, but simple) <<-

First, separate your game logic in 2 pieces: updateView(), and draw().

  • updateView(): Here, you calculate what objects are inside the screen, and add them to a simple List (you can choose ArrayList or LinkedList, each one will have different performance impact, so, benchmark them!).

  • draw(): Here, you iterate over all the objects on the List you created before on updateView, and draw them.

->> METHOD 2 (fast, but complex) <<-

The basic logic is somewhat like Method 1: you have the viewable objects inside a List, and draw them on draw() method. But the difference between these methods is that, on this method, instead of each tick verify what objects are viewable, you check when the objects move.

Depending on how your Game Objects are managed, Method 1 can be faster (if your Game Objects are moving every time, like particles), but for general purposes, this method is faster.

So, inside Game Object, you add a boolean called addedToViewList. This boolean indicates whether the object is added to the viewable objects list, so we don't need to use list.contains(object) and iterate over it. Then, every tick, you check if the object is already on the list. If it is, you check if he is viewable or not: if not, you remove him from list. If he wasn't on the list, but he is viewable, then you add him to list.

Example:

public void onMove() {
  if (addedToViewList && !insideScreenView()) {
    this.addedToViewList = false;
    (view list).remove(this);
  }
  else if (!addedToViewList && insideScreenView()) {
    this.addedToViewList = true;
    (view list).add(this);
  }
}

Hope I helped you. See ya!

João Vitor Verona Biazibetti
  • 2,223
  • 3
  • 18
  • 30