Most games written need some type of Artificial Intelligence to deliver a feeling of realism, excitement or challenge to the player. AI can be as simple as having an NPC (Non Player Character) respond to some action taken by a player or as complicated as smoothly navigating your way through a scene full of obstacles without getting stuck. It’s a time-consuming and significant challenge to develop these systems so its much easier to use an existing library to do the heavy lifting for you.

Unfortunately, the jMonkeyEngine comes with no official library for dealing with AI. There is, however, the jme3 Artificial Intelligence library that is probably the closest there is to an official release. Although it never made it into any official releases, it was designed, in part, by core team members. It consists of two separate AI models, a Navigation Mesh library using path-finding, and a simple Steering Behaviours library that uses path-following.

You can read about the introduction of the library in the forum thread: AI plugin now with NavMesh path-finding.

Requirements

Stephen Pratt explains in detail the configuration parameters of CritterAI/Jme3AI in a easy to follow format and is suggested reading.

Use Example

The jme3 Artificial Intelligence Library contains:

  • NavMesh - A Navigation Mesh path-finding AI system using the A* algorithm.[1]

  • Steering - The foundations of an Autonomous Agent system that uses path-following and forces to move a character through its environment. Includes a test case as well.[2] 

This scope of this tutorial is restricted to the NavMesh part of the library and expands upon the lessons taught in the tutorials. It demonstrates the use of some classes and methods found in the Medium and Advanced topics of the wiki as well. You can find the source code for this tutorial in the jMonkeyEngine/docs-examples repository.

Moving a character through your scene requires three things.

  • A navigation mesh.

  • A path-finding component that uses that navigation mesh to calculate a path.

  • A way to move the character.

The first thing you need for path-finding is a navigation mesh. There are two ways to generate the NavMesh, procedural or the jMonkey SDK.

  • The SDK has a built-in command, but comes with a trade-off that no parameter exceptions are thrown. This means you are flying blind when the NavMesh fails generation.

  • If you choose procedural, you see any generation exceptions, but you will have to do a little more work like saving, loading and/or displaying the NavMesh.

Both methods produce exactly the same NavMesh and both will be covered in this tutorial.

From the SDK

  • Open your scene in the Terrain Editor or Scene Explorer by RMB selecting the file in your assets folder and choosing Edit Terrain or Edit in SceneComposer.

  • Once open, RMB select the root node in the SceneExplorer and then select Spatial ▸ NavMesh.

This will open the Create NavMesh dialog with default settings. You can read in depth about each parameter by following the Configuration Parameters link under Requirements.

Parameter Insight

The jme3AI system uses CritterAI, which is based off Recast and Detour navigation. The author of Recast lays out a few specific rules for NavMesh creation in this blog post, which logically apply to jme3AI. Below is a translation of this post as it pertains to jme3AI.

  • First you should decide the size of your character "capsule". For example, if you are using meters as units in your game world, a good size of human sized character might be (r)adius=0.4, (h)eight=2.0.

  • Next the voxelization cell size (cs) will be derived from that. Usually good value for cs is r/2 or r/3. In outdoor environments, r/2 might be enough, indoors you sometimes want the extra precision and you might choose to use r/3 or smaller.

  • The voxelization cell height (ch) is defined separately in order to allow greater precision in height tests. Good starting point for ch is cs/2. If you get small holes where there are discontinuities in the height (steps), you may want to decrease cell height.

  • Next up is the character definition values. First up is minTraversableHeight, which defines the height of the agent.

  • The maxTraversableStep defines how high steps the character can climb.

  • The parameter traversableAreaBorderSize defines the agent radius. If this value is greater than zero, the navmesh will be shrunken by the traversableAreaBorderSize. If you want to have tight fit navmesh, use zero radius.

  • The parameter maxTraversableSlope is used before voxelization to check if the slope of a triangle is too high and those polygons will be given a non-walkable flag. The parameter is in radians.

  • In certain cases really long outer edges may decrease the triangulation results. Sometimes this can be remedied by just tessellating the long edges. The parameter maxEdgeLength defines the max edge length. A good value for maxEdgeLength is something like traversableAreaBorderSize*8. A good way to tweak this value is to first set it really high and see if your data creates long edges. If so, then try to find as big value as possible which happen to create those few extra vertices which makes the tessellation better.

  • When the rasterized areas are converted back to vectorized representation the edgeMaxDeviation describes how loosely the simplification is done. Good values are between 1.1-1.5 (1.3 usually yield good results). If the value is less, some stair-casing starts to appear at the edges and if it is more than that, the simplification starts to cut some corners.

A summary of the parameter effects is included in the comments of the NavMeshState.java file and discussed in the Procedural code examples that follow this section.

If there are problems with your parameter settings, you will only know if the NavMesh doesn’t appear under the Node you selected and there is no task running in the status area located at the bottom right of the SDK.

If the NavMesh doesn’t appear, then you will have to make adjustments to the Configuration Parameters until it completes successfully. Minor adjustments to cell size will usually work.

Cell size has the greatest impact on your NavMesh. The smaller the cell size, the more accurate the NavMesh, the longer it takes to generate. Generating a 1024x1024 NavMesh can take anywhere from 30 seconds to ten minutes to complete, depending on terrain complexity. Even larger NavMeshes can take many hours.
Selecting the NavMesh node in the SceneExplorer will show the NavMesh in the Terrain Editor or SceneComposer view-port. If it doesn’t show, with the NavMesh node selected, change the Cull Hint to Never in the NavMesh - Properties panel.

Procedural Method

There are many ways to create a NavMesh. If you look at the constructor for the Jme3AI.java file, you will see I use a BaseAppState named NavMeshState.java which creates a generator object and builds the NavMesh new every time the program is ran.

Jme3AI constructor
public Jme3AI() {
    super(new StatsAppState(), new DebugKeysAppState(), new TerrainState(),
            new NavMeshState(), new PCState(), new KeyboardRunState());
}

It can take from seconds to hours to build a NavMesh, depending on how complicated it is. Therefore, you would normally build the NavMesh or meshes, add them to your Assets folder and load them at startup. The NavMeshState and NavMeshGenerator classes are both convenience classes and are not required to create a NavMesh. If you wish to keep your game minimalist, you can set the variables for the CritterAI NavmeshGenerator (note the lower case 'm' in mesh) in the method call directly or by variable, and pass the IndexBuffer and VertexBuffer of your mesh into the CritterAI NavmeshGenerator object.

NavmeshGenerator nmgen = new NavmeshGenerator(cellSize, cellHeight, minTraversableHeight,
                maxTraversableStep, maxTraversableSlope,
                clipLedges, traversableAreaBorderSize,
                smoothingThreshold, useConservativeExpansion,
                minUnconnectedRegionSize, mergeRegionSize,
                maxEdgeLength, edgeMaxDeviation, maxVertsPerPoly,
                contourSampleDistance, contourMaxDeviation);
...
Get mesh buffers and set IntermediateData
...

//Pass buffers and IntermediateData to build process
TriangleMesh triMesh = nmgen.build(positions, indices, intermediateData);

...
Process trimesh
...

Let’s examine what it takes to create the NavMesh using the NavMeshState and NavMeshGenerator helper classes.

NavMeshState NavMesh generation method
/**
 * creates the NavMesh
 */
private void createNavMesh() {
    generator = new NavMeshGenerator();
    //The width and depth resolution used when sampling the source geometry.
    //outdoors = agentRadius/2, indoors = agentRadius/3, cellSize =
    //agentRadius for very small cells.
    //Constraints > 0 , default=1
    generator.setCellSize(.25f);
    //The height resolution used when sampling the source geometry.
    //minTraversableHeight, maxTraversableStep, and contourMaxDeviation
    //will need to be greater than the value of cellHeight in order to
    //function correctly. maxTraversableStep is especially susceptible to
    //impact from the value of cellHeight.
    //cellSize/2
    //Constraints > 0, default=1.5
    generator.setCellHeight(.125f);
    //Represents the minimum floor to ceiling height that will still allow
    //the floor area to be considered traversable.
    //minTraversableHeight should be at least two times the value of
    //cellHeight in order to get good results. Max spatial height.
    //Constraints > 0, default=7.5
    generator.setMinTraversableHeight(2f);
    //Represents the maximum ledge height that is considered to still be
    //traversable.
    //maxTraversableStep should be greater than two times cellHeight.
    //Constraints >= 0, default=1
    generator.setMaxTraversableStep(0.3f);
    //The maximum slope that is considered traversable. (In degrees.)
    //Constraints >= 0, default=48
    generator.setMaxTraversableSlope(50.0f);
    //Indicates whether ledges should be considered un-walkable.
    //Constraints None, default=false
    generator.setClipLedges(false);
    //Represents the closest any part of a mesh can get to an obstruction in
    //the source geometry.
    //traversableAreaBorderSize value must be greater than the cellSize to
    //have an effect. Radius of the spatial.
    //Constraints >= 0, default=1.2
    generator.setTraversableAreaBorderSize(0.6f);
    //The amount of smoothing to be performed when generating the distance
    //field used for deriving regions.
    //Constraints >= 0, default=2
    generator.setSmoothingThreshold(0);
    //Applies extra algorithms to help prevent malformed regions from
    //forming.
    //Constraints None, default=true
    generator.setUseConservativeExpansion(true);
    //The minimum region size for unconnected (island) regions.
    //Constraints > 0, default=3
    generator.setMinUnconnectedRegionSize(8);
    //Any regions smaller than this size will, if possible, be merged with
    //larger regions.
    //Constraints >= 0, default=10
    generator.setMergeRegionSize(20);
    //The maximum length of polygon edges that represent the border of
    //meshes.
    //setTraversableAreaBorderSize * 8
    //Constraints >= 0, default=0
    generator.setMaxEdgeLength(4.0f);
    //The maximum distance the edges of meshes may deviate from the source
    //geometry.
    //1.1 to 1.5 for best results.
    //Constraints >= 0 , default=2.4
    generator.setEdgeMaxDeviation(1.3f);
    //The maximum number of vertices per polygon for polygons generated
    //during the voxel to polygon conversion process.
    //Constraints >= 3, default=6
    generator.setMaxVertsPerPoly(6);
    //Sets the sampling distance to use when matching the detail mesh to the
    //surface of the original geometry.
    //Constraints >= 0, default=25
    generator.setContourSampleDistance(5.0f);
    //The maximum distance the surface of the detail mesh may deviate from
    //the surface of the original geometry.
    //Constraints >= 0, default=25
    generator.setContourMaxDeviation(5.0f);
    //Time allowed before generation process times out in miliseconds.
    //default=10000
    generator.setTimeout(40000);

    //the data object to use for storing data related to building the
    //navigation mesh.
    IntermediateData data = new IntermediateData();
    generator.setIntermediateData(data);

    Mesh mesh = new Mesh();
    GeometryBatchFactory.mergeGeometries(findGeometries(app.getRootNode(),
            new LinkedList<>(), generator), mesh);

    //uncomment to show mesh
//        Geometry meshGeom = new Geometry("MeshGeometry");
//        meshGeom.setMesh(mesh);
//        showGeometry(meshGeom, ColorRGBA.Yellow);
//        saveNavMesh(meshGeom);

    Mesh optiMesh = generator.optimize(mesh);
    navMesh.loadFromMesh(optiMesh);

    Geometry geom = new Geometry(DataKey.NAVMESH);
    geom.setMesh(optiMesh);
    //display the mesh
    showGeometry(geom, ColorRGBA.Green);
    //save the navmesh to Scenes/NavMesh for loading
    exportNavMesh(geom, DataKey.NAVMESH);
    //save geom to rootNode if you wish
    saveNavMesh(geom);
}

First, we create the NavMeshGenerator object and then use it to set the parameters for the NavMesh.

generator = new NavMeshGenerator();
...
generator.setCellSize(.25f);
...

In our next step we create an IntermediateData object.

//the data object to use for storing data related to building the
//navigation mesh.
IntermediateData data = new IntermediateData();
generator.setIntermediateData(data);

The IntermediateData object can be used to get information about the build process of the NavMesh such as build times. You query this object after building the NavMesh. If you don’t wish to see the data, set it to null.

At this point, you now have a generator object that you use to create the NavMesh with.

Included in the NavMeshState.java file is the helper method findGeometries.

//Gathers all geometries in supplied node into supplied List. Uses
//NavMeshGenerator to merge found Terrain meshes into one geometry prior to
//adding. Scales and sets translation of merged geometry.
private List<Geometry> findGeometries(Node node, List<Geometry> geoms,
          NavMeshGenerator generator)

It is used to collect all geometries, attached to a node, into a List. If a child of the node is a Terrain instance (which can consist of many meshes), it will use the generator object to merge them into one mesh, then scale and set translation of the merged mesh prior to being added to the list. You then use GeometryBatchFactory to merge all the geometries in the list into a single mesh object.

Mesh mesh = new Mesh();
GeometryBatchFactory.mergeGeometries(findGeometries(app.getRootNode(),
        new LinkedList<>(), generator), mesh);

After these methods execute, you have a single mesh object that is now ready to be optimized.

Mesh optiMesh = generator.optimize(mesh);

This is where the parameters you set with the generator object are applied to the supplied mesh. The optimize method will return a new Mesh object that reflects your generator settings. Now is when any problems with your parameters will show themselves as either warnings or exceptions. You should keep changing the various parameters, one at a time and in small increments/decrements, until your mesh generates with no errors. See each parameter’s notes for suggestions on how to do so.

After the mesh generates, you need to link all of its cells together so it can be used as your NavMesh object. You do this by calling loadFromMesh() or loadFromData(), depending on your implementation, on your optiMesh object.

navMesh.loadFromMesh(optiMesh);

If you look at the second contructor for the NavMesh class you will see this is all it does. You would use this constructor if you were loading a Mesh from a geometry that had already been optimized and saved into your Assets folder for example.

public NavMesh(Mesh mesh) {
  loadFromMesh(mesh);
}

The NavMesh object is now ready for use in your game, but you still need to create the geometry for it if you wish to save or view it. You do this the same as you would for any newly created mesh.

Geometry geom = new Geometry(DataKey.NAVMESH);
geom.setMesh(navMesh);

Now that you have your Mesh you should save it.

//save the navmesh to Scenes/NavMesh for loading
exportNavMesh(geom, DataKey.NAVMESH);
//save geom to rootNode if you wish
saveNavMesh(geom);

In this instance, the object is exported to the projects Assets folder so it can be loaded rather than generated every time the game starts. This is the preferred method. The saveNavMesh() method just attaches the geometry to the rootNode. How and where you choose to save depends on your implementation and personal preferences.

Pathfinding

There are many ways to implement the NavMeshPathfinder class of the jme3AI library. You can create a control, instantiate the NavMeshPathFinder class, and query the newly created object in a thread. You could use a single AppState to calculate all your paths. You could, as in this tutorial, extend the NavMeshPathFinder class in a custom control.

You also need a way to communicate Vector3f changes to the NavMeshPathfinder. This tutorial uses an ActionListener and Interface. You could just as easily create a public method in the control, and call it from the ActionListener, or store the Vector3f in UserData and look for changes from the control itself.

These are implementation decisions that are left up to you.

Loading the NavMesh

In this tutorial example, the optimized mesh was exported as a geometry using the jMonkey binary format .j3o. Doing so means the loading of your NavMeshes is done the same way you load any model, by using the AssetManager. Once you load the .j3o, you grab its Mesh and create the NavMesh object to be passed to the NavigationControl constructor. This tutorial uses a BaseAppState for model loading so access to the Application class is built in.

//load NavMesh geometry saved to assets folder
Geometry navGeom = (Geometry) getApplication().getAssetManager().
        loadModel("Scenes/NavMesh/NavMesh.j3o");
NavigationControl navControl = new NavigationControl(new NavMesh(
        navGeom.getMesh()), getApplication(), true)
charNode.addControl(navControl);
//NavigationControl implements Pickable Interface
picked = navControl;

This tutorial uses a custom control, NavigationControl, that extends the NavMeshPathfinder class. As this is a tutorial, some extra variables are used for dispalying the navigation path and are not needed. The constructor for NavMeshPathfinder requires just the the passing of the NavMesh object, which makes for a cleaner control.

public NavigationControl(NavMesh navMesh) {
  ...
}

Communicating with NavigationControl

This tutorial makes use of the Hello Picking and Mouse Picking tutorials so you should already be familiar with this method for picking and how to add the input mappings to your game. How you implement your ActionListener is up to you.

PCState ActionListener
    private class ClickedListener implements ActionListener {

        @Override
        public void onAction(String name, boolean isPressed, float tpf) {

            if (name.equals(ListenerKey.PICK) && !isPressed) {
                CollisionResults results = new CollisionResults();
                Vector2f click2d = getInputManager().getCursorPosition().clone();
                Vector3f click3d = app.getCamera().getWorldCoordinates(click2d,
                        0f).clone();
                Vector3f dir = app.getCamera().getWorldCoordinates(
                        click2d, 1f).subtractLocal(click3d).normalizeLocal();
                Ray ray = new Ray(click3d, dir);
                app.getRootNode().collideWith(ray, results);

                for (int i = 0; i < results.size(); i++) {
                    // For each hit, we know distance, impact point, name of geometry.
                    float dist = results.getCollision(i).getDistance();
                    Vector3f pt = results.getCollision(i).getContactPoint();
                    String hit = results.getCollision(i).getGeometry().getName();
                    System.out.println("* Collision #" + i);
                    System.out.println(
                            "  You shot " + hit
                            + " at " + pt
                            + ", " + dist + " wu away.");
                }

                if (results.size() > 0) {
                    // The closest collision point is what was truly hit:
                    CollisionResult closest = results.getClosestCollision();
                    // Let's interact - we mark the hit with a red dot.
                    mark.setLocalTranslation(closest.getContactPoint());
                    app.getRootNode().attachChild(mark);
                    picked.setTarget(closest.getContactPoint());
                    System.out.println("  Closest Contact " + closest.
                            getContactPoint());
                } else {
                    // No hits? Then remove the red mark.
                    app.getRootNode().detachChild(mark);
                }
            }
        }
    }

The main line of interest here is,

picked.setTarget(closest.getContactPoint());

where picked is the reference object used to communicate our Vector3f changes to the NavigationControl.

//NavigationControl implements Pickable Interface
picked = navControl;

At this point you have loaded your NavMesh, added the NavigationControl to your spatial, and instituted a method for communicating with the NavMeshPathFinder. Next we will delve into the details of the NavigationControl.

The NavigationControl is a custom control that extends the NavMeshPathFinder class of the Jme3AI library and implements the Pickable interface.

public class NavigationControl extends NavMeshPathfinder implements Control,
        JmeCloneable, Pickable {
}

The Pickable interface is straightforward and its sole purpose in this implementation is to communicate changes made to the pick target.

Pickable Interface implementation
/**
 * @param target the target to set
 */
@Override
public void setTarget(Vector3f target) {
    this.target = target;
}

The heartbeat of the control lies in the pathfinding thread which makes calls to the computePath() method. Potentially long running tasks like this should always be ran from a thread. Below, is the constructor you would normally use to instantiate your control.

public NavigationControl(NavMesh navMesh) {
    super(navMesh); //sets the NavMesh for this control
    executor = Executors.newScheduledThreadPool(1);
    startPathFinder();
}

First, you call super(navMesh) to set the NavMesh for the control, then setup your ExecutorService and start the pathfinding thread.

This is a custom thread implementation so it’s up to you to handle shutting it down. This is done in the controls setSpatial() method.

if (spatial == null) {
    shutdownAndAwaitTermination(executor);
    ...
} else {
    ...
}
Executor shutdown process
//standard shutdown process for executor
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();
    }
}

The easiest way to move a physics character is by using the BetterCharacterControl class. In this implementation, this is done in the PCControl class by extending BetterCharacterControl. Since BetterCharacterControl is required to be present on the spatial for pathfinding, in the setSpatial() method, we throw an exception to let us know if it’s missing.

if (spatial == null) {
    ...
} else {
    pcControl = spatial.getControl(PCControl.class);
    if (pcControl == null) {
        throw new IllegalStateException(
                "Cannot add NavigationControl to spatial without PCControl!");
    }
}

Pathfinding Thread

NavigationControl pathfinding thread
//Computes a path using the A* algorithm. Every 1/2 second checks target
//for processing. Path will remain untill a new path is generated.
private void startPathFinder() {
    executor.scheduleWithFixedDelay(() -> {
        if (target != null) {
            clearPath();
            setWayPosition(null);
            pathfinding = true;
            //setPosition must be set before computePath is called.
            setPosition(spatial.getWorldTranslation());
            //warpInside(target) moves endpoint within the navMesh always.
            warpInside(target);
            System.out.println("Target " + target);
            boolean success;
            //comput the path
            success = computePath(target);
            System.out.println("SUCCESS = " + success);
            if (success) {
                //clear target if successful
                target = null;
                ...
            }
            pathfinding = false;
        }
    }, 0, 500, TimeUnit.MILLISECONDS);
}

How you setup your pathfinding thread makes a significant difference.

executor.scheduleWithFixedDelay(() -> {
...
}, 0, 500, TimeUnit.MILLISECONDS);

This ExecutorService is set to start immediately (0) with a fixed delay of (500) milliseconds. This means the task has a fixed delay of 1/2 second between the end of an execution and the start of the next execution, i.e. it doesn’t take into account the actual duration of the task. If you were to use scheduleAtFixedRate(), you risk that the task doesn’t complete in the time allocated.

When you use the BetterCharacterControl, all that’s required to move the spatial is that you setWalkDirection() and the spatial will continuously move in that direction. The following code breakdown explains how the NavigationControl takes advantage of this.

It starts by having the pathfinding thread check a target variable for changes.

if (target != null) {
    ...
}

If it finds a target, it will compute a new path to that target, and if successful, update the NavMeshPathfinder path variable. The update() loop of the control continuously checks this path variable, and if its non-null, takes an appropriate action.

Before you compute the path you first clear the existing path, and set wayPosition to null.

if (target != null) {
    clearPath();
    setWayPosition(null);
    pathfinding = true;
    ...
}

Doing this allows the player to select a new target at any time and immediately start moving along the new path. Otherwise, the character must finish the path they are on, then backtrack to the position the character was at when the target change was made, before then continuing on the new path.

Next, you must call setPosition() before calling the computePath() method.

if (target != null) {
  ...
  setPosition(spatial.getWorldTranslation());
  ...
  //compute the path
  success = computePath(target);
  ...
}

There are some things you need to know about how a path is computed.

  • The first waypoint on any path is the one you set with setPosition().

  • The last waypoint on any path is always the target Vector3f.

  • computePath() adds one waypoint to the cell nearest to the target only if you are not in the goalCell (the cell target is in), and if there is a cell between first and last waypoint, and if there is no direct line of sight.

  • If inside the goalCell when a new target is selected, computePath() will do a direct line of sight placement of target. This means there will only be two waypoints set, setPosition() and target.

  • If the target is outside the NavMesh, your endpoint will be as well.

To guarantee that target is always inside the NavMesh, call

if (target != null) {
    ...
    //warpInside(target) moves endpoint within the navMesh always.
    warpInside(target);
    ...
    //compute the path
    success = computePath(target);
    ...
}

before calling computePath() and the endpoint of the path will be moved to the closest cell to the target that’s inside the NavMesh.

Character Movement

NavigationControl update() loop
@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);
        //move char between waypoints untill waypoint reached then set null
        if (distance > .25f) {
            Vector2f direction = waypoint2D.subtract(aiPosition);
            direction.mult(tpf);
            pcControl.setViewDirection(new Vector3f(direction.x, 0,
                    direction.y).normalize());
            pcControl.onAction(ListenerKey.MOVE_FORWARD, true, 1);
        } else {
            setWayPosition(null);
        }
    } else if (!isPathfinding() && getNextWaypoint() != null
            && !isAtGoalWaypoint()) {
        if (showPath) {
            showPath();
            showPath = false;
        }
        //advance to next waypoint
        goToNextWaypoint();
        setWayPosition(new Vector3f(getWaypointPosition()));

        //set spatial physical position
        if (getPositionType() == EnumPosition.POS_STANDING.position()) {
            setPositionType(EnumPosition.POS_RUNNING.position());
            stopFeetPlaying();
            stopTorsoPlaying();
        }
    } else {
        //waypoint null so stop moving and set spatials physical position
        if (getPositionType() == EnumPosition.POS_RUNNING.position()) {
            setPositionType(EnumPosition.POS_STANDING.position());
            stopFeetPlaying();
            stopTorsoPlaying();
        }
        pcControl.onAction(ListenerKey.MOVE_FORWARD, false, 1);
    }
}

If the computePath() successfully computes a new path, the path variable of the NavMeshPathfinder will no longer be null. The update loop of the NavigationControl checks this path variable, every iteration that wayPosition is null, by calling the getNextWaypoint() method. If the path has another waypoint, it will advance to the next position in the path and set the wayPosition variable of the NavigationControl to that position.

} else if (!isPathfinding() && getNextWaypoint() != null
        && !isAtGoalWaypoint()) {
    ...
    //advance to next waypoint
    goToNextWaypoint();
    setWayPosition(new Vector3f(getWaypointPosition()));
    ...
}
Remember, the first waypoint in the path is always the spatials current position. This is why you always advance the position first.

On the next iteration of the controls update() method, it sees that wayPosition is no longer null and calculates the distance from the spatials current position to the wayPosition.

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 it’s greater than the distance specified, it will setViewDirection() of the PCControl (which extends BetterCharacterControl) and then notify the PCControl that the spatial can move by calling the controls onAction() method directly.

if (getWayPosition() != null) {
    ...
    //move char between waypoints untill waypoint reached then set null
    if (distance > .25f) {
        Vector2f direction = waypoint2D.subtract(aiPosition);
        direction.mult(tpf);
        pcControl.setViewDirection(new Vector3f(direction.x, 0,
                direction.y).normalize());
        pcControl.onAction(ListenerKey.MOVE_FORWARD, true, 1);
    } else {
        ...
    }
}

It’s up to the NavigationControl to determine when the character should stop moving. Each time the spatial reaches a point that is less than the specified distance, it sets the wayPosition to null.

if (distance > .25f) {
    ...
} else {
    setWayPosition(null);
}

If the path position has not yet reached the end, it will once again be advance to the next waypoint in the path and update the wayPosition.

} else if (!isPathfinding() && getNextWaypoint() != null
        && !isAtGoalWaypoint()) {
    ...
    //advance to next waypoint
    goToNextWaypoint();
    setWayPosition(new Vector3f(getWaypointPosition()));
    ...
}

When the last waypoint is reached, the NavigationControl notifies the PCControl that the spatial can no longer move.

} else {
    ...
    pcControl.onAction(ListenerKey.MOVE_FORWARD, false, 1);
}

The PCControl class handles the actual movement of the spatial in its update() loop. It does this by checking the forward variable every iteration. This variable is set when you call the onAction() method from the NavigationControl update loop.

PCControl ActionListener
@Override
public void onAction(String name, boolean isPressed, float tpf) {
    if (name.equals(ListenerKey.MOVE_FORWARD)) {
        forward = isPressed;
    }
}
PCControl update() loop
@Override
public void update(float tpf) {
    super.update(tpf);
    this.moveSpeed = 0;
    walkDirection.set(0, 0, 0);
    if (forward) {
        Vector3f modelForwardDir = spatial.getWorldRotation().mult(Vector3f.UNIT_Z);
        position = getPositionType();
        for (EnumPosition pos : EnumPosition.values()) {
            if (pos.position() == position) {
                switch (pos) {
                    case POS_RUNNING:
                        moveSpeed = EnumPosition.POS_RUNNING.speed();
                        break;
                    default:
                        moveSpeed = 0f;
                        break;
                }
            }
        }
        walkDirection.addLocal(modelForwardDir.mult(moveSpeed));
    }
    setWalkDirection(walkDirection);
}

The PCControl will then set the walk direction, based off spatials world rotation, and set the speed.

Conclusion

The intent of this tutorial was to give you a general breakdown of how the Jme3AI navigation system works as well as demonstrate how flexible its implementation is. All the code in this tutorial is free for your use and can be found in the jme3 documentation repository. The implementations design is such that you can easily change each of the parameters and then visually see how they affect the NavMesh. If you have questions or suggestions on improving this tutorial you can do so in the jMonkeyEngine forum.

Other AI Options

There are other jME3 specific options available you can read about in the wiki under the topic Artificial Intelligence (AI).

Further Reading


1. Path-finding means computing the shortest route between two points. Usually mazes.
2. Path-following is taking a path that already exists and then following that path.