= jMonkeyEngine Artificial Intelligence
:revnumber: 2.1
:revdate: 2020/07/24



Most games written need some type of link:https://en.wikipedia.org/wiki/Artificial_intelligence_(video_games)[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 link:https://en.wikipedia.org/wiki/Navigation_mesh[Navigation Mesh] library using link:https://en.wikipedia.org/wiki/Pathfinding[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: link:https://hub.jmonkeyengine.org/t/ai-plugin-now-with-navmesh-pathfinding/24644[AI plugin now with NavMesh path-finding].


== Requirements

*  link:https://github.com/MeFisto94/jme3-artificial-intelligence/releases[jme3 Artificial Intelligence Library] - The library and javaDocs for jme3AI. This is also where you can report problems or help in maintaining the library.
*  link:https://github.com/stevefsp/critterai/releases[CritterAI] - Stephen Pratt's link:http://www.critterai.org/projects/nmgen_study/[NMGen Study] project files to generate the navmesh.
*  To get the assets (3D models) used in this example, add the <<sdk:sample_code.adoc#jme3testdata-assets,jME3-testdata.jar>> to your classpath.
*  Java SDK 8+.

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

*  link:http://www.critterai.org/projects/nmgen_study/config.html[Configuration Parameters]


== Use Example


The jme3 Artificial Intelligence Library contains:

*  NavMesh - A Navigation Mesh path-finding AI system using the link:https://en.wikipedia.org/wiki/A*_search_algorithm[A*] algorithm.footnote:[Path-finding means computing the shortest route between two points. Usually mazes.]
*  Steering - The foundations of an link:http://natureofcode.com/book/chapter-6-autonomous-agents/[Autonomous Agent] system that uses path-following and forces to move a character through its environment. Includes a test case as well.footnote:[Path-following is taking a path that already exists and then following that path.] 

[NOTE]
====
This scope of this tutorial is restricted to the NavMesh part of the library and expands upon the lessons taught in the xref:tutorials:beginner/beginner.adoc[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  link:https://github.com/jMonkeyEngine/doc-examples/tree/master/src/com/jme3/examples/jme3ai[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.


== NavMesh Creation


The first thing you need for path-finding is a navigation mesh. There are two ways to generate the NavMesh, procedural or the jMonkey link:https://github.com/jMonkeyEngine/sdk/releases[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 btn:[RMB] selecting the file in your assets folder and choosing `Edit Terrain` or `Edit in SceneComposer`.
*  Once open, btn:[RMB] select the root node in the `SceneExplorer` and then select `menu: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,Requirements>>.

.Parameter Insight
The jme3AI system uses CritterAI, which is based off link:https://github.com/recastnavigation/recastnavigation[Recast and Detour] navigation. The author of Recast lays out a few specific rules for NavMesh creation in this link:http://digestingduck.blogspot.dk/2009/08/recast-settings-uncovered.html[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.

NOTE: A summary of the parameter effects is included in the comments of the link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/ai/NavMeshState.java[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.

CAUTION: 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.

TIP: 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 link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/Jme3AI.java[Jme3AI.java] file, you will see I use a xref:core:app/state/application_states.adoc#baseappstate[BaseAppState] named link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/ai/NavMeshState.java[NavMeshState.java] which creates a `generator` object and builds the `NavMesh` new every time the program is ran.

.Jme3AI constructor
[source, java]
----
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.

[source, java]
----
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
[source, java]
----
/**
 * 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 link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/ai/NavMeshGenerator.java[NavMeshGenerator] object and then use it to set the parameters for the NavMesh.

[source, java]
----
generator = new NavMeshGenerator();
...
generator.setCellSize(.25f);
...
----

In our next step we create an IntermediateData object.

[source, java]
----
//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 link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/ai/NavMeshState.java[NavMeshState.java] file is the helper method `findGeometries`.

[source, java]
----
//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.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
Geometry geom = new Geometry(DataKey.NAVMESH);
geom.setMesh(navMesh);
----

Now that you have your Mesh you should save it.

[source, java]
----
//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 link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/ai/NavigationControl.java[NavigationControl] constructor. This tutorial uses a <<core:app/state/application_states.adoc#baseappstate,BaseAppState>> for model loading so access to the `Application` class is built in.

[source, java]
----
//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;
----

[NOTE]

====
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.

[source, java]
----
public NavigationControl(NavMesh navMesh) {
  ...
}
----

====

=== Communicating with NavigationControl

This tutorial makes use of the xref:tutorials:beginner/hello_picking.adoc[Hello Picking] and <<core:input/mouse_picking.adoc#pick-a-target-using-the-mouse-pointer,Mouse Picking>> tutorials so you should already be familiar with this method for picking and how to add the xref:tutorials:beginner/hello_input_system.adoc[input mappings] to your game. How you implement your ActionListener is up to you.

.PCState ActionListener
[source, java]
----
    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,

[source, java]
----
picked.setTarget(closest.getContactPoint());
----

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

[source, java]
----
//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`.


=== NavigationControl


The link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/ai/NavigationControl.java[NavigationControl] is a xref:core:scene/control/custom_controls.adoc[custom control] that extends the link:https://github.com/MeFisto94/jme3-artificial-intelligence/blob/master/AI/src/com/jme3/ai/navmesh/NavMeshPathfinder.java[NavMeshPathFinder] class of the Jme3AI library and implements the `Pickable` interface.

[source, java]
----
public class NavigationControl extends NavMeshPathfinder implements Control,
        JmeCloneable, Pickable {
}
----

The link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/interfaces/Pickable.java[Pickable] interface is straightforward and its sole purpose in this implementation is to communicate changes made to the pick target.

.Pickable Interface implementation
[source, java]
----
/**
 * @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.

[source, java]
----
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.

[source, java]
----
if (spatial == null) {
    shutdownAndAwaitTermination(executor);
    ...
} else {
    ...
}
----

.Executor shutdown process
[source, java]
----
//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 <<physics:control/walking_character.adoc#bettercharactercontrol,BetterCharacterControl>> class. In this implementation, this is done in the link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/controls/PCControl.java[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.

[source, java]
----
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
[source, java]
----
//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.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
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

[source, java]
----
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
[source, java]
----
@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.

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

IMPORTANT: 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`.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
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.

[source, java]
----
} 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.

[source, java]
----
} else {
    ...
    pcControl.onAction(ListenerKey.MOVE_FORWARD, false, 1);
}
----

The link:https://github.com/jMonkeyEngine/doc-examples/blob/master/src/com/jme3/examples/jme3ai/controls/PCControl.java[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
[source, java]
----
@Override
public void onAction(String name, boolean isPressed, float tpf) {
    if (name.equals(ListenerKey.MOVE_FORWARD)) {
        forward = isPressed;
    }
}
----


.PCControl update() loop
[source, java]
----
@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 link:https://github.com/jMonkeyEngine/doc-examples[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 link:https://hub.jmonkeyengine.org/[jMonkeyEngine forum].

== Other AI Options

There are other jME3 specific options available you can read about in the wiki under the topic link:https://wiki.jmonkeyengine.org/docs/jme3.html#artificial-intelligence-ai[Artificial Intelligence (AI)].


== Further Reading

*  link:{attachmentsdir}/Astar.pdf[A* path-finding for Beginners] by Patrick Lester
*  link:http://natureofcode.com/book/[The Nature of Code] by Daniel Shiffman
*  link:http://www.red3d.com/cwr/steer/gdc99/[Steering Behaviors For Autonomous Characters] by Craig W. Reynolds
*  link:http://www.critterai.org/projects/nmgen_study/[Study: Navigation Mesh Generation Java] by Stephen Pratt
