Shift portal mins and maxs together to try and align the portals. The system is dynamic and will take portal span into consideration. Also slightly changed the API to implement an optimization by switching the directional vector of the edges to their normals as we only need the normals in traverseLinkInLOS, this avoids having to recalculate them.
Draw inner and outer poly boundaries, and only draw detail meshes if this was specified by the user. Most of the time we don't want to draw detail as this has a huge performance cost.
This was increased in commit 0a4817a707035e49e757dcd16d132ac5a5a9a46c to address an issue where the AI gets stuck in corners, but the issue also happened on other traverse types (abeit much more rare). After investigating the problem again, the issue was caused by connecting adjacent polygons with traverse portals (which causes an infinite recursion during pathfinding if the first link of that polygon happens to reference the one from which the traversal is taking place). This issue has been patched in commit 582ecec0381b4071f2f7fd1920eeb27c8c8539c7, therefore, we should restore this to its default value again.
The static pathing data is either not built, or has to be rebuilt at this stage. If we have do happen to have dead polygons that we can use for traverse portals then we should leverage them to get as much coverage as possible.
Connecting adjacent polygons with traverse links will cause pathfinding to run into itself infinitely if either of the 2 poly's first link references the polygon from which the traverse link originates from. The behavior in-game is that the AI become stuck in the area with error code FAIL_NO_ROUTE_BLOCKED. Implemented the method 'dtNavMesh::arePolysAdjacent' to make sure we never connect adjacent polygons on our own or neighboring tile with a traverse link.
Use a cell size of 15 instead for navmeshes used for titans and goliaths (_large and _extra_large). This value results in identical values with Titanfall 2 regarding bounding volume quantization factors.
The traversability of off-mesh links is not dictated by the walkable climb in this engine; an off-mesh connection can be higher from the ground due to ziplines.
Currently, trigger only gets used for hazard or door area's, and we don't want NPC's to traverse through these. The collision detection system needs a small overhaul to take actual polygon flags or contents into account which will allow for a much more detailed filtering. This will be done once we use more areas than just hazard or door.
Some of them were incorrectly assigned and also missed a few traverse types dedicated to of-mesh connections. These new values now correspond exactly to the values the game uses. The only one that couldn't be confirmed is GOLIATH, but it should be the same as TITAN. This will fix cases where a polygon island is marked as unreachable for an NPC hull that could traverse a link connecting its current island to the goal one.
Convex volume hmin and hmax are mapped to world coordinates, thus we need to treat them as such. Also fixed a bug where deselecting a shape, and selecting another one, and then resetting the other ones causes it to be reset to the data of the previously selected shape as the index thereof was never reset on deselect.
These new parameters give the best results so far when generating the navmesh over both vphysics and BVH4 collision geometry. Also removed a todo comment that has been addressed.
Type 1 can cause the AI to become stuck when a link is established within a hole that is too short. Testing revealed that any link beyond this length, wether its on a hole or gap, does not cause the AI to become stuck. Updated default.
The mesh data from the game's BVH4 tree does not appear to have a fixed triangle winding order, making it nearly impossible to generate correct navmeshes while using the decoded BVH4 data. Fixing the sign enables us to generate the navmesh over the game's collision data properly rather than using the render mesh. This change does not appear to have a negative effect on the generated NavMesh.
These changes seem to yield better results for the larger maps. The improvements are minimal however. This change is probably more noticable on tile cache.
In recastnavigation/recastnavigation@15ebb8bd25 the change was made to use detail polygons, but it appears that after this change, the bounding volume gets build under the polygons, especially if the polygons's Z are equal on all vertices. Flooring the mins and ceiling the maxs appears to yield correct behavior in all scenarios by making sure the bounding volume always encases its respective polygon.
Reverse engineered the last types that were mostly unused and unneeded by the navmesh. But to properly implement the destructor it had to go in. Cells and hints now get freed as well and we can now rely on our own destructor for the navmesh data allocated by the game.
This was required as a cell height of 2.0 is too low for the map "mp_rr_canyonlands_64k_x_64k". This particular level is very large, and has another level far underneath; its the old firing range. In order to ensure full coverage on Z, the cell height must be increased. After the change in commit b3946e924aeea05f65f9fcba5e9043771d14af23, the new cell height actually produces more accurate and consistent results accross all levels.
If an off-mesh connection has a base link, but no land link, there will be an invalid link as we never process there. These links must be removed. Due to this change, the link flagging had to be moved to a separate loop as we would otherwise store the dead link in the file (it won't cause a crash as it has been unlinked, but there is no reason it should be stored). Also improved the detection of external off-mesh connections landing on our current tile, instead of doing a position lookup just decode the polyref and check if the index equals our current tile.
The Hull_s::height field is actually Hull_s::stepHeight. This results in much better navigation and prevents entities "popping" into air as they shouldn't be able to walk over some obstacles.
After the implementation of brush intersection detection in commit 6fa5080fe51e2ea118f2cf4f922bcb6e815b3a9f, we return out as soon as we have a hit, even when tmin is provided. But if tmin is provided, the caller is interested in finding the closest intersection so we must go over the input mesh as well. This fixes a bug of raycasts going through geometry when there's a brush behind it.
External references were never updated. Especially when the tile we process doesn't own an off-mesh connection, but does have one landing on it. After this patch, the navmesh passes all tests in game and all polygons appear to be remapped correctly when using all features of the Detour NavMesh (single step verification). Also no issues reported from address sanitizer after several tests on extremely large and complicated navmeshes.
- Off-mesh connections should always be linked to target poly's first. Also set the linked flag on titanfall navmeshes as this is necessary during the pruning stage.
- When connecting off-mesh links, we need to iterate over tiles using m_maxTiles, not m_tileCount as m_tileCount counts the number of added tiles, while m_maxTiles contains the maximum tiles in the lookup array, there can be empties in between.
- Radians to degrees and visa versa has been moved to a simple inline function, but during this, a regression was made where it was accidentally inverted in dtCalcOffMeshRefYaw and dtCalcOffMeshRefPos.
