[Recast] Tiles not aligning

[xalcon]

So close D: I finaly can process the wow maps in recast. I've copied most of the building process from the recast demo into a C++/CLI lib including recast and detour and it works realy well. I just have an annoying problem: my tiles are not connected. I've already read through serveral posts, like this or this but I still have the problem, that my tiles are a bit too small to connect.

Path finding inside a single tile works fine


But when I try to get the path between tiles, it looks like this


May anyone share his config values or point out whats wrong on my side?
I think the problem is, I'm using a TileSize of 533.3333 (like namereb suggested) which leads to an effective size of 177.777 for each tile -> 3x3 tiles, but most function in the recast lib expect integers for the size :/

Also some general questions:
How big do you make your tiles? I would like to do 1 tile per ADT but I dont know if this is a viable idea
Can I just add tiles from another adt to the navmesh and detour is able to find path between them?
What are reasonable values for dtNavMeshParams.maxTiles and dtNavMeshParams.maxPolys? I currently use 64 Tiles and 65536 polygons but I would like to load up to 9 adt files (9x3x3 => 81 tiles). Are 32k polygons enough?

Here is my configuration:

#define IR_RECAST_TILE_SIZE (1600.0f / 3.0f)
#define IR_RECAST_TILE_VOXEL_COUNT 1778

#define IR_RECAST_CELL_SIZE (IR_RECAST_TILE_SIZE / IR_RECAST_TILE_VOXEL_COUNT)
#define IR_RECAST_CELL_HEIGHT 0.3f

#define IR_RECAST_AGENT_HEIGHT 1.652778f
#define IR_RECAST_AGENT_RADIUS 0.35f
#define IR_RECAST_AGENT_MAX_CLIMB 1.0f
#define IR_RECAST_AGENT_MAX_SLOPE 50.0f

#define IR_RECAST_REGION_MIN_SIZE 20
#define IR_RECAST_REGION_MERGE_SIZE 40

#define IR_RECAST_EDGE_MAX_LEN 12.0f
#define IR_RECAST_EDGE_MAX_ERROR 1.3f

#define IR_RECAST_VERTS_PER_POLY 6.0f
#define IR_RECAST_DETAIL_SAMPLE_DIST 3.0f
#define IR_RECAST_DETAIL_SAMPLE_MAX_ERROR 1.25f

rcConfig m_cfg;
memset(&m_cfg, 0, sizeof(m_cfg));
m_cfg.cs = IR_RECAST_CELL_SIZE;
m_cfg.ch = IR_RECAST_CELL_HEIGHT;
m_cfg.walkableSlopeAngle = IR_RECAST_AGENT_MAX_SLOPE;
m_cfg.walkableHeight = (int)ceilf(IR_RECAST_AGENT_HEIGHT / m_cfg.ch);
m_cfg.walkableClimb = (int)floorf(IR_RECAST_AGENT_MAX_CLIMB / m_cfg.ch);
m_cfg.walkableRadius = (int)ceilf(IR_RECAST_AGENT_RADIUS / m_cfg.cs);
m_cfg.maxEdgeLen = 8;//(int)(IR_RECAST_EDGE_MAX_LEN / IR_RECAST_CELL_SIZE);
m_cfg.maxSimplificationError = IR_RECAST_EDGE_MAX_ERROR;
m_cfg.minRegionArea = (int)rcSqr(IR_RECAST_REGION_MIN_SIZE);		// Note: area = size*size
m_cfg.mergeRegionArea = (int)rcSqr(IR_RECAST_REGION_MERGE_SIZE);	// Note: area = size*size
m_cfg.maxVertsPerPoly = (int)IR_RECAST_VERTS_PER_POLY;
m_cfg.tileSize = (int)IR_RECAST_TILE_SIZE;
m_cfg.borderSize = m_cfg.walkableRadius + 3; // Reserve enough padding.
m_cfg.width = m_cfg.tileSize + m_cfg.borderSize*2;
m_cfg.height = m_cfg.tileSize + m_cfg.borderSize*2;
m_cfg.detailSampleDist = IR_RECAST_DETAIL_SAMPLE_DIST < 0.9f ? 0 : IR_RECAST_CELL_SIZE * IR_RECAST_DETAIL_SAMPLE_DIST;
m_cfg.detailSampleMaxError = IR_RECAST_CELL_HEIGHT * IR_RECAST_DETAIL_SAMPLE_MAX_ERROR;

rcVcopy(m_cfg.bmin, bmin);
rcVcopy(m_cfg.bmax, bmax);
// add border to bounds
m_cfg.bmin[0] -= m_cfg.borderSize*m_cfg.cs;
m_cfg.bmin[2] -= m_cfg.borderSize*m_cfg.cs;
m_cfg.bmax[0] += m_cfg.borderSize*m_cfg.cs;
m_cfg.bmax[2] += m_cfg.borderSize*m_cfg.cs;

[573737534947]

How do you create the vertices from the heightmaps? My guess is you're doing it and wrong, which leads inherently to disconnected tiles. You probably created the faces only within the chunks not across them. I mean how are they supposed to be connected if you didn't create those connections? I don't know if recast can help you with that, but the best option from my point of view would be to start of with correct geometry. Basically the edge vertices are duplicated along the each side shared by two adjacent chunks (Coordinates don't match exactly sometimes due to floating point precision errors). So just collapse the edge vertices and your map will be connected (You have to adjust the indices of the faces as well, of course). Should work just like that with blocks, too. However I didn't test that.

[xalcon]

well, its just a guess, but I think recast doesnt need them to be "connected". If you were right, recast would create those gaps for every adt chunk, but its not. I only have a gap for each dtTileMesh.
also, just to support my theory, when I create a solo mesh, everyting works fine. Also using some other values like 512 instead of 533.333 seem to work (but I have to investigate this further if it causes any other problems).

I will look into it anyway, since I want to optimize the exported meshes to reduce size and processing time.

[xalcon]

I was able to optimize my meshes, reducing their size by up to 60% (those WMOs do have a shit ton of unused vertices when only exporting collision triangles) effectivly reducing processing time in recast by nearly 66% but the outcome does still have those gaps.

I've done some testing and it seems, that those gaps are related to the rcConfig.width and rcConfig.height values. When I set the tilesize to 512, the gaps disappear and navigation between tiles is working fine. I'll use 512 for now, but there is now another problem.

When I create a recast solo mesh, the navmesh looks realy nice but when I create a tile mesh, i have some weired artefacts:

Solo Mesh created by RecastDemo


Tile-Mesh 512x Tile Size created by RecastDemo, other values on default


Tile-Mesh 512x Tile Size, created by my lib code, loaded into RecastDemo


It looks like there are some vertices of the navmesh outside of the bounding box and I have no idea how this is even possible :/ There are no unused vertices in the input mesh and I've double checked the bounding box.

I'm so confused D:

[Bananenbrot]

That's probably due to integer overflow. IIRC, recast uses unsigned shorts to represent indices, which most probably are 16 bit wide on todays machines. Tiling causes more vertices to be generated. You need to find all places in recasts code referring to indices and change that if you want to fix it.
Have fun debugging the inevitable conversion errors not intercepted by C++' type system

[MaiN]

For your tiles not aligning issue, make sure that you are passing the geometry of the neighbor tiles into Recast when you mesh a tile. You cannot pass only one tile and then expect it to line up with the 8 neighboring tiles; you need to pass all 9 tiles.
For your other issue, it might be related to this (R+D Mesh Generation - Issues on AbyssalMaw_Interior (contours/ncid)).

[xalcon]

That's probably due to integer overflow. IIRC, recast uses unsigned shorts to represent indices, which most probably are 16 bit wide on todays machines. Tiling causes more vertices to be generated. You need to find all places in recasts code referring to indices and change that if you want to fix it.
Have fun debugging the inevitable conversion errors not intercepted by C++' type system

I reverted my recast to revision 298 (oldest I could select) because in another thread someone said, he had success with an older version... and the problem is gone o_O no artefacts... Might try latest version sometime again, but as long as I dont get any other problems, why bothering?

For your tiles not aligning issue, make sure that you are passing the geometry of the neighbor tiles into Recast when you mesh a tile. You cannot pass only one tile and then expect it to line up with the 8 neighboring tiles; you need to pass all 9 tiles.
For your other issue, it might be related to this (R+D Mesh Generation - Issues on AbyssalMaw_Interior (contours/ncid)).

Yeah, I found that thread too, but I also have a problem getting navigation in single adt but across tiles to work properly. At least when using 533.333 as a TileSize. As soon as I set the size to something like 512, navigation works perfectly. But the tiles on the lower and on the right end are smaller then the others and I think that I might cause problems when loading multiple adt files, but I cant test this by now.

[Game2Mesh]

1.About the gap,the key point is the size of the geometry data you passed to the recast must bigger than (tilesize*cellsize + agent radius + border size).For example,if your tilesize*cellsize=300,the size of the geometry data you passed must bigger than 300+0.4+4(by default configs).The follow picture will help you understand how it works.



2.About the maxTiles and maxPolys,if you want to navigation in the whole continent,you need to set the dtPolyRef from 32bit to 64bit,otherwise you can't load all the meshes.

3.About the vertical mesh,it's a bug from recast,set the climb angle smaller will be helpful,but if you want to fix it,the easy way is disable the detail mesh processing(just remove the rcBuildPolyMeshDetail function).The detail mesh processing is optional,i think it's useless for bot navigation.

[namreeb]

I didn't check your settings but as MaiN mentioned, the two things I know of that can cause this are a cell size which does not perfectly divide the tile size, or not providing enough geometry past the boundary of your tile.

[xalcon]

yeah, I think its my geo mesh. I'm only loading a single adt. I was just confused about the fact, that I had those gaps between tiles in a single tilemesh, not just between multiple tilemeshes. How would I create a tile mesh for a single ADT when there is no other ADT around? Just decreasing/increasing the bounding box?

2.About the maxTiles and maxPolys,if you want to navigation in the whole continent,you need to set the dtPolyRef from 32bit to 64bit,otherwise you can't load all the meshes.

Just looked into DetourNavMesh.h and found the info too. Is it realy that simple to increase it? I guess modifying the dtHashRef() might not be that easy, right?

3.About the vertical mesh,it's a bug from recast,set the climb angle smaller will be helpful,but if you want to fix it,the easy way is disable the detail mesh processing(just remove the rcBuildPolyMeshDetail function).The detail mesh processing is optional,i think it's useless for bot navigation.

I've removed that step from my build process and the mesh look still quite good. So the detail mesh just improves the height/location of the triangles? Thanks for that tip!

[xalcon]

It works !! Thank you all for you all for your help and patience! *spreading some rep*

I had some errors in the configuration. I just went back and refactored my whole recast wrapper class and found some errors.
In my opinion, recast/detour is using some weired naming sometimes.
for example: the rcConfig.tileSize is not the same as the dtNavMeshParams.tileWidth/Height! But anyway :3

I still have some issues with path generation, but nothing serious, just a bit annoying. Maybe someone has a tip? If not, i may live with it.

[namreeb]

Perhaps this is a stupid question, but what is the problem with this?

Edit: Oh, I assume you mean how the path changes so strangely when you move the destination over a bit. Did you ever put the detail mesh back in?

[Game2Mesh]

yeah, I think its my geo mesh. I'm only loading a single adt. I was just confused about the fact, that I had those gaps between tiles in a single tilemesh, not just between multiple tilemeshes. How would I create a tile mesh for a single ADT when there is no other ADT around? Just decreasing/increasing the bounding box?

If there is no neighbor ADT,means this ADT is not connected with other ADT,so you don't need to pass other ADT in this case.

Just looked into DetourNavMesh.h and found the info too. Is it realy that simple to increase it? I guess modifying the dtHashRef() might not be that easy, right?

It's very easy,just extend the hash range from 32bit-int to 64bit-int.

I've removed that step from my build process and the mesh look still quite good. So the detail mesh just improves the height/location of the triangles? Thanks for that tip!

Yes,the detail mesh just for getting the height of a point on a mesh plane,and I think the height don't need to be very accurate for bot navigation.

[MaiN]

It works !! Thank you all for you all for your help and patience! *spreading some rep*

I had some errors in the configuration. I just went back and refactored my whole recast wrapper class and found some errors.
In my opinion, recast/detour is using some weired naming sometimes.
for example: the rcConfig.tileSize is not the same as the dtNavMeshParams.tileWidth/Height! But anyway :3

I still have some issues with path generation, but nothing serious, just a bit annoying. Maybe someone has a tip? If not, i may live with it.

The A* process only works on a per polygon basis. In this case it thinks that's the path that will be best, but after string pulling, you can see that's not the best path. There is no easy way to fix it, but you can improve on it by always raycasting towards 4-5 next points and then skipping points if one of the rays don't hit anything.