How to limit calculations to just a subset of the total objects on screen.

eightohnine · October 2015

Guys and gals,

I've been searching for a solution to my question in the forums – because I'm pretty sure I'm not the first person to ask this – but obviously I'm not using the right keywords, because I've not yet found any answers.

This is my hypothetical setup: Let's say I have a few thousand white ellipses scattered randomly on the screen and I want to turn every object fill-color within a 100px radius of the mouse to red. The working and obvious solution is to loop through EVERY object in play and use dist() to determine it's distance to the mouse and then act accordingly. Which does work fine, but slows down considerably the more objects are on the screen and the more complex the behaviours of these objects become.

Now I'm thinking that it ought to be possible to limit the actual calculations to just a fraction of the total objects, create sort of a "preselection" I you want, and thus forego the dist()-check on all object. But that's where I'm stuck. I know there are optimisation processes in programming to prevent ALL calculations happening at ALL time (like chunks in Minecraft) but I can't find the right terms to start reading into this topic. I've thought about creating quadrants, then checking which object is in which quadrant and then just apply calculations to the objects in the same quadrant as the mouse currently is. But my code always turns out to at some point require the same calculations across all objects. I'm stumped and would be grateful, not for a code solution, but on pointers on where I could read about this topic/which keywords I should be searching for. (Given the facts, that what I'm imagining is in fact a thing).

Also, I'm not specifically only trying to turn white ellipses red, that's just a simple example. I'd like to know how to set up a system which does the selection of a subset of objects, no matter what the actual operations then might be.

Thanks!

KevinWorkman · October 2015

Sounds like a job for a quadtree.

Or you could try a grid system. Picture a Mario game: the game doesn't have to perform collision checks on every object in the game, it just figures out which grid cells Mario is in and checks the object in those cells.

Or you could try a square hitbox instead of a circular hitbox. The less-than / greater-than comparisons a square hitbox requires would probably be faster than the distance function a circular hitbox requires. Then you can do the circular distance check only between object whose square hitboxes collide.

eightohnine · October 2015

Whoa, thanks for the swift reply.

I actually edited my initial post to explicitly not look for the solution for a turn-white-to-red-using-dist()-problem, but a more general approach for selecting only a subset of objects to operate on. In fact, my actual problem doesn't use stationary ellipses at all, but ones moving around the screen at varying velocities. Therefore assigning objects to a specific quadrant would be moot the very next cycle when all positions have shifted. Or rather, the quadrant-reassigning process would happen as often as a direct dist()-check and so not reduce the amount of cpu-power needed.

I've actually bumped into quadtree on a couple occasions in the past, and while I understand how they can become in handy, I have zero clue where to start utilising them for my kind of problem. Will definitely have to dig into that topic.

Thanks for the suggestions!

quark · October 2015

As well as searching for quadtree you could also try space partitioning which would probably be easier to implement.

I have a Processing example using quadtree that I created a while ago which you could have, uses PS2 and G4P but I could easily update it if you are using PS3. My AI library uses space partitioning.

KevinWorkman · October 2015

I actually edited my initial post to explicitly not look for the solution for a turn-white-to-red-using-dist()-problem, but a more general approach for selecting only a subset of objects to operate on.

All of the solutions I posted are general.

Therefore assigning objects to a specific quadrant would be moot the very next cycle when all positions have shifted. Or rather, the quadrant-reassigning process would happen as often as a direct dist()-check and so not reduce the amount of cpu-power needed.

I disagree. You're going off what you think is true instead of doing any actual profiling. The whole goal is to reduce the number of distance checks you have to do. That's exactly what a quadtree does. The point is that inserting into a quadtree is cheaper than the collision check, so even though you still have to do that for every object, you're still saving time.

I have zero clue where to start utilising them for my kind of problem.

Start by googling "Java quadtree" or "Processing quadtree" for a ton of examples. The wikipedia link I gave you contains examples of pseudocode.

Yet another option would be to use a physics engine like Box2D, but that might be overkill for your actual goal.

eightohnine · October 2015

You're going off what you think is true instead of doing any actual profiling.

...aaaand now I have egg on my face. You're completely right, I have no idea how quadtree works, so I shouldn't assume.

And you're right, I've already found a plethora of promising tutorials... time to learn!

eightohnine · October 2015

@quark

I have a Processing example using quadtree that I created a while ago which you could have

If you'd let me look into the source, yeah, that'd be great! Also, I'll look into your AI library as well. Thanks!

quark · October 2015

The quadtree source code example is not secret, but it uses the G4P library so you can modify the quadtree parameters to see what happens. Changes made in moving PS2 to PS3 means each have a different version of G4P. So I need to know whether you are using PS2 or 3.

Let me know are I will provide a link to download the code.

I mentioned the AI library because it proves that space partitioning is a viable alternative to quadtrees. I would not recommend looking at the source code to see cell-partitioning in action. The library uses some very complex data structures to enable a limitless game space game and would probably make little sense except to very experienced programmers.

eightohnine · October 2015

I would not recommend looking at the source code to see cell-partitioning in action.

Ah, yeah, makes sense.

I'm currently using PS3 beta... so right in the middle. But I'll be updating to PS3 soon, now that it's launched officially.

quark · October 2015

You can download the demo sketch from here. Unzip the sketch and put it into your sketch folder. The sketch includes the G4P library jar file so it should run from PS3b7 and PS3 without further installs.

When you run it you will get 2 windows as shown below. The left window is the control panel and the black square shows the current simulation parameters. To create a new simulation change them in the bottom panel and click New Simulation

The centre panel shows the number of balls at each level of the quadtree and the current simulation has 5 levels and the quad partition is half the size of the partition above. You can increase the number of levels but be careful if the quad partition gets too small then the balls are never completely within them and you can see this in the centre panel, when that happens it becomes less efficient.

qtree

Anyway have a play with it and if you have any questions post them here.

GoToLoop · October 2015

There's a more modest approach w/ Comparable + sort():

The point is to implement a compareTo() method inside the class which represents the ellipse().

We then compare the x coordinate against the other x from another ellipse().

This way, when we invoke sort(), the container will be sorted by the order of the x coordinate.

Then when checking an area for a mousePressed(), we can skip all those x coordinates outside mouseX's range.

That'll boost a lot the double loop check, since we can skip a whole ellipse() when it's far away from mouseX!

Here's an upgraded version sketch from a very old thread for Processing 2 & 3 now.
So you can have some idea how it works: O:-)
http://forum.Processing.org/one/topic/interaction-among-objects-in-an-array.html

/**
 * Vector Dot Lines (v3.65)
 * by GokPotter (2013/Feb)
 * modders v.k., Thomas.Diewald, GoToLoop (2015/Oct/06)
 *
 * forum.Processing.org/two/discussion/12855/
 * how-to-limit-calculations-to-just-a-subset-of-the-total-objects-on-screen
 *
 * forum.Processing.org/one/topic/gradual-movement-within-a-for-loop
 * forum.Processing.org/one/topic/drawing-a-network-of-nodes-and-links
 * forum.Processing.org/one/topic/interaction-among-objects-in-an-array
 *
 * studio.ProcessingTogether.com/sp/pad/export/ro.9Kzw4QVZGKeFZ
 * studio.ProcessingTogether.com/sp/pad/export/ro.9s0026dE7B8v-
 */

static final color BG = -1, FG = 0;
static final short DOT_DIST = 50, DOT_OPACITY = 60;
static final float DOT_MAX_SPD = 3, FPS = 60, BOLD = 1;

static final short NUM_DOTS = 5000;
final Point[] points = new Point[NUM_DOTS];

static final String GFX = FX2D; // P2D for Processing 2

int dotConnects;

void setup() {
  size(1024, 800, GFX);
  frameRate(FPS);
  noSmooth();
  strokeWeight(BOLD);
  stroke(FG, DOT_OPACITY);

  for ( int i = 0; i != NUM_DOTS; points[i++] = new Point() );
}

void draw() {
  background(BG);

  java.util.Arrays.sort(points);

  final float dotRange = map(mouseX, 0, width, 1, DOT_DIST);
  dotConnects = 0;

  for (int i = 0; i != NUM_DOTS; ) {
    final Point p = points[i++];

    p.update();
    p.drawPoint();

    nearestNeighbors(p, i, dotRange, points);
  }

  frame.setTitle(" Nearest neighbor"
    + " | fps "         + nf(frameRate, 0, 2)
    + " | dotRange "    + nf(dotRange, 0, 2)
    + " | numPoints "   + NUM_DOTS
    + " | numConnects " + dotConnects);
}

void nearestNeighbors(Point p1, int idx, float range, Point[] dots) {
  final float rangeSq = range * range;
  final float x = p1.loc.x, y = p1.loc.y;

  for (int j = idx; j != NUM_DOTS; ) {
    final Point p2 = dots[j++];

    final float dx = p2.loc.x - x;
    if (dx > range)  return;

    final float dy = abs(p2.loc.y - y);
    if (dy < range && dx*dx + dy*dy < rangeSq) {
      p1.drawLine(p2);
      ++dotConnects;
    }
  }
}

class Point implements Comparable<Point> {
  final PVector loc = new PVector(), dir = new PVector();

  Point() {
    respawn();
  }

  void respawn() {
    PVector.random2D(dir).mult(random(.5, DOT_MAX_SPD));
    loc.set(random(width), random(height));
  }

  void update() {
    loc.add(dir);
    if (isOffScreen())  respawn();
  }

  boolean isOffScreen() {
    return loc.x < 0 | loc.x > width | loc.y < 0 | loc.y > height;
  }

  void drawPoint() {
    point(loc.x, loc.y);
  }

  void drawLine(Point other) {
    line(loc.x, loc.y, other.loc.x, other.loc.y);
  }

  @ Override int compareTo(Point other) {
    return (int) Math.signum(loc.x - other.loc.x);
  }
}

GoToLoop · October 2015

The crucial point is inside nearestNeighbors() function, which actually acts an inner loop for the outer loop within draw():

for (int j = i; j != NUM_DOTS; ) {
  final Point p2 = dots[j++];

  final float dx = p2.loc.x - x;
  if (dx > range)  return;

  // ...

When it detects @ if (dx > range) return; that the x distance between 2 Point objects are outside range, it abruptly quits the whole function, since there's no point going on if they're far away to each other already! *-:)

In your case, you'd check against mouseX range.
If it's outside, quit the whole thing prematurely. :P

quark · October 2015

@GoToLoop although your solution is interesting it is still of the same order as a brute force approach i.e. N^2

For large N a quadtree or space-partitioning would give better performance.

For a generic what-is-in-the-neighbourhood type situation I believe the best approach would be to use space partitioning. The AI_CityPatrol example in my AI library would not run if it didn't use space-partitioning and attempted to use a N^2 algorithm.

KevinWorkman · October 2015

@GoToLoop: Please post a profiling of your "approach" compared to other approaches. I'm going to be very skeptical until I see real numbers. How is your approach better than simply using a square hitbox to test which circles should be then checked based on distance?

KevinWorkman · October 2015

I found a simple quadtree implementation here: http://www.java-gaming.org/index.php?action=pastebin&hex=4af3b227b3d1a

And I mixed it with the CircleCollision example sketch that comes with the Processing IDE (go to File > Examples > Topics > Motion > CircleCollision).

I created a sketch that consisted of 800 circles that all bounce off each other. If I use the brute force approach, I get 40 FPS. If I use a quadtree, I get 55 FPS.

Note that I have done absolutely no optimizations for either approach. This was just a quick proof that using a quadtree can save you time, even if you're rebuilding it every frame. This is because you're avoiding checking every other circle for each circle! You're doing N amount of work (technically nlgn) to build the tree so you can avoid doing N^2 amount of work.

Think about it this way: with the brute force approach, I have to loop through my N circles and then, for each of those circles, I have to loop through the N circles again. But with the quadtree approach, I build my quadtree before any looping. This is NlgN amount of work (inserting into the quadtree takes lgN time, and I have to do it N times). Then I still have to loop through my N circles, but now I only have to loop over the circles that might be near each of those N circles! Now my loop is only N*x, where x is the number of close neighbors. NlgN + N*x is less than N^2 when your N is large, which is why a quadtree saves you time.

This code is just thrown together, but if you feel like playing with it, here it is:

ArrayList<Ball> balls = new ArrayList<Ball>();
ArrayList<Ball> near = new ArrayList<Ball>();

void setup() {
  size(1000, 500);

  ellipseMode(RADIUS);

  for (float x = 10; x < 1000; x+= 25) {
    for (float y = 10; y < 500; y+=25) {
      balls.add(new Ball(x, y, 5));
    }
  }

  println(balls.size());
}

void draw() {
  background(0);

  QuadTree<Ball> qt = new QuadTree<Ball>(new Rectangle(0, 0, 1000, 500));
  for (Ball b : balls) {
    qt.insert(b);
  }

  for (Ball b : balls) {

    near.clear();

    qt.query(new Rectangle(b.position.x-b.r, b.position.y-b.r, b.r*2, b.r*2), near);

    for (Ball neighbor : near) {
      if (b != neighbor) {
        b.checkCollision(neighbor);
      }
    }
    b.checkBoundaryCollision();
    b.update();
    b.display();
  }

  textSize(18);
  text(frameRate, 25, 100);
}

class Ball implements Boundable {
  PVector position;
  PVector velocity;

  float r, m;

  Ball(float x, float y, float r_) {
    position = new PVector(x, y);
    velocity = PVector.random2D();
    //velocity.mult(3);
    r = r_;
    m = r*.1;
  }

  public Rectangle getBounds() {
    return new Rectangle(position.x-r, position.y-r, r*2, r*2);
  }

  void update() {
    position.add(velocity);
  }

  void checkBoundaryCollision() {
    if (position.x > width-r) {
      position.x = width-r;
      velocity.x *= -1;
    } else if (position.x < r) {
      position.x = r;
      velocity.x *= -1;
    } else if (position.y > height-r) {
      position.y = height-r;
      velocity.y *= -1;
    } else if (position.y < r) {
      position.y = r;
      velocity.y *= -1;
    }
  }

  void checkCollision(Ball other) {

    // get distances between the balls components
    PVector bVect = PVector.sub(other.position, position);

    // calculate magnitude of the vector separating the balls
    float bVectMag = bVect.mag();

    if (bVectMag < r + other.r) {
      // get angle of bVect
      float theta  = bVect.heading();
      // precalculate trig values
      float sine = sin(theta);
      float cosine = cos(theta);

      /** bTemp will hold rotated ball positions. You 
       just need to worry about bTemp[1] position*/
      PVector[] bTemp = {
        new PVector(), new PVector()
      };

      /** this ball's position is relative to the other
       so you can use the vector between them (bVect) as the 
       reference point in the rotation expressions.
       bTemp[0].position.x and bTemp[0].position.y will initialize
       automatically to 0.0, which is what you want
       since b[1] will rotate around b[0] */
      bTemp[1].x  = cosine * bVect.x + sine * bVect.y;
      bTemp[1].y  = cosine * bVect.y - sine * bVect.x;

      // rotate Temporary velocities
      PVector[] vTemp = {
        new PVector(), new PVector()
      };

      vTemp[0].x  = cosine * velocity.x + sine * velocity.y;
      vTemp[0].y  = cosine * velocity.y - sine * velocity.x;
      vTemp[1].x  = cosine * other.velocity.x + sine * other.velocity.y;
      vTemp[1].y  = cosine * other.velocity.y - sine * other.velocity.x;

      /** Now that velocities are rotated, you can use 1D
       conservation of momentum equations to calculate 
       the final velocity along the x-axis. */
      PVector[] vFinal = {  
        new PVector(), new PVector()
      };

      // final rotated velocity for b[0]
      vFinal[0].x = ((m - other.m) * vTemp[0].x + 2 * other.m * vTemp[1].x) / (m + other.m);
      vFinal[0].y = vTemp[0].y;

      // final rotated velocity for b[0]
      vFinal[1].x = ((other.m - m) * vTemp[1].x + 2 * m * vTemp[0].x) / (m + other.m);
      vFinal[1].y = vTemp[1].y;

      // hack to avoid clumping
      bTemp[0].x += vFinal[0].x;
      bTemp[1].x += vFinal[1].x;

      /** Rotate ball positions and velocities back
       Reverse signs in trig expressions to rotate 
       in the opposite direction */
      // rotate balls
      PVector[] bFinal = { 
        new PVector(), new PVector()
      };

      bFinal[0].x = cosine * bTemp[0].x - sine * bTemp[0].y;
      bFinal[0].y = cosine * bTemp[0].y + sine * bTemp[0].x;
      bFinal[1].x = cosine * bTemp[1].x - sine * bTemp[1].y;
      bFinal[1].y = cosine * bTemp[1].y + sine * bTemp[1].x;

      // update balls to screen position
      other.position.x = position.x + bFinal[1].x;
      other.position.y = position.y + bFinal[1].y;

      position.add(bFinal[0]);

      // update velocities
      velocity.x = cosine * vFinal[0].x - sine * vFinal[0].y;
      velocity.y = cosine * vFinal[0].y + sine * vFinal[0].x;
      other.velocity.x = cosine * vFinal[1].x - sine * vFinal[1].y;
      other.velocity.y = cosine * vFinal[1].y + sine * vFinal[1].x;
    }
  }


  void display() {
    fill(255);
    ellipse(position.x, position.y, r, r);
  }
}


public class Rectangle {
  public float x;
  public float y;
  public float width;
  public float height;

  public Rectangle() {
  }

  public Rectangle(float x, float y, float width, float height) {
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;
  }

  public String toString() {
    return x + ", " + y + " : " + width + " x " + height;
  }
}

public abstract interface Boundable {
  Rectangle getBounds();
}

public class QuadTree<T extends Boundable> {

  private static final int MAX_OBJECTS_PER_NODE = 500;

  // Constants for the quadrants of the quadtree
  private static final int PXNY = 0;
  private static final int NXNY = 1;
  private static final int NXPY = 2;
  private static final int PXPY = 3;

  private Rectangle bounds;
  private ArrayList<T> objects;
  private QuadTree<T>[] children;

  public QuadTree(Rectangle b) {
    bounds = b;
  }

  private void split() {
    float hw = bounds.width / 2.0f;
    float hh = bounds.height / 2.0f;
    float x = bounds.x;
    float y = bounds.y;
    children = new QuadTree[4];
    children[NXNY] = new QuadTree<T>(new Rectangle(x, y, hw, hh));
    children[PXNY] = new QuadTree<T>(new Rectangle(x + hw, y, hw, hh));
    children[NXPY] = new QuadTree<T>(new Rectangle(x, y + hh, hw, hh));
    children[PXPY] = new QuadTree<T>(new Rectangle(x + hw, y + hh, hw, hh));
  }

  private boolean insertIntoChild(T o) {
    Rectangle r = o.getBounds();
    float xm = bounds.x + bounds.width / 2.0f;
    float ym = bounds.y + bounds.height / 2.0f;
    boolean inserted = false;
    if (r.x >= xm && r.x + r.width < bounds.x + bounds.width) {
      if (r.y >= ym && r.y + r.height < bounds.y + bounds.height) {
        inserted = children[PXPY].insert(o);
      } else if (r.y >= bounds.x && r.y + r.height < ym) {
        inserted = children[PXNY].insert(o);
      }
    } else if (r.x >= bounds.x && r.x + r.width < xm) {
      if (r.y >= ym && r.y + r.height < bounds.y + bounds.height) {
        inserted = children[NXPY].insert(o);
      } else if (r.y >= bounds.x && r.y + r.height < ym) {
        inserted = children[NXNY].insert(o);
      }
    }
    return inserted;
  }

  /**
   * @return <code>true</code> if the given object could be inserted anywhere; or <code>false</code> if not
   */
  public boolean insert(T object) {
    if (children != null && insertIntoChild(object))
      return true;
    if (objects != null && objects.size() == MAX_OBJECTS_PER_NODE) {
      // too many objects in this quadtree level
      if (children == null) {
        // split this quadtree once
        split();
        // and try to redistribute the objects into the children
        for (int i = 0; i < objects.size(); i++) {
          if (insertIntoChild(objects.get(i))) {
            // succeeded with that one -> it fitted within a child!
            objects.remove(i);
            i--;
          }
        }
      }
      if (!insertIntoChild(object)) {
        // cannot distribute the object to any child
        if (objects.size() == MAX_OBJECTS_PER_NODE) {
          // and we are still full!
          // -> cannot insert
          return false;
        } else {
          objects.add(object);
        }
      }
    } else {
      if (objects == null)
        objects = new ArrayList<T>();
      objects.add(object);
    }
    return true;
  }

  public void query(Rectangle r, ArrayList<T> res) {
    if (children != null) {
      // query children
      float xm = bounds.x + bounds.width / 2.0f;
      float ym = bounds.y + bounds.height / 2.0f;
      if (r.y < ym && r.y + r.height >= bounds.y) {
        if (r.x < bounds.x + bounds.width && r.x + r.width >= xm)
          children[PXNY].query(r, res);
        if (r.x < xm && r.x + r.width >= bounds.x)
          children[NXNY].query(r, res);
      }
      if (r.y < bounds.y + bounds.height && r.y + r.height >= ym) {
        if (r.x < xm && r.x + r.width >= bounds.x)
          children[NXPY].query(r, res);
        if (r.x < bounds.x + bounds.width && r.x + r.width >= xm)
          children[PXPY].query(r, res);
      }
    }
    // query objects in this level
    for (int i = 0; objects != null && i < objects.size(); i++) {
      T o = objects.get(i);
      Rectangle bounds = o.getBounds();
      if (r.x < bounds.x + bounds.width && r.x + r.width >= bounds.x && r.y < bounds.y + bounds.height
        && r.y + r.height >= bounds.y)
        res.add(o);
    }
  }
}

Howdy, Stranger!

Categories

In this Discussion

How to limit calculations to just a subset of the total objects on screen.

Best Answers

Answers