Some experimentation.
I created world with bodies with two fixtures each, solid (sensor = false) = circle with r=1, and sensor = circle with r=1 or 40 (small and large).
Randomly placed them in square 100 high and wide (so there will be a lot of overlaping of solid-sensor and even more of sensor-sensor) and give them random velocity (random direction and absVelocity random up to 5)
Then I called update few times (if body got out of the box, I "teleported" it to other side) and timed how long it took.
Tried it with both small and large sensors and with and without collision listener filtering out sensor-sensor collisions.
To make sure that movement was same, I computed hash of positions of all bodies. (btw, Vector2 implements its own equals, but not hashCode (it is not strictly in violiation of equals/hash code contract, because it overloads equals, so it is different equals, but it is confusing).
Another experiment - staticQuery: similar setup, but more bodies and no moving, only static detect queries.
results:
moving experiment: (100 bodies)
small sensor - much faster, around 20 ms, large sensor 1270 ms (with skiping via listener) and 1470 ms (without).
step size was 1/60 s and number of steps 100, so total represented time is 1666 ms.
1470 ms of 1666 spent in movement alone does not leave much room for AI/graphics, so I call this problem. Because I'm interested in sensor-solid collisions (for AI) comparing it with 20ms of small sensor case is not fair, but I hope that there is some room for improvement. If not, I will have to rethink my design.
static query experiment: (500 bodies, 1000 random positions queried)
small sensor - 1.5 ms
large sensor - 144 ms (using detectNoSensor from previous post) and 231 ms (detect) and the detect case would need some more time to remove sensor only collisions from result, which I forgot to do.
Code: Select all
package mygame.experimets;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import org.dyn4j.collision.narrowphase.NarrowphaseDetector;
import org.dyn4j.collision.narrowphase.Penetration;
import org.dyn4j.dynamics.Body;
import org.dyn4j.dynamics.BodyFixture;
import org.dyn4j.dynamics.CollisionAdapter;
import org.dyn4j.dynamics.World;
import org.dyn4j.geometry.AABB;
import org.dyn4j.geometry.Circle;
import org.dyn4j.geometry.Convex;
import org.dyn4j.geometry.Transform;
import org.dyn4j.geometry.Vector2;
/**
*
* @author Martin
*/
public class BPExperiment {
public static final int LARGE_SENSOR = 40;
public static final int SMALL_SENSOR = 1;
public static void largeSensor(boolean skipSensorSensor) {
System.out.println("large skip = " + skipSensorSensor);
experimentMovement(LARGE_SENSOR, skipSensorSensor);
}
public static void smallSensor(boolean skipSensorSensor) {
System.out.println("small skip = " + skipSensorSensor);
experimentMovement(SMALL_SENSOR, skipSensorSensor);
}
public static void staticLargeSensor() {
System.out.println("staticLarge");
experimentStatic(LARGE_SENSOR, true);
experimentStatic(LARGE_SENSOR, false);
}
public static void staticSmallSensor() {
System.out.println("staticSmall");
experimentStatic(SMALL_SENSOR, true);
experimentStatic(SMALL_SENSOR, false);
}
public static void experimentMovement(int sensorSize, boolean skipSensorSensor) {
for (int k = 0; k < 5; k++) {
for (int j = 0; j < 10; j++) {
World w = new World();
if (skipSensorSensor) {
w.addListener(new SkipSensorSensorListener());
}
Tester t = new Tester(w, new Random(0), 100, 100, 1.0 / 60.0, true);
t.populate(100, 1, sensorSize, 5);
long start = System.nanoTime();
for (int i = 0; i < 100; i++) {
t.step();
}
long stop = System.nanoTime();
long time = stop - start;
if (k > 3) {
if (j == 0) {
System.out.println("");
}
System.out.println("time = " + time / 1000000.0 + " ms" + ", worldTime = " + t.worldTime * 1000 + " ms, positionHash = " + t.positionHash());
}
}
if (k < 4) {
System.out.print(" k = " + k);
}
}
}
public static void experimentStatic(int sensorSize, boolean noSensor) {
for (int k = 0; k < 5; k++) {
boolean print = k > 3;
for (int j = 0; j < 10; j++) {
Random r = new Random(0);
Tester t = new Tester(new World(), r, 100, 100, 1.0 / 60.0, true);
t.populate(500, 1, sensorSize, 5);
int hits = 0;
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
Transform tr = new Transform();
tr.setTranslation(t.randomPosition());
if (noSensor) {
hits += detectNoSensor(new Circle(1), tr, t.w).size();
} else {
hits += detect(new Circle(1), tr, t.w).size();
}
}
long stop = System.nanoTime();
long time = stop - start;
if (print) {
System.out.print("time = " + time / 1000000.0 + " ms");
System.out.print(" noSensor = " + noSensor);
System.out.print(" sensorSize = " + sensorSize);
System.out.print(" hits = " + hits);
System.out.println("");
}
}
}
System.out.println("");
}
public static List<Body> detect(Convex convex, Transform transform, World w) {
return w.detect(convex, transform);
}
public static List<Body> detectNoSensor(Convex convex, Transform transform, World w) {
// create an aabb for the given convex
AABB aabb = convex.createAABB(transform);
// test using the broadphase to rule out as many bodies as we can
List<Body> bodies = w.getBroadphaseDetector().detect(aabb);
// now perform a more accurate test
Iterator<Body> bi = bodies.iterator();
while (bi.hasNext()) {
Body body = bi.next();
// get the body transform
Transform bt = body.getTransform();
// test all the fixtures
int fSize = body.getFixtureCount();
boolean collision = false;
for (int i = 0; i < fSize; i++) {
BodyFixture bf = body.getFixture(i);
if (bf.isSensor()) {
continue;
}
Convex bc = bf.getShape();
final NarrowphaseDetector npd = w.getNarrowphaseDetector();
// just perform a boolean test since its typically faster
if (npd.detect(convex, transform, bc, bt)) {
// if we found a fixture on the body that is in collision
// with the given convex, we can skip the rest of the fixtures
// and continue testing other bodies
collision = true;
break;
}
}
// if we went through all the fixtures of the
// body and we didn't find one that collided with
// the given convex, then remove it from the list
if (!collision) {
bi.remove();
}
}
// return the bodies in collision
return bodies;
}
public static class Tester {
World w;
Random r;
double width;
double height;
double stepLength; //s
boolean boundaryTepleport;
double worldTime = 0;
public Tester(World w, Random r, double width, double height, double stepLength, boolean boundaryTepleport) {
this.w = w;
this.r = r;
this.width = width;
this.height = height;
this.stepLength = stepLength;
this.boundaryTepleport = boundaryTepleport;
}
public void populate(int bodies, double nonSensorRadius, double sensorRadius, double absVelocity) {
for (int i = 0; i < bodies; i++) {
Body b = new Body();
BodyFixture solid = new BodyFixture(new Circle(nonSensorRadius));
solid.setSensor(false);
b.addFixture(solid);
b.setMass();
BodyFixture sensor = new BodyFixture(new Circle(sensorRadius));
sensor.setSensor(true);
b.addFixture(sensor);
b.getTransform().setTranslationX(r.nextDouble() * width);
b.getTransform().setTranslationY(r.nextDouble() * height);
Vector2 vel = new Vector2(absVelocity);
vel.setDirection(r.nextDouble() * Math.PI * 2 - Math.PI);
b.setLinearVelocity(vel);
b.setLinearDamping(0);
w.addBody(b);
}
}
public Vector2 randomPosition() {
return new Vector2(r.nextDouble() * width, r.nextDouble() * height);
}
public void step() {
worldTime += stepLength;
w.update(stepLength);
if (boundaryTepleport) {
for (Body b : w.getBodies()) {
Vector2 t = b.getTransform().getTranslation();
if (t.x < 0) {
t.x = width;
}
if (t.x > width) {
t.x = 0;
}
if (t.y < 0) {
t.y = height;
}
if (t.y > height) {
t.y = 0;
}
}
}
}
private int v2Hash(Vector2 v) {
int hash = 7;
hash = 29 * hash + (int) (Double.doubleToLongBits(v.x) ^ (Double.doubleToLongBits(v.x) >>> 32));
hash = 29 * hash + (int) (Double.doubleToLongBits(v.y) ^ (Double.doubleToLongBits(v.y) >>> 32));
return hash;
}
public int positionHash() {
int result = 7;
for (Body b : w.getBodies()) {
Vector2 tr = b.getTransform().getTranslation();
result = 29 * result + v2Hash(tr);
}
return result;
}
}
public static void main(String[] args) {
smallSensor(true);
smallSensor(false);
largeSensor(true);
largeSensor(false);
staticSmallSensor();
staticLargeSensor();
System.out.println("END");
}
private static class SkipSensorSensorListener extends CollisionAdapter {
@Override
public boolean collision(Body body1, BodyFixture fixture1, Body body2, BodyFixture fixture2, Penetration penetration) {
return !(fixture1.isSensor() && fixture2.isSensor());
}
}
}
results:
small skip = true
k = 0 k = 1 k = 2 k = 3
time = 20.181225 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.443241 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.059273 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.283254 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.146511 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.086743 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.557344 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.028785 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.014598 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.080102 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
small skip = false
k = 0 k = 1 k = 2 k = 3
time = 20.133531 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.039954 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.592059 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.300159 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.132022 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.244617 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.355701 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.16402 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.005844 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 20.516895 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
large skip = true
k = 0 k = 1 k = 2 k = 3
time = 1274.25469 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1270.362493 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1284.454275 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1284.153017 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1270.846075 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1269.971885 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1274.808605 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1273.029738 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1272.565476 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1270.987647 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
large skip = false
k = 0 k = 1 k = 2 k = 3
time = 1476.92121 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1496.742315 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1482.699737 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1479.167661 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1483.570606 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1487.261462 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1476.633235 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1477.331137 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1477.258087 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
time = 1473.347477 ms, worldTime = 1666.6666666666656 ms, positionHash = -470516429
staticSmall
time = 1.633371 ms noSensor = true sensorSize = 1 hits = 583
time = 1.636691 ms noSensor = true sensorSize = 1 hits = 583
time = 1.553679 ms noSensor = true sensorSize = 1 hits = 583
time = 1.670499 ms noSensor = true sensorSize = 1 hits = 583
time = 1.489987 ms noSensor = true sensorSize = 1 hits = 583
time = 1.569979 ms noSensor = true sensorSize = 1 hits = 583
time = 1.548548 ms noSensor = true sensorSize = 1 hits = 583
time = 1.541604 ms noSensor = true sensorSize = 1 hits = 583
time = 1.592921 ms noSensor = true sensorSize = 1 hits = 583
time = 1.537077 ms noSensor = true sensorSize = 1 hits = 583
time = 1.559716 ms noSensor = false sensorSize = 1 hits = 583
time = 1.572999 ms noSensor = false sensorSize = 1 hits = 583
time = 1.585676 ms noSensor = false sensorSize = 1 hits = 583
time = 1.610429 ms noSensor = false sensorSize = 1 hits = 583
time = 1.633068 ms noSensor = false sensorSize = 1 hits = 583
time = 1.640615 ms noSensor = false sensorSize = 1 hits = 583
time = 1.618881 ms noSensor = false sensorSize = 1 hits = 583
time = 1.603788 ms noSensor = false sensorSize = 1 hits = 583
time = 1.63005 ms noSensor = false sensorSize = 1 hits = 583
time = 1.620088 ms noSensor = false sensorSize = 1 hits = 583
staticLarge
time = 144.46589 ms noSensor = true sensorSize = 40 hits = 583
time = 143.065557 ms noSensor = true sensorSize = 40 hits = 583
time = 144.143804 ms noSensor = true sensorSize = 40 hits = 583
time = 144.257908 ms noSensor = true sensorSize = 40 hits = 583
time = 143.177848 ms noSensor = true sensorSize = 40 hits = 583
time = 144.008872 ms noSensor = true sensorSize = 40 hits = 583
time = 145.158058 ms noSensor = true sensorSize = 40 hits = 583
time = 145.190961 ms noSensor = true sensorSize = 40 hits = 583
time = 145.195489 ms noSensor = true sensorSize = 40 hits = 583
time = 144.422422 ms noSensor = true sensorSize = 40 hits = 583
time = 231.158887 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.526252 ms noSensor = false sensorSize = 40 hits = 180065
time = 233.357945 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.899654 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.256689 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.498179 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.378038 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.299856 ms noSensor = false sensorSize = 40 hits = 180065
time = 230.98411 ms noSensor = false sensorSize = 40 hits = 180065
time = 231.068932 ms noSensor = false sensorSize = 40 hits = 180065
END