Comments (15)
I think this is a good idea. I would accept a PR, if it also would be backwards compatible. There a lot of folks who have data in the current format.
from recastnavigation.
That is fair enough.
I think the only thing I'll need to change to maintain perfect compatibility (ie keep structs identical) is to go back to bit packing the area id of the polygon and the polygon type into one variable in dtPoly struct. This should be do-able, i'll just need to change the setting / getting masks to use some bit-shifting based on the size of the variable rather than hard coded masks.
I'll give it a shot in the near future and let you know how it goes / create a pull request once I have it working on a fork.
from recastnavigation.
I have my first attempt (not properly tested yet, but quick tests with RecastDemo seem to work fine):
bryanmcconkey@b77cb35
Do you think rcSpan needs to be data compatible? I'm not sure what data is commonly stored. (I do not save out generated meshes as levels are procedural generated) Due to rcSpan members currently being bit packed, I do not see a way to maintain data compatibility and have the size of the area be adjustable without a define to opt in to adjustable.
dtPoly was hard to keep the same (due to bit packing as well with areaAndType) but I worked around this by having type use the upper two bits of the variable regardless of the size. I had to rewrite the accessors for area and type but this seems to work fine with area as a unsigned char, unsigned short, or unsigned int in my tests so far.
I also made DT_MAX_AREAS auto calculate the max possible (given the upper to bit reservation), though this size gets way to large for sizes unsigned int or above. Though it does compile / work fine if I manually define DT_MAX_AREAS so the array size is legal in dtNavMeshQuery.
Additionally, currently area and flags are used in different places with no current shared header to place a typedef in. For now I've created a DetourTypes.h and RecastTypes.h for this purpose, though I'd like to know where you would like to see them (my other thought would be Recast.h and DetourCommon.h ?)
Thanks for your input
from recastnavigation.
Found a few remaining issues when merging these changes into a game I am working on. So if you go to look at diffs, please check my current master.
https://github.com/bryanmcconkey/recastnavigation
from recastnavigation.
I saw discussion from @jswigart and @hymerman in the #123 topic about splitting the multiple variables out into their own components. I think this simplifies things greatly and would approve of that change. However I still think its worth making the size of those be adjustable as I had done (ie a typedef instead of hard coded int32 or 64 etc) so that projects that need less or more granularity can adjust for that easily.
from recastnavigation.
Agreed! I'll have a look through your changes sometime soon, as well as @jswigart's and my own (not currently on GitHub), since it sounds like we've all done fairly similar things!
from recastnavigation.
Awesome! Personally, I'm all for making typedefs where it makes sense. I also agree with Mikko that the changes should be backwards compatible, though, so long as you're not changing default data types, it should be.
from recastnavigation.
My changes went further than typedefing the existing fields.
Rather than an 1 byte area type and a 2 byte flags(iirc), I merged them both into a single 32 or 64 bit(via typedef) 'area mask', and used that throughout the entire build process, from rasterization to detour. As a single mask type field, it can correctly track stacked area types where area types overlap and accumulate. I use this for things such as maintaining crouch area contextual information on top of other information such as team specific areas, etc
You really can't keep track of the stacking effect of area markings without treating it as a mask to some degree. Maintaining a priority ordered 1 byte area type and then trying to convert that to flags after rasterization after the navmesh is built was less intuitive to me and is very lossy in terms of the underlying rasterization data that a mask can carry through.
from recastnavigation.
Yeah. Externally to the lib i map the dtAreas to masks game side to correspond to some game side material type information. This was the root cause of my need for larger types to represent the areas (as I needed 1 dt area per unique area mask in the game). Internally using masks would have worked much better for me overall. The changes I did were done when the approach we had used, with vanilla recast/detour, required more unique areas than i could represent in the original type.
The change I made did support the backwards compatibility (until you changed the typedef), which from a personal standpoint I do not care about, but do understand the concern for some.
from recastnavigation.
@bryanmcconkey I don't fully understand the description of your implementation. Are we talking about the same thing? If you are maintaining this mapping external to the library how do you ensure that the rasterization process maintains the region shapes for each custom area? And how does it allow them to have a cumulative effect?
from recastnavigation.
I am saying having the areas be a mask would be better in my option, which is what it sounds like you have done.
In my use of recast for Below, I already have game specific area masks (used for particles, sounds, and various other things). In order for these to influence the nav mesh generation, i assign a detour/recast area to each unique game specific mask that exists in the level.
Simplified Example:
Game Specific Area Types
Stone: 0001
Grass: 0010
These can stack and one area could have say grass and stone.
In order to get vanilla recast / detour to generate based on these stacked masks, I in game code (external to the library) map the game area type masks to recast/detour area ids.
Stone: 0001 Recast/Detour Area ID: 1
Grass: 0010 Recast/Detour Area ID: 2
Stone&Grass: 0011 Recast/Detour Area ID: 3
Combinations of bits that don't exist in a level are not assigned a recast area id, and thus I was able to get by with this approach for a while, while still having the rasterization maintain the region shapes for my custom area type masks.
As the game grew I ran out of unique combinations of mask bits that i could uniquely count within the detour/recast area id variable size. This is why I changed recast to use typedefs so I could easily increase their size and therefore increase the number of unique masks I could represent.
Having detour/recast use masks internally (which sounds like what you have done) would be an ideal solution for me. If recast/detour used masks I would not need this external mapping to get it to represent my areas. However I do not know how to maintain binary compatibility by doing so aside from some sort of versioning in the data format.
from recastnavigation.
Thanks. Just trying to understand what others have done to accomplish similar goals.
Does that mean your input area type combinations were known ahead of time and passed into rcRasterizeTriangle explicitely with the geometry? As opposed to individual bits worth of 'types' and recast maintaining the OR value of them? Presumably you would have to feed in the full type(stone+grass) with the geometry if we're talking vanilla recast/detour.
from recastnavigation.
For more information, another recent modification I did that piggybacks this mask functionality, is that I wanted to be able to access, via an area type, the entities that were responsible for influencing an area. I use this in my bot in Half-life 2 so that when the path goes through the area resulting from a dynamic prop, I can have ready access back to the entity.
https://www.youtube.com/watch?v=5qYgRA5oINs
I'm using a 64 bit area mask in my recast, and the top 32 bits are used for what I am calling 'user references'. This is basically an optional array of user refs that may be added to a tile such that each bit position is effectively an index to the dtUserRef array also stored for that tile. If multiple props(using this example) overlap, the overlapping region will have multiple bits set, so that both entities can be known quickly and easily from an area. Since the user ref array is unique per tile, that basically means that so long as no more than 32 overlap within a single tile, there's no limit to how many user references you can have total throughout the entire navmesh, since the limitation is pushed down to the tile level, and it's highly unlikely that I will have more than 32 navigation effecting props within a single tile.
struct dtUserRef
{
int id;
};
Not sure if this is a contribution that might be desired as well, but I find it quite useful to have the ability to bake direct mappings into the navmesh such that areas can quickly map back to game entities or whatever you need to store about an area. Currently I only store an integer which is an entity Id, but it could be whatever you want.
from recastnavigation.
Not exactly, but close enough logically. I won't bother going into details of the other game specific systems, but in terms of the area types combinations and inputs to recast, in my scenario I do know the input set of area type combinations ahead of time, which is how i can assign unique combinations to area ids.
I use the flags one to one with my game area type combinations, which let me later use them to control queries (example: only path on grass). Thus in my usage flags and area ids ended up having the same meaning.
I even have a std::map<dtFlags, dtArea>
existing in one place.
Overall having to convert masks to area ids was a bunch of stepping through hoops, that if the library supported directly would have made my use / integration much easier.
from recastnavigation.
Pulling out the remaining unimplemented idea from this old issue into #644
from recastnavigation.
Related Issues (20)
- Inconsistent naming of HeightField and Heightfield across the codebase
- Typedef integer flag types as appropriate
- Why use dtMathFloorf to calculate tx1/ty1 (max_x/max_y) but not dtMathCeilf in dtTileCache::queryTiles HOT 1
- Bug when culling out off-mesh start locations?
- Infinite loop in triangulateHull when detailSampleDist == 0
- Small optimizations for CalculateDistanceField() in RecastRegion.cpp HOT 1
- Nullptr dereference leading to a crash in closestPointOnDetailEdges<true> HOT 2
- TempObstacles problem on stair HOT 1
- Can I add Android, IOS, and Linux libraries?
- The "min region size" does not take effect when constructing the navmesh using the TempObstacles mode. HOT 2
- Triangles looks strange. HOT 2
- [Detour] Incorrect layout of tile links in DT_POLYREF64 mode HOT 3
- cannot load new geometry file in RecastDemo HOT 1
- rcFilterLowHangingWalkableObstacles Study HOT 2
- Add revision to the generated navmesh HOT 1
- maxTiles value in the navmesh initialization parameters HOT 1
- dividePoly crashes on the attempt to add 8th point HOT 2
- Bug while loading vertices/indices HOT 4
- [Github Action] Segmentation fault, process completed with exit code 139 HOT 2
- Unable to Export Off-Mesh Links in recastdemo Temp Obstacles HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from recastnavigation.