Navigation Mesh

So, I’ve heard it was already implemented and the algorithm can generate a Navigation Mesh given an input, let’s say, a terrain. I’ve seen it on the MonkeyZone, but no comments are given. I imagine that has something to do with createNavMesh(). Am I correct at this point? I think yes, so that was what I did.

I copied that code and tried to generate the navmesh.

public void createNavMesh() {
    Mesh mesh = new Mesh();

    //version a: from mesh
    GeometryBatchFactory.mergeGeometries(findGeometries(terrain, new LinkedList<Geometry>()), mesh);
    Mesh optiMesh = new NavMeshGenerator().optimize(mesh);

    NavMesh navmesh = new NavMesh();

    //TODO: navmesh only for debug
    Geometry navGeom = new Geometry("NavMesh");
    Material green = new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md");
    green.setColor("Color", ColorRGBA.Green);


So far so good, but there is a problem. When running, it goes inside here
Mesh optiMesh = new NavMeshGenerator().optimize(mesh);

In this optimize, there is a a call to this
TriangleMesh triMesh =, indices, null, null);

It goes inside here, and never leave. So, I started debugging to check out, and found out that those two parameters are quite big. the positions lenght is about 800k and the indicies has 1.6 millions entries. I'm sure that's the problem. But knowing what is the problem doesn't mean I can solve it, because I couldn't find a way to solve it. Someone help me?

Here's my code for the terrain creation
private void createTerrain() { matRock = new Material(assetManager, "Common/MatDefs/Terrain/TerrainLighting.j3md"); matRock.setBoolean("useTriPlanarMapping", false); matRock.setBoolean("WardIso", true); matRock.setTexture("AlphaMap", assetManager.loadTexture("Textures/Terrain/splat/alphamap.png")); Texture heightMapImage = assetManager.loadTexture("Textures/Terrain/splat/mountains512.png"); Texture grass = assetManager.loadTexture("Textures/Terrain/splat/grass.jpg"); grass.setWrap(WrapMode.Repeat); matRock.setTexture("DiffuseMap", grass); matRock.setFloat("DiffuseMap_0_scale", 64); Texture dirt = assetManager.loadTexture("Textures/Terrain/splat/dirt.jpg"); dirt.setWrap(WrapMode.Repeat); matRock.setTexture("DiffuseMap_1", dirt); matRock.setFloat("DiffuseMap_1_scale", 16); Texture rock = assetManager.loadTexture("Textures/Terrain/splat/road.jpg"); rock.setWrap(WrapMode.Repeat); matRock.setTexture("DiffuseMap_2", rock); matRock.setFloat("DiffuseMap_2_scale", 128); Texture normalMap0 = assetManager.loadTexture("Textures/Terrain/splat/grass_normal.jpg"); normalMap0.setWrap(WrapMode.Repeat); Texture normalMap1 = assetManager.loadTexture("Textures/Terrain/splat/dirt_normal.png"); normalMap1.setWrap(WrapMode.Repeat); Texture normalMap2 = assetManager.loadTexture("Textures/Terrain/splat/road_normal.png"); normalMap2.setWrap(WrapMode.Repeat); matRock.setTexture("NormalMap", normalMap0); matRock.setTexture("NormalMap_1", normalMap2); matRock.setTexture("NormalMap_2", normalMap2);
    AbstractHeightMap heightmap = null;
    try {
        heightmap = new ImageBasedHeightMap(ImageToAwt.convert(heightMapImage.getImage(), false, true, 0), 0.25f);
    } catch (Exception e) {

    terrain = new TerrainQuad(&quot;terrain&quot;, 65, 513, heightmap.getHeightMap());
    List&lt;Camera&gt; cameras = new ArrayList&lt;Camera&gt;();
    TerrainLodControl control = new TerrainLodControl(terrain, cameras);
    terrain.setLocalScale(new Vector3f(4, 4, 4));

    matWire = new Material(assetManager, &quot;Common/MatDefs/Misc/Unshaded.j3md&quot;);
    matWire.setColor(&quot;Color&quot;, ColorRGBA.Green);

    terrainPhysicsNode = new RigidBodyControl(CollisionShapeFactory.createMeshShape(terrain), 0);

So, noone knows? Can anyone exlpain me a bit what is the logic behind this implementation to find the navigation mesh? Or at least provide me some comments?

If I remove the line:

terrain.setLocalScale(new Vector3f(4, 4, 4));

It take about 5 seconds to compute. With it, I let it calculating for about 10 minutes but no answer was given. Maybe I need more time, like a few hours, or maybe a day? At least could anyone tell me who made this, or from wich library is it from?

The Nav mesh isn’t part of the core, it’s been made by @Momoko_Fan as an example.

Also i’m pretty sure it was not made to work with terrain.

Maybe try with a lower poly mesh, like a home brewed terrain.

There a a few possible issues, first the navmesh isn’t supposed to work with the terrain system at all. Second, you have to really tweak the parameters to make it generate something useful for each type of terrain. I had a special GUI utility that let you do that but I don’t know if its available in MonkeyZone anymore.

Well, I didn’t understand it. If it doesn’t work with the terrain, how is he getting the information where he can walk or not? I need to provide it some information for it? And tweak how? I didn’t get it @Momoko_Fan , do you have any comments for that library?

The library as it is in monkey zone doesn’t work, simple as that. We are looking into providing something similar but as of now you’re on your own I’m afraid.

I have a working copy of the navmesh generator, but I am keeping it to myself!!! muahhahaha

just kidding. I haven’t had time yet to release it but I will. I have an SDK plugin for it too. I guess I can try and do that in the next week or so (whenever I say that it takes 3x as long)

So the issue is that the navmesh generator crashes if the input variables are out of range, you will have to read the API for it (the library is 3rd party, can’t remember the address). Also the default implementation does not support triangle strips (which is what terrain is made of). I had to convert the terrain heightfield into a regular triangle mesh, then sending it into the generator worked.

Now I understood :stuck_out_tongue:

My final work in the college is generating a pathfinding algorithm for a group of units that can keep up with a formation. So, I’ve decided to work with navigation meshes for maximaze the simulation’s reality to today’s games.

Edit: Look what I have found =]

Yeah, Recast looks great. Make sure to keep up with the developer’s blog. There’s also a somewhat dated Java project based on Recast called NMGen:

…nmgen is what comes with monkey zone, albeit in an old version