NavMesh, displacement problem when navmesh is superimposed (or gateways to bridge)

Hello, sorry for my English.
I use the library “JM3 Ai Library” have to use NavMesh. It works fine but I found a problem when two paths superimposed (eg a road on a bridge or gateway). I publish a little video to show the problem. According to you what is my problem? The AI ​​Library bookstore JM3 she has usage limits?

The problem arises in the 15th seconds of the video

Agent (cube) does not borrow deck to stop it. By cons, he uses it well to take the plunge.

Thank you

https://youtu.be/ngzLMb8g6bQ

When you launch a search with the NavMeshPathFinder “NavMeshPathFinder.computePath (destPosition)” and that the target position is placed on the bridge, the algorithm seems to be a path search problem

That’s because JME AI does a 2D Plane path finding, means it does not consider height (Y axis) values. One thought might be, you separate bridge mesh from ground mesh and create separate NavMesh for each, then based on player position and destination position decide on which navMesh you need to find path.
Note that using this way you should control path finding from one mesh to an other mesh. For example when player is on ground and want to go somewhere on bridge.
There might be other better ways too, let’s see what others will come up with.

*btw, it might be good idea to add 3D path finding support to JME AI if possible.

Another easy way is to just cut cells on ground mesh where is located under bridge if you will never want to find path under bridge. In this case JME AI will work OK.

like this :

btw, can you please generate debug mesh of your navMesh. You can do this by iterating over cells and call getDebugMesh() on each cell .
Want to see if it is the same with original geometry mesh or looks different.

Thank you for your answers,
I use getDebugMesh () to see if the navmesh corresponds to my level. It is identical to my mesh level. I thought that to use NavMesh also allowed to have verticality, unlike the pathfinding algorithm A *. On video I think navmesh are not used, is that correct? Do you know another library for NavMesh JMonkeyEngine? Thank you

Create two NavMesh seems a good alternative. A mesh for each level. Depending on the destination, I use the first or second NavMesh. The only problem is for example the stairs at many levels. Must be each time a new NavMesh. The code will change each level.

It is a random video i picked from youtub not know what method they are using. :wink: As you can see under the bridge on the ground has no cell. You can do the same and cut those polygons on your mesh in blender so JME AI can not find path through them.

There is also Recast Navigation for JME, I have not used it before and do not know if it also has this problem or not. @Darkchaos can recast be helpful for this problem ?
There is also GDX-AI Path finding library for java used by libGdx, not tested it also.

Then if it really keeps those cells with their exact positions same with original mesh then i think it will be easy to add support of 3D path finding over JME AI, we might need to just consider Y position in path finder ??
@Darkchaos what do you think ?

Yes indeed, this should be possible. If only it was that easy, I wonder why the developers of the library have not implemented directly. I do not know if I would be able to modify the source code to add this option. I have already developed a A Star but by reading the source code and NavMeshPathFinder NavMesh, I do not know if I have enough experience to do it.

I am in the same position too, :slight_smile: I am looking through source code right now but i do not know if i have enough experience to do that.

I feel that the NavMesh is remembered for the Y position when traveling. But when the search path is a path 2d map search with the application of A Star is used.

see here

/**
     * Generate a new Path from the currentPos3d to the supplied goal 
     * position.
     * setPosition() must be called first for this to work. If the 
     * point is not in the mesh, false is returned. You should use
     * warp() in that case to place the point in the mesh.
     * 
     * @return fail if no path found or start location outside of a cell
     */
    public boolean computePath(Vector3f goal, DebugInfo debugInfo) {
        // get the cell that this point is in
        Vector3f newPos2d = new Vector3f(currentPos3d.x, 0, currentPos3d.z);
        currentCell = navMesh.findClosestCell(newPos2d);
        if (currentCell == null) {
            return false;
        }

        goalPos3d = goal;
        goalPos = new Vector2f(goalPos3d.getX(), goalPos3d.getZ());
        Vector3f goalPos2d = new Vector3f(goalPos.getX(), 0, goalPos.getY());
        goalCell = navMesh.findClosestCell(goalPos2d);
        boolean result = buildNavigationPath(path, currentCell, currentPos3d, goalCell, goalPos3d, entityRadius, debugInfo);
        if (!result) {
            goalPos = null;
            goalCell = null;
            return false;
        }
        nextWaypoint = path.getFirst();
        return true;
    }

I wonder if we change it like this, it will work !!

   currentCell = navMesh.findClosestCell(currentPos3d);
   goalCell = navMesh.findClosestCell(goalPos3d);
1 Like

When I look at the findClosestCell NavMesh method in the class, it creates a Vector2f for research Closest cells. I do not think is so easy. But I’ll modify the source code and compile the library. I tell you if it works then. But I have my doubts.

it works !!! I’m doing a video and I post to show you

1 Like

Glad that it worked. :grinning:
I am waiting for video.

here is the video.
I do not understand why it was not directly implemented in the library? I still do other tests to be sure of the result but
it is already promising.

https://youtu.be/L6cPAuyN-Xg

1 Like

Cool, thanks.

A new video.
This time using two levels. This seems to work properly. I am happy

1 Like

Well actually it’s like this:
Recast & Detour is the most used NavMesh Framework and there already is github:QuietOne\jNavigation which I have to work on a bit in a few months once I need to improve my Navigation.

Just for clarification: Recast creates the NavMesh whereas Detour is searching the Path.
I always thought that we might already rely on R&D but it seems like we only use Recast but not Detour.

That means one could take the time to use detour and see how it works.

Also some Information:
You can always categorize Navigation into two main parts grid based and polygonal/tile based meshes.
What you saw in that video is actually a bad example, especially for 3d. It is using the grid based technology.
The Pro is that you can use an array of booleans (boolean[][] navMesh) but the cons are the waste of space (you could use like 4 quads to cover the whole scene) and that it’s mostly designed for 2d worlds.

If you would want to roll your own Navigation, you can use A* and grids just fine, but only for 2d strategy games. You see that there is no possible way to have crossing paths (because they might specify a height for each cell instead of a 3d array (which would be HUGE in space)).

With polygonal meshes you have a way more easy structure and that should be possible. Unfortunately those are way more compilcated by nature. Your bug indeed seems to be a flaw in the implementation of our NavMesh and it definately deserves some overhaul but considering that other engines (Unity, Unreal) also only have bad support, well…

If you really want to investigate and such I’d suggest you to download the Recast Demo to explore (It can even import .obj files) and also maybe use some Raw Detour (It even supports some Steering Behaviors as Detour Crowd).

The ultimate goal would be to improve and update said jNavigation work and maybe add a JME Layer over it for easy use, but that might be quite some work.

1 Like