Hey, I’m coding AI for my game, and I’m thinking of using NavMeshes for the AI’s pathfinding. What libraries should I look at for NavMesh generation and traversal? Thanks in advance.
1 Like
Recast4j is very cool, because you can re-calculate tiles, so for open-world games where map can change its very good, because only tile with change can update.
This library here as i remember was not fully done. Tho it would be nice if someone would create full fledged library.
I needed to do a lot in wrapper to have it working.
im not sure what stage it is on, @mitm is this current one or there was newer?
i think one of most important parts are:
RecastBuilderConfig bcfg = new RecastBuilderConfig(cfg, new float[]{bmin.x, bmin.y, bmin.z}, new float[]{bmax.x, bmax.y, bmax.z}, tx, ty, true);
where:
protected Vector3f bmin = new Vector3f(-m_tileSize,-1000,-m_tileSize);
protected Vector3f bmax = new Vector3f(100000,1000,100000);
and config is:
cfg = new RecastConfig(m_partitionType, m_cellSize,
m_cellHeight, m_agentHeight, m_agentRadius,
m_agentMaxClimb, m_agentMaxSlope, m_regionMinSize,
m_regionMergeSize, m_edgeMaxLen, m_edgeMaxError,
m_vertsPerPoly, m_detailSampleDist, m_detailSampleMaxError,
m_tileSize, SampleAreaModifications.SAMPLE_AREAMOD_GROUND);
builder = new RecastBuilder(this);
(im sorry some descriptions are in Polish, you would need put them into translator)
public final NavMesh navMesh;
private boolean initialized = false;
private NavMeshQuery query;
private Crowd crowd;
//voxelizacja - wielkosc komorki, czym mniej tym dokladniej ale tez wiecej pozera czasu
private final float m_cellSize = 0.3f;
//voxelizacja - wysokosc komorki, czym mniej tym dokladniej ale tez wiecej pozera czasu
private final float m_cellHeight = 0.2f;
//wysokosc postaci
private final float m_agentHeight = 2.0f;
//szerokosc postaci
private final float m_agentRadius = 0.5f;
//pionowo - jak wysoko może się wspiąć jednorazowo (np. wykrywanie schodów)
private final float m_agentMaxClimb = 0.7f;
//stopień pod którym może się wspinać
private final float m_agentMaxSlope = 45.0f;
//minimalna wielkosc regionu niepołaczonej wyspy navmeshu
private final int m_regionMinSize = 8;
//regiony mniejsze od tej wielkosci jezeli to mozliwe zostaną połączone z większymi regionami
private final int m_regionMergeSize = 20;
//The maximum length of polygon edges that represent the border of meshes. //Adjust to decrease dangling errors. //>= 0, m_agentRadius * 8
private final float m_edgeMaxLen = 12.0f;
//The maximum distance the edges of meshes may deviate from the source geometry.
//A lower value will result in mesh edges following the xz-plane geometry
//contour more accurately at the expense of an increased triangle count.
//>= 0, 1.1 to 1.5 for best results.
private final float m_edgeMaxError = 1.3f;
//The maximum number of vertices per polygon for polygons generated during
//the voxel to polygon conversion process.
//>= 3
private final int m_vertsPerPoly = 6;
//Sets the sampling distance to use when matching the detail mesh to the
//surface of the original geometry.
//Higher values result in a detail mesh that conforms more closely to the
//original geometry's surface at the cost of a higher final triangle count
//and higher processing cost.
//The difference between this parameter and m_edgeMaxError is that this
//parameter operates on the height rather than the xz-plane. It also matches
//the entire detail mesh surface to the contour of the original geometry.
//m_edgeMaxError only matches edges of meshes to the contour of the original
//geometry.
//Decrease to reduce dangling errors.
//>= 0
private final float m_detailSampleDist = 3.0f;
//The maximum distance the surface of the detail mesh may deviate from the
//surface of the original geometry.
//Increase to reduce dangling errors.
//>= 0
private final float m_detailSampleMaxError = 2.0f;
//wielkość komórki - najwazniejsze, to te komorki mozna przeladowywac
private final int m_tileSize = 128;
//rodzaj rasteryzacji geometri do navmeshu
protected Vector3f bmin = new Vector3f(-m_tileSize,-1000,-m_tileSize);
protected Vector3f bmax = new Vector3f(100000,1000,100000);
protected int navMeshMaxTiles = 500; // need to care not to exceeed this
protected int navMeshMaxPolys = 32768; // same, need to care
protected int tileVisibleElipse = 10; //elipse of visible tiles, 10 mean total 20 tiles in one axis
private final RecastConstants.PartitionType m_partitionType = RecastConstants.PartitionType.WATERSHED;
and then in Thread i just use:
private final RecastBuilder builder;
private final InputGeomProvider geom;
private final RecastBuilderConfig bcfg;
and
rcResult = builder.build(geom, bcfg);
long time2 = System.nanoTime();
LOGGER.log(Level.FINE, "Tile build Done! Building took time: {0}", time2 - time1);
onDone(rcResult);
where onDone do:
if(tiles.containsKey(key)){
tiles.remove(key);
}
tiles.put(key, result);
LOGGER.log(Level.INFO, "Pathfinder, Tile generated pos: {0} {1}", new Object[]{tx, ty});
updateDetourNavMesh(key.x, key.y);
debugMeshUpdateRequired = true;
tileBuildingState.put(key, false);
“geom param” (i should name it scene or smething) are populared Geoms from JME SceneGraph and parsed for Recast
(its for InputGeomProvider)
private synchronized void updateGeometry() {
//todo - get only tile geometries that their bounding are within tile.
if(requireGeometryUpdate) {
requireGeometryUpdate = false;
Mesh mesh = new Mesh();
List<Geometry> geoms = findGeometries(CoreApp.APP.getRootNode(), new LinkedList<>());
if(geoms != null && !geoms.isEmpty()){
GeometryBatchFactory.mergeGeometries(geoms, mesh);
List<Float> vertexPositions = getVertices(mesh);
List<Integer> indices = getIndices(mesh);
setGeom(new SimpleInputGeomProvider(vertexPositions, indices));
}
}
}
as you can see todo i didnt even still done this properly, but it was working when i tested before, and even had some video:
Here are some veeeeery old videos when i were playing with pathfinding:
(please note white/blue are different tiles)
and here playing with GoalAI + navmesh:
3 Likes
i cant give full code in one message, so i will just send here full without comments
(please do not mind my test code is ugly and not well written, but it was working like in videos back then)
public class Pathfinder implements RecastBuilder.RecastBuilderProgressListener {
public Node debugNode = new Node("RecastDebugNode");
public Node debugPathNode = new Node("RecastDebugPathNode");
public final NavMesh navMesh;
private boolean initialized = false;
private NavMeshQuery query;
private Crowd crowd;
//voxelizacja - wielkosc komorki, czym mniej tym dokladniej ale tez wiecej pozera czasu
private final float m_cellSize = 0.3f;
//voxelizacja - wysokosc komorki, czym mniej tym dokladniej ale tez wiecej pozera czasu
private final float m_cellHeight = 0.2f;
//wysokosc postaci
private final float m_agentHeight = 2.0f;
//szerokosc postaci
private final float m_agentRadius = 0.5f;
//pionowo - jak wysoko może się wspiąć jednorazowo (np. wykrywanie schodów)
private final float m_agentMaxClimb = 0.7f;
//stopień pod którym może się wspinać
private final float m_agentMaxSlope = 45.0f;
//minimalna wielkosc regionu niepołaczonej wyspy navmeshu
private final int m_regionMinSize = 8;
//regiony mniejsze od tej wielkosci jezeli to mozliwe zostaną połączone z większymi regionami
private final int m_regionMergeSize = 20;
//The maximum length of polygon edges that represent the border of meshes. //Adjust to decrease dangling errors. //>= 0, m_agentRadius * 8
private final float m_edgeMaxLen = 12.0f;
//The maximum distance the edges of meshes may deviate from the source geometry.
//A lower value will result in mesh edges following the xz-plane geometry
//contour more accurately at the expense of an increased triangle count.
//>= 0, 1.1 to 1.5 for best results.
private final float m_edgeMaxError = 1.3f;
//The maximum number of vertices per polygon for polygons generated during
//the voxel to polygon conversion process.
//>= 3
private final int m_vertsPerPoly = 6;
//Sets the sampling distance to use when matching the detail mesh to the
//surface of the original geometry.
//Higher values result in a detail mesh that conforms more closely to the
//original geometry's surface at the cost of a higher final triangle count
//and higher processing cost.
//The difference between this parameter and m_edgeMaxError is that this
//parameter operates on the height rather than the xz-plane. It also matches
//the entire detail mesh surface to the contour of the original geometry.
//m_edgeMaxError only matches edges of meshes to the contour of the original
//geometry.
//Decrease to reduce dangling errors.
//>= 0
private final float m_detailSampleDist = 3.0f;
//The maximum distance the surface of the detail mesh may deviate from the
//surface of the original geometry.
//Increase to reduce dangling errors.
//>= 0
private final float m_detailSampleMaxError = 2.0f;
//wielkość komórki - najwazniejsze, to te komorki mozna przeladowywac
private final int m_tileSize = 128;
//rodzaj rasteryzacji geometri do navmeshu
protected Vector3f bmin = new Vector3f(-m_tileSize,-1000,-m_tileSize);
protected Vector3f bmax = new Vector3f(100000,1000,100000);
protected int navMeshMaxTiles = 500; // need to care not to exceeed this
protected int navMeshMaxPolys = 32768; // same, need to care
protected int tileVisibleElipse = 10; //elipse of visible tiles, 10 mean total 20 tiles in one axis
private final RecastConstants.PartitionType m_partitionType = RecastConstants.PartitionType.WATERSHED;
private RecastBuilder builder;
private InputGeomProvider geom;
private RecastConfig cfg;
//todo tiles tak samo ograniczac ilosc jak navMeshTileRefs, poniewaz zapcha pamiec
private final HashMap<Point, RecastBuilder.RecastBuilderResult> tiles = new HashMap<>();
private final HashMap<Point, Boolean> tileBuildingState = new HashMap<>();
private final HashMap<Point, Long> navMeshTileRefs = new HashMap<>();
private boolean requireGeometryUpdate = true;
private final ArrayList<Point> requireUpdateTiles = new ArrayList<>();
private float updateNavMeshTimeCurr = 0f;
private final float updateNavMeshTimeMax = 0.5f;
private float updateNavMeshVisibleTilesTimeCurr = 0f;
private final float updateNavMeshVisibleTilesTimeMax = 5f;
private int[] closeTilePos;
private int threadNum;
private Thread[] buildTileThreads;
private boolean debugMeshUpdateRequired = false;
private static final Logger LOGGER = Logger.getLogger(Pathfinder.class.getName());
public Pathfinder() {
prepareRecastMesh();
NavMeshParams navMeshParams = new NavMeshParameters();
// ustawia origin dla navmesh(detour) - MUSI BYC SPOJNY Z ORIGIN DLA RECAST
RecastVectors.copy(navMeshParams.orig, new float[]{bmin.x, bmin.y, bmin.z});
navMeshParams.tileWidth = m_tileSize * m_cellSize;
navMeshParams.tileHeight = m_tileSize * m_cellSize;
navMeshParams.maxTiles = navMeshMaxTiles;
navMeshParams.maxPolys = navMeshMaxPolys;
this.navMesh = new NavMesh(navMeshParams, 6);
}
public synchronized InputGeomProvider getGeom(){
return this.geom;
}
public synchronized void setGeom(InputGeomProvider geom){
this.geom = geom;
}
public void init(int threadNum) {
this.threadNum = threadNum;
this.buildTileThreads = new BetterThread[this.threadNum];
CoreApp.APP.getRootNode().attachChild(debugNode);
CoreApp.APP.getRootNode().attachChild(debugPathNode);
setupCrowd(navMesh);
initialized = true;
}
public void update(float tpf) {
if(initialized && CoreApp.APP.ecs.getSystemByClass(PlayerControlSystem.class) != null){
getCrowd().update(tpf, null);
Vector3f playerPos = CoreApp.APP.ecs.getSystemByClass(PlayerControlSystem.class).player.getComponent(GridComponent.class).localLocation;
if(playerPos != null){
closeTilePos = getDetourTileLocation(playerPos);
if(closeTilePos != null){
//System.out.println("player close tile pos: "+ closeTilePos[0] + "," + closeTilePos[1]);
updateNavMeshTimeCurr+=tpf;
if(updateNavMeshTimeCurr >= updateNavMeshTimeMax){
updateNavMeshTimeCurr = 0;
buildRecastTile(closeTilePos[0],closeTilePos[1]);
buildRecastTile(closeTilePos[0]-1,closeTilePos[1]);
buildRecastTile(closeTilePos[0],closeTilePos[1]-1);
buildRecastTile(closeTilePos[0]-1,closeTilePos[1]-1);
buildRecastTile(closeTilePos[0]+1,closeTilePos[1]-1);
buildRecastTile(closeTilePos[0]+1,closeTilePos[1]);
buildRecastTile(closeTilePos[0],closeTilePos[1]+1);
buildRecastTile(closeTilePos[0]+1,closeTilePos[1]+1);
buildRecastTile(closeTilePos[0]-1,closeTilePos[1]+1);
if(getFreeBuildThread() != null){
int xMin = closeTilePos[0] - 3;
int xMax = closeTilePos[0] + 3;
int yMin = closeTilePos[1] - 3;
int yMax = closeTilePos[1] + 3;
for (int x = xMin; x < xMax; x++) {
for (int y = yMin; y < yMax; y++) {
buildRecastTile(x,y);
}
}
}
if(debugMeshUpdateRequired) {
debugMeshUpdateRequired = false;
debugRecastMesh(new Vector3f(0, 0.2f, 0));
}
}
updateNavMeshVisibleTilesTimeCurr+=tpf;
if(updateNavMeshVisibleTilesTimeCurr >= updateNavMeshVisibleTilesTimeMax){
updateNavMeshVisibleTilesTimeCurr = 0;
updateDetourNavMeshVisibleTiles(closeTilePos[0], closeTilePos[1]);
}
}
}
}
}
public LinkedList<Vector3f> findPath(Vector3f start, Vector3f end){
RecastNavControl recastNavControl = new RecastNavControl(navMesh);
return recastNavControl.findPath(start, end);
}
public void buildAllTiles() {
//todo - test
RecastBuilder.RecastBuilderResult[][] rcResult = builder.buildTiles(getGeom(), cfg, threadNum);
// update maxTiles
int tw = rcResult.length;
int th = rcResult[0].length;
getNavMesh().getParams().maxTiles = tw * th;
for (int y = 0; y < th; y++) {
for (int x = 0; x < tw; x++) {
tiles.put(new Point(x,y), rcResult[x][y]);
updateDetourNavMesh(x, y);
}
}
}
public void saveTilesData() {
//todo
}
public void loadTilesData() {
//todo
}
public synchronized void markTileInLocationToUpdate(Spatial spatToUpdate) {
markTileInLocationToUpdate((BoundingBox)spatToUpdate.getWorldBound());
}
public synchronized void markTileInLocationToUpdate(BoundingBox bounding) {
float xExtent = bounding.getXExtent();
float zExtent = bounding.getZExtent();
float xExtentIncrease = xExtent/2;
float zExtentIncrease = zExtent/2;
for (float x = bounding.getCenter().x - xExtent; x < bounding.getCenter().x + xExtent; x+=xExtentIncrease) {
for (float z = bounding.getCenter().z - zExtent; z < bounding.getCenter().z + zExtent; z+=zExtentIncrease) {
markTileInLocationToUpdate(new Vector3f(x, bounding.getCenter().y, z));
}
}
}
public synchronized void markTileInLocationToUpdate(Vector3f pos) {
LOGGER.log(Level.INFO, "markTileInLocationToUpdate: {0}", pos);
int[] vector = getDetourTileLocation(pos);
if(vector.length > 0){
System.out.println("markTileInLocationToUpdate" + Arrays.toString(vector));
LOGGER.log(Level.INFO, "markTileInLocationToUpdate tilepos: {0} {1}", new Object[]{vector[0], vector[1]});
if(!requireUpdateTiles.contains(new Point(vector[0], vector[1]))){
requireUpdateTiles.add(new Point(vector[0], vector[1]));
requireGeometryUpdate = true;
}
}
}
private Integer getFreeBuildThread() {
for (int i = 0; i < threadNum; i++) {
if(buildTileThreads[i] == null){
return i;
}
}
return null;
}
private synchronized void updateGeometry() {
//todo - get only tile geometries that their bounding are within tile.
if(requireGeometryUpdate) {
requireGeometryUpdate = false;
Mesh mesh = new Mesh();
List<Geometry> geoms = findGeometries(CoreApp.APP.getRootNode(), new LinkedList<>());
if(geoms != null && !geoms.isEmpty()){
GeometryBatchFactory.mergeGeometries(geoms, mesh);
List<Float> vertexPositions = getVertices(mesh);
List<Integer> indices = getIndices(mesh);
// System.out.println("update geometry center:");
// System.out.println(mesh.getBound().getCenter());
// System.out.println(mesh.getBound().getVolume());
// System.out.println(((BoundingBox)mesh.getBound()).getXExtent());
setGeom(new SimpleInputGeomProvider(vertexPositions, indices));
}
}
}
private void prepareRecastMesh() {
cfg = new RecastConfig(m_partitionType, m_cellSize,
m_cellHeight, m_agentHeight, m_agentRadius,
m_agentMaxClimb, m_agentMaxSlope, m_regionMinSize,
m_regionMergeSize, m_edgeMaxLen, m_edgeMaxError,
m_vertsPerPoly, m_detailSampleDist, m_detailSampleMaxError,
m_tileSize, SampleAreaModifications.SAMPLE_AREAMOD_GROUND);
builder = new RecastBuilder(this);
}
private synchronized boolean buildRecastTile(final int tx, final int ty) {
updateGeometry();
final Point key = new Point(tx, ty);
if(getFreeBuildThread() != null && (!tiles.containsKey(key) || requireUpdateTiles.contains(key)) && !(tileBuildingState.containsKey(key) && tileBuildingState.get(key) == true)) {
tileBuildingState.put(key, true);
if(requireUpdateTiles.contains(key)){
requireUpdateTiles.remove(key);
}
final int newThreadNum = getFreeBuildThread();
//RecastBuilderConfig bcfg = new RecastBuilderConfig(cfg, geom.getMeshBoundsMin(), geom.getMeshBoundsMax(), tx, ty, true); //todo 0 0
RecastBuilderConfig bcfg = new RecastBuilderConfig(cfg, new float[]{bmin.x, bmin.y, bmin.z}, new float[]{bmax.x, bmax.y, bmax.z}, tx, ty, true); //todo 0 0
BuildRecastTileThread buildRecastTileThread = new BuildRecastTileThread(builder, getGeom(), bcfg) {
@Override
public void onDone(RecastBuilder.RecastBuilderResult result) {
buildTileThreads[newThreadNum] = null;
synchronized(tiles){
if(tiles.containsKey(key)){
tiles.remove(key);
}
tiles.put(key, result);
LOGGER.log(Level.INFO, "Pathfinder, Tile generated pos: {0} {1}", new Object[]{tx, ty});
updateDetourNavMesh(key.x, key.y);
debugMeshUpdateRequired = true;
tileBuildingState.put(key, false);
}
}
};
buildTileThreads[newThreadNum] = new BetterThread(buildRecastTileThread, "buildRecastTile");
buildTileThreads[newThreadNum].start();
return true;
}
return false;
}
// private void fillDetourNavMesh() {
// for (Iterator<Point> iterator = tiles.keySet().iterator(); iterator.hasNext();) {
// Point key = iterator.next();
// updateDetourNavMesh(key.x, key.y);
// }
// }
private NavMeshDataCreateParams getDetourNavMeshPolymeshParams(int x, int y) {
RecastBuilder.RecastBuilderResult tile = tiles.get(new Point(x,y));
if(tile != null){
PolyMesh pmesh = tile.getMesh();
if (pmesh.npolys != 0) {
for (int i = 0; i < pmesh.npolys; ++i) {
pmesh.flags[i] = 1;
}
NavMeshDataCreateParams params = new NavMeshDataParameters();
params.verts = pmesh.verts;
params.vertCount = pmesh.nverts;
params.polys = pmesh.polys;
params.polyAreas = pmesh.areas;
params.polyFlags = pmesh.flags;
params.polyCount = pmesh.npolys;
params.nvp = pmesh.nvp;
PolyMeshDetail dmesh = tile.getMeshDetail();
params.detailMeshes = dmesh.meshes;
params.detailVerts = dmesh.verts;
params.detailVertsCount = dmesh.nverts;
params.detailTris = dmesh.tris;
params.detailTriCount = dmesh.ntris;
params.walkableHeight = m_agentHeight;
params.walkableRadius = m_agentRadius;
params.walkableClimb = m_agentMaxClimb;
params.bmin = pmesh.bmin;
params.bmax = pmesh.bmax;
params.cs = m_cellSize;
params.ch = m_cellHeight;
params.tileX = x;
params.tileY = y;
params.buildBvTree = true;
return params;
}
}
return null;
}
private synchronized void updateDetourNavMeshVisibleTiles(int x, int y) {
System.out.println("updateDetourNavMeshVisibleTiles");
synchronized(navMeshTileRefs){
ArrayList<Point> visibleTiles = new ArrayList<>();
for (int xi = x - tileVisibleElipse; xi <= x + tileVisibleElipse; xi++) {
for (int yi = y - tileVisibleElipse; yi <= y + tileVisibleElipse; yi++) {
Point key = new Point(xi,yi);
if(!navMeshTileRefs.containsKey(key)){
addTile(key, 0);
// NavMeshDataCreateParams params = getDetourNavMeshPolymeshParams(xi, yi);
// if(params != null){
// long ref = navMesh.addTile(NavMeshBuilder.createNavMeshData(params), 0, 0);
// navMeshTileRefs.put(key, ref);
// LOGGER.log(Level.INFO, "Pathfinder, adding tile to visible: {0}, {1}", new Object[]{xi, yi});
// }
}
visibleTiles.add(key);
}
}
for (Iterator<Point> iterator = navMeshTileRefs.keySet().iterator(); iterator.hasNext();) {
Point key = iterator.next();
if(!visibleTiles.contains(key)){
removeTile(key);
// long tileReference = navMeshTileRefs.get(key);
// navMesh.removeTile(tileReference);
// iterator.remove();
// LOGGER.log(Level.INFO, "Pathfinder, removing tile from visible: {0}, {1}", new Object[]{key.x, key.y});
}
}
}
debugMeshUpdateRequired = true;
}
/*
* Update only existing and visible tiles in NavMesh detour.
* if tile is generated, but not visible in navmesh, it will do nothing
*/
private synchronized void updateDetourNavMesh(int x, int y) {
Point key = new Point(x,y);
NavMeshDataCreateParams params = getDetourNavMeshPolymeshParams(x, y);
if(params != null){
synchronized(navMeshTileRefs){
if(navMeshTileRefs.containsKey(key)){
replaceTile(key);
// LOGGER.log(Level.INFO, "Pathfinder, replacing tile to visible: {0}, {1}", new Object[]{x, y});
// long tileReplaceReference = navMeshTileRefs.get(key);
// navMesh.removeTile(tileReplaceReference);
// navMeshTileRefs.remove(key);
// long ref = navMesh.addTile(NavMeshBuilder.createNavMeshData(params), 0, 0);
// navMeshTileRefs.put(key, ref);
}
}
}
}
public float[] getDetourProjectedLocation(Vector3f pos) {
float[] vectors = new float[3];
vectors[0] = pos.x;
vectors[1] = pos.y;
vectors[2] = pos.z;
return vectors;
}
public int[] getDetourTileLocation(Vector3f pos) {
return getNavMesh().calcTileLoc(getDetourProjectedLocation(pos));
}
//(-255.1, 0.17136395, -253.01135)
//`InputGeom` is a part of the demo and unrelated to the tile cache.
//
//It would certainly be possible to only rebuild parts of the tiles and reload those, using `dtTileCache::removeTile`, `dtTileCache::addTile` and `dtTileCache::buildNavMeshTilesAt`. The demo does not demonstrate how to do this.
public void debugPath(LinkedList<Vector3f> waypoints){
debugPathNode.detachAllChildren();
Material lineMat = new Material(CoreApp.APP.getAssetManager(), "Common/MatDefs/Misc/Unshaded.j3md");
lineMat.setColor("Color",ColorRGBA.Orange);
Vector3f lastVector = null;
for (Vector3f waypoint : waypoints) {
if(lastVector != null){
Line line = new Line(lastVector, waypoint);
Geometry lineGeom = new Geometry("debugLine", line);
lineGeom.setMaterial(lineMat);
lineGeom.setQueueBucket(RenderQueue.Bucket.Translucent);
debugPathNode.attachChild(lineGeom);
}
lastVector = waypoint;
}
}
private synchronized Long removeTile(Point point){
synchronized(navMesh) {
Long tileReference = navMeshTileRefs.get(point);
try {
if(tileReference != null) {
getNavMesh().removeTile(tileReference);
navMeshTileRefs.remove(point);
} else {
List<MeshTile> tilesToRemove = getNavMesh().getTilesAt(point.x, point.y);
for (Iterator<MeshTile> iterator = tilesToRemove.iterator(); iterator.hasNext();) {
MeshTile next = iterator.next();
getNavMesh().removeTile(getNavMesh().getTileRef(next));
}
}
LOGGER.log(Level.INFO, "Pathfinder, removed tile from visible: {0}, {1}", new Object[]{point.x, point.y});
} catch(Exception err) {
LOGGER.log(Level.WARNING, "Pathfinder, Unable to remove tile!", err);
}
return tileReference;
}
}
private synchronized void addTile(Point point, long tileReference){
synchronized(navMesh) {
NavMeshDataCreateParams params = getDetourNavMeshPolymeshParams(point.x, point.y);
if(params != null) {
try {
long ref = getNavMesh().addTile(NavMeshBuilder.createNavMeshData(params), 0, tileReference);
navMeshTileRefs.put(point, ref);
LOGGER.log(Level.INFO, "Pathfinder, adding tile to visible: {0}, {1}", new Object[]{point.x, point.y});
} catch(Exception err) {
removeTile(point);
LOGGER.log(Level.WARNING, "Pathfinder, Unable to add tile! removing to make sure its clear", err);
}
}
}
}
private synchronized void replaceTile(Point point){
synchronized(navMesh) {
Long tileReference = removeTile(point);
addTile(point, tileReference != null ? tileReference : 0);
}
}
private Vector3f[] getVector3Array(PolyMeshDetail dmesh) {
Vector3f[] vector3Array = new Vector3f[dmesh.nverts];
for (int i = 0; i < dmesh.nverts; i++) {
vector3Array[i] = new Vector3f(dmesh.verts[i * 3], dmesh.verts[i * 3 + 1], dmesh.verts[i * 3 + 2]);
}
return vector3Array;
}
public void addAgentGrid(int size, float distance, int updateFlags, int obstacleAvoidanceType, float[] startPos) {
//todo use it
CrowdAgentParams ap = getAgentParams(updateFlags, obstacleAvoidanceType);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
float[] pos = new float[3];
pos[0] = startPos[0] + i * distance;
pos[1] = startPos[1];
pos[2] = startPos[2] + j * distance;
int addAgent = getCrowd().addAgent(pos, ap);
}
}
}
public void setMoveTarget(float[] pos, boolean adjust) {
//todo use it
float[] ext = getCrowd().getQueryExtents();
QueryFilter filter = getCrowd().getFilter(0);
if (adjust) {
for (int i = 0; i < getCrowd().getAgentCount(); i++) {
CrowdAgent ag = getCrowd().getAgent(i);
if (!ag.isActive()) {
continue;
}
float[] vel = calcVel(ag.npos, pos, ag.params.maxSpeed);
getCrowd().requestMoveVelocity(i, vel);
}
} else {
FindNearestPolyResult nearest = query.findNearestPoly(pos, ext, filter);
for (int i = 0; i < getCrowd().getAgentCount(); i++) {
CrowdAgent ag = getCrowd().getAgent(i);
if (!ag.isActive()) {
continue;
}
getCrowd().requestMoveTarget(i, nearest.getNearestRef(), nearest.getNearestPos());
}
}
}
protected float[] calcVel(float[] pos, float[] tgt, float speed) {
float[] vel = vSub(tgt, pos);
vel[1] = 0.0f;
vNormalize(vel);
vel = vScale(vel, speed);
return vel;
}
/**
* @return the crowd
*/
public Crowd getCrowd() {
return crowd;
}
/**
* @return the query
*/
public synchronized NavMeshQuery getQuery() {
return query;
}
/**
* Returns a built Recast NavMesh.
*
* @return the generated NavMesh
*/
public synchronized NavMesh getNavMesh() {
return navMesh;
}
/**
* Progress method.
*
* @param i how much done
* @param i1 how many to do
*/
@Override
public void onProgress(int i, int i1) {
System.out.println("onProgress "+ i + " " + i1);
}
protected void setupCrowd(NavMesh navMesh) {
query = new NavMeshQuery(navMesh);
crowd = new Crowd(1500, 0.6f, navMesh);
ObstacleAvoidanceParams params = new ObstacleAvoidanceParams();
params.velBias = 0.5f;
params.adaptiveDivs = 5;
params.adaptiveRings = 2;
params.adaptiveDepth = 1;
getCrowd().setObstacleAvoidanceParams(0, params);
params = new ObstacleAvoidanceParams();
params.velBias = 0.5f;
params.adaptiveDivs = 5;
params.adaptiveRings = 2;
params.adaptiveDepth = 2;
getCrowd().setObstacleAvoidanceParams(1, params);
params = new ObstacleAvoidanceParams();
params.velBias = 0.5f;
params.adaptiveDivs = 7;
params.adaptiveRings = 2;
params.adaptiveDepth = 3;
getCrowd().setObstacleAvoidanceParams(2, params);
params = new ObstacleAvoidanceParams();
params.velBias = 0.5f;
params.adaptiveDivs = 7;
params.adaptiveRings = 3;
params.adaptiveDepth = 3;
getCrowd().setObstacleAvoidanceParams(3, params);
}
protected CrowdAgentParams getAgentParams(int updateFlags, int obstacleAvoidanceType) {
CrowdAgentParams ap = new CrowdAgentParams();
ap.radius = 0.6f;
ap.height = 2f;
ap.maxAcceleration = 8.0f;
ap.maxSpeed = 3.5f;
ap.collisionQueryRange = ap.radius * 12f;
ap.pathOptimizationRange = ap.radius * 30f;
ap.updateFlags = updateFlags;
ap.obstacleAvoidanceType = obstacleAvoidanceType;
ap.separationWeight = 2f;
return ap;
}
cant send all code in 1 message so need split at 2:
(and i cant send part 2 because HUB dont allow me post 3 messages in row lol)
1 Like
private List<Geometry> findGeometries(Node node, List<Geometry> geoms) {
for (Iterator<Spatial> it = node.getChildren().iterator(); it.hasNext();) {
Spatial spatial = it.next();
if (!(spatial instanceof ParticleEmitter) && !(spatial instanceof AudioNode) && spatial.getName() != null && !spatial.getName().equals("Sky") && !spatial.getName().equals("water") && !spatial.getName().equals("NavMesh") && !spatial.getName().equals("Marker") && !spatial.getName().equals("MarkerNormal") && !spatial.getName().contains("Debug")) {
if (spatial instanceof Geometry) {
if(((Geometry) spatial).getMesh().getMode() != Mesh.Mode.Lines){
Mesh clone = ((Geometry) spatial).getMesh().clone();
Geometry g = new Geometry("merged" + spatial.getName());
g.setMesh(clone);
g.setLocalScale(spatial.getWorldScale());
g.setLocalRotation(spatial.getWorldRotation());
g.setLocalTranslation(spatial.getWorldTranslation().subtract(new Vector3f(0, m_cellHeight, 0)));
//System.out.println("distance:" + g.getWorldTranslation().distance(CoreApp.APP.player.getPlayerLocation()));
//if(g.getWorldTranslation().distance(CoreApp.APP.player.getPlayerLocation()) < 400){
geoms.add(g);
//}
//System.out.println("findGeometries " + spatial.getName());
}
} else if (spatial instanceof Node) {
if (spatial instanceof Terrain) {
Mesh merged = terrain2mesh((Terrain) spatial);
Geometry g = new Geometry("merged" + spatial.getName());
g.setMesh(merged);
g.setLocalScale(spatial.getLocalScale());
//must offset due to terrain2mesh offsetting
g.setLocalTranslation(spatial.getLocalTranslation().subtract(new Vector3f(-0.5f, m_cellHeight, -0.5f)));
//System.out.println("distance:" + g.getWorldTranslation().distance(CoreApp.APP.player.getPlayerLocation()));
//if(g.getWorldTranslation().distance(CoreApp.APP.player.getPlayerLocation()) < 400){
geoms.add(g);
//}
//System.out.println("findGeometries " + spatial.getName());
} else {
findGeometries((Node) spatial, geoms);
}
}
}
}
return geoms;
}
private Mesh terrain2mesh(Terrain terr) {
float[] heights = terr.getHeightMap();
int length = heights.length;
int side = (int) FastMath.sqrt(heights.length);
float[] vertices = new float[length * 3];
int[] indices = new int[(side - 1) * (side - 1) * 6];
// Vector3f trans = ((Node) terr).getWorldTranslation().clone();
Vector3f trans = new Vector3f(0, 0, 0);
trans.x -= terr.getTerrainSize() / 2.0f;
trans.z -= terr.getTerrainSize() / 2.0f;
float offsetX = trans.x;
float offsetZ = trans.z;
// do vertices
int i = 0;
for (int z = 0; z < side; z++) {
for (int x = 0; x < side; x++) {
vertices[i++] = x + offsetX;
vertices[i++] = heights[z * side + x];
vertices[i++] = z + offsetZ;
}
}
// do indexes
i = 0;
for (int z = 0; z < side - 1; z++) {
for (int x = 0; x < side - 1; x++) {
// triangle 1
indices[i++] = z * side + x;
indices[i++] = (z + 1) * side + x;
indices[i++] = (z + 1) * side + x + 1;
// triangle 2
indices[i++] = z * side + x;
indices[i++] = (z + 1) * side + x + 1;
indices[i++] = z * side + x + 1;
}
}
Mesh mesh2 = new Mesh();
mesh2.setBuffer(VertexBuffer.Type.Position, 3, vertices);
mesh2.setBuffer(VertexBuffer.Type.Index, 3, indices);
mesh2.updateBound();
mesh2.updateCounts();
return mesh2;
}
/**
* Get vertcices of a mesh boxed to Float.
*
* @param mesh
* @return Returns boxed List of vertices.
*/
private List<Float> getVertices(Mesh mesh) {
FloatBuffer buffer = mesh.getFloatBuffer(VertexBuffer.Type.Position);
float[] vertexArray = BufferUtils.getFloatArray(buffer);
List<Float> vertexList = new ArrayList<>();
for (float vertex : vertexArray) {
vertexList.add(vertex);
}
return vertexList;
}
/**
* Get all triangles from a mesh boxed to Integer.
*
* @param mesh
* @return Returns boxed List of triangles.
*/
private List<Integer> getIndices(Mesh mesh) {
int[] indices = new int[3];
Integer[] triangles = new Integer[mesh.getTriangleCount() * 3];
for (int i = 0; i < triangles.length; i += 3) {
mesh.getTriangle(i / 3, indices);
triangles[i] = indices[0];
triangles[i + 1] = indices[1];
triangles[i + 2] = indices[2];
}
//Independent copy so Arrays.asList is garbage collected
List<Integer> indicesList = new ArrayList<>(Arrays.asList(triangles));
return indicesList;
}
private void debugRecastMesh(Vector3f offset){
debugNode.detachAllChildren();
synchronized(tiles) {
//System.out.println("debugRecastMesh");
//System.out.println(tiles.size());
//System.out.println(navMeshTileRefs.size());
for (Map.Entry<Point, RecastBuilder.RecastBuilderResult> entry : tiles.entrySet()) {
Point key = entry.getKey();
Material lineMat = new Material(CoreApp.APP.getAssetManager(), "Common/MatDefs/Misc/Unshaded.j3md");
if(closeTilePos != null && key.x == closeTilePos[0] && key.y == closeTilePos[1]){
lineMat.setColor("Color",ColorRGBA.Blue);
} else {
lineMat.setColor("Color",ColorRGBA.White);
}
//System.out.println("Tile["+key.x+","+key.y+"]");
RecastBuilder.RecastBuilderResult tile = entry.getValue();
if(navMeshTileRefs.containsKey(key)){
PolyMesh pmesh = tile.getMesh();
PolyMeshDetail dmesh = tile.getMeshDetail();
if (pmesh.npolys != 0) {
//System.out.println("debugRecastMesh verts" + pmesh.nverts);
Vector3f[] vectors = new Vector3f[dmesh.nverts];
for (int v = 0; v < pmesh.nverts; v++) {
vectors[v] = new Vector3f((pmesh.bmin[0] + pmesh.verts[v * 3] * pmesh.cs), (pmesh.bmin[1] + pmesh.verts[v * 3 + 1] * pmesh.ch), (pmesh.bmin[2] + pmesh.verts[v * 3 + 2] * pmesh.cs));
}
for (int i = 0; i < pmesh.npolys; i++) {
int p = i * pmesh.nvp * 2;
//face
Vector3f firstVector = null;
Vector3f lastVector = null;
for (int j = 0; j < pmesh.nvp; ++j) {
int v = pmesh.polys[p + j];
if (v == RecastConstants.RC_MESH_NULL_IDX) {
break;
}
if(firstVector == null){
firstVector = vectors[v];
}
if(lastVector != null){
Line line = new Line(lastVector.add(offset), vectors[v].add(offset));
Geometry lineGeom = new Geometry("debugLine", line);
lineGeom.setMaterial(lineMat);
//lineGeom.setQueueBucket(RenderQueue.Bucket.Translucent);
debugNode.attachChild(lineGeom);
}
lastVector = vectors[v];
}
if(firstVector != null && lastVector != null){
Line line = new Line(lastVector.add(offset), firstVector.add(offset));
// System.out.println("line");
// System.out.println(lastVector.add(offset));
// System.out.println(firstVector.add(offset));
Geometry lineGeom = new Geometry("debugLine", line);
lineGeom.setMaterial(lineMat);
//lineGeom.setQueueBucket(RenderQueue.Bucket.Translucent);
debugNode.attachChild(lineGeom);
}
}
}
}
}
}
}
}
public abstract class BuildRecastTileThread implements Runnable {
private RecastBuilder.RecastBuilderResult rcResult;
private final RecastBuilder builder;
private final InputGeomProvider geom;
private final RecastBuilderConfig bcfg;
private static final Logger LOGGER = Logger.getLogger(BuildRecastTileThread.class.getName());
public BuildRecastTileThread(RecastBuilder builder, InputGeomProvider inputGeomProvider, RecastBuilderConfig bcfg) {
this.builder = builder;
this.geom = inputGeomProvider;
this.bcfg = bcfg;
}
@Override
public void run() {
long time1 = System.nanoTime();
rcResult = builder.build(geom, bcfg);
long time2 = System.nanoTime();
LOGGER.log(Level.FINE, "Tile build Done! Building took time: {0}", time2 - time1);
onDone(rcResult);
}
public abstract void onDone(RecastBuilder.RecastBuilderResult result);
}
public class EntityMoveControl extends AbstractControl {
private Vector3f currentVector;
private LinkedList<Vector3f> waypoints = new LinkedList<>();
private RecastNavControl recastNavControl;
public EntityMoveControl() {
}
public Vector3f getCurrentVector() {
return currentVector;
}
public void goTo(Vector3f vect){
currentVector = null;
if(spatial != null && vect != null && recastNavControl != null) {
waypoints = recastNavControl.findPath(spatial.getWorldTranslation(), vect);
}
// System.out.println("waypoints: ");
// System.out.println(waypoints);
}
public void stop(){
currentVector = null;
waypoints.clear();
}
@Override
public void setSpatial(Spatial spatial) {
super.setSpatial(spatial);
}
@Override
protected void controlUpdate(float tpf){
if(recastNavControl == null) {
if(CoreApp.APP.pathfinder.navMesh != null){
recastNavControl = new RecastNavControl(CoreApp.APP.pathfinder.navMesh);
}
} else {
if(currentVector == null){
if(!waypoints.isEmpty()){
CoreApp.APP.pathfinder.debugPath(waypoints);
currentVector = waypoints.pop();
}
} else {
float distance = spatial.getLocalTranslation().distance(currentVector);
if(distance > 0.01f){
spatial.getLocalTranslation().interpolateLocal(currentVector, (tpf * 10) / distance);
spatial.setLocalTranslation(spatial.getLocalTranslation());
float newDistance = spatial.getLocalTranslation().distance(currentVector);
if(newDistance > distance && distance < 1f){
spatial.setLocalTranslation(currentVector);
}
spatial.lookAt(currentVector, Vector3f.UNIT_Y);
} else {
currentVector = null;
}
}
}
}
@Override
protected void controlRender(RenderManager rm, ViewPort vp) {
}
}
public class RecastNavControl extends NavMeshQuery {
//extents The search distance along each axis. [(x, y, z)]
//jak daleko ma szukać ściezki po płaszczyznach
private final float[] extents = new float[]{6, 10, 6};
public RecastNavControl(NavMesh nav) {
super(nav);
}
public LinkedList<Vector3f> findPath(Vector3f startVect, Vector3f endVect) {
// float[] startArray = CoreApp.app.pathfinder.getDetourProjectedLocation(startVect);
// float[] endArray = CoreApp.app.pathfinder.getDetourProjectedLocation(endVect);
LinkedList<Vector3f> waypoints = new LinkedList<>();
QueryFilter filter = new DefaultQueryFilter();
float[] endArray = new float[3];
float[] startArray = new float[3];
startVect.toArray(startArray);
endVect.toArray(endArray);
FindNearestPolyResult startPos = findNearestPoly(startArray, extents, filter);
FindNearestPolyResult endPos = findNearestPoly(endArray, extents, filter);
Result<List<Long>> path = findPath(startPos.getNearestRef(), endPos.getNearestRef(), startPos.getNearestPos(), endPos.getNearestPos(), filter);
if(path.result != null){
Result<List<StraightPathItem>> straightPath = findStraightPath(startPos.getNearestPos(), endPos.getNearestPos(), path.result, Integer.MAX_VALUE, 0);
for (int i = 0; i < straightPath.result.size(); i++) {
float[] pos = new float[3];
pos[0] = straightPath.result.get(i).getPos()[0];
pos[1] = straightPath.result.get(i).getPos()[1];
pos[2] = straightPath.result.get(i).getPos()[2];
Vector3f vector = new Vector3f(pos[0], pos[1], pos[2]);
waypoints.add(vector);
}
System.out.println("RecastNavControl waypoints " + waypoints);
}
return waypoints;
}
}
2 Likes
Wow, that’s a whole mess of code. 
Thanks for sharing it with me.
1 Like
But its really not good code what i wrote for test purpose there ;p, also there are some Mitm code there.
I think it could be lowered by 50%, but in same time also still some more due to proper Agent movement classes that are missing.
You should look Demo one, i just given my Test code if you might like to see some params/etc 
1 Like
Hi @codex, Recast4j is a very powerful library, but also very complex to use and configure.
If you are new to NavMesh I would suggest you start with something simple. The SDK already provides a tool to generate a NavMesh jme-wiki.
- Open your scene in the Terrain Editor or Scene Explorer by RMB selecting the file in your assets folder and choosing
Edit TerrainorEdit in SceneComposer.- Once open, RMB select the root node in the
SceneExplorerand then selectSpatial NavMesh
You will then need to write a controller (e.g. NavMeshAgent) that uses the jME3-ai library to compute paths to the desired point.
You can find some very interesting examples here:
I created a git repo where I optimized these functions by making them easier and clearer to use inspired a lot by Unity. I added useful tools for debugging NavMesh (see NavMeshDebugRenderer) and for visualizing the paths calculated by Agents (see PathViewer). I also added tools for exporting NavMesh (see NavMeshExporter), for reading/writing construction parameters (see NavMeshProperties & NavMeshBuildSettings), a graphical editor written with Lemur if you don’t use the SDK (see NavMeshEditorState). I have also retrieved links to documentation for sites that are no longer available and all source code.
The demo also contains some examples on physics optimization and the use of InstancedNodes suggested to me by @Ali_RS and @sgold
If you find the project useful and have suggestions for improvement, please feel free to write to me.
Here is a demo from my YT channel:
5 Likes