I have been using some idle cycles every now and then to try to think about a nice method to update the navmesh without requiring to completely rasterize and rebuild a tile from scratch. This would be useful for obstacles, which may break and may be pushed around and usually only contribute blocking areas into the navmesh.
Cookie Cutter Obstacles
One method to do that is to punch holes in the navmesh using CSG. Some path finding middleware support that and some games shipped using it. So it definitely works, but I don't like the method.
Firstly, you have to work around the floating point accuracy, which is paramount pain. Secondly, it usually is too accurate, which means that you get some small polygons all over the place. Thirdly, it does not scale well when you have multiple overlapping obstacles. So it is an option, but very very low on my list of things to try.
Local Grid
Another option would be to use local grid and rasterize all the temporary obstacles into it and then use another simple pathfinder to find around the way.
The good thing about this method is that overlapping obstacles is not a performance issue anymore. Because grids often have lower resolution than actual world geometry, they tend to simplify the obstacle area too, so it solves the small triangle problem too.
The down side is that you have second representation of your world. The problem it creates is that what to do when the path is blocked? There is no way to reliably pass that data back to the navmesh and replan the path, as it would require to change the layout of the mesh. Simply blocking certain polygons temporarily does not fix it.
Recreate Piece of a Navmesh
Currently the way I prefer to handle dynamic obstacles is to recreate the tiles where an obstacle has changed. Tiling helps to limit the amount of work that needs to be done. While it works well in practice it is overkill for many situations, including the temporary obstacle case.
That has lead me to thinking that how much of the work that goes into rebuilding a tile could be cached?
In practice the answer is that at minimum you need to have the data that is stored in Recast compact heightfield to rebuild a tile and have the benefits of the grid. At the compact heightfield level each obstacle could be rasterized in the heightfield as specific area type and then the rest of the Recast pipeline would be run to obtain the final mesh for a tile.
There are some shortcuts that can be taken to make the rest of the Recast process quite a bit faster than usually. One optimization is to use monotone region building function. Another one is to use more loose parameters for detail mesh calculation. For small tiles, this can halve the build time which is spent after rasterization.
In practice it means, that if we could start from compact heighfield, we could rebuild a tile on 1 ms instead of 10 ms. And by using the simpler methods the work can by split into similar sized chunks so it is possible to handle the building over several frames.
But compact heightfield can be a lot of data which makes the idea impractical. Only if we could compress it...
Compressing 2.5D Heightfield Data
By inspecting the data stored in the compact heightfield, we can see that the data per span does not vary very much between neighbours. Also it happens to be stored in a way that helps usual compression algorithms to pack it well too.
The spans in compact heightfield are stored in one flat array. In addition to that there is a grid of cells at XZ-plane, which stores index and span count for that column. So when you need to find all the spans at certain location, you first lookup the index to the large span array from the cell and loop through all the spans that belong to the column.
The layout is also awesome to store links to neighbours, you only need to store a small sub-index, which added to the index found from the neighbour cell to finally find the actualy span.
Because of the memory layout, all the parameters of spans can be easily stored in one contiguous array, which is good for compression since neighbour parameters are often the same. In practice only the span y and area type are needed to rebuild compact heightfield.
For the base grid, it is only necessary to store the span count per grid cell. The index can be recalculated by accumulating the counts.
The above picture shows 2.5D heightfield of size 208 x 503. The resulting compact heightfield data that is required by Recast to build the navmesh is 1662 kB.
When the data is stripped down to the minimum as explained above, the amount of data is 508 kB. Since the data is so similar it is only 29 kB after being compressed with zip! The height data should compress even better if delta encoding is added.
Conclusion
Using compressed compact heightfield could potentially be interesting solution to handle temporary obstacles. For small tiles, the rasterization can often take up to 90% of the total time required to build one tile worth of navmesh. The method would require extra data to be stored per tile, but the data should be manageable since it can be compressed by about 1:50.
When we used NavPower at my previous job for Mercenaries 3 I loved how it handled obstacles. At the time it only supported bounding box obstacles, with the promise that other convex hulls were coming. You add the hull(bounds) to the environment, it expanded it for each navmesh layer it was applicable to, and then booleaned it out of the environment. The performance of this operation was very fast and it could more than cope with the demands of a highly dynamic and destructible game like Mercenaries. It was welcome functionality after evaluating PathEngine and Kynapse at the time, both of which it were set up so the user has to 'project' your own obstacle boundaries onto the mesh. With NavPower, it was handled, and if a long slender object fell and had walkable space under part of it, NavPower would handle that. Most of the objects in Mercenaries 2-3 are destructible, so we were using obstacles far more aggressively than most games need to. So much in fact that the NavPower guys added some deferred obstacle queries to better manage our requests. I think we were sometimes adding 20-30 obstacles a frame into the mesh.
ReplyDeleteThe overlapping obstacles was initially a minor issue, because when obstacles overlap, I believe it would re-obstacle-ize the whole polygon, so for each overlapping obstacle you added, a polygon might be rebuilt multiple times. It may be fixed by now, but I think the plan was to group overlapping(after extrusion) obstacles together and boolean them out as a group or something. It was a rare problem but I ran into it a couple times.
I have some nasty experiences from past where overlapping obstacles caused problems. Or actually it does not even need to be overlapping, the same performance problem could potentially happen if you have one large polygon and lots of objects on it.
ReplyDeleteWith the heightfield approach it should be possible to use anything you can voxelize to mark an obstacle. Simple shapes will of course be faster but for larger objects you could use a trimesh too (at least in theory :)).
Also one Detour specific detail is that, the way data is stored does not allow polygons to be easily moved around. This means that if one tiles was changed using some CSG method, you would need to create a copy of it and keep the previous one so that I could undo the change. With that in mind, reusing the existing pipeline is also maybe favorable.
Can you tell, or do you remember how much time it usually took to add an obstacle with NavPower? Or 30?
I don't remember the specific timings of the obstacles, just that we kept a fine framerate adding about 20-30 obstacles a frame or so at the high end, along side regular AI logic. It was an extreme case, being a streaming open world game, but because we had such a destructible environment, every tree in the terrain was an obstacle, every sandbag, some U-shaped sand bags were represented by 3 box obstacles, etc. Basically whenever these game objects would page in, obstacle information would be added if they had any associated with it, then when destroyed we would remove them. Removal was practically free, and I believe the devs explain how they layout the memory to facilitate dynamic meshes in the power point they did a long time ago. For games that have a much smaller number of dynamic entities, they might be able to remove and add an obstacle every frame for something like a vehicle. For a while during eval I was adding a box obstacle for moving vehicles every frame. Since you can't move an obstacle, you can only remove and re-add it. So for tanks and stuff I would remove and re-add it each frame because the NavPower dynamic avoidance was repulsor and radius based, and not greatly suitable to represent an elongated object like a vehicle. He had 'eliptical' repulsors on the todo list, but I'm not sure if they are in the latest. I no longer work for Pandemic anymore so I'm not up to date on the latest in NavPower offerings. Anyways, re-creating the obstacle every frame when moving was suitable for a few vehicles, but once all the environmental objects were creating obstacles and we had maps with more vehicles it was no longer an option so I used the dynamic repulsors for moving vehicles and when they stopped it would add an obstacle.
ReplyDeleteI'm very curious to see how the dynamic voxellization stuff works out. It certainly appears like it could have some interesting advantages. Would the entire tile be rebuilt? Or would the obstacle-ized tile voxellize the base navmesh tile + obstacles and override the base tile?
As an aside, one of the main culprits of obstacle performance that we discovered when I sent the NavPower guys some of our real world test data from Mercenaries was the fact that for nearly every obstacle, it ended up being baked into 4 different navmesh layers. We had humanoid, car, tank, and helicopter navmesh layers, so in effect every obstacle involved a boolean operation on 4 different meshes.
ReplyDeleteThanks Jeremy for sharing! Real world stories always help me to aim better :)
ReplyDeleteThe idea was to rebuild a whole tile. For relatively small tiles, say 6x6m, the majority of the time to rebuild a tile is the rasterization, usually up to 90%. So the compressed stuff would allow me to skip that heavy part.
In practice this would mean that one tile would take about 1ms to process when any number of new obstacles are added or removed. I'm quite sure there are some things that can be done to speed that up.
That 1ms is for a relatively complicated piece of a building, which has multiple stories and is standing on ground mesh.
My preferred way to handle moving obstacles (i.e. tank from human point of view) would be to use velocity obstacles for them. Once the obstacle stops it should be baked into the navmesh in one way or other.
Good point about the multiple navmeshes.
This approach sounds really promising.
ReplyDeleteI wonder if it would be worthwhile to precompute a mini compact heightfield to represent the space occupied by the obstacle, so even that doesn't have to be rasterized at runtime, it can just be subtracted from the heightfield...
BestAliasEver, in certain cases it might work. But in general you would need "sub voxel" accuracy. So if you translate or rotate the object, then then that voxelization would not be very useful anymore. If your object does not change location, then it is easier to use the area generation stuff and just change polygon flags or area types.
ReplyDeleteVery Nice Blog !
ReplyDeleteI Like This Very Much.
Methods of Modern Farming
Duck keeping