Detour path finding - not much documentation

Dear community,

thanks to Mitm help I do have now a navigation mesh and can start with pathfinding.
According to JME3 wiki - detour

I should use NavMeshQuery object to find navigation path for my solo navigation mesh.
However, this class has quite a lot of methods.
For example, method initSlicedFindPath has parameters:

long startRef, long endRef, float[] startPos, float[] endPos

Is this a correct method at all?

For the startPos and endPost position I assume it is a position which I can acquire in JME3 (startPos is mesh center, endPos by raycasting).
However, startRef and endRef are reference ids of first and last polygons. How do I get them?

Any advice/code examples would be helpful.

Thank you,
Denis

You can look in recast4j under any test folder and find examples of how to do things. This is one for pathfinding,

You still have to understand how jme works to get things configured right.

I will give you a simple one that mimics the jme3Ai examples found here
https://wiki.jmonkeyengine.org/jme3/advanced/jme3_ai.html#navigationcontrol

package mygame.recast;

import com.jme3.app.Application;
import com.jme3.app.SimpleApplication;
import com.jme3.cinematic.MotionPath;
import com.jme3.export.JmeExporter;
import com.jme3.export.JmeImporter;
import com.jme3.math.Spline;
import com.jme3.math.Vector2f;
import com.jme3.math.Vector3f;
import com.jme3.renderer.RenderManager;
import com.jme3.renderer.ViewPort;
import com.jme3.scene.Spatial;
import com.jme3.scene.control.Control;
import com.jme3.util.clone.Cloner;
import com.jme3.util.clone.JmeCloneable;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;
import mygame.controls.AnimationControl;
import mygame.controls.PCControl;
import mygame.enums.EnumPosType;
import mygame.interfaces.DataKey;
import mygame.interfaces.ListenerKey;
import mygame.interfaces.Pickable;
import static org.recast4j.detour.DetourCommon.vCopy;
import org.recast4j.detour.FindNearestPolyResult;
import org.recast4j.detour.FindPathResult;
import org.recast4j.detour.NavMesh;
import org.recast4j.detour.NavMeshQuery;
import org.recast4j.detour.QueryFilter;
import org.recast4j.detour.StraightPathItem;

/**
 * @literal
 RecastNavControl implements pathfinding. When target != null, Querry thread 
 will calculate a newpath.
 
 controlUpdate continuously checks the path for two or more waypoints. If path
 contains enough waypoints, moves the path pos to the next wayPoint, sets
 wayPosition and spatials Animation pos.
 
 If wayPosition != null, calculates the distance from current spatial world
 position to the wayPosition. If distance > value, sets the viewDirection of
 PCControl by subtracting spatial world pos from wayPosition, then sets
 PCControl forward variable to true. If distance < value, nulls wayPosition.

 If wayPosition = null, sets Animation pos and PCControl forward variable
 to false.

 @author mitm
 */
public class RecastNavControl extends NavMeshQuery implements Control, JmeCloneable, Pickable {

    private static final Logger LOG = Logger.getLogger(RecastNavControl.class.getName());
    private Spatial spatial;
    private PCControl pcControl;
    private final ScheduledExecutorService executor;
    private Vector3f target, wayPosition, nextWaypoint;
    private List<StraightPathItem> straightPath;
    private final List<Vector3f> wayPoints;
    private boolean showPath, finding;
    private final MotionPath motionPath;
    private final SimpleApplication app;
    private final float[] extents;
    private final float[] startArray;
    private final float[] endArray;
    private final float[] pos;
    private final NavMeshQuery query;
    
    public RecastNavControl(NavMesh nav, Application app) {
        super(nav);
        this.pos = new float[3];
        this.endArray = new float[3];
        this.startArray = new float[3];
        this.extents = new float[]{2, 4, 2};
        this.app = (SimpleApplication) app;
        wayPoints = new ArrayList<>();
        motionPath = new MotionPath();
        motionPath.setPathSplineType(Spline.SplineType.Linear);
        query = new NavMeshQuery(nav);
        executor = Executors.newScheduledThreadPool(1);
        startRecastQuery();
    }

    @Override
    public void setSpatial(Spatial spatial) {
        if (this.spatial != null && spatial != null && spatial != this.spatial) {
            throw new IllegalStateException(
                    "This control has already been added to a Spatial");
        }
        this.spatial = spatial;
        if (spatial == null) {
            shutdownAndAwaitTermination(executor);
            setPcControl(null);
        } else {
            setPcControl(spatial.getControl(PCControl.class));
            if (getPcControl() == null) {
                throw new IllegalStateException(
                        "Cannot add RecastNavControl to spatial without PCControl!");
            }
        }
    }
    
    private void shutdownAndAwaitTermination(ExecutorService pool) {
        pool.shutdown(); // Disable new tasks from being submitted
        try {
            // Wait a while for existing tasks to terminate
            if (!pool.awaitTermination(6, TimeUnit.SECONDS)) {
                pool.shutdownNow(); // Cancel currently executing tasks
                // Wait a while for tasks to respond to being cancelled
                if (!pool.awaitTermination(6, TimeUnit.SECONDS)) {
                    LOG.log(Level.SEVERE, "Pool did not terminate {0}", pool);
                }
            }
        } catch (InterruptedException ie) {
            // (Re-)Cancel if current thread also interrupted
            pool.shutdownNow();
            // Preserve interrupt status
            Thread.currentThread().interrupt();
        }
    }
    
    @Override
    public void update(float tpf) {
        if (getWayPosition() != null) {
            Vector3f spatialPosition = spatial.getWorldTranslation();
            Vector2f aiPosition = new Vector2f(spatialPosition.x, spatialPosition.z);
            Vector2f waypoint2D = new Vector2f(getWayPosition().x, getWayPosition().z);
            float distance = aiPosition.distance(waypoint2D);                       

            if (distance > 1f) {
                Vector2f direction = waypoint2D.subtract(aiPosition);
                direction.mult(tpf);
                getPcControl().setViewDirection(new Vector3f(direction.x, 0, direction.y).normalize());
                getPcControl().onAction(ListenerKey.MOVE_FORWARD, true, 1);
            } else {
                setWayPosition(null);
            }
        } else if (!finding && nextWaypoint != null && !isAtGoalWaypoint()) {
            //must be called from the update loop
            if (showPath) {
                showPath();
                showPath = false;
            }
            goToNextWaypoint();
            setWayPosition(new Vector3f(getNextWaypoint()));

            if (getAutorun() && getPositionType() != EnumPosType.POS_RUNNING.pos()) {
                setPositionType(EnumPosType.POS_RUNNING.pos());
                stopPlaying();
            } else if (!getAutorun() && getPositionType() != EnumPosType.POS_WALKING.pos()) {
                setPositionType(EnumPosType.POS_WALKING.pos());
                stopPlaying();
            }
//            System.out.println("Next wayPosition = " + getWayPosition() + " SpatialWorldPosition " + spatialPosition);
        } else {
            if (canMove() && getPositionType() != EnumPosType.POS_STANDING.pos()) {
                setPositionType(EnumPosType.POS_STANDING.pos());
                stopPlaying();
            }
            getPcControl().onAction(ListenerKey.MOVE_FORWARD, false, 1);
        }
    }

    @Override
    public void render(RenderManager rm, ViewPort vp) {
    }

    @Override
    public void write(JmeExporter ex) throws IOException {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public void read(JmeImporter im) throws IOException {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    
    @Override
    public Control cloneForSpatial(Spatial spatial) {
        try {
            RecastNavControl c = (RecastNavControl) clone();
            c.spatial = null; // to keep setSpatial() from throwing an exception
            c.setSpatial(spatial);
            return c;
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException("Can't clone control for spatial", e);
        }
    }
    
    @Override
    public Object jmeClone() {
        try {
            return super.clone();
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException("Can't clone control for spatial", e);
        }
    }

    @Override
    public void cloneFields(Cloner cloner, Object original) {
        this.spatial = cloner.clone(spatial);
    }
    
    //Pathfinding thread
    private void startRecastQuery() {
        QueryFilter filter = new QueryFilter();
        executor.scheduleWithFixedDelay(() -> {
            if (target != null) {
                finding = true;
                clearPath();
                Vector3f spatialPos = spatial.getWorldTranslation();
                boolean success;
                spatialPos.toArray(startArray);                
                target.toArray(endArray);
                FindNearestPolyResult startPos = findNearestPoly(startArray, extents, filter);
                FindNearestPolyResult endPos = findNearestPoly(endArray, extents, filter);
                
                if (startPos.getNearestRef() == 0 || endPos.getNearestRef() == 0) {
                    success = false;
                } else {
                    System.out.println("StartPosRef " + startPos.getNearestRef() 
                    + " EndPosRef " + endPos.getNearestRef()
                    + " StartPos " + Arrays.toString(startPos.getNearestPos())
                    + " EndPos "  + Arrays.toString(endPos.getNearestPos()));
                    FindPathResult path = findPath(startPos.getNearestRef(), endPos.getNearestRef(), startPos.getNearestPos(), endPos.getNearestPos(), filter);
                    straightPath = findStraightPath(startPos.getNearestPos(), endPos.getNearestPos(), path.getRefs(), Integer.MAX_VALUE, 0);
                    
                    for (int i = 0; i < straightPath.size(); i++) {             
                        vCopy(pos, straightPath.get(i).getPos());
                        Vector3f vector = new Vector3f(pos[0], pos[1], pos[2]);
                        wayPoints.add(vector);
                    }
                    System.out.println("RecastNavControl waypoints " + wayPoints);
                    nextWaypoint = this.getFirst();
                    success = true;
                }
                System.out.println("RECAST SUCCESS " + success);
                if (success) {
                    target = null;
                    showPath = true;
                }
                finding = false;
            }
        }, 0, 500, TimeUnit.MILLISECONDS);
    }
    
    //Returns the first wayPoint in wayPoints List
    private Vector3f getFirst() {
        return wayPoints.get(0);
    }

    /**
     * Sets target for pathfinding.
     * @param target Vector3f to target 
     */
    @Override
    public void setTarget(Vector3f target) {
        this.target = target;
    }
    
    //Returns true if at last wayPoint in wayPoints List
    private boolean isAtGoalWaypoint() {
        return nextWaypoint == this.getLast();
    }
    
    //Returns last wayPoint in wayPoints List
    private Vector3f getLast() {
        return wayPoints.get(wayPoints.size() - 1);
    }

    //Returns the wayPoints List
    private List<Vector3f> getWayPoints() {
        return wayPoints;
    }
    
    //Next wayPoint in wayPoints List
    private Vector3f getNextWaypoint() {
        return nextWaypoint;
    }
    
    //Advances to the next wayPoint in wayPoints List
    private void goToNextWaypoint() {
        int from = getWayPoints().indexOf(nextWaypoint);
        nextWaypoint = getWayPoints().get(from + 1);
    }
    
    //Displays the wayPoints in the wayPoints List using a motionPath.
    private void showPath() {
        if (motionPath.getNbWayPoints() > 0) {
            motionPath.clearWayPoints();
            motionPath.disableDebugShape();
        }

        for (Vector3f wp : this.getWayPoints()) {
            motionPath.addWayPoint(wp);
        }
        motionPath.enableDebugShape(this.app.getAssetManager(), this.app.getRootNode());
    }

    /**
     * @return the wayPosition
     */
    private Vector3f getWayPosition() {
        return wayPosition;
    }

    //Sets the wayPosition 
    private void setWayPosition(Vector3f wayPosition) {
        this.wayPosition = wayPosition;
    }

    //Returns the PCControl
    private PCControl getPcControl() {
        return pcControl;
    }

    //Sets the PCControl
    private void setPcControl(PCControl pcControl) {
        this.pcControl = pcControl;
    }
    
    //Returns true is AutRun is set to run
    private boolean getAutorun() {
        return (Boolean) spatial.getUserData(DataKey.AUTORUN);
    }
    
    //Returns the physical position of Spatial
    private int getPositionType() {
        return (Integer) spatial.getUserData(DataKey.POSITION_TYPE);
    }
    
    //Sets the Physical position of Spatial
    private void setPositionType(int position) {
        spatial.setUserData(DataKey.POSITION_TYPE, position);
    }
    
    //Stops the animation thats currently playing
    private void stopPlaying() {
        spatial.getControl(AnimationControl.class).getAnimChannel()
                .setTime(spatial.getControl(AnimationControl.class)
                        .getAnimChannel().getAnimMaxTime());
    }
    
    //Returns true if the Spatial can move
    private boolean canMove() {

        int position = getPositionType();
        boolean move = true;

        for (EnumPosType pos : EnumPosType.values()) {
            if (pos.pos() == position) {
                switch (pos) {
                    case POS_DEAD:
                    case POS_MORTAL:
                    case POS_INCAP:
                    case POS_STUNNED:
                    case POS_TPOSE:
                        move = false;
                        break;
                }
            }
        }
        return move;
    }
    
    //Clears the wayPoints list, nextWaypoint and wayPosition
    private void clearPath() {
        wayPoints.clear();
        nextWaypoint = null;
        setWayPosition(null);
    }
}

There are many, many, many ways to implement this. This is just one example. I have 1/2 a dozen different implementations myself, including writing my own Detour Crowd class for straight pathfinding.

The reason there is no documentation for detour is its not a jme library. I personally do not want to spend a month refactoring my code to write a wiki topic since I am trying to get through my final stages of learning the engine.

The jme3 AI library is based off nmgem study which is based of recast.

Recast4j is a direct conversion of recast, nothing added. I spent 6 months learning this stuff so you should expect this to not be something you learn overnight.

Lastly, totally ignore that recast page, the project is dead and will only give you grief. Use the test examples at recast4j to learn. Every top project folder has them. They are awesome.

1 Like

Thank you for the support. I am trying to learn it since weeks already and thought it is only difficult for a beginner :D.
When you said project is dead, you meant not recast but bridge from recast4j to jme, right?

Right, the page you link to is a incomplete jni implementation whereas recast4j is a completed java conversion. Much better.

I still have to learn how to do on the fly changes like changing a tile mesh when a door is closed for example and implementing behaviors’ but I will do that when I get to the server stage.

1 Like