First succesful path query on tiled mesh got done today!
I initially thought that I would use similar structure of simply connected polygons as I used for the static meshes and make the connections between the tiles a special case. It turned out that with my target tile size (32-64 voxels) actually the opposite was true. There are more tile-to-tile connections than inter-tile connections. So I went and changed my data structure a bit and I got rid of few levels of indirection, cleaner code and less conditionals with the expense of a bit more memory.
The tiled mesh is going to be a bit slower than the static mesh, but I expect it to be quite swift still. Once I get the initial full version done, I will experiment a little with different packed data maybe even limiting the vertices to range of 0-255 (the height will need few more bits), to get the data size as low as possible. A lot of the calculations can be done in integer coords anyways, so it should not be a problem.
One design decision that is biting me in the ass constantly is that I wanted the changes to tiles be as local as possible. For that reason I allow axis aligned T-junctions at the connections at the tile edges. That is adding a bit more work on the runtime as I need to clamp some coordinates when an edge at the tile border is processed. But it think in the end it is worth it. This also forced me to make support for more links per polygon than there are edges, so this work should be useful later when I will add support for non-polygonal links (jump/animation links).
I'm having trouble figuring out why you added this tile functionality.
ReplyDeleteSure a square is one less navigation node than two triangles, but I don't think that's your reason.
The tiles also add vertices in the middle of traversable space on the navigation mesh. Most path smoothing algorithms do not 'hop' vertices. So your paths would look unnatural.
Could you explain why you did this? :)
great blog btw!
The main goal was to implement simple and fast method of allowing to change the navigation mesh data. The tile method allows you to add and remove a tile of mesh data at any time.
ReplyDeleteOne use case is that you want to stream in and out certain pieces of your level, and another, more interesting use is to regenerate a tile at runtime [1]. Currently you can add and remove tiles to a navmesh and it will not allocate any extra memory and patching up the edge polygons is pretty fast too.
The trade off is that you get extra vertices at the tile edges, but on the other hand you can swap data in and out so in high level you have better control over your memory usage.
Finding straight path within polygons is hard problem [2]. Unnecessarily jaggy paths will happen with or without the tiles. The only way to guarantee absolutely straight paths is to calculate many of them, straighten them and then pick the shortest.
[1] http://yak32.blogspot.com/
[2] webdocs.cs.ualberta.ca/~mburo/ps/tra.pdf
Ah, so you want to be able to do 'lod-ish' streaming on the navmesh. To be able to have different tessellation, to conserve memory. Similar to some geomipmapping techniques. The tiling helps you with seams and stitching chunks together. Got it:)
ReplyDeleteI don't see the need for the tiles just for streaming out parts of levels though. What ever kind of streaming you're doing, scripted or distance based. You should be able to bundle up the triangles in the different streaming sections no problem.
Flip side is tiling does add extra nodes for your path finding to search through.
Which goes against my favorite part of a navigation mesh. The fact that they can describe the traversable surface with the fewest amount of nodes.
It's not LOD, it is a way to change a piece of navigation mesh at time.
ReplyDeleteThe idea came from slightly another direction. Initially I was working on the tiled navmesh generation in order to be able to generate big meshes. In my method the memory needed for the voxelization grows past gigabytes when you have fields larger than 3000x3000, so you run out of memory.
Generating the mesh small chunks at a time and stitching the tiles together allows to create meshes spanning across large distances.
Then later when I was thinking about dynamic changes to the meshes, I decided to reuse the idea. Firstly, it meshes nicely to my generation process, secondly it turned out to be quite multi-use method. The dynamic navmesh generation was the first problem that I wanted the tiling to solve, I dont mind at all that it allows me to handle streaming too.
For completely dynamic navmeshes you want the changes to be as local as possible. If you would have one large polygon which covers a big field and there would be many small obstacles on that field which you would like to add to the navmesh, then that single change can become really really costly. If you do it tile by tile, the local changes are much smaller, and the overhead to add an obstacle is more controllable. You trade of speed of the graph search to speed of the dynamic adjusting of the mesh.
The sort of preferred way to dynamically adjust navmeshes with recast and detour is to rebuild a tile, rather than cookie cutting holes for obstacles. This allows to remove as well as add walkable areas.
Tiling does add extra polys, but adjusting the tile size to match your needs will allow to minimize that. If you just want streaming, use few big tiles, if you want completely dynamic world, then use smaller tiles so it is way faster to regenerate them.
Sorry for resurrecting an old post, but I was wondering if you could elaborate a little more on how you resolve exterior links between tiles.
ReplyDeleteBrowsing the code, it looks like this is all handled on the run-time side of things (Detour) as opposed to during generation (Recast). Am I correct in this assumption?
Were there any big performance implications because of this approach?
I've thought about handling the exterior tile connection resolution during mesh generation, but this runs into problems when a neighbor tile is not properly updated, etc.
Thanks for your time! :)
@elmon, during preprocess I mark each potential external edge. Each of these edges also gets tagged on which direction they are facing. So at runtime when connecting the tiles, I get the neighbour tile and walk through opposite tagged edges and see if they touch [1]. That way there usually is only very few edges to test.
ReplyDeleteSince the portals are axis aligned, it is easy to detect how much the portals overlap, and then allow to connect the portals partially. That helps a lot with certain corner cases where the preprocess fails to generate exactly matching meshes.
[1] You can see the "portal slabs" in action in this image http://digestingduck.blogspot.com/2010/04/more-accurate-tile-connection.html