Enhancement: allow static query ignore sensor fixtures

Posts regarding potential bugs, enhancement requests, and general feedback on use of dyn4j
Forum rules
Post Reply
alpedar
Posts: 7
Joined: Sat Jan 25, 2014 11:08 am

Enhancement: allow static query ignore sensor fixtures

Postby alpedar » Sat Jan 25, 2014 11:44 am

I needed to check whether location is free before spawning new unit, so I tried to use detect(Convex) (or detect(Convex, Transform)), but because my units have sensor fixtures, I got collision with them. I could have iterate through returned list and check whether its nonsensor collision, but it seems repeating work that was needlessly done.
So I looked in detect source code and copied it into new method where I needed it and added checking whether fixture is sensor there. So for my purposes all is good, but I think it would be better if it was in library, not in user code.

Maybe even allowing to pass some predicate on fixtures, to allow even more custom filtering could be usefull, but it could be both overkill and not flexible enough, so maybe go full lister style. But maybe it is too special purpose and it belogs in user code. But considering that sensor flag is already there, allowing filtering by it is imo appropriate.

btw, what I don't like about what I did is, that there will be a lot of collisions from broadphaseDetector that are only sensor collisions. Is there way how to not include them? Maybe some way how to tweek broad phase detector to work with nonsesor fixtures only?

For those needing it, here is my method

Code: Select all

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);
// this is what i added
                if (bf.isSensor()) {
                    continue;
                }
//
                Convex bc = bf.getShape();
                // just perform a boolean test since its typically faster
                if (w.getNarrowphaseDetector().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;
    }
Top
William
Site Admin
Posts: 377
Joined: Sat Feb 06, 2010 10:23 pm

Re: Enhancement: allow static query ignore sensor fixtures

Postby William » Wed Jan 29, 2014 5:22 pm

I can add another method which could accept more parameters, maybe a boolean to check against sensors, and maybe a Filter object to test against the fixture's filters. I'll give some thought to what the parameters should be.

As for modifying the broadphase, I wouldn't worry about skipping sensors in the broadphase unless you are seeing a big performance hit. Right now the broadphase doesn't evaluate on the fixture level, but rather on the body level, so this would require a redesign of the broadphase (and the classes using it).

William
Top
zoom
Posts: 144
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:
Contact zoom

Re: Enhancement: allow static query ignore sensor fixtures

Postby zoom » Thu Jan 30, 2014 8:19 am

I currently have no sensors in my "world" but was planning to introduce them and would probalby have run into this :-) Such a flag/filter would be great to have. I currently just test for "free space" using

Code: Select all

final AABB translatedAABB = aabb.getTranslated(translation);
final List<Body> detect = world.detect(translatedAABB);
return ((detect == null) || (detect.size() < 1));
Top
alpedar
Posts: 7
Joined: Sat Jan 25, 2014 11:08 am

Re: Enhancement: allow static query ignore sensor fixtures

Postby alpedar » Fri Jan 31, 2014 2:29 pm

William wrote:I can add another method which could accept more parameters, maybe a boolean to check against sensors, and maybe a Filter object to test against the fixture's filters. I'll give some thought to what the parameters should be.

As for modifying the broadphase, I wouldn't worry about skipping sensors in the broadphase unless you are seeing a big performance hit. Right now the broadphase doesn't evaluate on the fixture level, but rather on the body level, so this would require a redesign of the broadphase (and the classes using it).

William

So far I'm not far enough to have any performance problems, so that part about broad phase is purely theoretical. So far it only seems that lot of bodies in my game will have large sensor fixtures and small actual nonsesor fixture, and lot of them will be close enough to intersect with multiple sensors, but far away to not intersect AABB's of their nonsesnsor parts.

But I made experiment where I randomly added bodies with sensor and and nonsensor (I'll call it solid) fixtures and let them move in ranom direction for some time (ammount of iterarations).
When performance was much worse when sensor was large then when it was small. But this is not exactly fair, because although I'm (and I guess most of others too) are not interested in sensor sensor collision, these experimets differed in more than that. With small sensor there was much less sensor-solid collisions and they are definitely important.

I will experiment with static queries where I controll one side of collision, that will be much more fair comparision, even though less important than performance wise.
Top
alpedar
Posts: 7
Joined: Sat Jan 25, 2014 11:08 am

Re: Enhancement: allow static query ignore sensor fixtures

Postby alpedar » Sat Feb 01, 2014 7:58 am

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
Top
William
Site Admin
Posts: 377
Joined: Sat Feb 06, 2010 10:23 pm

Re: Enhancement: allow static query ignore sensor fixtures

Postby William » Sat Feb 01, 2014 12:41 pm

I think I'm a little confused here. There are a few instances where the broadphase is being used:

  1. Normal collision detection done by the engine.
  2. Static collision detection done by a call to a World.detect(...) method.
  3. Static raycast/convex cast detection done by a call to the respective World class methods.

In the first case, what you are talking about cannot be done. Sensor fixtures should be used when you want to know when two fixtures are overlapping. This, by definition, requires them to be detectable by both the broadphase and the narrowphase and excluding them would defeat the purpose. In short, you can't know if something is overlapping if you don't test it.

Now when it comes to the static collision tests, I definitely understand why you might want to filter them out. I'm planning on adding methods that will allow that, but the broadphase will not be changed. Broadphase algorithms are used to filter the O(n<sup>2</sup>) collision tests and do so by using the spacial data of the objects. To achieve what you are talking about would require two broadphase instances (or two runs of the same instance), one that includes sensor fixtures and one that doesn't. In summary, the inclusion/exclusion of the sensor fixtures changes the spacial data, so as a result, you either need two collision detectors, or one that just runs twice.

You can do what I describe above by doing something like the following:
  • Create a subclass of one of the broadphase classes and store an instance of it somewhere.
    • Override the add and update methods to call a custom method that returns an AABB that does not include sensor fixtures (rather than the Collidable.createAABB() method). All the other code in the methods should remain the same.
  • Create a new class that implements the StepListener interface, specifically the end(...) method.
    • Inside this method, call the update method on your custom broadphase for every body in the world.
  • Whenever you add or remove a body from the World, call the add/remove methods of your custom broadphase.
  • Create your own detect method that uses your custom broadphase.

This is not something that should be included in the library in my opinion. I'd like to know the reason for having very large sensor fixtures. To me, this sounds like you are trying to use them for a purpose they were not designed for. Can you elaborate a little more on why you are using large sensor fixtures?

William
Top
alpedar
Posts: 7
Joined: Sat Jan 25, 2014 11:08 am

Re: Enhancement: allow static query ignore sensor fixtures

Postby alpedar » Sat Feb 01, 2014 6:26 pm

1)
After some reading of BroadPhase detector source I think that it is not possible for some implementations (they treat all collidables equally, there is not currently tested and node and others).
I think that DynamicAABBTree maybe could be modified to do what i had in mind.

Code: Select all

      // test each collidable in the list
      for (int i = 0; i < size; i++) {
         // get the current collidable to test
         Node node = this.proxyList.get(i);
         // perform a stackless detection routine
         detectNonRecursive(node, this.root, pairs);
         // update the tested flag
         node.tested = true;
      }

tests each Node against all others (via tree, so its not O(n^2)), and marks it as tested to prevent detecting collisions twice.
inside detectNonRecursive

Code: Select all

   protected void detectNonRecursive(final Node node, Node root, List<BroadphasePair<E>> pairs) {
      // start at the root node
      Node n = root;
      // perform a iterative, stack-less, traversal of the tree
      while (n != null) {
         // check if the current node overlaps the desired node
         if (n.aabb.overlaps(node.aabb)) {
...

Imagine that it instead of testing "full" aabb of node (represening Collidable) vs aabb of node from tree (that itself was created from full aabbs) tested only nonsensor aabb vs full aabb and did not skip already tested nodes.
This would lead to sensor-solid collisions beaing detected once, but solid-solid colisions twice. But to do that, node would need to have both aabbs, so it would be possible to detect whether it is solid solid collision and then add pair only when the other is not tested.

2) why I need it.
My idea is, that every unit in my game will have nonsensor fixtures representing its shape and sensor fixtures (like sight - big one, so far its circle, but I'm thinking about other shapes, some narrow rectanngular "whiskers" etc.).
In CollisionListener I will store information that something is colliding with specific sensor and store it for AI/rules to use. What I liked about this idea is, that I will not have to manually loop through all units and their sensors.
I thought that by doing it this way, it would be more declarative and more efficient.
When I formulated it, I realized that I don't need to do that this way, I can do what I did try to avoid and use static queries. And maybe use raycasting casting instead of some of sensor fixtures.
Top
William
Site Admin
Posts: 377
Joined: Sat Feb 06, 2010 10:23 pm

Re: Enhancement: allow static query ignore sensor fixtures

Postby William » Sat Feb 01, 2014 9:32 pm

Imagine that it instead of testing "full" aabb of node (represening Collidable) vs aabb of node from tree (that itself was created from full aabbs) tested only nonsensor aabb vs full aabb and did not skip already tested nodes.

This is the key: One of the tests will be invalid because the AABBs have changed.

Take this simple example: You create the following binary tree:

300px-Binary_tree.svg.png
Simple Binary Tree
300px-Binary_tree.svg.png (9.14 KiB) Viewed 4911 times

You are saying that if we change the number 5 to 10, without modifying where it is in the binary tree, that the binary tree will continue to function properly. I'm sure you can see how this cannot be the case. The same goes for the broadphase, you cannot change the values of the AABBs, without updating the broadphase, and expect it function properly.

The broadphase is an data structure used to avoid O(n^2) collision tests, just like a binary tree is used to improve the speed of a search. To do so it requires knowledge of the spacial state of the objects, just like the numbers in the binary tree example above. If this spacial state is changed in any way, whether by moving the objects or by turning on or off fixtures, the data structure must be rebuilt or updated to continue functioning properly (like when the number 5 was changed to 10, the binary tree must be updated to reflect the change).

I hope that makes it a little clearer.

If you are wanting to do vision testing, raycasting was made for you. Here is a good article about it: http://www.redblobgames.com/articles/visibility/. Afterwards you could clip the area further by an arbitrary shape to get what you are looking for.

William
Top
alpedar
Posts: 7
Joined: Sat Jan 25, 2014 11:08 am

Re: Enhancement: allow static query ignore sensor fixtures

Postby alpedar » Sun Feb 02, 2014 5:17 am

Thnaks. Interesting article, looks like I have lot to learn.
Top
zoom
Posts: 144
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:
Contact zoom

Re: Enhancement: allow static query ignore sensor fixtures

Postby zoom » Sun Feb 02, 2014 8:08 am

The "ray cast to corners to find what is visible" is exactly what I am doing for drawing lights using this library: https://code.google.com/p/straightedge/
That library also has a nice implementation of nav-mesh and A* path finding that I use.

I think that for AI it is probably better to implement some spatial division that fits with the use case you have. For example, in my game I divide the world in "tiles" that are 64x64 world units. I page them in and out when needed. So the Dyn4j world is never bigger than 4 such tiles, which means that I don't have hundreds of dynamic objects active all the time, just the ones that are "close enough" to a player. That cuts down a lot on the number of tests that are needed.
For determining visibility I use ray casts, i.e. "can this monster see the player?" I ray cast from the monster to the player(s) and see if they are visible. I only do these tests once per second (or some other value). It is not possible or even "a good thing" to do these tests every frame. For game mechanics I don't need millisecond accuracy in "did the monster see the player", for sound I don't even ray cast, I just calculate the distance from the monster to the player(s) once every few seconds.

So yeah, I think using sensors for these kind of game mechanics aren't the best tool, you'll probably want to use other types of tests, whatever works for your use case.

I was planning on using sensors for things like "if something is close to the door, open the door" type of things but so far I haven't tried so I don't know if they fit that use case.
Top
Post Reply

Return to “Bugs, Enhancements, Feedback”

Who is online

Users browsing this forum: No registered users and 7 guests