I have been working recently on the area generation improvements. One area I have been researching is how to generate and store the different areas. It looks like there is need for two kinds of areas, the ones that describe the basic structure of the level, such danger spots, and the ones that are modifiers to the previous ones, such as encoding movement type into the mesh.Additionally some areas may need dilation and others may require erosion. For example the general walkable space needs to be eroded by the agent radius (if desired), while an area marked for crouching should be dilated at least the agent radius, same applies for danger locations too.
The area generation code will most likely get quite a bit more complicated. That is one reason I've been looking into some alternative ways to partition the area into simpler pieces.
I like water shed partitioning because it generates nice regions, but another way faster alternative is monotone partitioning. One thing that is really nasty about monotone regions is that in practice it tends to create a lot of long sliver areas, which is not good for navigation.
The above picture shows a scene partitioned which is processed by partitioning the walkable are into monotone regions. The region buiding process is almost an order of magnitude faster (my favorite performance improvement), the total build time about twice as fast. Normal single pass process suffers a lot from long sliver polygons, but the tiled process is almost unaffected.
It is going to be a challenge to implement the area stuff efficiently. I'm not too worried about actually tagging the areas, but any further process such as dilation or other kinds of filtering can become a bottleneck. Not to mention how setup the API, and how the Detour API is going to cope with that without exploding.
Tags and flags are nice, but sometimes they can end up bloating your compact data.
Can you elaborate on why crouch regions need dilation?
ReplyDeleteIt depends how you use the navmesh, but the way I like to use it is to bake the Minkowski sum of the agent radius in the mesh. So any point inside the mesh is agent radius away from any obstacle. The same idea applies to crouch areas. In order not to hit your head to a door frame the crouch are needs to start a bit further away.
ReplyDeleteI see, but it seems rather complex to include that sort of navmesh building into the core library, when there are much simpler ways to handle the situation of needing to crouch before actually getting inside the region, such as simple stuff like knowing your next region is a crouch region and allowing the user to crouch early(maybe distance to the area border and such). I'm not sure the problem warrants that sort of special consideration in the mesh.
ReplyDeleteIn that kind of case it might work, but if you need to do a point query, whether a certain location is inside a crouch region, then it will not work anymore. Or if you are moving next a crouch region tangentially, then your character's head would clip through geometry.
ReplyDeleteThe dilation process is not really a big deal. Making really fast may be challenging, though. The version I just made yesterday takes 9.6ms on the above level. I want to make it faster and more accurate still.
The more interesting problem will be how to handle the cases where you start to have multiple overlapping areas so that the technique will not generate huge amount of tiny triangles. Or... how to still keep the area building procedure fast and simple when the are many areas.
I'm not sure what you mean with your head clipping example. I would envision a crouch region as all the navigable space that requires crouching to enter. Crouching ahead of entering it wouldn't be difficult to do external to the system Seems to me that expanding the crouch regions would cause the issue you describe, if the path involved skirting the expanded edges of the crouch regions. I just think it's over complicating things to get into handling aspects like that in the nav building step. I just see the region building steps as a way to encode more environmental data into the navmesh, and not necessarily to expand or extrude that data contextually. I've never found myself wanting that type of functionality in any middleware I've used, and I haven't seen a middleware yet that supported it, so it sounds of dubious value to me.
ReplyDeleteI understand your point that by expanding the crouch areas to push into the non crouch areas you get a 'cleaner' representation of the where the agent must start crouching, I'm just skeptical that it's a significant enough problem to add extra complexity is all.
Maybe a picture is worth additional 1000 words.
ReplyDeletehttp://sites.google.com/site/recastnavigation/crouch_explanation.jpg
On left you see the common case. The boudaries of the obstacles are dilated by the agent radius in order to create navigable space where each voxel represents a location where the character can stand without obstruction.
On right you see the same case when the walkable space is divided into a crouch area.
First, the whole navigable space is found by using the smallest possible navigable height (in this example it could be the crouch height), then the walkable space is partitioned into areas based on height. And next up is the same dilation pass so that each area type represents locations where the agent can be without obstructions.
I do not see anything dubious about that.
As I stated earlier, the dilation pass does not add any complexity to the process, the only challenge is to make it really fast.
Whether you like to bake the Minkowski sum into your navmesh or not is matter of taste. Recast is able to handle both. I like to bake it in, and hence Detour will assume such data. It just makes a lot of things so much easier.
That's fair. I don't mean to seem argumentative. I think I had it in my mind of a more complex process. Thanks for the visual aid.
ReplyDeleteThese comments are pretty old at this point. Did this ever manifest in recast functionality so that crouch areas can be expanded in this way?
ReplyDeleteThe experiments did not get integrated into Recast and a bit later I got sunken into the path following rabbit hole. If you need that functionality, I'd be glad to help you out to implement it.
ReplyDelete