Large NavMesh Generation

[Piotr Zaremba]

Hello,

I have a question concerning the generation of a large navigation
mesh. The project that I am working on generates a large terrain skin
composed of individual terrain tiles. Now I am using Recast as my
navigation system of course. And here is the problem I am running
into. My system traverses each terrain tile from disk and composes
the overall terrain skin at run-time for visualization, however each
terrain tile still exists in memory. Now during the traversal I also
create a DetourTileCache for every Terrain Tile I traverse. Now at
run time I want to load all of my DetourTileCaches that I created into
a single NavMesh and then that NavMesh would get passed into a single
instance of a NavMeshQuery. My problem is I am generating each
DetourTileCache fine however when I iterate over all my
DetourTileCaches and load them into my large NavMesh my routes fail
and I get no results because my startRef's and endRef always end up as
"0". Am I approaching my problem incorrectly?

[Mikko Mononen]

If you debug draw your navmesh, does it look ok? Recast has nice library of debug draw functions. All you need to do is to implement duDebugDraw. There is example implementation in the recastdemo.

--mikko

Sent from my iPhone

[Piotr Zaremba]

I feel my issues lie in how I load each DetourTileCache into a single
dtNavMesh. Does my DetourTileCache rcConfig need to reflect the
overall size of the dtNavMesh or its local configurations. What I
mean is the total_width and total_height of each individual
DetourTileCache is 32 tiles by 32 tiles however the configuration for
my NavMesh at the init() state islets say 64 by 32 for two adjacent
tiles. Is that how you correctly configure a DetourTileCache and a
dtNavMesh. Also could you explain how the tileRef's work. Does the
tileRef order matter or is it just a way to obtain tile data via a
reference? Could I just go through every tile from every
DetourTileCache in a loop while adding them to a single dtNavMesh,
with a "0" lastRef parameteror do I have to input a valid lastRef as I
enter each tile into the dtNavMesh. Does each individual tile in each
DetourTileCache know its correct location within the overall Tile
Navigation Mesh?

On Feb 2, 9:15 pm, Mikko Mononen <memono...@gmail.com> wrote:
> If you debug draw your navmesh, does it look ok? Recast has nice library of debug draw functions. All you need to do is to implement duDebugDraw. There is example implementation in the recastdemo.
>
> --mikko
>
> Sent from my iPhone
>

[Piotr Zaremba]

Please also remember that I create a new TriangleMesh for each terrain
tile, and each DetourTileCache is composed from each TriangleMesh. I
am not sure that even matters though.

[Mikko Mononen]

Hi,

TileRefs are just handlers which are kind of like pointers which can
be stored to disk.

Your could not completely follow your example case. I recommend you to
try to mimic the example code.

TileCache tiles know their world position. When you update tile cache,
it will compute any changes that happen and directly add/remove
navmesh pieces in the attached navmesh.

--mikko

[Piotr Zaremba]

Yes I believe my sample case was a bit hard to understand. Here is a
simplified versus of what I am trying to do.

I am basing my example code off the code within the following method
Sample_TempObstacles::handleBuild().

foreach (DetourTileCache within a std::vector<>) // pseudo code
{
for (int y = 0; y < th; ++y)
{
for (int x = 0; x < tw; ++x)
{
dtStatus status = DetourTileCache->buildNavMeshTilesAt(x,y,
dtNavMesh);
}
}
}

This is where I believe my navigation mesh constructions are starting
to occur. Does the "tw" and "th" variables need to be relative to
each independent DetourTileCache or to the overall size of the
dtNavMesh being created? I feel I am overriding tiles after each
DetourTileCache iteration.

[Mikko Mononen]

Hi,

Why many tile caches? There should be one tile cache per navmesh.

--mikko

[Piotr Zaremba]

I am trying to associate one DetourTileCache with every terrain tile
that I have. So if I have 10 terrain tiles that compose my entire
terrain environment, then I would have 10 DetourTileCaches that at
runtime are added to a single dtNavMesh. The reasons for this are to
long to explain. Is this possible? Or do I need to compose all of my
DetourTileCaches into one DetourTileCache.

On Feb 17, 4:19 pm, Mikko Mononen <memono...@gmail.com> wrote:
> Hi,
>

[Mikko Mononen]

Hi,

You should not do that. But you can store the cache tiles per your
terrain tile if you want to do so. Tile cache does not care where the
data comes from.

What is really important is to make sure the tile coordinates are
correct. They describe at which location the tile will be put in the
world. The tile coordinates are set when you build the cached tile.

--mikko

[Piotr Zaremba]

So when you say I can store the cache tiles, what do you exactly
mean. Which data struct are you referring to? Are you referring to
dtCompressedTiles or another data structure? The reason I am storing
off the navigation tiles per terrain tile is that my areas are
extremely large.

- Piotr

On Feb 18, 3:44 am, Mikko Mononen <memono...@gmail.com> wrote:
> Hi,
>

[Mikko Mononen]

Hi,

If you have large world, you should only add the tiles to the cache
that can fit into memory at any given time (or based on some other
constraint). The data to dtTileCache.addTile() can be stored in any
where you like, it is just a blob of data.

When you add a tile to tile cache, the intended procedure is to first
add all the layers (addTile()), and the build navmesh piece for that
location (buildNavMeshTilesAt()). I probably could add few things
there it simplify this process.

--mikko

[Piotr Zaremba]

So in essence the DetourTileCache should only be used when I want to
build certain locations of the entire environment at run-time
correct? Do I really need to use the DetourTileCache at all. What
are the advantages for using the DetourTileCache vs just building all
the tiles such as in the Sample_TileMesh demo code.

Also I am following the Sample_TempObstacles demo code. And when I
build each set of navigation tiles it is in relation to each of my
terrain tiles, so I start with x=0 and y=0 and th=32 and tw=32 (32
being the max tile size width and height). I am assuming this is
wrong and I should offsite the initial x and y based on what terrain
tile I am using to create navigation tiles, since I believe that the
(x,y) values within this loop get stored as the navigation tiles
location with respect to the overall environment.

for (int y = 0; y < th; ++y)
{
for (int x = 0; x < tw; ++x)
{

rasterizeTileLayers(x,y);

}
}


On Feb 18, 6:47 am, Mikko Mononen <memono...@gmail.com> wrote:
> Hi,
>

[Mikko Mononen]

You should use tile cache when you need to add and remove simple obstacles at runtime. If your environment is static then you should stick to tile mesh. Much easier to use too.

Your thoughts about rebuild are correct. Also note that recast stores the navmesh in world coordinates.

--mikko

Sent from my iPhone

[Piotr Zaremba]

How are are individual tiles stored? I am assuming if I pass in the
position of (0,14) when building a tile before it is added to a
DetourTileCache or a NavMesh, then that would represent tile 0 (row)
and 14 (column). And those coordinates matter when the tile is first
built, since that is how they are positioned within the
DetourTileCache or the NavMesh.

On Feb 20, 11:41 am, Mikko Mononen <memono...@gmail.com> wrote:
> You should use tile cache when you need to add and remove simple obstacles at runtime. If your environment is static then you should stick to tile mesh. Much easier to use too.
>
> Your thoughts about rebuild are correct. Also note that recast stores the navmesh in world coordinates.
>
> --mikko
>
> Sent from my iPhone
>

[Mikko Mononen]

Hi,
The tile locations are related to some origin. In the demo case, it is
the scene bounding box min. dtNavMesh::calcTileLoc() shows you how the
tile locations are related to world coordinates.

--mikko

[Piotr Zaremba]

Mikko,

I successfully created TileData with respect to each of my terrain
tiles. Again TileData for each terrain tile, does not know about
TileData that is contained within other terrain tiles. Essentially I
am trying to link up TileData from each terrain tile via the dtNavMesh
addTile call. When I load data from all of my terrain tiles which
includes navigation TileData (i.e. data, dataSize), the TileData from
each tile loads fine into a dtNavMesh using addTile(), however I am
having an issue at the "seems" of the terrain tiles. When I try to
dtNavMeshQuery route across terrain tiles the Recast route services
i.e. findPath etc can find references to both the start point triangle
and the end point triangle, but only a partial path is created due to
the fact that the route stops at the edge or "seem" of the adjacent
terrain tile I am trying to route to. The data that is on the seem is
the same (x,y,z) along an adjoining edge, as a note the seem edge data
is duplicated within the TileData that is storage in a terrain tile.
So for a center terrain tile the right most edge contains the same
(x,y,z)'s as the left most edge of the terrain tile that is to the
right of the center tile. It seems that two adjoining TileData
"tiles" can not recognize that they share adjoining edges. Or two
adjoining dtMeshTiles can not recognize that both share an edge.

On Feb 20, 2:17 pm, Mikko Mononen <memono...@gmail.com> wrote:
> Hi,

[Matthew Endsley]

If you want the seams of the tiles to get patched up at run time, you need to pass in the neighboring geometry to the tile generation process.  This allows recast to 1: make sure vertices along neighbor edges have the same quantized position in all tiles and 2:  actually know those points on the edge should generate portals to polygons in the neighbor instead of being eroded.

It sounded like you were going to go the route of just adding tiles instead of using the tile cache.  With this approach you'll still only need one dtNavMesh; you just add multiple tiles.  If you want to generate paths across your tiles they'll need to be in the same dtNavMes or you'll need to implement your own solution for traversing the tiles.

[Piotr Zaremba]

All of my TileData or dtMeshTiles for every terrain tile are in a
single dtNavMesh. I am only having an issue along the edges.

On Mar 16, 1:10 am, Matthew Endsley <mends...@gmail.com> wrote:
> If you want the seams of the tiles to get patched up at run time, you need
> to pass in the neighboring geometry to the tile generation process.  This
> allows recast to 1: make sure vertices along neighbor edges have the same
> quantized position in all tiles and 2:  actually know those points on the
> edge should generate portals to polygons in the neighbor instead of being
> eroded.
>
> It sounded like you were going to go the route of just adding tiles instead
> of using the tile cache.  With this approach you'll still only need one
> dtNavMesh; you just add multiple tiles.  If you want to generate paths
> across your tiles they'll need to be in the same dtNavMes or you'll need to
> implement your own solution for traversing the tiles.

>  On Mar 15, 2012 9:44 PM, "Piotr Zaremba" <piotrzare...@gmail.com> wrote:> Mikko,

[Piotr Zaremba]

Do you have an example of what your trying to state in 1: and in 2:?
I am a bit lose as to were I need to pass in the geometry.

> ...
>
> read more »

[Mikko Mononen]

When you process your world tile, you will need to pass in all the
data from neighbour world tiles too, or else Recast thinks that world
ends where the geometry ends. Or vice versa, in order to process a
Recast tile, it needs a little bit of geometry beyond the requested
bounding box to detect that the world continues to the next tile.

--mikko

[Piotr Zaremba]

So lets say that one of my TileData structures contains a vertex in
one terrain tile. Now that same vertex is also stored in in another
TileData structure in another terrain tile. Now when both TileData's
(unsigned char* and dataSize) are passed into addTile and a dtNavMesh
is computed does Recast not notice the that the vertices are shared?

> ...
>
> read more »

[Mikko Mononen]

One more time, with a picture :)

The tiles A, B, C, D... are your game world tiles. Now when you build
Recast tile 1 for your game world tile E, you will need to pass the
level geometry from your tiles A, B, D, and E. That is, all the
geometry that touches the expanded bounding box (dotted line around
the Recast tile).

This expanded bounding box is calculate here:
http://code.google.com/p/recastnavigation/source/browse/trunk/RecastDemo/Source/Sample_TileMesh.cpp#927

This whole process ensures that the Recast navmesh tiles will match
when they are build for your different game world tiles, and that the
obstacles which are close to the border will be computed correctly.

--mikko

[Piotr Zaremba]

So this should work correct? When I know send in data as a
TriangleMesh object (based on your InputGeom.h). The TriangleMesh
contains data now that extends beyond its own extents i.e. the
triangle mesh for tile "D" is composed of vertex data from "D" and
extend data from tile "E". The same goes for "E" it is composed of
vertex data from "E" and data extended data from "D". And after the
dtNavMesh is constructed I should be able to route between "D" and "E"
correct? I am currently still faulting on the edge, but that is the
approach I took.

On Mar 16, 11:56 am, Mikko Mononen <memono...@gmail.com> wrote:
> One more time, with a picture :)
>
> The tiles A, B, C, D... are your game world tiles. Now when you build
> Recast tile 1 for your game world tile E, you will need to pass the
> level geometry from your tiles A, B, D, and E. That is, all the
> geometry that touches the expanded bounding box (dotted line around
> the Recast tile).
>

> This expanded bounding box is calculate here:http://code.google.com/p/recastnavigation/source/browse/trunk/RecastD...

> ...
>
> read more »
>
>  Photo on 16.3.2012 at 17.45.jpg
> 67KViewDownload

[Mikko Mononen]

Can you post a screenshot of your case?

--mikko

[Piotr Zaremba]

The red and green boxes represent TriangleMeshes for world tiles "D"
and "E", these serve as input into a method that looks very similar to
your Smaple_TileMesh::buildTiles() for TileData construction.

--
- Piotr Zaremba