Recast & Destour, navmesh problem

[nerexis]

Since I was creating navmesh files in single navmesh file per whole continent, I've run into a problem of losing accuracy, missing tiles etc.
I've created one big obj file for each continent then parsed it into Recast. After testing many different settings I've created navmesh file which covers (almost) whole continent and is only 100-200mb in size. But it's not accurate. It works most of the time outdoor but its losing accuracy indoors. Setting lower cell size makes recast generating bad navmesh which is not working or it doesnt cover whole continent.

Everyone here on forum is writing to create navmesh file for each ADT.
I was trying to test it out using RecastDemo so i generated using standard settings 2 navmesh files.
I have files for ADTs (Azeroth): 32_48, 32_49 then now I wanna see generated navmesh in RecastDemo.

I have added function to add another file to currently loaded:

void Sample_TileMesh::addTileToMesh(const char * path, dtNavMesh * navPtr)
{
	FILE* fp = fopen(path, "rb");
	if (!fp) return;
	
	// Read header.
	NavMeshSetHeader header;
	fread(&header, sizeof(NavMeshSetHeader), 1, fp);
	
	// Read tiles.
	for (int i = 0; i < header.numTiles; ++i)
	{
		NavMeshTileHeader tileHeader;
		fread(&tileHeader, sizeof(tileHeader), 1, fp);
		if (!tileHeader.tileRef || !tileHeader.dataSize)
			break;

		unsigned char* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);
		if (!data) break;
		memset(data, 0, tileHeader.dataSize);
		fread(data, tileHeader.dataSize, 1, fp);

		navPtr->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);
	}
	
	fclose(fp);
}

// Loading part somewhere in the Load button function:
		dtFreeNavMesh(m_navMesh);
		m_navMesh = loadAll("32_48.bin");
		addTileToMesh("32_49.bin",m_navMesh);

Then I'm probably doing something wrong because navmesh data from 32_49 isnt fully loaded:



Any suggestions?
Just to clarify I didnt change any Recast settings when building/saving/loading, I guess Im missing something here so that's why navmesh isnt fully loaded.

[xalcon]

I think you ran out of tiles.
You have a tilesize of 32, which leads to maximum amount of 4096 tiles with a maximum of 1024 Polygons per tile. Thats way to small.
Recastdemo is not capable of creating tilemeshes with a tilesize of 533.3333 world units. You can create those tiles on your own (using recast lib) and load them in the demo just fine though.

You may also consider increasing the reference size limit by changing the underlying type of dtPolyRef to 64 Bit type and also change the hashing algorithm, see DetourNavMesh.h and Game2Mesh's hint about this ([Recast] Tiles not aligning)

[nerexis]

I've manually changed settings to those in other threads, then builded navmesh but it was mess... Still couldnt load both of them so error is probably somewhere else.

Then I was checking return value of addTile function and it is returning errors while adding tiles:

dtStatus dtNavMesh::addTile(unsigned char* data, int dataSize, int flags,
							dtTileRef lastRef, dtTileRef* result)
{
	// Make sure the data is in right format.
	dtMeshHeader* header = (dtMeshHeader*)data;
	if (header->magic != DT_NAVMESH_MAGIC)
		return DT_FAILURE | DT_WRONG_MAGIC;
	if (header->version != DT_NAVMESH_VERSION)
		return DT_FAILURE | DT_WRONG_VERSION;
		
	// Make sure the location is free.
	if (getTileAt(header->x, header->y, header->layer))
	{
		printf("Location not free!\n");
		return DT_FAILURE;
	}
...

Am I saving/loading files in wrong way? Should I change x, y variable of subtiles in secondary tile (32_49)?

[xalcon]

So you are getting the "location not free" error? Then its an easy fix. When you create the tiles, you also assign a tile positon (dtNavMeshCreationParams.x/.y). The position is created by the double-for-loop inside buildAllTiles and used in the buildTileMesh method.

for (int y = 0; y < th; ++y)
			{
				for (int x = 0; x < tw; ++x)
				{
					m_tileBmin[0] = bmin[0] + x*tcs;
					m_tileBmin[1] = bmin[1];
					m_tileBmin[2] = bmin[2] + y*tcs;
			
					m_tileBmax[0] = bmin[0] + (x+1)*tcs;
					m_tileBmax[1] = bmax[1];
					m_tileBmax[2] = bmin[2] + (y+1)*tcs;
					int dataSize = 0;
					unsigned char* data = buildTileMesh(x, y, m_tileBmin, m_tileBmax, dataSize);

Thats why you get that error :P Just calculate the TilePositon and use that instead. detour is using the following code to calculate the TilePosition by a given coordinate:

// DetourNavMesh.cpp, line 1115
void dtNavMesh::calcTileLoc(const float* pos, int* tx, int* ty) const
{
	*tx = (int)floorf((pos[0]-m_orig[0]) / m_tileWidth);
	*ty = (int)floorf((pos[2]-m_orig[2]) / m_tileHeight);
}

where pos is the position to look for a tile and m_orig is the nav_mesh origin. You can set the origin when create the nav_mesh. I'm using these values:

dtNavMeshParams params;
params.maxPolys = MaxPoly;
params.maxTiles = MaxTiles;
params.tileWidth = (GRID_SIZE / 4);
params.tileHeight = (GRID_SIZE / 4);
params.orig[0] = -(32 * GRID_SIZE);
params.orig[1] = 0;
params.orig[2] = -(32 * GRID_SIZE);

GRID_SIZE = 1600.0f / 3.0f

and this is my buildAllTiles Function

bool buildAllTiles(float* bounds)
		{
			if (!m_geom) return false;
			if (!m_navMesh) return false;
	
			const float* bmin = bounds;
			const float* bmax = &bounds[3];
			int gw = 0, gh = 0;
			rcCalcGridSize(bmin, bmax, CellSize, &gw, &gh);
			const int ts = (int)TileSize;
			const int tw = (int)((gw + ts-1) / ts);
			const int th = (int)((gh + ts-1) / ts);
			const float tcs = TileSize / GridDiv;

			float m_tileBmin[3];
			float m_tileBmax[3];

			for (int y = 0; y < th; ++y)
			{
				for (int x = 0; x < tw; ++x)
				{
					m_tileBmin[0] = bmin[0] + x*tcs;
					m_tileBmin[1] = bmin[1];
					m_tileBmin[2] = bmin[2] + y*tcs;
			
					m_tileBmax[0] = bmin[0] + (x+1)*tcs;
					m_tileBmax[1] = bmax[1];
					m_tileBmax[2] = bmin[2] + (y+1)*tcs;

					int tx = (int)floorf((m_tileBmin[0]-(-32 * GRID_SIZE)) / (TileSize / GridDiv));
					int ty = (int)floorf((m_tileBmin[2]-(-32 * GRID_SIZE)) / (TileSize / GridDiv));

					Console::WriteLine("Building Tile {0} / {1} for ADT_{2}_{3}", tx, ty, ty / 4, tx / 4);
					
					int dataSize = 0;
					unsigned char* data = buildTileMesh(tx, ty, m_tileBmin, m_tileBmax, dataSize);
					if (data)
					{
						// Remove any previous data (navmesh owns and deletes the data).
						m_navMesh->removeTile(m_navMesh->getTileRefAt(tx,ty,0),0,0);
						// Let the navmesh own the data.
						dtStatus status = m_navMesh->addTile(data,dataSize,DT_TILE_FREE_DATA,0,0);
						if (dtStatusFailed(status))
						{
							Console::WriteLine("Error on m_navMesh->addTile()");
							dtFree(data);
							return false;
						}
					}
				}
			}

			return true;
		}

[nerexis]

I don't fully understand it, buy anyway it didn't fix my problem.

Then I'm back to my approach, just for testing.

I was thinking about this and checked few things.

My settings are:
512 tilesize
Tiles 5x5
Cell Size 0.25
Max Tiles 32
Max Polys 131072

So when I generate navmesh for 32_48, it has 5x5 and same for 32_49.
So in 2 navmesh files I have currently 10 tiles.

First tile has coords: 0/0 and last has 4/4 in first file.

Just for testing, Im using this code to load secondary tile, after first is loaded.
Tile X,Y looks like it's correct:

...
	for (int i = 0; i < header.numTiles; ++i)
	{
		printf("Adding tile %i...\n",i);
		NavMeshTileHeader tileHeader;
		fread(&tileHeader, sizeof(tileHeader), 1, fp);
		if (!tileHeader.tileRef || !tileHeader.dataSize)
			break;

		unsigned char* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);
		if (!data) break;
		memset(data, 0, tileHeader.dataSize);
		fread(data, tileHeader.dataSize, 1, fp);
		
		dtMeshHeader* header = (dtMeshHeader*)data;
		header->x+=5;
		header->y+=5;

		navPtr->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);

Now I didn't get 'Location not free error' but got another problem in addTile:

dtStatus dtNavMesh::addTile(unsigned char* data, int dataSize, int flags,
							dtTileRef lastRef, dtTileRef* result)
{
	// Make sure the data is in right format.
	dtMeshHeader* header = (dtMeshHeader*)data;
	if (header->magic != DT_NAVMESH_MAGIC)
		return DT_FAILURE | DT_WRONG_MAGIC;
	if (header->version != DT_NAVMESH_VERSION)
		return DT_FAILURE | DT_WRONG_VERSION;
	//if(header->x==0&&header->y==0)
	//	return DT_FAILURE;
	// Make sure the location is free.
	printf("Adding tile: X: %i Y: %i\n",header->x,header->y);
	if (getTileAt(header->x, header->y, header->layer))
	{
		printf("Location not free!\n");
		return DT_FAILURE;
	}
	//printf("Allocating tile");
	// Allocate a tile.
	dtMeshTile* tile = 0;
	if (!lastRef)
	{
		if (m_nextFree)
		{
			tile = m_nextFree;
			m_nextFree = tile->next;
			tile->next = 0;
		}
	}
	else
	{
		// Try to relocate the tile to specific index with same salt.
		int tileIndex = (int)decodePolyIdTile((dtPolyRef)lastRef);
		if (tileIndex >= m_maxTiles)
		{
			printf("Could not realocate title with specific index with the same salt\n");
			return DT_FAILURE | DT_OUT_OF_MEMORY;
		}
		// Try to find the specific tile id from the free list.
		dtMeshTile* target = &m_tiles[tileIndex];
		dtMeshTile* prev = 0;
		tile = m_nextFree;
		while (tile && tile != target)
		{
			prev = tile;
			tile = tile->next;
		}

		// Could not find the correct location.
		if (tile != target)
		{
			printf("Could not find correct location\n");
			return DT_FAILURE | DT_OUT_OF_MEMORY;
		}
		// Remove from freelist
		if (!prev)
			m_nextFree = tile->next;
		else
			prev->next = tile->next;

		// Restore salt.
		tile->salt = decodePolyIdSalt((dtPolyRef)lastRef);
	}

I assume, when I use navMesh->init(), it allocates memory for navmesh to load.
If I have 2 adts then I have to multiply maxTiles number to allocate enough memory:

header.params.maxTiles*=2;

But it doesn't help.
I dont fully understand how tiles are allocated in m_tiles variable and how index is calculated.
Looks like addTile can't find location where tile should fit in tiles array (m_tiles) because when tiles are separately generated, index of tile in second file is wrong?

Any suggestions? How can I fix wrong location error?

[xalcon]

1. In order to load 2 adts with 5x5 tiles each, you need a navmesh capable of handling at least that amount of tiles (i.e. MaxTiles = 64). In this case, you also need to adjust the MaxPoly Count since you only have 22 bits referencing a polygon and a tile (limitation of detour).

2. You cannot set the tile x/y position to some random values. That wont work. You need to calculate those, otherwise detour will not be able to find the right tile for a given position.
Please post you navmesh init code. The origin needs to be correct!

[nerexis]

Navmesh init code:

dtNavMesh* Sample_TileMesh::loadAll(const char* path)
{
	FILE* fp = fopen(path, "rb");
	if (!fp) return 0;
	
	// Read header.
	NavMeshSetHeader header;
	fread(&header, sizeof(NavMeshSetHeader), 1, fp);
	if (header.magic != NAVMESHSET_MAGIC)
	{
		fclose(fp);
		return 0;
	}
	if (header.version != NAVMESHSET_VERSION)
	{
		fclose(fp);
		return 0;
	}
	
	dtNavMesh* mesh = dtAllocNavMesh();
	if (!mesh)
	{
		fclose(fp);
		return 0;
	}

	header.params.maxTiles*=2;
	header.params.maxPolys*=2;
	//header.numTiles*=2;
	
	dtStatus status = mesh->init(&header.params);
	if (dtStatusFailed(status))
	{
		fclose(fp);
		return 0;
	}
		
	// Read tiles.
	for (int i = 0; i < header.numTiles; ++i)
	{
		NavMeshTileHeader tileHeader;
		fread(&tileHeader, sizeof(tileHeader), 1, fp);
		if (!tileHeader.tileRef || !tileHeader.dataSize)
			break;

		unsigned char* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);
		if (!data) break;
		memset(data, 0, tileHeader.dataSize);
		fread(data, tileHeader.dataSize, 1, fp);

		mesh->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);
	}
	
	fclose(fp);
	
	return mesh;
}

Function to add second tile to current navmesh. When 32_48 is loaded, im using this functiont o load 32_49.
Tiles positions should be correct.

void Sample_TileMesh::addTileToMesh(const char * path, dtNavMesh * navPtr)
{
	FILE* fp = fopen(path, "rb");
	if (!fp) return;
	
	// Read header.
	NavMeshSetHeader header;
	fread(&header, sizeof(NavMeshSetHeader), 1, fp);
	
	// Read tiles.
	for (int i = 0; i < header.numTiles; ++i)
	{
		printf("Adding tile %i...\n",i);
		NavMeshTileHeader tileHeader;
		fread(&tileHeader, sizeof(tileHeader), 1, fp);
		if (!tileHeader.tileRef || !tileHeader.dataSize)
			break;

		unsigned char* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);
		if (!data) break;
		memset(data, 0, tileHeader.dataSize);
		fread(data, tileHeader.dataSize, 1, fp);
		
		dtMeshHeader* header = (dtMeshHeader*)data;
		header->x+=5;
		header->y+=5;

		navPtr->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);
	}
	
	fclose(fp);
}

[xalcon]

sorry, maybe my post wasn't clear enough. I was talking about the navmesh init code for creating the tiles.
(You wont really need a dtNavMesh for creating the tiles in recast, but I assume you are using a lot of code from recast demo which is using some dt stuff in the creation and saving process, like the dtNavMeshSetHeader).

Anyway:

header.params.maxTiles*=2;
header.params.maxPolys*=2;

Depending on the initial values, you cant just do this. As I said, detour only has 22 bit of space for addressing a Polygon (maxTiles + maxPolys must not be bigger than 2^22).

[nerexis]

If it's impossible by this way then, what would be the best way to load whole map to being able to navigate whole continent, with good resolution so I can also enter buildings etc.
I also need to avoid spawn radius of units through temp obstacle features.

[xalcon]

You need to change the source of detour (see http://www.ownedcore.com/forums/worl...ml#post2974310), but to be honest... dont try to load a whole continent. You will need a huge amount of system memory just to load all tiles. Creating a path from like undercity to booty bay would take a long time, if you even have enough memory to let detour traverse the tiles. Atm I need more then 2048 nodes to get the path from the bloodelf spawn point to the top of the big tower above the lake.
Its better to manually define a mesh of PoI's (like Flightpoints) and connect them to each other. Atleast thats the way I'm doing it. I use detour for short distance movement (< 1000m), if the distance is too long, I just try to calculate a better path using stuff like flightpoints.

To implement obstacle avoidance, you might need to fix the path afterwards. This thread was talking about fixing path's a bit: http://www.ownedcore.com/forums/worl...l-corners.html

[nerexis]

I don't agree about memory usage because I've generated good whole continent map but with problem with indoors and it was using 110-150mb of memory and calculation of path from undercity to northshire took maybe 100ms + my path calculation and storage of map are on the server which is sending generated path to client.

I was thinking about your idea, it might work, but what if your character didn't discover flightpoints? Or if area where you wanna operate is between two regions etc.

[nerexis]

PROBLEM SOLVED:

Currently I'm using kind of hybrid method you suggested. I'm using the big maps of whole continent for long travels and detailed high resolution map of one adt when start and end is close and on the same tile. Works like a charm, even with temp obstacle system!

Thanks for your help!

[redcatH]

l like Automatic routing，but i can't