"Dynamic" NavMesh

[capdevon]

hi everyone,
I started studying the jme3-recast4j library code. I compiled and launched the demo project.
The result looks very promising and the documentation is well detailed.

Tiled NavMesh | jMonkeyEngine

It seems that the source code is compatible up to version recast4j-1.2.8 released on January 24, 2021

dependencies {
    ...
    
    implementation 'org.recast4j:parent:1.2.8'
    implementation 'org.recast4j:detour-tile-cache:1.2.8'
    implementation 'org.recast4j:detour-crowd:1.2.8'
    implementation 'org.recast4j:detour-extras:1.2.8'
    implementation 'org.recast4j:recast:1.2.8'
    implementation 'org.recast4j:detour:1.2.8'
}

The latest version 1.5.1 of June 17, 2021 broke the backward compatibility.

Release 1.5.1 · ppiastucki/recast4j

@mitm I noticed that the DetourMoveControl class probably uses a more updated version of the recast4j library. Could you provide us the RecastMeshGenState class to understand how the NavMesh is generated?

I would like to know how other people have used this library and if they can provide other sample material or a personal opinion.

[oxplay2]

you know that you can even change map during game, and re-generate single Tile in reacst thats nice.

[capdevon]

Very interesting. Can you give me some code examples or a demonstration video? I’d like to learn more about the capabilities of the library by looking at the contexts in which it was used. I am studying the demo to identify the main objects that are used to create a NavMesh. I’m doing some testing, updating the libraries, changing the variables and moving some code…

Edit:
I created a single working project with all the source files and all the latest versions of the libraries.
I refactored a few classes to make the code easier to read.

Anyone wishing to contribute is welcome. I hope it can be a good starting point for anyone who wants to start studying this library. If an official library for the engine were created from here it would be really cool! Thank you very much @mitm and @MeFisto94 for the excellent work they have done and for the knowledge they have shared.

GitHub - capdevon/jme3-recast4j-test-1

[mitm]

Sorry for not getting back but I am not kidding when I say no time for anything. Things are getting dragged out but the end is now in sight. I am looking forward to getting back to work on jmonkey projects.
if you need anything else it will have to wait till I get back to this computer on Monday.

This is way to large to post one piece so I will try to break it up in a reasoned way. You maty recognize some of it in the demo. This is only building a one tile mesh just like you get with jmeai. mefistos library incorporates some of these ideas but in a way more efficient and user friendly way. jme3-recast4j, even in current state, is by far the best way to go.

What sucks is jme3-recast4j is almost done, like 90%, only needed to refactor some of the code to make it really shine.

RecastMeshGenState.java

package mygame.recast;

import com.jme3.app.Application;
import com.jme3.app.SimpleApplication;
import com.jme3.app.state.BaseAppState;
import com.jme3.asset.AssetKey;
import com.jme3.export.binary.BinaryExporter;
import com.jme3.material.Material;
import com.jme3.math.ColorRGBA;
import com.jme3.math.FastMath;
import com.jme3.math.Triangle;
import com.jme3.math.Vector3f;
import com.jme3.scene.Geometry;
import com.jme3.scene.Mesh;
import com.jme3.scene.Node;
import com.jme3.scene.Spatial;
import com.jme3.scene.Spatial.CullHint;
import com.jme3.scene.VertexBuffer;
import com.jme3.terrain.Terrain;
import com.jme3.util.BufferUtils;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.FloatBuffer;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;
import jme3tools.optimize.GeometryBatchFactory;
import org.recast4j.detour.NavMeshBuilder;
import org.recast4j.detour.NavMeshDataCreateParams;
import org.recast4j.recast.PolyMesh;
import org.recast4j.recast.PolyMeshDetail;
import org.recast4j.recast.RecastConfig;
import org.recast4j.recast.RecastConstants.PartitionType;
import org.recast4j.detour.MeshData;
import org.recast4j.detour.NavMesh;
import org.recast4j.detour.NavMeshParams;
import org.recast4j.recast.CompactHeightfield;
import org.recast4j.recast.Context;
import org.recast4j.recast.ContourSet;
import org.recast4j.recast.Heightfield;
import org.recast4j.recast.Recast;
import org.recast4j.recast.RecastArea;
import org.recast4j.recast.RecastBuilder;
import org.recast4j.recast.RecastBuilder.RecastBuilderProgressListener;
import org.recast4j.recast.RecastBuilder.RecastBuilderResult;
import org.recast4j.recast.RecastBuilderConfig;
import org.recast4j.recast.RecastConstants;
import static org.recast4j.recast.RecastConstants.RC_MESH_NULL_IDX;
import org.recast4j.recast.RecastContour;
import org.recast4j.recast.RecastFilter;
import org.recast4j.recast.RecastMesh;
import org.recast4j.recast.RecastMeshDetail;
import org.recast4j.recast.RecastRasterization;
import org.recast4j.recast.RecastRegion;
import static org.recast4j.recast.RecastVectors.copy;
import org.recast4j.recast.geom.InputGeomProvider;
import org.recast4j.recast.geom.SimpleInputGeomProvider;
import org.recast4j.recast.geom.TriMesh;

/**
 *
 * @author mitm
 */
public class RecastMeshGenState extends BaseAppState {
    //Settings Explained.
    //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=0.4, h=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 ourdoor 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 walkableHeight, 
    //which defines the height of the agent in voxels, that is ceil(h/ch).
    
    //The walkableClimb defines how high steps the character can climb. In most 
    //levels I have encountered so far, this means almost waist height! Lazy 
    //level designers. If you use down projection+capsule for NPC collision 
    //detection you may derive a good value from that representation. Again this 
    //value is in voxels, remember to use ch instead of cs, ceil(maxClimb/ch).
    
    //The parameter walkableRadius defines the agent radius in voxels, 
    //ceil(r/cs). If this value is greater than zero, the navmesh will be 
    //shrunken by the agent radius. The shrinking is done in voxel 
    //representation, so some precision is lost there. This step allows simpler 
    //checks at runtime. If you want to have tight fit navmesh, use zero radius.
    
    //The parameter walkableSlopeAngle is used before voxelization to check if 
    //the slope of a triangle is too high and those polygons will be given 
    //non-walkable flag. You may tweak the triangle flags yourself too, for 
    //example if you wish to make certain objects or materials non-walkable. The 
    //parameter is in radians.
    
    //In certain cases really long outer edges may decrease the triangulation 
    //results. Sometimes this can be remedied by just tesselating the long edges. 
    //The parameter maxEdgeLen defines the max edge length in voxel coordinates. 
    //A good value for maxEdgeLen is something like walkableRadius*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 
    //happens to create those few extra vertices which makes the tesselation 
    //better.
    
    //When the rasterized areas are converted back to vectorized representation 
    //the maxSimplificationError describes how loosely the simplification is 
    //done (the simplification is Douglas-Peucker, so this value describes the 
    //max deviation in voxels). Good values are between 1.1-1.5 (1.3 usually 
    //yield good results). If the value is less, some strair-casing starts to 
    //appear at the edges and if it is more than that, the simplification starts 
    //to cut some corners.
    //Watershed partitioning is really prone to noise in the input distance 
    //field. In order to get nicer ares, the ares are merged and small isolated 
    //areas are removed after the water shed partitioning. The parameter 
    //minRegionSize describes the minimum isolated region size that is still 
    //kept. 
    //A region is removed if the regionVoxelCount < minRegionSize*minRegionSize.
    //The triangulation process greatly benefits from small local data. The 
    //parameter mergeRegionSize controls how large regions can be still merged. 
    //If regionVoxelCount > mergeRegionSize*mergeRegionSize the region is not 
    //allowed to be merged with another region anymore.
    //Yeah, I know these last two values are a bit weirdly defined. If you are 
    //using tiled preprocess with relatively small tile size, the merge value 
    //can be really high. If you have followed the above steps, then I'd 
    //recommend using the demo values for minRegionSize and mergeRegionSize. If 
    //you see small patched missing here and there, you could lower the 
    //minRegionSize.
    //Mikko Mononen
    /**
     * ***********************************************************************
     */
    //The width/height size of tile's on the xz-plane.
    //[Limit: >= 0] [Units: vx]
    private final int m_tileSize = 64;
    //The size of the non-navigable border around the heightfield.    
    //>=0
    private final int m_borderSize = 0;
    //The width and depth resolution used when sampling the source geometry. The 
    //width and depth of the cell columns that make up voxel fields.
    //Cells are laid out on the width/depth plane of voxel fields. Width is 
    //associated with the x-axis of the source geometry. Depth is associated 
    //with the z-axis.
    //A lower value allows for the generated mesh to more closely match the 
    //source geometry, but at a higher processing and memory cost.
    //Small cell size needed to allow mesh to travel up stairs.
    //Adjust m_cellSize and m_cellHeight for contour simplification exceptions.
    //[Limit: > 0] [Units: wu], outdoors = m_agentRadius/2, indoors = m_agentRadius/3, m_cellSize = 
    //m_agentRadius for very small cells.
    private final float m_cellSize = 0.2f;
    //Height is associated with the y-axis of the source geometry.
    //A smaller value allows for the final mesh to more closely match the source 
    //geometry at a potentially higher processing cost. (Unlike cellSize, using 
    //a lower value for cellHeight does not significantly increase memory use.)
    //This is a core configuration value that impacts almost all other 
    //parameters. 
    //m_agentHeight, m_agentMaxClimb, and m_detailSampleMaxError will 
    //need to be greater than this value in order to function correctly. 
    //m_agentMaxClimb is especially susceptible to impact from the value of 
    //m_cellHeight.
    //[Limit: > 0] [Units: wu], m_cellSize/2
    private final float m_cellHeight = 0.1f;
    //Represents the minimum floor to ceiling height that will still allow the 
    //floor area to be considered traversable. It permits detection of overhangs 
    //in the geometry that make the geometry below become un-walkable. It can 
    //also be thought of as the maximum agent height.
    //This value should be at least two times the value of m_cellHeight in order 
    //to get good results. 
    //[Limit: >= 3][Units: vx] 
    private final float m_agentHeight = 2.0f;
    //Represents the closest any part of a mesh can get to an obstruction in the 
    //source geometry.
    //Usually this value is set to the maximum bounding radius of agents 
    //utilizing the meshes for navigation decisions.
    //This value must be greater than the m_cellSize to have an effect.
    //[Limit: >=0] [Units:vx]
    private final float m_agentRadius = 0.5f;
    //Represents the maximum ledge height that is considered to still be 
    //traversable.
    //Prevents minor deviations in height from improperly showing as 
    //obstructions. Permits detection of stair-like structures, curbs, etc.
    //m_agentMaxClimb should be greater than two times m_cellHeight. 
    //(m_agentMaxClimb > m_cellHeight * 2) Otherwise the resolution of the voxel 
    //field may not be high enough to accurately detect traversable ledges. 
    //Ledges may merge, effectively doubling their step height. This is 
    //especially an issue for stairways. 
    //[Limit: >=0] [Units: vx], m_agentMaxClimb/m_cellHeight = voxels.
    private final float m_agentMaxClimb = .5f;
    //The maximum slope that is considered traversable.
    //[Limits: 0 <= value < 90] [Units: Degrees]  
    private final float m_agentMaxSlope = 50.0f;
    //The minimum region size for unconnected (island) regions.
    //[Limit: >=0] [Units: vx]
    private final int m_regionMinSize = 8;
    //Any regions smaller than this size will, if possible, be merged with 
    //larger regions.
    //[Limit: >=0] [Units: vx] 
    private final int m_regionMergeSize = 20;
    //The maximum length of polygon edges that represent the border of meshes.
    //Adjust to decrease dangling errors.
    //[Limit: >=0] [Units: vx], m_agentRadius * 8
    private final float m_edgeMaxLen = 4.0f;
    //The maximum distance the edges of meshes may deviate from the source 
    //geometry.
    //A lower value will result in mesh edges following the xz-plane geometry 
    //contour more accurately at the expense of an increased triangle count.
    //1.1 takes 2x as long to generate mesh as 1.5
    //[Limit: >=0][Units: vx], 1.1 to 1.5 for best results.
    private final float m_edgeMaxError = 1.3f;
    //The maximum number of vertices per polygon for polygons generated during 
    //the voxel to polygon conversion process.
    //[Limit: >= 3] 
    private final int m_vertsPerPoly = 6;
    //Sets the sampling distance to use when matching the detail mesh to the 
    //surface of the original geometry.
    //Higher values result in a detail mesh that conforms more closely to the 
    //original geometry's surface at the cost of a higher final triangle count 
    //and higher processing cost.
    //The difference between this parameter and m_edgeMaxError is that this 
    //parameter operates on the height rather than the xz-plane. It also matches 
    //the entire detail mesh surface to the contour of the original geometry. 
    //m_edgeMaxError only matches edges of meshes to the contour of the original 
    //geometry. 
    //Increase to reduce dangling errors at the cost of accuracy.
    //[Limits: 0 or >= 0.9] [Units: wu] 
    private final float m_detailSampleDist = 5.0f;
    //The maximum distance the surface of the detail mesh may deviate from the 
    //surface of the original geometry.
    //Increase to reduce dangling errors at the cost of accuracy.
    //[Limit: >=0] [Units: wu]
    private final float m_detailSampleMaxError = 5.0f;
    private final PartitionType m_partitionType = PartitionType.WATERSHED;
    
    private NavMesh navMesh;
    private SimpleApplication app;
    private final String sep = File.separator;
    private final Path exportPath = Paths.get("assets" + sep + "Scenes" + sep + "Recast");
    private final String exportFilename = exportPath + sep + "navmesh.obj";
    private static final Logger LOG = Logger.getLogger(RecastMeshGenState.class.getName());
    
    @Override
    protected void initialize(Application app) {
        this.app = (SimpleApplication) app;
//        soloNavMeshBuilder();
//        tiledNavMeshBuilder();
//        this.app.getRootNode().depthFirstTraversal((Spatial spat) -> {
//            System.out.println("SGV:" + spat);
//        });
    }

    @Override
    protected void cleanup(Application app) {
        //TODO: clean up what you initialized in the initialize method,
        //e.g. remove all spatials from rootNode
    }

    //onEnable()/onDisable() can be used for managing things that should 
    //only exist while the state is enabled. Prime examples would be scene 
    //graph attachment or input listener attachment.
    @Override
    protected void onEnable() {
        //Called when the state is fully enabled, ie: is attached and 
        //isEnabled() is true or when the setEnabled() status changes after the 
        //state is attached.
    }

    @Override
    protected void onDisable() {
        //Called when the state was previously enabled but is now disabled 
        //either because setEnabled(false) was called or the state is being 
        //cleaned up.
    }

    @Override
    public void update(float tpf) {
        //TODO: implement behavior during runtime
    }
    private void soloNavMeshBuilder() {

        Mesh mesh = new Mesh();
        GeometryBatchFactory.mergeGeometries(findGeometries(app.getRootNode(),
                new LinkedList<>()), mesh);
        List<Float> vertexPositions = getVertices(mesh);
        List<Integer> indices = getIndices(mesh);
        InputGeomProvider geomProvider = new SimpleInputGeomProvider(vertexPositions, indices);
        long time1 = System.nanoTime();
        float[] bmin = geomProvider.getMeshBoundsMin();
        float[] bmax = geomProvider.getMeshBoundsMax();

        // Step 1. Initialize build config.
        RecastConfig cfg = new RecastConfig(m_partitionType, m_cellSize,
                m_cellHeight, m_agentHeight, m_agentRadius,
                m_agentMaxClimb, m_agentMaxSlope, m_regionMinSize,
                m_regionMergeSize, m_edgeMaxLen, m_edgeMaxError,
                m_vertsPerPoly, m_detailSampleDist, m_detailSampleMaxError,
                m_tileSize, SampleAreaModifications.SAMPLE_AREAMOD_GROUND);
        RecastBuilderConfig bcfg = new RecastBuilderConfig(cfg, bmin, bmax);
        Context m_ctx = new Context();

        // Step 2. Rasterize input polygon soup.
        // Allocate voxel heightfield where we rasterize our input data to.
        Heightfield m_solid = new Heightfield(bcfg.width, bcfg.height, bcfg.bmin,
                bcfg.bmax, cfg.cs, cfg.ch);

        for (TriMesh geom : geomProvider.meshes()) {
            float[] verts = geom.getVerts();
            int[] tris = geom.getTris();
            int ntris = tris.length / 3;
            // Allocate array that can hold triangle area types.
            // If you have multiple meshes you need to process, allocate
            // and array which can hold the max number of triangles you need to
            // process.

            // Find triangles which are walkable based on their slope and rasterize
            // them.
            // If your input data is multiple meshes, you can transform them here,
            // calculate
            // the are type for each of the meshes and rasterize them.
            int[] m_triareas = Recast.markWalkableTriangles(m_ctx, cfg.walkableSlopeAngle, verts, tris, ntris, cfg.walkableAreaMod);
//            System.out.println("tris length " +  + tris.length + " " + Arrays.toString(tris));
//            System.out.println("m_triareas length " + m_triareas.length + " " + Arrays.toString(m_triareas));

            RecastRasterization.rasterizeTriangles(m_ctx, verts, tris, m_triareas, ntris, m_solid, cfg.walkableClimb);
        }
        // Step 3. Filter walkables surfaces.
        // Once all geometry is rasterized, we do initial pass of filtering to
        // remove unwanted overhangs caused by the conservative rasterization
        // as well as filter spans where the character cannot possibly stand.
        RecastFilter.filterLowHangingWalkableObstacles(m_ctx, cfg.walkableClimb, m_solid);
        RecastFilter.filterLedgeSpans(m_ctx, cfg.walkableHeight, cfg.walkableClimb, m_solid);
        RecastFilter.filterWalkableLowHeightSpans(m_ctx, cfg.walkableHeight, m_solid);

        // Step 4. Partition walkable surface to simple regions.
        // Compact the heightfield so that it is faster to handle from now on.
        // This will result more cache coherent data as well as the neighbours
        // between walkable cells will be calculated.
        CompactHeightfield m_chf = Recast.buildCompactHeightfield(m_ctx,cfg.walkableHeight, cfg.walkableClimb, m_solid);

        // Erode the walkable area by agent radius.
        RecastArea.erodeWalkableArea(m_ctx, cfg.walkableRadius, m_chf);

        // (Optional) Mark areas.
        /*
         * ConvexVolume vols = m_geom->getConvexVolumes(); for (int i = 0; i < m_geom->getConvexVolumeCount(); ++i)
         * rcMarkConvexPolyArea(m_ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned
         * char)vols[i].area, *m_chf);
         */

        // Partition the heightfield so that we can use simple algorithm later
        // to triangulate the walkable areas.
        // There are 3 martitioning methods, each with some pros and cons:
        // 1) Watershed partitioning
        // - the classic Recast partitioning
        // - creates the nicest tessellation
        // - usually slowest
        // - partitions the heightfield into nice regions without holes or
        // overlaps
        // - the are some corner cases where this method creates produces holes
        // and overlaps
        // - holes may appear when a small obstacles is close to large open area
        // (triangulation can handle this)
        // - overlaps may occur if you have narrow spiral corridors (i.e
        // stairs), this make triangulation to fail
        // * generally the best choice if you precompute the nacmesh, use this
        // if you have large open areas
        // 2) Monotone partioning
        // - fastest
        // - partitions the heightfield into regions without holes and overlaps
        // (guaranteed)
        // - creates long thin polygons, which sometimes causes paths with
        // detours
        // * use this if you want fast navmesh generation
        // 3) Layer partitoining
        // - quite fast
        // - partitions the heighfield into non-overlapping regions
        // - relies on the triangulation code to cope with holes (thus slower
        // than monotone partitioning)
        // - produces better triangles than monotone partitioning
        // - does not have the corner cases of watershed partitioning
        // - can be slow and create a bit ugly tessellation (still better than
        // monotone)
        // if you have large open areas with small obstacles (not a problem if
        // you use tiles)
        // * good choice to use for tiled navmesh with medium and small sized
        // tiles

[mitm]

        if (m_partitionType == PartitionType.WATERSHED) {
                // Prepare for region partitioning, by calculating distance field
                // along the walkable surface.
                RecastRegion.buildDistanceField(m_ctx, m_chf);
                // Partition the walkable surface into simple regions without holes.
                RecastRegion.buildRegions(m_ctx, m_chf, m_borderSize, cfg.minRegionArea, cfg.mergeRegionArea);
        } else if (m_partitionType == PartitionType.MONOTONE) {
                // Partition the walkable surface into simple regions without holes.
                // Monotone partitioning does not need distancefield.
                RecastRegion.buildRegionsMonotone(m_ctx, m_chf, m_borderSize, cfg.minRegionArea, cfg.mergeRegionArea);
        } else {
                // Partition the walkable surface into simple regions without holes.
                RecastRegion.buildLayerRegions(m_ctx, m_chf, m_borderSize, cfg.minRegionArea);
        }

        // Step 5. Trace and simplify region contours.
        // Create contours.
        ContourSet m_cset = RecastContour.buildContours(m_ctx, m_chf, cfg.maxSimplificationError, cfg.maxEdgeLen, RecastConstants.RC_CONTOUR_TESS_WALL_EDGES);
        // Step 6. Build polygons mesh from contours.
        // Build polygon navmesh from the contours.
        PolyMesh m_pmesh = RecastMesh.buildPolyMesh(m_ctx, m_cset, cfg.maxVertsPerPoly);

        // Step 7. Create detail mesh which allows to access approximate height
        // on each polygon.
        PolyMeshDetail m_dmesh = RecastMeshDetail.buildPolyMeshDetail(m_ctx,
                m_pmesh, m_chf, cfg.detailSampleDist, cfg.detailSampleMaxError);
        long time2 = System.nanoTime() - time1;
        System.out.println(exportFilename + " : " + m_partitionType + "  "
                + TimeUnit.SECONDS.convert(time2, TimeUnit.NANOSECONDS) + " s");
        exportObj(exportFilename.substring(0, exportFilename.lastIndexOf('.'))
                + "_debug.obj", m_dmesh);

        //must set flags for navigation controls to work
        for (int i = 0; i < m_pmesh.npolys; ++i) {
            m_pmesh.flags[i] = SampleAreaModifications.SAMPLE_POLYFLAGS_WALK;
        }
//        NavMeshDataCreateParams params = new NavMeshDataCreateParams();
        NavMeshDataCreateParams params = new NavMeshDataParameters();
        
        params.verts = m_pmesh.verts;
        params.vertCount = m_pmesh.nverts;
        params.polys = m_pmesh.polys;
        params.polyAreas = m_pmesh.areas;
        params.polyFlags = m_pmesh.flags;
        params.polyCount = m_pmesh.npolys;
        params.nvp = m_pmesh.nvp;
        params.detailMeshes = m_dmesh.meshes;
        params.detailVerts = m_dmesh.verts;
        params.detailVertsCount = m_dmesh.nverts;
        params.detailTris = m_dmesh.tris;
        params.detailTriCount = m_dmesh.ntris;
        params.walkableHeight = m_agentHeight;
        params.walkableRadius = m_agentRadius;
        params.walkableClimb = m_agentMaxClimb;
        params.bmin = m_pmesh.bmin;
        params.bmax = m_pmesh.bmax;
        params.cs = m_cellSize;
        params.ch = m_cellHeight;
        params.buildBvTree = true;
        
        MeshData meshData = NavMeshBuilder.createNavMeshData(params);
        navMesh = new NavMesh(meshData, params.nvp, 0);
        
        //create object to save solo NavMesh parameters
        MeshParameters meshParams = new MeshParameters();
        meshParams.addMeshDataParameters((NavMeshDataParameters) params);
        //save NavMesh parameters as .j3o
        saveNavMesh(meshParams, exportFilename.substring(0, exportFilename.lastIndexOf('.'))
                                                            + "_solo_C" + m_tileSize);

        //display NavMesh.obj
//        showDebugMesh("Scenes/Recast/recastmesh_debug.obj", ColorRGBA.Green);
        //save as obj no normals
//        saveObj(exportFilename.substring(0, exportFilename.lastIndexOf('.')) + "_solo_" + m_partitionType + "_C" + m_tileSize + "_detail.obj", m_dmesh);
        saveObj(exportFilename.substring(0, exportFilename.lastIndexOf('.')) + "_solo_" + m_partitionType + "_C" + m_tileSize + ".obj", m_pmesh);
        //save as obj with normals
        exportObj(exportFilename.substring(0, exportFilename.lastIndexOf('.')) + "_solo_" + m_partitionType + "_C" + m_tileSize + "_detail.obj", m_dmesh);
    }

    private void tiledNavMeshBuilder() {
        Mesh mesh = new Mesh();        
        GeometryBatchFactory.mergeGeometries(findGeometries(app.getRootNode(),
                new LinkedList<>()), mesh);
        List<Float> vertexPositions = getVertices(mesh);
        List<Integer> indices = getIndices(mesh);
        InputGeomProvider geom = new SimpleInputGeomProvider(vertexPositions, indices);
        long time1 = System.nanoTime();

        // Initialize build config.
        RecastConfig cfg = new RecastConfig(m_partitionType, m_cellSize,
                m_cellHeight, m_agentHeight, m_agentRadius,
                m_agentMaxClimb, m_agentMaxSlope, m_regionMinSize,
                m_regionMergeSize, m_edgeMaxLen, m_edgeMaxError,
                m_vertsPerPoly, m_detailSampleDist, m_detailSampleMaxError,
                m_tileSize, SampleAreaModifications.SAMPLE_AREAMOD_GROUND);

        // Build all tiles
//        RecastBuilder builder = new RecastBuilder();
//        time3 = System.nanoTime();
        //uses listener param (this)
        RecastBuilder builder = new RecastBuilder(new ProgressListen());
        //use listener when calling buildTiles
        RecastBuilderResult[][] rcResult = builder.buildTiles(geom, cfg, 1);
        long time2 = System.nanoTime() - time1;
        System.out.println(exportFilename + " : " + m_partitionType + "  "
                + TimeUnit.SECONDS.convert(time2, TimeUnit.NANOSECONDS) + " s");

        // Add tiles to nav mesh
        int tw = rcResult.length;
        int th = rcResult[0].length;

        // Create empty nav mesh
//        NavMeshParams navMeshParams = new NavMeshParams();
        NavMeshParams navMeshParams = new NavMeshParameters();
        copy(navMeshParams.orig, geom.getMeshBoundsMin());
        navMeshParams.tileWidth = m_tileSize * m_cellSize;
        navMeshParams.tileHeight = m_tileSize * m_cellSize;
        navMeshParams.maxTiles = tw * th;
        navMeshParams.maxPolys = 32768;
        //Create object to save NavMeshParameters for tiled NavMesh
        MeshParameters meshParams = new MeshParameters();
        meshParams.addMeshParameters((NavMeshParameters) navMeshParams);
        navMesh = new NavMesh(navMeshParams, 6);
        
        List<PolyMeshDetail> dmeshList = new ArrayList<>();

        for (int y = 0; y < th; y++) {
            for (int x = 0; x < tw; x++) {
                PolyMesh pmesh = rcResult[x][y].getMesh();
                if (pmesh.npolys == 0) {
                    continue;
                }
                for (int i = 0; i < pmesh.npolys; ++i) {
                    pmesh.flags[i] = 1;
                }
//                NavMeshDataCreateParams params = new NavMeshDataCreateParams();
                NavMeshDataCreateParams params = new NavMeshDataParameters();
                params.verts = pmesh.verts;
                params.vertCount = pmesh.nverts;
                params.polys = pmesh.polys;
                params.polyAreas = pmesh.areas;
                params.polyFlags = pmesh.flags;
                params.polyCount = pmesh.npolys;
                params.nvp = pmesh.nvp;
                PolyMeshDetail dmesh = rcResult[x][y].getMeshDetail();
                dmeshList.add(dmesh);
                params.detailMeshes = dmesh.meshes;
                params.detailVerts = dmesh.verts;
                params.detailVertsCount = dmesh.nverts;
                params.detailTris = dmesh.tris;
                params.detailTriCount = dmesh.ntris;
                params.walkableHeight = m_agentHeight;
                params.walkableRadius = m_agentRadius;
                params.walkableClimb = m_agentMaxClimb;
                params.bmin = pmesh.bmin;
                params.bmax = pmesh.bmax;
                params.cs = m_cellSize;
                params.ch = m_cellHeight;
                params.tileX = x;
                params.tileY = y;
                params.buildBvTree = true;
                navMesh.addTile(NavMeshBuilder.createNavMeshData(params), 0, 0);
                //Add parameters to the 
                meshParams.addMeshDataParameters((NavMeshDataParameters) params);
            }
        }

        //save NavMesh parameters as .j3o
        saveNavMesh(meshParams, exportFilename.substring(0, exportFilename.lastIndexOf('.')) 
                                + "_tiled_C" + m_tileSize);

        //save NavMesh as .obj
        exportObj(exportFilename.substring(0, exportFilename.lastIndexOf('.'))
                + "_tiled_C" + m_tileSize + ".obj", dmeshList);
        //display NavMesh.obj
//        showDebugMesh("Scenes/Recast/recastmesh_tiled64_debug.obj", ColorRGBA.Green);
    }

    //Merges terrain meshes into one mesh.
    public Mesh terrain2mesh(Terrain terr) {
        float[] heights = terr.getHeightMap();
        int length = heights.length;
        int side = (int) FastMath.sqrt(heights.length);
        float[] vertices = new float[length * 3];
        int[] indices = new int[(side - 1) * (side - 1) * 6];
        
//        Vector3f trans = ((Node) terr).getWorldTranslation().clone();
        Vector3f trans = new Vector3f(0, 0, 0);
        trans.x -= terr.getTerrainSize() / 2.0f;
        trans.z -= terr.getTerrainSize() / 2.0f;
        float offsetX = trans.x;
        float offsetZ = trans.z;      
        
        // do vertices
        int i = 0;
        for (int z = 0; z < side; z++) {
            for (int x = 0; x < side; x++) {
                vertices[i++] = x + offsetX;
                vertices[i++] = heights[z * side + x];
                vertices[i++] = z + offsetZ;
            }
        }
        
        // do indexes
        i = 0;
        for (int z = 0; z < side - 1; z++) {
            for (int x = 0; x < side - 1; x++) {
                // triangle 1
                indices[i++] = z * side + x;
                indices[i++] = (z + 1) * side + x;
                indices[i++] = (z + 1) * side + x + 1;
                // triangle 2
                indices[i++] = z * side + x;
                indices[i++] = (z + 1) * side + x + 1;
                indices[i++] = z * side + x + 1;
            }
        }
        Mesh mesh2 = new Mesh();
        mesh2.setBuffer(VertexBuffer.Type.Position, 3, vertices);
        mesh2.setBuffer(VertexBuffer.Type.Index, 3, indices);
        mesh2.updateBound();
        mesh2.updateCounts();

        return mesh2;
    }

    //Gathers all geometries in supplied node into supplied List. Uses 
    //terrain2mesh 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) {
        for (Iterator<Spatial> it = node.getChildren().iterator(); it.hasNext();) {
            Spatial spatial = it.next();
            if (!spatial.getName().equals("Sky")
                    && !spatial.getName().equals("water")
                    && !spatial.getName().equals("NavMesh") 
                    && !spatial.getName().equals("TerrainA")
                    && !spatial.getName().equals("TerrainB")
                    && !spatial.getName().equals("terrain-terrainC")
                 /* && !spatial.getName().equals("Terrain_C")*/
                    && !spatial.getName().equals("terrainD") 
                  /*&& !spatial.getName().equals("Neo")
                    && !spatial.getName().equals("Platform")
                    && !spatial.getName().equals("Stairs")
                    && !spatial.getName().equals("Stairs90")
                    && !spatial.getName().equals("Stairs180")
                    && !spatial.getName().equals("StairPlat180")
                    && !spatial.getName().equals("Table")
                    && !spatial.getName().equals("Ramp")*/) {

                if (spatial instanceof Geometry) {
                    Mesh clone = ((Geometry) spatial).getMesh().clone();
                    Geometry g = new Geometry("merged" + spatial.getName());
                    g.setMesh(clone);
                    g.setLocalScale(spatial.getWorldScale());
                    g.setLocalRotation(spatial.getWorldRotation());
                    g.setLocalTranslation(spatial.getWorldTranslation().subtract(new Vector3f(0, m_cellHeight, 0)));
                    geoms.add(g);
//                    geoms.add((Geometry) spatial);
                    System.out.println("findGeometries " + spatial.getName());
                } else if (spatial instanceof Node) {
                    if (spatial instanceof Terrain) {
                        //create new merged mesh
                        Mesh merged = terrain2mesh((Terrain) spatial);
                        Geometry g = new Geometry("merged" + spatial.getName());
                        g.setMesh(merged);
                        g.setLocalScale(spatial.getLocalScale());
                        //must offset due to terrain2mesh offsetting
                        g.setLocalTranslation(spatial.getLocalTranslation().subtract(new Vector3f(-0.5f, m_cellHeight, -0.5f)));
                        geoms.add(g);
                        System.out.println("findGeometries " + spatial.getName());
                    } else {
                        findGeometries((Node) spatial, geoms);
                    }
                }
            }
        }
//        System.out.println(geoms);
        return geoms;
    }

    /**
     * Get vertcices of a mesh boxed to Float.
     *
     * @param mesh
     * @return Returns boxed List of vertices.
     */
    private List<Float> getVertices(Mesh mesh) {
        FloatBuffer buffer = mesh.getFloatBuffer(VertexBuffer.Type.Position);
        float[] vertexArray = BufferUtils.getFloatArray(buffer);
        List<Float> vertexList = new ArrayList<>();

        for (float vertex : vertexArray) {
            vertexList.add(vertex);
        }
        return vertexList;
    }

    /**
     * Get all triangles from a mesh boxed to Integer.
     *
     * @param mesh
     * @return Returns boxed List of triangles.
     */
    private List<Integer> getIndices(Mesh mesh) {
        int[] indices = new int[3];
        Integer[] triangles = new Integer[mesh.getTriangleCount() * 3];

        for (int i = 0; i < triangles.length; i += 3) {
            mesh.getTriangle(i / 3, indices);
            triangles[i] = indices[0];
            triangles[i + 1] = indices[1];
            triangles[i + 2] = indices[2];
        }
        //Independent copy so Arrays.asList is garbage collected
        return new ArrayList<>(Arrays.asList(triangles));
    }

    private Vector3f[] getVector3Array(PolyMeshDetail dmesh) {
        Vector3f[] vector3Array = new Vector3f[dmesh.nverts];
        for (int i = 0; i < dmesh.nverts; i++) {
            vector3Array[i] = new Vector3f(dmesh.verts[i * 3],
                    dmesh.verts[i * 3 + 1], dmesh.verts[i * 3 + 2]);
        }
        return vector3Array;
    }
    
    //export obj no normals
    private void saveObj(String filename, PolyMesh mesh) {
        try {
            File file = new File(filename);
            FileWriter fw = new FileWriter(file);
            for (int v = 0; v < mesh.nverts; v++) {
                fw.write("v " + (mesh.bmin[0] + mesh.verts[v * 3] * mesh.cs) + " "
                         + (mesh.bmin[1] + mesh.verts[v * 3 + 1] * mesh.ch) + " "
                         + (mesh.bmin[2] + mesh.verts[v * 3 + 2] * mesh.cs) + "\n");
            }

            for (int i = 0; i < mesh.npolys; i++) {
                int p = i * mesh.nvp * 2;
                fw.write("f ");
                for (int j = 0; j < mesh.nvp; ++j) {
                    int v = mesh.polys[p + j];
                    if (v == RC_MESH_NULL_IDX)
                        break;
                    fw.write((v + 1) + " ");
                }
                fw.write("\n");
            }
            fw.close();
        } catch (Exception e) {
        }
    }

    //export obj no normals
    private void saveObj(String filename, PolyMeshDetail dmesh) {
        try {
            File file = new File(filename);
            FileWriter fw = new FileWriter(file);
            for (int v = 0; v < dmesh.nverts; v++) {
                fw.write("v " + dmesh.verts[v * 3] + " " 
                         + dmesh.verts[v * 3 + 1] + " " 
                         + dmesh.verts[v * 3 + 2] + "\n");
            }

            for (int m = 0; m < dmesh.nmeshes; m++) {
                int vfirst = dmesh.meshes[m * 4];
                int tfirst = dmesh.meshes[m * 4 + 2];
                for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                    fw.write("f " + (vfirst + dmesh.tris[(tfirst + f) * 4] + 1) + " "
                             + (vfirst + dmesh.tris[(tfirst + f) * 4 + 1] + 1) + " "
                             + (vfirst + dmesh.tris[(tfirst + f) * 4 + 2] + 1) + "\n");
                }
            }
            fw.close();
        } catch (Exception e) {
        }
    }

    //export obj with normals
    private void exportObj(String filename, PolyMeshDetail dmesh) {

        File file = new File(filename);
        File dir = file.getParentFile();
        if (!dir.exists()) {
            dir.mkdir();
        }
        try (FileWriter out = new FileWriter(file)) {
            //vertex
            for (int v = 0; v < dmesh.nverts; v++) {
                out.write("v " + dmesh.verts[v * 3] + " "
                        + dmesh.verts[v * 3 + 1] + " "
                        + dmesh.verts[v * 3 + 2] + "\n");
            }
            //vertex normal
            Vector3f[] vector3Array = getVector3Array(dmesh);
            for (int m = 0; m < dmesh.nmeshes; m++) {
                int vfirst = dmesh.meshes[m * 4];
                int tfirst = dmesh.meshes[m * 4 + 2];
                for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                    Vector3f normal = Triangle.computeTriangleNormal(
                            vector3Array[(vfirst + dmesh.tris[(tfirst + f) * 4])],
                            vector3Array[(vfirst + dmesh.tris[(tfirst + f) * 4
                            + 1])],
                            vector3Array[(vfirst + dmesh.tris[(tfirst + f) * 4
                            + 2])],
                            null);
                    out.write("vn " + normal.x + " " + normal.y + " " + normal.z
                            + "\n");
                }
            }
            //face
            int count = 1;
            for (int m = 0; m < dmesh.nmeshes; m++) {
                int vfirst = dmesh.meshes[m * 4];
                int tfirst = dmesh.meshes[m * 4 + 2];
                for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                    out.write("f "
                            + (vfirst + dmesh.tris[(tfirst + f) * 4] + 1)
                            + "//" + count + " "
                            + (vfirst + dmesh.tris[(tfirst + f) * 4 + 1] + 1)
                            + "//" + count + " "
                            + (vfirst + dmesh.tris[(tfirst + f) * 4 + 2] + 1)
                            + "//" + count + "\n");
                    count++;
                }
            }
            out.close();
        } catch (IOException ex) {
            LOG.log(Level.SEVERE, null, ex);
        }
    }

    //export obj with normals
    private void exportObj(String filename, RecastBuilderResult[][] rcResult) {

        File file = new File(filename);
        File dir = file.getParentFile();
        if (!dir.exists()) {
            dir.mkdir();
        }
        try (FileWriter out = new FileWriter(file)) {
            //vertex
            int tw = rcResult.length;
            int th = rcResult[0].length;
            for (int i = 0; i < tw; i++) {
                for (int j = 0; j < th; j++) {
                    PolyMesh pmesh = rcResult[i][j].getMesh();
                    if (pmesh.npolys == 0) {
                        continue;
                    }
                    PolyMeshDetail dmesh = rcResult[i][j].getMeshDetail();
                    for (int v = 0; v < dmesh.nverts; v++) {
                        out.write("v " + dmesh.verts[v * 3] + " "
                                + dmesh.verts[v * 3 + 1] + " "
                                + dmesh.verts[v * 3 + 2] + "\n");
                    }
                }
            }
            //vertex normal
            for (int i = 0; i < tw; i++) {
                for (int j = 0; j < th; j++) {
                    PolyMesh pmesh = rcResult[i][j].getMesh();
                    if (pmesh.npolys == 0) {
                        continue;
                    }

                    PolyMeshDetail dmesh = rcResult[i][j].getMeshDetail();
                    Vector3f[] vector3Array = getVector3Array(dmesh);
                    for (int m = 0; m < dmesh.nmeshes; m++) {
                        int vfirst = dmesh.meshes[m * 4];
                        int tfirst = dmesh.meshes[m * 4 + 2];
                        for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                            Vector3f normal = Triangle.computeTriangleNormal(
                                    vector3Array[(vfirst + dmesh.tris[(tfirst
                                    + f) * 4])],
                                    vector3Array[(vfirst + dmesh.tris[(tfirst
                                    + f) * 4 + 1])],
                                    vector3Array[(vfirst + dmesh.tris[(tfirst
                                    + f) * 4 + 2])],
                                    null);
                            out.write("vn " + normal.x + " " + normal.y + " "
                                    + normal.z + "\n");
                        }
                    }
                }
            }
            //face
            int count = 1;
            int offset = 0;
            for (int i = 0; i < tw; i++) {
                for (int j = 0; j < th; j++) {
                    PolyMesh pmesh = rcResult[i][j].getMesh();
                    if (pmesh.npolys == 0) {
                        continue;
                    }

                    PolyMeshDetail dmesh = rcResult[i][j].getMeshDetail();
                    for (int m = 0; m < dmesh.nmeshes; m++) {
                        int vfirst = dmesh.meshes[m * 4];
                        int tfirst = dmesh.meshes[m * 4 + 2];
                        for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                            out.write("f "
                                    + ((vfirst + dmesh.tris[(tfirst + f) * 4]
                                    + 1) + offset)
                                    + "//" + count + " "
                                    + ((vfirst
                                    + dmesh.tris[(tfirst + f) * 4 + 1] + 1)
                                    + offset)
                                    + "//" + count + " "
                                    + ((vfirst
                                    + dmesh.tris[(tfirst + f) * 4 + 2] + 1)
                                    + offset)
                                    + "//" + count + "\n");
                            count++;
                        }
                    }
                    offset += dmesh.nverts;
                }
            }
            out.close();
        } catch (IOException ex) {
            LOG.log(Level.SEVERE, null, ex);
        }
    }

    //Exports a List of detailed meshes to .obj format with normals.
    private void exportObj(String filename, List<PolyMeshDetail> dmeshList) {

        File file = new File(filename);
        File dir = file.getParentFile();
        if (!dir.exists()) {
            dir.mkdir();
        }

        try (FileWriter out = new FileWriter(file)) {
            //vertex
            for (int j = 0; j < dmeshList.size(); j++) {
                PolyMeshDetail dmesh = dmeshList.get(j);
                for (int v = 0; v < dmesh.nverts; v++) {
                    out.write("v " + dmesh.verts[v * 3] + " "
                            + dmesh.verts[v * 3 + 1] + " "
                            + dmesh.verts[v * 3 + 2] + "\n");
                }
            }
            //vertex normal
            for (int j = 0; j < dmeshList.size(); j++) {
                PolyMeshDetail dmesh = dmeshList.get(j);
                Vector3f[] vector3Array = getVector3Array(dmesh);
                for (int m = 0; m < dmesh.nmeshes; m++) {
                    int vfirst = dmesh.meshes[m * 4];
                    int tfirst = dmesh.meshes[m * 4 + 2];
                    for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                        Vector3f normal = Triangle.computeTriangleNormal(
                                vector3Array[(vfirst + dmesh.tris[(tfirst + f)
                                * 4])],
                                vector3Array[(vfirst + dmesh.tris[(tfirst + f)
                                * 4 + 1])],
                                vector3Array[(vfirst + dmesh.tris[(tfirst + f)
                                * 4 + 2])],
                                null);
                        out.write("vn " + normal.x + " " + normal.y + " "
                                + normal.z + "\n");
                    }
                }
            }
            //face
            int count = 1;
            int offset = 0;
            for (int j = 0; j < dmeshList.size(); j++) {
                PolyMeshDetail dmesh = dmeshList.get(j);
                for (int m = 0; m < dmesh.nmeshes; m++) {
                    int vfirst = dmesh.meshes[m * 4];
                    int tfirst = dmesh.meshes[m * 4 + 2];
                    for (int f = 0; f < dmesh.meshes[m * 4 + 3]; f++) {
                        out.write("f "
                                + ((vfirst + dmesh.tris[(tfirst + f) * 4] + 1)
                                + offset)
                                + "//" + count + " "
                                + ((vfirst + dmesh.tris[(tfirst + f) * 4 + 1]
                                + 1) + offset)
                                + "//" + count + " "
                                + ((vfirst + dmesh.tris[(tfirst + f) * 4 + 2]
                                + 1) + offset)
                                + "//" + count + "\n");
                        count++;
                    }
                }
                offset += dmesh.nverts;
            }
            out.close();
        } catch (IOException ex) {
            LOG.log(Level.SEVERE, null, ex);
        }
    }

    //Exports the Recast NavMesh to assets in .j3o format so can load a 
    //saved Recast NavMesh rather than building.
    private void saveNavMesh(MeshParameters params, String filename) {
        BinaryExporter exporter = BinaryExporter.getInstance();
        File file = new File(filename + ".j3o");
        try {
            exporter.save(params, file);
        } catch (IOException ex) {
            LOG.log(Level.SEVERE, "Error: Failed to save recastMesh!", ex);
        }
    }
    
    //Exports the Recast NavMesh to assets in .j3o format so can load a 
    //saved Recast NavMesh rather than building.
    private void saveNavMesh(Mesh mesh, String filename) {
        Path path = Paths.get("assets" + sep + "Scenes" + sep + "Recast");
        BinaryExporter exporter = BinaryExporter.getInstance();
        File file = new File(path + sep + filename + ".j3o");
        try {
            exporter.save(mesh, file);
        } catch (IOException ex) {
            LOG.log(Level.SEVERE, "Error: Failed to save recastMesh!", ex);
        }
    }

    /**
     * Returns a built Recast NavMesh.
     *
     * @return the generated NavMesh
     */
    public NavMesh getNavMesh() {
        return navMesh;
    }

    /**
     * Loads and displays the NavMesh.obj for debugging. Uses assetManager() so
     * expects the file to live in the assets folder.
     *
     * @param filename Path of file to be saved
     * @param color the color to be used for viewing the NavMesh
     */
    public void showDebugMesh(String filename, ColorRGBA color) {
        final Geometry meshGeom = (Geometry) getApplication().getAssetManager().loadModel(filename);
        Material mat = new Material(getApplication().getAssetManager(), "Common/MatDefs/Misc/Unshaded.j3md");
        mat.setColor("Color", color);
        mat.getAdditionalRenderState().setWireframe(true);
        meshGeom.setMaterial(mat);
        meshGeom.setCullHint(CullHint.Never);
        app.getRootNode().attachChild(meshGeom);
    }
    
    public void showMesh(String filename, ColorRGBA color) {
        AssetKey<Mesh> keyLoc = new AssetKey<>(filename);    
        final Mesh meshGeom = (Mesh) getApplication().getAssetManager().loadAsset(keyLoc);
        Geometry geom = new Geometry();
        geom.setMesh(meshGeom);
        Material mat = new Material(getApplication().getAssetManager(), "Common/MatDefs/Misc/Unshaded.j3md");
        mat.setColor("Color", color);
        mat.getAdditionalRenderState().setWireframe(true);
        geom.setMaterial(mat);
        geom.setCullHint(CullHint.Never);
        app.getRootNode().attachChild(geom);
    }
    
    private class ProgressListen implements RecastBuilderProgressListener {

        private long time = System.nanoTime();
        private long elapsedTime;
        private long avBuildTime;
        private long estTotalTime;
        private long estTimeRemain;
        private long buildTimeNano;
        private long elapsedTimeHr;
        private long elapsedTimeMin;
        private long elapsedTimeSec;
        private long totalTimeHr;
        private long totalTimeMin;
        private long totalTimeSec;
        private long timeRemainHr;
        private long timeRemainMin;
        private long timeRemainSec;

        @Override
        public void onProgress(int completed, int total) {
            elapsedTime += System.nanoTime() - time;
            avBuildTime = elapsedTime/(long)completed;
            estTotalTime = avBuildTime * (long)total;
            estTimeRemain = estTotalTime - elapsedTime;

            buildTimeNano = TimeUnit.MILLISECONDS.convert(avBuildTime, TimeUnit.NANOSECONDS);
            System.out.printf("Completed %d[%d] Average [%dms] ", completed, total, buildTimeNano);

            elapsedTimeHr = TimeUnit.HOURS.convert(elapsedTime, TimeUnit.NANOSECONDS) % 24;
            elapsedTimeMin = TimeUnit.MINUTES.convert(elapsedTime, TimeUnit.NANOSECONDS) % 60;
            elapsedTimeSec = TimeUnit.SECONDS.convert(elapsedTime, TimeUnit.NANOSECONDS) % 60;
            System.out.printf("Elapsed Time [%02d:%02d:%02d] ", elapsedTimeHr, elapsedTimeMin, elapsedTimeSec);

            totalTimeHr = TimeUnit.HOURS.convert(estTotalTime, TimeUnit.NANOSECONDS) % 24;
            totalTimeMin = TimeUnit.MINUTES.convert(estTotalTime, TimeUnit.NANOSECONDS) % 60;
            totalTimeSec = TimeUnit.SECONDS.convert(estTotalTime, TimeUnit.NANOSECONDS) % 60;
            System.out.printf("Estimated Total [%02d:%02d:%02d] ", totalTimeHr, totalTimeMin, totalTimeSec);

            timeRemainHr = TimeUnit.HOURS.convert(estTimeRemain, TimeUnit.NANOSECONDS) % 24;
            timeRemainMin = TimeUnit.MINUTES.convert(estTimeRemain, TimeUnit.NANOSECONDS) % 60;
            timeRemainSec = TimeUnit.SECONDS.convert(estTimeRemain, TimeUnit.NANOSECONDS) % 60;
            System.out.printf("Remaining Time [%02d:%02d:%02d]%n", timeRemainHr, timeRemainMin, timeRemainSec);

            //reset time
            time = System.nanoTime();
        }
        
    }

}

[mitm]

Now you have the demo running, hit the F1 button and you can test crowds.

Its in the docs how to run it. Plus the help button for every aspect of crowd.

[capdevon]

Thanks for your time @mitm. I hope you come back soon. If the jme3-recast4j library is already 90% complete, that’s great news. I continue to study it.

Edit:
New optimizations committed and available on github.

[capdevon]

New optimizations available on github.

1. Single NavMesh
   

   

2. Single NavMesh
   

   

3. Tile NavMesh
   

   

Edit:
Added description of images.

[Ali_RS]

Hi @capdevon. Great job.

I have a few questions to ask.

In what format are the inputs, JME meshes, or obj files or…? Should the whole scene compose into a single mesh or we can add objects separately at runtime?

Are you using the detailed mesh of the game objects or a simplified one?

I am also interested in performance benchmarks. Is it fast to do pathfinding each (or after a few) frames?

What is the difference between the tiled one with the others?

Do you have an idea how/if it can be used on the server side?

I am currently using jwalkable (but it is 2D) in my game on the server-side and I am thinking about adding recast as well in the future.

I separately create a polygonal shape for each game object and serialize it to a file then when loading the game objects on the server I also load its navigation shape and add it to the jwalkable navigation space (with ECS).

Can I do a similar thing with recast?

Navigation Shape Editor

Thanks in advance.

[capdevon]

Hi @Ali_RS, good questions!
I don’t have a great experience yet. I started studying the jme3-recast4j and recast4j libraries just 3 days ago and there are a lot of things to read to understand. Anyway, I try to answer your questions

@Ali_RS

In what format are the inputs, JME meshes, or obj files or…? Should the whole scene compose into a single mesh or we can add objects separately at runtime?

The recast4j library accepts input in .obj format - The jme3-recast4j library accepts as input the jme classes: Node and Geometry. Gathering-Geometries

//Step 1. Gather our geometry.
Node worldMap = ...;
JmeInputGeomProvider geomProvider = new GeometryProviderBuilder(worldMap).build();

@Ali_RS

I am also interested in performance benchmarks. Is it fast to do pathfinding each (or after a few) frames?

The performances look great. It all depends on the configuration parameters and the context you are using.
In the video I posted, you can see that the time to calculate the best path to the point selected with the mouse click is really short (in the original code this operation is not performed in a separate thread, it would not be complicated to add it)
See NavMeshAgent

3. (I add comments to my previous post with pictures. I think the @mitm post already contains the explanation.)

@Ali_RS

What is the difference between the tiled one with the others?

@mitm

First, jme3 ai is only good for simple path finding. What you are showing us in this image is its major fault of only being able to build a solo mesh, i.e. a navmesh consisting of one tile.

Second, this stuff gets real complicated real fast.

To do dynamic navmesh like you want requires a tiled navmesh and a tile cache. This allows you to build a single cache of tiles identical to the navmesh of tiles to swap out when an object blocks part of the navmesh.

As an example, someone pushes a box onto a tile and that box now blocks the path across that tile. You cut a hole into the navmesh by removing that tile that has been blocked by the box. The path finding routine will find there is a hole in the navmesh and try to find a path around it if possible or just end at the nearest walkable tile. You can only cut squares from a navmesh but you can use a circle or boxed shaped object to do the cutting i.e selecting of what tile to remove. Recast will accept only those two shapes if I remember correctly. Basically barrels or boxes.

If the offending box gets removed, simply grab the tile from the cache and insert it back into the navmesh and you now have a walkable tile. Recast does this all for you.

@Ali_RS

Do you have an idea how/if it can be used on the server side?

I don’t know, I don’t have enough experience in games with client-server architecture.

@Ali_RS

I separately create a polygonal shape for each game object and serialize it to a file then when loading the game objects on the server I also load its navigation shape and add it to the jwalkable navigation space (with ECS).

Can I do a similar thing with recast?

I don’t know if I understood the question correctly, however you can generate the NavMesh and then save and read them (in .md or .nm format)
See saving-and-loading

I hope I gave you the info you were looking for. If you want to exploit the full potential of the library you will need a lot of code. I’m refactoring the methods of the original project, to make these steps easier to read.

All the ways to build a NavMesh with the recast4j library can be found here NavState

//Uncomment the method you want to use.
        //====================================================================
//        //Original implementation using jme3-recast4j methods.
//        buildSolo();
//        //Solo build using jme3-recast4j methods. Implements area and flag types.
//        buildSoloModified();
//        //Solo build using recast4j methods. Implements area and flag types.
//        buildSoloRecast4j();
//        //Tile build using recast4j methods. Implements area and flag types plus offmesh connections.
//        buildTiledRecast4j();
//        buildTileCache();
        //====================================================================

---

Edit: Updated links.

[Ali_RS]

Thanks so much, @capdevon.

[capdevon]

Hi everyone,
lots of new technical updates and debugging tools on the project are available on github. I am designing an API to encapsulate the objects of the recast4j library so that they do not appear in the code of a jme3 application. In this way, the functions are easier and clearer to use, since building a NavMesh with the recast4j library really requires a lot of code to write.

Recently added features:

• NavMeshAgent that allows you to move the character in the Scene using the NavMesh. The com.jme3.recast4j.ai package is very easy to use and is designed taking inspiration from Unity modules (see NavMeshAgent).

Write me a suggestion if you want, or report any bugs.
I hope the project can be useful to the community.

GitHub - capdevon/jme3-recast4j-test-1: Navigation-mesh Toolset for...

[xuan]

Amazing work! I’ll be trying it soon

[capdevon]

Thank you. I also want to mention @mitm and @MeFisto94 for sharing the original project.

Let me know your opinion after trying the project.

[capdevon]

to-do list:

1. A simple graphical editor written using the Lemur library, to modify the NavMesh generation parameters. (WIP)
   

   

2. A more precise way to exclude objects or assign them a specific ‘AreaModification’ during the NavMesh generation process (I like this approach used in Unity, based on markers which also returns the list of the scene’s objects selected and the assigned areas. See here). In the NavState class you can find an approach based on the Material name of the objects (see here).

3. Update the project with the latest version of recast4j-1.5.1

4. Wiki section

Recently added features:

the IORecast class to export the NavMesh in .obj format (see here)

[oxplay2]

nice, i will also need update navmesh code soon too. So your code will be very helpfull for me.

Anyway it would be nice if JME would be updated with recast4j AI version.

[capdevon]

@oxplay2

Anyway it would be nice if JME would be updated with recast4j AI version.

Hi @oxplay2, I hope my project can help the community achieve this goal; recast4j is a great library with tons of features and options, and it’s actively maintained. I think it is the component we need. If you have any suggestions, feel free to write me. I will be posting new updates on github soon.

[oxplay2]

hard to tell now, since not working on AI currently hehe

Anyway if you gonna make lib for it, i will use it in future and check if anything more is needed.

[capdevon]

Hi everyone,
lots of updates and new features of the jme3-recast4j library are available on github here.

Recently added features:

• NavMeshAgent that allows you to move the character in the Scene using the NavMesh.
• NavMeshQueryFilter - Specifies which areas to consider when searching the NavMesh.
• NavMeshTools - Use the NavMesh class to perform spatial queries such as pathfinding and walkability tests. (eg. computePath, randomPath and raycast)
• NavMeshBuildMarkup allows you to control how certain objects are treated during the NavMesh build process, specifically when collecting sources for building.
• NavMeshBuildSettings allows you to specify a collection of settings which describe the dimensions and limitations of a particular agent type.
• SoloNavMeshBuilder
• TileNavMeshBuilder
• IORecast to export NavMesh in .obj format.
• Graphic editor to modify the NavMesh generation parameters at Runtime.
• Debugging tools (NavMeshDebugViewer and NavPathDebugViewer).

Here you can see a demo of all these things.

Navigation-mesh Toolset for jMonkeyEngine3

The com.jme3.recast4j.Detour.Crowd package, is still under development and could vary a lot with each update, but it works and you can already try it.

Hope you like it.

[capdevon]

Hi everyone,
I’ve been working for months now to improve the jme3-recast4j library. At the moment I am focusing on CrowdAgents. Lots of updates and new features are available on github.

Recently added features:

• Improved debugging tool. Added a minimal geometry cylinder to display agent radius, height and status.
• Added new 2d Circle Mesh class to view the configuration of parameters such as collQueryRange or TargetProximity.
• New enum ObstacleAvoidanceType for configuring the quality level of obstacle avoidance (Low, Med, Good, High).
• New CrowdControl class with animation update based on agent state.
• FlyCam added to give better freedom of movement during testing.
• Improved graphics.
• Improved code to allow users to better understand the concepts.

Hope you like it.