Mesh Navigation buildNavigationPath

Hi,



i created a navigation mesh of my level using the java implementation of CRITTERAI



now i was trying to compute a path calling the method buildNavigationPath but i don’t know which parameters

put in because everytime i get a false calling this method… any advices or an example of how to use it?

If you checkout the latest version of the SDK from trunk we added in the navmesh generator. Just right-click on any spatial in the scene explorer and select the navmesh generate option (can’t remember the actual name sorry).



As for building the path, where did you get the code to generate the path?

To generate the path

i used the critterai jar contained in the jm3tools, is it a good java porting or not?

As far as I can tell the only navmesh “path” calculation we have is in MonkeyZone. It isn’t perfect but it will generate the path for you.



The latest (which isn’t very new) critterai java port is v0.2, and it doesn’t have actual path generation.

The navmesh code in MonkeyZone was never really working or active in the game… Its just there, no guarantees :wink:

Yes pardon,



i am using critterai for the mesh generation

and to compute the path i am using the code taken from the monkey zone.

Is in this code that i am experiencing the problem because i always get a false.

Is there a better library to create a navigation mesh in java?

More on this , which implementation is the jdk using to create the navigation mesh?

The SDK uses the critterai v0.2 jar to generate the mesh.



The only navmesh path calculation we have so far is in MonkeyZone. It does work, I have used it. I suggest you run it in debug mode and see what is failing.

Thank you ,

my actual problem is that i don’t know how to populate the parameters :



path, currentCell, currentPos3d, goalCell, goalPos3d, entityRadius



in particular currentCell and goalCell.

when I use it I call “computePath()”

[java]

// 1) make sure the point is in the navMesh

targetLocation = navMeshPathfinder.warpInside(targetLocation);

// 2) init the navMesh position and cell data

navMeshPathfinder.setPosition(spatial.getWorldTranslation());

// 3) find the path

hasPath = navMeshPathfinder.computePath(targetLocation);

if (hasPath) {

List<Vector3f> wpPositions = new ArrayList<Vector3f>();

for (Waypoint wp : navMeshPathfinder.getPath().getWaypoints()) {



[/java]

That’s all the code I can give you.

Ok i am missing the meaning of warpInside,

by the way i am calling computePath.

You can ignore warpinside as long as you know your point is inside a nav cell. It just makes sure the point is inside the navmesh; if it is not, then it moves it inside to the closest cell.

Thank you very much,

i will go on this way.

Hey @Sploreg,



Sorry to revive an old topic, but it’s related to this. While generating the Navigation Path, I found out this result. I know the current library isn’t perfect, but that’s exactly what I was my intention: to fix it. After thinking and thinking a lot what could be causing this problem, I think I’ve found out why:


  • The heuristic being calculated is related to the center of the cell, instead of the closest point to the goal.
  • The arrivalCost being passed to the next cell is unacuratted, giving the distance between the intersecting wall between these two cells.



    Am I correct up to this point?



    I tried to come up with a solution for those 2 problems, and I figured it out how to fix the heurisct, but I faled at the cost.



    http://img688.imageshack.us/img688/934/navpath.png

yep you are correct there. One solution is to give the navmesh more triangles. A more detailed map will automatically fix this. I think you can set the max triangle size with the navmesh generator.

Interesting is that Detour’s Recast library fixed this by doing these operations:



const float curCost = filter->getCost(bestNode->pos, neighbourNode->pos,
parentRef, parentTile, parentPoly,
bestRef, bestTile, bestPoly,
neighbourRef, neighbourTile, neighbourPoly);
cost = bestNode->cost + curCost;
heuristic = dtVdist(neighbourNode->pos, endPos)*H_SCALE;



float dtQueryFilter::getCost(const float* pa, const float* pb,
const dtPolyRef /*prevRef*/, const dtMeshTile* /*prevTile*/, const dtPoly* /*prevPoly*/,
const dtPolyRef /*curRef*/, const dtMeshTile* /*curTile*/, const dtPoly* curPoly,
const dtPolyRef /*nextRef*/, const dtMeshTile* /*nextTile*/, const dtPoly* /*nextPoly*/) const
{
return dtVdist(pa, pb) * m_areaCost[curPoly->getArea()];
}


Where dtVdist = distance between two points. But what does that m_areaCost[curPoly->getArea()] do I failed to understand.

/// Sets the user defined area id. [Limit: < #DT_MAX_AREAS]
inline void setArea(unsigned char a) { areaAndtype = (areaAndtype & 0xc0) | (a & 0x3f); }

/// Sets the polygon type. (See: #dtPolyTypes.)
inline void setType(unsigned char t) { areaAndtype = (areaAndtype & 0x3f) | (t << 6); }

/// Gets the user defined area id.
inline unsigned char getArea() const { return areaAndtype & 0x3f; }

/// Gets the polygon type. (See: #dtPolyTypes)
inline unsigned char getType() const { return areaAndtype >> 6; }


Yes, a more detailed NavMesh would fix this, but even though with a more detailed navmesh, the behavior would continue. Only in perfect meshes with high number of triangles and none of them being big enough to cause this. That's pretty impratical for most cases.

Do you have any ideas now or you have had ideas in the past to fix this? I tried some crazy shit over here, but all of them lack a proper design, they pretty much need information not avaliable to the cells and on.

I thought also the problem could be on the NavMesh class, after the path is generated, when it computate the waypoints, but I failed to confirm if this could be causing these errors.

I never fixed this issue. I just worked around it with more polygons.



I assume the area he is using for the cost scales the cost of the path. The larger the area the farther you probably have to travel. All of that is needed for A*, before the refined path is created. So you need to sort of fudge the weights of the edges of the A* graph. But if it is used that way, there is still no guarantee it is the best path. It just might be better.

Just for information,



the version of the recast algorithm that we are using is pretty old,

it’s no wonder that in the new version of recast or better detour things work better,

one day i will port them.

ya ours is very old and needs a port.

Yeah, Detour’s algorithm is really good, but a little bit more complex. I understood the most part of it, since they are similar, but the main difference it’s those 2 points I’ve found. I’ll try to see if I can something about this. I saw a guy saying that a good approach was to transform the triangles in 6 possible waypoints and the cost would be the distance between them. I liked that idea, and in the optimization the final result would be great anyway.

Hi Shirkit this you read this page?

it gives explanations about all parameters that can be used to tune the construction of the navigation mesh



http://www.critterai.org/nmgen_config



Detour is a very powerful algorithm but it shows is power when a level changes it’s structure dinamically

or in the case the BOT has to change path dinamically for some game scenario…