"Dynamic" NavMesh

Thanks so much, @capdevon. :slightly_smiling_face:

1 Like

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.

7 Likes

Amazing work! I’ll be trying it soon :smiley:

1 Like

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

Let me know your opinion after trying the project. :wink:

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)

6 Likes

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.

1 Like

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.

3 Likes

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

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

1 Like

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.

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.

8 Likes

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.

4 Likes

Without offense, but is there a reason you seem to reinvent the wheel instead of directly basing off jme3-recast4j?
A lot of the things you do have been implemented or were at least on the todolist for us, so I guess we definitely should talk.
Especially things like Crowd and navigating Agents should already be implemented in some way.

The biggest challenge we had was understanding/adding/testing all of the high level concepts such as off-mesh-links, flags to dynamically disable voxels (the actual OP here) etc

3 Likes

Sorry @Darkchaos, I don’t understand the meaning of your post.
Any sentence that begins with “Without offense” always contains an offense. You seem angry with me, but I don’t understand why. You talk about “todolist” and “should already be implemented in some way …”

The original “jme3-recast4j” design was incomplete, but it had some interesting basic ideas like marking area polygons differently. The project seemed abandoned and was not updated since 14 Sep 2019. The libraries (jmonkeyengine, lemur and recast4j) were out of date and the project was incompatible with the latest version of recast4j-1.5.1 which broke backwards compatibility with the previous ones.

  • I modernized the whole project. I removed redundancies, simplified and cleaned up the code.
  • I edited the javadoc.
  • I have updated the libraries to the latest versions.
  • I have added tons of new features, debugging tools, use cases and a graphical editor for the NavMesh generation.
  • I showed the functionality and potential of the library with sample images and videos.
  • I made all the material available in a completely free way.
  • I have mentioned and thanked the authors of the original project on the forum and on github.

Here are the projects before and after:
The “wheel” before:

The “wheel” after:

We haven’t seen demos on the forum based on this library for years. After 3 months of effort, on the thread of the month finally a user has successfully used the features I added.

I thought I was providing a useful tool for the community. Nobody pays me and I don’t earn anything from the hours I invested in research, algorithm analysis and study of other engines. I was just happy to share my ideas with the community and maybe get some good advice.

So I don’t understand the meaning of your post.

I’m not looking for problems. Tell me what to do and I will do it.

2 Likes

fyi I think you are, I’ve been following your progress and I’m looking forward to use it myself for revamping my game’s ai. But I haven’t made that a priority yet so couldn’t provide any feedback.

1 Like

I use @capdevon work, that saved me time, and works. I tried original MeFisto94 jme3-recast4j-demo , still hitting errors I can’t handle. To use further in my game now I try to see @capdevon approach.

I suggest to keep original MeFisto94 jme3-recast4j.

2 Likes

Thats interesting. In the end i wrote A* finding the path from a given set of waypoints where each of waypoints is stored in a HashMap that contains the location of the waypoint as the key and ArrayList of location vectors of adjacent waypoints.

HashMap<Vector3f,ArrayList> adjacencyMatrix = new HashMap<>();

Works pretty well, and if i need to add a waypoint (because i.e a door opened) i just put it where it needs to be, and then check for adjacent waypoints for the algorithm to be able to find a path (although adding a waypoint means checking distance to every other waypoint on the map, so its far from optimal in case you want to add a whole lot of waypoints). I’ll share the code soon

1 Like

I always enjoy hearing different ideas. I await your news.

so, here’s a working A* algorithm + path reconstruction (no physics control needed)
A* pathfinding:

 public static void aStarSearch(GameObject actor){
    HashSet<Vector3f> openSet = new HashSet();
    HashSet<Vector3f> closedSet = new HashSet();
    LinkedHashMap<Vector3f,Vector3f> cameFrom = new LinkedHashMap();// 1 - node / 2 - nodes parent
    HashMap<Vector3f,Float> gScore = new HashMap();
    HashMap<Vector3f,Float> fScore = new HashMap();
    

    gScore.put(actor.getStartingNode(), 0f);
    fScore.put(actor.getStartingNode(), (abs(actor.getStartingNode().x-actor.getEndingNodePos().x)+abs(actor.getStartingNode().z-actor.getEndingNodePos().z)));
    openSet.add(actor.getStartingNode());
//    long sum = 0;
//   System.out.println("ending node " + actor.getEndingNodePos());
    while(!actor.getFoundPath() && !openSet.isEmpty() && !actor.hasLineOfSight){ // # 4 a) b)
    float lowestF =  Collections.min(fScore.values());
    Vector3f currentNode = null;

//    long time1 = System.currentTimeMillis();
    for(Object entry: fScore.entrySet()) {
    Entry<Vector3f,Float>entry1 = (Entry) entry;
      if(entry1.getValue().equals(lowestF)) {
        currentNode = entry1.getKey();
        break;
      }
    }
//    long time2 = System.currentTimeMillis()-time1;
//    sum += time2;

    
    if(currentNode.equals(actor.getEndingNodePos())){
    actor.setFoundPath(true);
    reconstructPath(cameFrom,currentNode);

    break;
    }
    
    openSet.remove(currentNode);
    closedSet.add(currentNode);
    
    for(Object adjacentToCurrent : adjacencyMatrix.get(currentNode)){
    Vector3f neighbor = (Vector3f) adjacentToCurrent;
    if(!closedSet.contains(neighbor)){
    float tentativeScore = gScore.get(currentNode)+(abs(currentNode.x-neighbor.x)+abs(currentNode.z-neighbor.z));
   boolean tentativeScoreIsBetter = false;
   
   
   if(!openSet.contains(neighbor)){    
//    cameFrom.putIfAbsent(neighbor, currentNode);
//    gScore.putIfAbsent(neighbor, tentativeScore);
//    fScore.putIfAbsent(neighbor,tentativeScore+(abs(neighbor.x-actor.getEndingNodePos().x)+abs(neighbor.z-actor.getEndingNodePos().z)));
    openSet.add(neighbor);
    tentativeScoreIsBetter = true;
//    System.out.println("dodaje");
    } else if(tentativeScore<gScore.get(neighbor)){
    tentativeScoreIsBetter = true;
    }
   if(tentativeScoreIsBetter){
   if(cameFrom.keySet().contains(neighbor)){
   cameFrom.replace(neighbor, currentNode);
       gScore.replace(neighbor, tentativeScore);
    fScore.replace(neighbor,tentativeScore+(abs(neighbor.x-actor.getEndingNodePos().x)+abs(neighbor.z-actor.getEndingNodePos().z)));

   }else{
   cameFrom.put(neighbor,currentNode);
    gScore.put(neighbor, tentativeScore);
    fScore.put(neighbor,tentativeScore+(abs(neighbor.x-actor.getEndingNodePos().x)+abs(neighbor.z-actor.getEndingNodePos().z)));

   }
   }
   
    }
    }
 fScore.remove(currentNode);
        gScore.remove(currentNode);

    }
   

    }

path reconstruction:

 public static void reconstructPath(GameObject actor,HashMap cameFrom,Vector3f currentNode){
        
        LinkedList<Vector3f>finalPath = new LinkedList();

      while(cameFrom.keySet().contains(currentNode)){
      currentNode = (Vector3f)cameFrom.get(currentNode);
      finalPath.addFirst(currentNode);
      }
actor.setPath(finalPath);
    
    }

example of end result:


But you may ask: what is dynamic about it?
note that the first node (the one on the top left,blue spheres represent the nodes) is notably closer to the second one, and the other ones are spaced evenly. that is because you can add it to the

adjacencyMatrix

and check adjacent nodes to the node you are adding by checking distances (for example, nodes are considered adjacent if distance from each other is <= 2).
I will post full code soon so if someone wants simple and efficient pathfinding they’ll be able to copy- paste it and adjust it to their need.

as for now, can i ask you for advice on optimizing the algorithm? (it works really fast but in pathfinding every milisecond counts)

2 Likes

By the way, i’d like to create a topic soon about optimising your games based on my experience (soon means 2 weeks- a month, because i started CS at uni and have a lot of work during 1st sem), covering some basic theory about optimising collision, pathfinding, and anything worth mentioning i will come across, so anyone new to jMonkey can wrap their head around some gamedev techniques that are hard/time consuming to find,learn, and write on their own. Would such thing be appreciated or is it redundant?

6 Likes

Sounds great!

Interesting idea, but I can’t give you any advice about it, as I don’t have a working code to try.

Of course it would be appreciated!