Find nearest geometry in field of view

Troubleshooting General Help
1

Hello fellow monkeys,

I’m implementing automated turrets that will rotate and fire at anything in their specified field of fire.
The idea is as follows:

  • Each turret has a set of valid targets
  • Each turret has a maximum amount of degrees it can turn
  • If a target is in front of the turret, it fires
  • The turrets continuously look for that target within their field of fire for which they have to turn the least and rotate until they face it
  • If a turret is already turned to the left, targets to the left will be preferred over targets on the right
  • If the target the turret is currently firing on moves slower than the turret can rotate, it will remain the closest one, so the turret follows the target and keeps firing
  • If the target the turret is currently firing on runs away faster than the turret can rotate, the turret may pick another target that requires less rotation

Now to my problem: The targets are different meshes of different sizes (some of them very large) and the turrets should be able to hit them even when only pointing towards an edge of the mesh (whenever a ray cast in the turrets facing direction results in a collision with the target).
So how can my turrets find their preferred targets (the ones that require the least turning)? Using the dot product of the turrets facing and the vector to the targets’ worldTranslation doesn’t work, because the target’s center can be far away even if parts of the mesh are directly in front of the turret

I thought about going through all available targets (probably sorting them by the degrees to their worldTranslation) and check the dot product to each of their vertices, but this somehow seems a bit heavy if I have many turrets looking at many targets.

Another idea I had was casting an array of rays, all point towards different angles and choosing the target that was hit by the ray with the smallest angle. But this seems quite dirty and the turrets will miss targets that are between the arrays.

Can anyone think of a better way?

2

Someone will probably come with better, but maybe have a collection of vectors (per targetable object) representing points of interests (translations from their origin) and have the turrets check those points and shoot at them? Could mark them in blender with a cube or something and when loading the model, remove the cubes and create the vectors from their position. Or add user data with their position in blender instead.

3

If you want something that performs well then I don’t think you are going to be able to get around some short cuts.

If it were me, I’d do an initial check against the last thing you targeted to see if it was still in range then I’d do kind of a broad phase against some representative spheres (using a variation on the dot product check). You can then tailor the size of these spheres to some theoretical hit target size to avoid ridiculous things like attacking a target just because you can hit its antenna or something.

If you want to know more about the modified dot product then let me know.

4

Yes, please. This sounds like something that could help.

5

Roughly, the dot product can be used to find the point in space that would be closes to the object’s bounding sphere.

Vector3f dir = ...
Vector3f relative = shipPos.subtract(turretPosition);
float distance = dir.dot(relative);
Vector3f projected = turretPosition.add(dir.mult(distance));

If the distance squared between projected and shipPos are less than the radius squared then you are in range to fire. Else you can use the actual distance between projected and shipPos (minus radius) to decide if you can turn fast enough… but you will have to divide by relative.length(). That gives you the sin of the angle you’d have to turn… which on its own should be good enough without ever converting to an actual angle.

float sinTurn = (projected.subtract(turretPos).length() - shipRadius) / relative.length();
if( sinTurn < sinMaxTurretTurnAngle ) {
    // turret can turn in time
}

Sort by projected.subtract(turretPos).length() - shipRadius I guess.

2 Likes
6

This is great, thanks.

I built a small test program, where everything is on the XZ plane (the camera is looking straight down):

001.png1296×758 74.4 KB

The red line is the direction the turret is facing, the red spheres represent the different ships’ radiuses.
The blue lines should be the maximum turn angle (which is 60° to either side).

But while it works pretty well near the red line (the 5.16° to the edge of the smallest sphere seem to be ok and it also successfully detects if the red line hits a sphere), the ship to the right returns an asin(sinTurn) of 44.26°, although it is outside the 60° range.

Here is my test case:

import com.jme3.app.SimpleApplication;
import com.jme3.font.BitmapText;
import com.jme3.material.Material;
import com.jme3.material.RenderState;
import com.jme3.math.ColorRGBA;
import com.jme3.math.FastMath;
import com.jme3.math.Quaternion;
import com.jme3.math.Vector3f;
import com.jme3.renderer.RenderManager;
import com.jme3.renderer.ViewPort;
import com.jme3.scene.Geometry;
import com.jme3.scene.Node;
import com.jme3.scene.control.AbstractControl;
import com.jme3.scene.control.BillboardControl;
import com.jme3.scene.shape.Line;
import com.jme3.scene.shape.Sphere;

public class TargetingShipsInFoV extends SimpleApplication {

    private float turretMaxTurnAngle = FastMath.DEG_TO_RAD * 60f;
    private Node turret;

    public static void main(String[] args) {
        TargetingShipsInFoV app = new TargetingShipsInFoV();
        app.start();
    }

    @Override
    public void simpleInitApp() {
        flyCam.setMoveSpeed(50);
        cam.setLocation(Vector3f.UNIT_Y.mult(75));
        cam.lookAt(Vector3f.ZERO, Vector3f.UNIT_Y);

        createTurret();
        createShips();
    }

    private void createTurret() {
        // Create geometries
        Geometry geoDir = new Geometry("geoDir",
                new Line(Vector3f.ZERO, Vector3f.UNIT_Z.mult(100)));
        Geometry geoBoundry1 = new Geometry("geoBoundry1",
                new Line(Vector3f.ZERO, new Quaternion().fromAngles(0, turretMaxTurnAngle, 0).mult(Vector3f.UNIT_Z.mult(100))));
        Geometry geoBoundry2 = new Geometry("geoBoundry2",
                new Line(Vector3f.ZERO, new Quaternion().fromAngles(0, -turretMaxTurnAngle, 0).mult(Vector3f.UNIT_Z.mult(100))));

        // Create materials
        geoDir.setMaterial(new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md"));
        geoBoundry1.setMaterial(new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md"));
        geoBoundry2.setMaterial(new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md"));
        geoDir.getMaterial().setColor("Color", ColorRGBA.Red);
        geoBoundry1.getMaterial().setColor("Color", ColorRGBA.Blue);
        geoBoundry2.getMaterial().setColor("Color", ColorRGBA.Blue);

        // Put everything in node
        turret = new Node("turret");
        turret.attachChild(geoDir);
        rootNode.attachChild(geoBoundry1);
        rootNode.attachChild(geoBoundry2);
        rootNode.attachChild(turret);

        // Set default orientation
        turret.lookAt(Vector3f.UNIT_Z, Vector3f.UNIT_Y);

        // Let the turret rotate to view calculation
        turret.addControl(new AbstractControl() {
            @Override
            protected void controlUpdate(float tpf) {
                spatial.rotate(0, tpf * 0.1f, 0);
            }

            @Override
            protected void controlRender(RenderManager rm, ViewPort vp) {
            }
        });
    }

    private void createShips() {
        int targets = 10;
        for (int i = 0; i < targets; i++) {
            Quaternion quat = new Quaternion().fromAngleAxis(FastMath.TWO_PI / (float) targets * (float) i, Vector3f.UNIT_Y);
            createShip(quat.mult(Vector3f.UNIT_Z.mult(10 * (float) Math.pow(1.15f, i))), i + 1);
        }
    }

    private void createShip(final Vector3f shipPos, final float shipRadius) {
        // Create sphere to show radius
        Geometry ship = new Geometry("ship", new Sphere(12, 24, shipRadius));
        ship.setMaterial(new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md"));
        ColorRGBA color = new ColorRGBA(ColorRGBA.Red);
        color.a = 0.2f;
        ship.getMaterial().setColor("Color", color);
        ship.getMaterial().getAdditionalRenderState().setBlendMode(RenderState.BlendMode.Alpha);
        ship.setLocalTranslation(shipPos);

        // Build text to show targeting status or angle
        BitmapText text = new BitmapText(guiFont, false);
        text.setSize(1.5f);
        text.setLocalTranslation(shipPos);
        text.addControl(new BillboardControl());

        // Add control to automatically update text
        text.addControl(new AbstractControl() {
            @Override
            protected void controlUpdate(float tpf) {
                Vector3f turretPos = turret.getWorldTranslation();
                Vector3f dir = turret.getWorldRotation().mult(Vector3f.UNIT_Z);

                Vector3f relative = shipPos.subtract(turretPos);
                float distance = dir.dot(relative);
                Vector3f projected = turretPos.add(dir.mult(distance));

                float distVec = projected.subtract(shipPos).length();
                float sinTurn = (projected.subtract(shipPos).length() - shipRadius) / relative.length();

                // also check for distance >= 0 to avoid targeting ships behind the turret
                if (distance >= 0 && sinTurn <= FastMath.sin(turretMaxTurnAngle)) {
                    if (distVec * distVec <= shipRadius * shipRadius) {
                        ((BitmapText) spatial).setText("can hit");
                    } else {
                        ((BitmapText) spatial).setText("angle=" + String.format("%4.2f", FastMath.RAD_TO_DEG * FastMath.asin(sinTurn)));
                    }
                } else {
                    ((BitmapText) spatial).setText("out of reach");
                }
            }

            @Override
            protected void controlRender(RenderManager rm, ViewPort vp) {
            }
        });

        // Attach both to rootNode
        rootNode.attachChild(ship);
        rootNode.attachChild(text);
    }
}

I don’t know what’s wrong with the code because I admittedly don’t understand all the math you put in that short paragraph… I would really appreciate if you could explain that in more detail

7

Not sure why it isn’t working… I figured out the sin can be a little off because I took a short cut but I don’t think that’s your issue.

I’ve tried to make a diagram that explains where the math comes from:

Hopefully the big giant right triangle is obvious… and thus it’s obvious that ‘dot’ is the cosine(theta) * hypotenuse and ship.subtract(projected).length() is the sine(theta) * hypotenuse

So in truth, the sinTurn I had you calculate isn’t wholly accurate because really it should be divided by the distance between the green T and the turret position. (Which isn’t hard to calculate) However, even if wrong, it should be close I think. I don’t believe it accounts for the error you are seeing but perhaps seeing the diagram may help you debug it.

Edit: occurs to me that I should leave this here just in case donuts are in order. :wink: https://www.patreon.com/pspeed42?ty=h

1 Like
8

Wow, this helps a lot. Thanks again.
And I think the inaccuracy you mentiond might very well the reason for the miscalculation. The ship where this happened has a large radius while being relatively near to the turret.
I will try to fix that in my code and see what happens.

What I still don’t understand about the calculation however is why you square both sides in this equation:

If the distance squared between projected and shipPos are less than the radius squared then you are in range to fire

Looking at the diagram it should be enough to check if |Ship Projected| < radius

PS: I will push some donuts along your way as soon as patreon stops showing me nothing but this:

patr.png767×405 44.1 KB

Edit: Haha, who would have thought: Where Firefox and Chrome failed, Internet Explorer finally let me use patreon. Now I can die and claim that I have seen everything :scream_cat:

9

it’s Pythagoras

10

This seems to be false, since you project the turret too much far. Since you seem to work In two dimension, maybe try this (imo more simple) approach :

  • compute angle of your turret’s direction vector
  • compute angle of your relative vector
  • compute the smalest difference between those two angles (exemple of implementation).

Then you just have to compare this angle with your max allowed rotation.

Hope it helps !

11

In the before time, the long long ago, computing square roots was 100x more expensive than a multiply… which itself was 20x more expensive than an add. So many of us have ‘avoid sqrt’ instincts.

length() = Math.sqrt(lengthSquared). The reason the ‘squared’ versions of the methods are provided is because they do not do the sqrt and in some cases (like when comparing distances) you don’t need it.

Thus, my statement about the squared versions is a way to rule out ships without performing sqrts.

12

? Too far? No, it calculates exactly the point where the ship’s sphere comes closest to the direction vector line… in 3D space.

Relative to what in 3D space? Not to mention “compute an angle is expensive”.

Relative to what in 3D space?

Almost always, if you find yourself calculating an angle then you are doing something wrong. Angles are only general useful for people (which is why his code only converts to angle for display).

13

Reading the code, I thought we where in two dimensions. Obiously, angles are not the good aproach if you add an axis :smile:

The projection using the dot seemed strange to me but it makes sense. Usefull !

14

To be honest I still don’t get the squaring …

JME already used pythagoras to determine the distance between shipPos and projected. Why square that distance again just to compare it to the radius?

The radius can be measured along the vector between shipPos and projected, so basically it all happens along the same line.

15

We AREN"T squaring. When we have squared distances it’s because we DIDN"T calculate a SQAURE ROOT.

A^2 + B^2 = C^2

…when C^2 is good enough then there is no reason to calculate a square root… so old school programmers don’t.

In other words, if you are just trying to see if one distance is less than another then you can avoid square roots by squaring the constant and not ‘unsquaring’ the distance.

In other other words, which is more expensive:
float dSquared = x * x + y * y + z * z;
Or:
float d = FastMath.sqrt(x * x + y * y + z * z);

Hint: it’s the one with the sqrt().

16

For distance comparisons, you can also try the even faster manhattan distance ! :stuck_out_tongue:

17

True… the benefit of the ‘squared distance’ is that if the check passes then you can immediately just sqrt() it to get the actual distance needed in the next math steps.

For two extra multiplies (cheap), you get to reuse the value.

1 Like