Path Finding - MeFisto94/jme3-recast4j-demo GitHub Wiki

The basics of path finding in Recast4j are very similar to what is explained in the jme3-ai tutorial. As such, this tutorial will be mostly directed towards how to use the methods of Recast4j for path finding rather than its direct implementation.

Straight Path

//Create a query object for a navmesh.
query = new NavMeshQuery(navMesh);

//Use the DefaultQueryFilter so can set flags.
DefaultQueryFilter filter = new DefaultQueryFilter();

//The target.
Vector3f locOnMap = getLocationOnMap();

//The search distance along each axis. [(x, y, z)]
//Extents can be anything you determine is appropriate.
float[] extents = new float[] { 2f, 4f, 2f };

//Spatials current position.
float[] start = spatial.getWorldTranslation().toArray(null);

//Convert to Recast4j native format.
float[] end = DetourUtils.toFloatArray(locOnMap);

//Get closet poly for start position.
Result<FindNearestPolyResult> findPolyStart = query.findNearestPoly(start, extents, filter);
//Get the closest poly for end position.
Result<FindNearestPolyResult> findPolyEnd = query.findNearestPoly(end, extents, filter);

//Get the references for the found polygons.
long startRef = findPolyStart.result.getNearestRef();
long endRef = findPolyEnd.result.getNearestRef();

//Get the points inside the polygon.
float[] startPos = findPolyStart.result.getNearestPos();
float[] endPos = findPolyEnd.result.getNearestPos();

//Get list of polys along the path.
Result<List<Long>> path = query.findPath(startRef, endRef, startPos, endPos, filter);

//Set the parameters for straight path. Paths cannot exceed 256 polygons.
int maxStraightPath = 256;
int options = 0;

//Calculate corners within the path corridor.
Result<List<StraightPathItem>> pathStr = query.findStraightPath(startPos, endPos, path.result, maxStraightPath,
options);

//Provide list for waypoints.
List<Vector3f> wayPoints = new ArrayList<>(pathStr.result.size());
//Add waypoints to the list
for (StraightPathItem p: pathStr.result) {
    Vector3f vector = DetourUtils.createVector3f(p.getPos());
    wayPoints.add(vector);
}

  • Create a query object for the navmesh.

  • Create the query filter.

  • Determine the extents for the search.

  • Find end polygon on NavMesh using findNearestPoly.

  • Find start polygon on the NavMesh using findNearestPoly.

  • Check if the results returned are valid.

  • Build a list of polygons in the path using the start and end results with findPath.

  • Build the path corners from the list of polygons using findStraightPath.

  • Create a list of waypoints from findStraightPath results.

  • Determine if a polygon reference is valid and passes the filter restrictions.

Query object

//Create a query object for a navmesh.
query = new NavMeshQuery(navMesh);

You create a NavMeshQuery object for each navmesh you will use for path finding. It is specific to the the navmesh you pass to the constructor. A query object allows you to do things like:

  • Finding a random point on the navmesh.

  • Finding a random point within the reach of a specified location.

  • Find the closest point on a polygon.

  • Get the height of the polygon at a position.

  • Find the polygon nearest to a specified center point.

  • Find polygons that overlap in a given search box.

  • Find a path from A to B.

  • Find the distance from a point to the nearest wall.

See: NavMeshQuery.java for other potential uses.

Path Filters

//Use the DefaultQueryFilter so can set flags.
DefaultQueryFilter filter = new DefaultQueryFilter();

Must read:

The polygon flag filter works so that you can specify certain flags (abilities), which must be on (included), and certain flags which must not be on (excluded) for a polygon to be valid for the path. A navigation mesh polygon must have at least one flag set to ever be considered by a query. So a polygon with no flags will never be considered.

Polygons have a travel cost set when generating the NavMesh which is the Area Type. Paths that have a lower cost scalar will take precedence.

Consider the following, you could for example have a filter for “humans”:

int includeFlags = SAMPLE_POLYFLAGS_WALK | SAMPLE_POLYFLAGS_DOOR;
filter.setIncludeFlags(includeFlags);

int excludeFlags = SAMPLE_POLYFLAGS_DISABLED;
filter.setExcludeFlags(excludeFlags);

It means that it will accept polygons which are either ground or door, but not disabled.

Then it’s matter of setting or clearing the SAMPLE_POLYFLAGS_DISABLED flag for the polys which are disabled (i.e. locked door).

You can change the flags of a polygon using NavMesh.getPolyFlags() and NavMesh.setPolyFlags().

Result<Integer> polyFlags = navMesh.getPolyFlags(flags);

Status setPolyFlags = navMesh.setPolyFlags(id, flags);

Take care if multiple sources can change the same polygon flags.

Remember that a door area can be potentially composed of many polygons. One way to handle this is to query the necessary polygons using NavMesh.findPolysAroundCircle() at the door center location (and approx radius) with the following filter:

int includeFlags = SAMPLE_POLYFLAGS_DOOR;
filter.setIncludeFlags(includeFlags);

int excludeFlags = 0; // will return both enabled and disabled polys
filter.setExcludeFlags(excludeFlags);

Result<FindPolysAroundResult> result = query.findPolysAroundCircle(startRef, startPos, 7.5f, filter);
FindPolysAroundResult polys = result.result;

This will only expand to polygons which have the door “ability”. Then on your door logic you can change their flags based on the door state.

Area Type is meant to specify how expensive the polygon is to travel, but you can misuse it in certain cases to do secondary manual filtering yourself.

findNearestPoly

//Get closet poly for start position.
Result<FindNearestPolyResult> findPolyStart = query.findNearestPoly(start, extents, filter);
//Get the closest poly for end position.
Result<FindNearestPolyResult> findPolyEnd = query.findNearestPoly(end, extents, filter);

For path finding, you will need to know the first and last polygons and a point inside those polygons that will constitute the start and end position for your path. The findNearestPoly() method returns references and points where references are polygons, and points are Vectors inside the polygon. The findNearestPoly() method will find the closest polygon to a point, using the given extent and the supplied filter.

If the point supplied by you is inside the found polygon, that point will be returned, otherwise, findNearestPoly() will constrain the point to the polygon found, assuming one is found. If the search does not intersect any polygons, the search getNearestRef() will be zero. You should always check for this prior to calling getNearestPos().

An example of something that could return zero would be supplying a point that is not part of the NavMesh like walls or objects that are to far outside the extents of the search, or if all polygons are filtered out.

//Get the references for the found polygons.
long startRef = findPolyStart.result.getNearestRef();
long endRef = findPolyEnd.result.getNearestRef();

//Get the points inside the polygon.
float[] startPos = findPolyStart.result.getNearestPos();
float[] endPos = findPolyEnd.result.getNearestPos();

Once you have valid start and end polygons, you can grab the references and points to be used for the path finding method.

findPath

//Get list of polys along the path.
Result<List<Long>> path = query.findPath(startRef, endRef, startPos, endPos, filter);

The findPath() method will return a list of polygons from start to end. This is known as the “path corridor”. If the end polygon cannot be reached, the last polygon in the path will be the nearest one found to the end polygon.

findStraightPath

//Set the parameters for straight path. Paths cannot exceed 256 polygons.
int maxStraightPath = 256;
int options = 0;

//Calculate corners within the path corridor.
Result<List<StraightPathItem>> pathStr = query.findStraightPath(startPos, endPos, path.result, maxStraightPath,
options);

Once you have your polygons used in the path, you need to find the corners inside the “path corridor”. This is the purpose of the findStraightPath() method. These corners are your waypoints.

No path may exceed 256 polygons in length. The options parameter will give you the same path in XZ, but will add and additional point to the path for each of the in-between polys for either area crossings or for every border crossing, depending on the constant.

  • NavMeshQuery.DT_STRAIGHTPATH_AREA_CROSSINGS

  • NavMeshQuery.DT_STRAIGHTPATH_ALL_CROSSINGS

The findStraightPath() method will generate a path that does not take into account height. With this method of path finding, you will need something that keeps the character restrained to the ground, such as ray casting or a physics control like BetterCharacterControl.

Another method when using the DT_STRAIGHTPATH_ALL_CROSSINGS option is getting the height of the polygons at the borders, which gives you the poly refs too. You can then subdivide the line between two sequential points and check their height on the detail mesh, knowing which poly the points are on.

//Provide list for waypoints.
List<Vector3f> wayPoints = new ArrayList<>(pathStr.result.size());

//Add waypoints to the list
for (StraightPathItem p: pathStr.result) {
    Vector3f vector = DetourUtils.createVector3f(p.getPos());
    wayPoints.add(vector);
}

The results returned by the findStraightPath() search are next added to your waypoints list. How you use this list is a design issue for you to determine. The first point in the list will be your starting position, typically, you advance your pointer to the next waypoint in the list first, then use that point for your first navigation target. Checking your distance to the waypoint every frame and when you have reached the desired distance from the waypoint, advance to the next point in the list, repeating these steps until you reach the end. You can see examples of this in the jme3-ai tutorial.

⚠️ **GitHub.com Fallback** ⚠️