Oh noes, this dude cannot swim so he has to walk around the pond!
I'm starting to be happy about the workflow of creating the areas and the ability flags and areas are passes all the way to Detour.
Solution
The solution I settled into was to use area type and ability flags per polygon. Area type specifies the cost to travel across the polygon and ability flags specifies if the agent can travel through the area at all. There are 64 area types and 16 abilities. Should be enough for everyone. The cost value will be multiplier to travel distance across the polygon.
Other than that Detour does not imply the meaning of flags or area types at all. The actual abilities and area types are specified by the game. Recast demo has some example types and abilities just to keep the samples consistent.
Convex Volumes
The building block of marking areas is extruded convex polygon. I will add other types as people need them. You should get pretty far with that type already.
Note that, the resulting area on the navmesh will not be the same as the input polygon. This is because the area generation goes through voxelization, which snaps the area to a grid, and through contour simplification which may cut few more corners. I'm eager to hear how this works in practice.
For the time being, I don't have plans to add area marking cookie cutters which work at geometry level.
To Do
The path finding cost is not adjusted yet. It is a bit nasty task to do as I need to refactor few things, such as querying the polygons during path search. I'm also seeing funky pathing cases here and there, which I hope to fix in the process too.
Another thing that still needs to be done is adding API to adjust the polygon ability flags and area types.
The latest iteration is available from the SVN, use with caution :)
Mikko,
ReplyDeleteConvexVolumeTool.h is missed in svn
thanks
Looks like the whole convex volume tool is missing. Oh well, I'll add it once I get back to my home comp. Thanks for reporting.
ReplyDeleteMikko,
ReplyDeleteIn the VS project in the SVN are some recent files not added yet. Manually adding worked fine though.
Another point:
I recently found obviously simple cases where the navigation way is not optimal for some reason.
If you have just a thin hole or pillar (like in the nav_test mesh) and put the start and end point around it so that the pillar is between them and slightly shift one of the points around a bit it happens that the evaluated way goes around the pillar on the opposite side. I hope you get what I mean.
Another point:
ReplyDeleteThe area code works pretty nice in your demo. You added some flags, one of them is "door". I´m wondering if this approach is feasable for doors because you could have a some doors where some are open and some are closed. To simulate this you would need a flag for every specific door then and exclude the closed ones etc.
Mirko,
ReplyDeleteThe VS project is dragging behind the xcode project. I try to boot my other computer to windows once a week, but sometimes that fails :)
Path: The navigation problem is known something that most polygon based pathfinders exhibit. The way the path finder works is that it actually follows the midpoints of the polygons edges. A* needs points/nodes in space to calculate the shortest path. After the polygons are found, I use string pulling to find the final path.
Areas: You could use one flag to describe if a polygon is enabled or disabled and add that to exclude flags and that will handle all kinds of blocked polygons.
Mikko,
ReplyDeleteThank you for your reply.
Areas:
I do not yet understand how this workflow would look like. E.g. If I have two rooms connected via two different doors (lets say both open). Do you suggest to define an area for every door with the flag "open" and generate the mesh?
How would I then switch one door to "closed"? By searching for the polygons in this area and setting their flag to closed?
Thanks for your help!
Mirko
The idea for doors is to mark each door using certain area type when you generate them. Then at runtime you get the polygons that are used for a door i.e. using getPolysAround, I will extend it to allow to use convex poly as bounds, and you would discard all polys which do not have the door area set. This gives you door polygon set.
ReplyDeleteThe in your door logic, you would add and remove flags from the door polygon set. You can use any flag you like, for example you could have one generic disabled flag which you always have in the "excludeFlags" part of the filter. Or you could have specific flag for locked doors, etc.
Hi Mikko,
ReplyDeleteI think I got it now! Thank you very much for your explanations. Sounds like a clean straight forward workflow so far.
Mirko