I have imported a simple model into jMonkeyEngine and created a NavMesh for this model, with the intention of implementing a pathfinding algorithm for an NPC.
However, I don’t know how the NavMesh methods works and how I can use it to implement a pathfinding algorithm. Can someone point me in the right direction with regards to how a character can move from one point to another on the navigation mesh and how I can code this in my game?
A simple example of using methods of the NavMesh library would be ideal.
I have had a look at the MonkeyZone game but it seems that it is not developed anymore and the latest version is not fully functional.
Thank you.
@tl888 said:
and the latest version is not fully functional.
Whats the problem? The code for pathfinding should still be okay, it was never used in the code yet though.
Hey,
Yeah, it’s missing some documentation. I have some of that done, and some other part missing. Also, I’ve add some fixes in some parts of that project, but there are still some issues to solve. I’m going to focus on those things in the Winter break.
First thing you want to do is to load the mesh. You can either load it from some pre-baked creating, or you can load on the fly by using NavMeshGenerator (look at the optimize method and remember to set the parameters first. This is quite complicated, so I suggest reading the docs on http://www.critterai.org/nmgen_study). My examples assumes you have a mesh called navm.
[java]NavMesh navmesh = new NavMesh();
navmesh.loadFromMesh(navm.getMesh());[/java]
You have several ways to do that. One is:
[java]
Vector3f init; // some initial point
Vector3f end; //some destination/end point
Path path = new Path();
boolean buildNavigationPath = navmesh.buildNavigationPath(path, navmesh.findClosestCell(init), init, navmesh.findClosestCell(end), end, 0.4f);
if (buildNavigationPath) {
for (Path.Waypoint p : path.getWaypoints()) {
// Now you need to create some code to solve this for you. Maybe remebering what was the last waypoint, so you can know which one is the next and how to proceed.
}
}
[/java]
Or you can use NavMeshPathfinder, that helps you a lot on this
[java]
NavMeshPathfinder nmp = new NavMeshPathfinder(navmesh);
nmp.setPosition(init);
nmp.setEntityRadius(radius);
nmp.computePath(end);
[/java]
Now you need to choose how are you going to use this. Whenever you move your object (or store some moves to avoid many computations), you call nmp.onMove(Vector3f moveVec) to update the position until you reach your waypoint. When you do, you need to call nmp.gotoToNextWaypoint() until you reach your destination (nmp.isAtGoalWaypoint()).
Remember to use the utils method on NavMeshPathfinder
[java]nmp.getWaypointPosition();
nmp.getDirectionToWaypoint();
nmp.getDistanceToWaypoint();[/java]
What do you mean by not functional? I’ve been using it for the last 9 months.
@shirkit: Its very cool that you have the NavMeshPathfinder working 
I am actually the one who wrote it. Have you found any issues with it so far?
@Sploreg and me already did this, it will be added to the “AI” plugin in the repo (if that didn’t happen already). The way it is in MonkeyZone its quite convoluted and the class separation is not very good. You have to configure and mess with mutliple classes and then getbyour info at some other place later.
1 Like
I don’t use NavMeshPathfinder at all, I found it so confusing that I gave up using it I think if it was put inside some Control, then it would be useful. But without that, I just can’t find it useful 
Sorry for the shameless hijacking of this. For anyone interrested in navmeshes, pathfinding and paths across different navmeshes I can offer this video: http://l2jserver-client.googlecode.com/svn/wiki/navigation_cross_tiles_norm_and_opt.2.mp4
The video shows several tile regions loaded dynamically each one with a navmesh. The video shows the found resulting path from the starting point at tile 1 to the endpoint on tile 2. The first run of the video shows the unoptimized path (please notice that the navmesh is not optimal and contains many unneeded triangles). The walker uses a pathusing the centers of all triangle edges on the path.
The second run where optimized paths are used removes unneeded path nodes (can be identified by the gray poles of the path) and creates a more “natural path”.
@Sploreg and @normen if you would like to have some details on how the tiled navmeshes works you can have a look at the code at http://l2jserver-client.googlecode.com/ The interresting code is in the NavigationMesh and EntityNavigationManager.
Not sure if the jme navigation mesh stuff is still based on my old code, but from what I learned, my last implementation (which I also saw in the jme repo) was not really able to save/load a navmesh.
Edit: tescase is com.l2jclient.test.TestRegion4.java.
I also had a somewhat basic doxumentation in the docs section about the pathfinding across tiles (though it has changed that the full path is build instead of only the part to the border):
a tile has a fixed size in world coordinates. a navmesh is created exclusively for a tile.
all triangles of the navmesh must be within the navmesh. some triangles of the navmesh which should be used as bridges to other tiles lie with one edge on the tile edge. other triangles of the navmesh which should not be connecting to other tiles must be a minimal unit away from the tile edge.
tiles which connect must create a navmesh in a way, that the edges of the overlapping lines match in their center.
+
|
+
| side b
side a . center point is in center of quad on side a and quad on side b
|
+
|
+
path planning will use the "border cells" (trinagles which have one side on the tile border) to prepare transitions to other tile navmeshes.
path planning will go along waypoints, these are placed in a manor where tile transition is supported by having two waypoints lying close by on the two different tile sides. in addition path planning will normally cover a very small area
Path lookup should go as follows:
determin the navmesh where the endpoint is on.
determin if it is a different navmesh than the one we are on.
if it is a different one
if the start is on the other side too normal path lookup
else navigate to the closest borderpoint
else
normal path lookup
path execution:
if in border cell and path result would be exiting to a side outside the tile
switch the navmesh to the adjecant navmesh
new path lookup
2 Likes
Video just stays stuck displaying the same thing with no sound.