It's probably obvious from the number of open issues and PRs that I have not had the time to maintain this project properly in recent years.

I'm looking for one or more individuals to take the detours going forward.

Should you choose to accept the challenge, I'll be around to answer questions and discuss details by email or Skype through out the nest year.

I'm having an issue with this function: rcVsub(Single* dest, Single* v1, Single* v2) dans

Wether I'm 100% ram or just < 30%, it will sometimes throw a System.AccessViolationException, and it will always be inside this specific function.

Also, on a specific tile generation, I'm able to reproduce this issue 100% of the time, even if I just rebooot my PC and my RAM is empty.

v1/v2 unable to read memory

sometimes only v1, sometimes only v2, sometimes both.

Any idea ?

 à rcVsub(Single* dest, Single* v1, Single* v2) dans e:\développement\thenoobbot\thenoobbot\meshreader\recastlayer\recast\recast.h:ligne 649
   à ?A0xc7c409e5.calcTriNormal(Single* v0, Single* v1, Single* v2, Single* norm) dans e:\développement\thenoobbot\thenoobbot\meshreader\recastlayer\recast\recast.cpp:ligne 235
   à rcClearUnwalkableTriangles(rcContext* ctx, Single walkableSlopeAngle, Single* verts, Int32 nv, Int32* tris, Int32 nt, Byte* areas) dans e:\développement\thenoobbot\thenoobbot\meshreader\recastlayer\recast\recast.cpp:ligne 293
   à RecastLayer.RecastContext.ClearUnwalkableTriangles(Single walkableSlopeAngle, Single[]& vertices, Int32[]& tris, Byte[] areas) dans e:\développement\thenoobbot\thenoobbot\meshreader\recastlayer\recastlayer.cpp:ligne 56
   à meshBuilder.TileBuilder.Build(Int32 i, Int32 j) dans E:\Développement\TheNoobBot\TheNoobBot\meshReader\meshBuilder\TileBuilder.cs:ligne 242
   à meshBuilder.ContinentBuilder.Build() dans E:\Développement\TheNoobBot\TheNoobBot\meshReader\meshBuilder\ContinentBuilder.cs:ligne 257
   à meshBuilderGui.Interface.RunBuild() dans E:\Développement\TheNoobBot\TheNoobBot\meshReader\meshBuilderGui\Interface.cs:ligne 154
   à System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)
   à System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)
   à System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
   à System.Threading.ThreadHelper.ThreadStart()

Hi,

My test input as bellow,

float start[3] = { -22.636648178101, 12.46023273468, -123.88012695313 };
float end[3] = { -12.93, 12.08, -110.27 };
float speed = 0.77999997138978;

And the target test navmesh binary as bellow,

all_tiles_navmesh.zip

If i am trying find a smooth path use these data, i will enter an infinite loop from a iteration. From smooth_path_count_ = 17, the loop keeps give me bad point (-14.4847, 12.4086, -113.422).

Is there any hints for me?

Thanks

In our server we get a segfault in dtNavMeshQuery::findPath after some time (most of the time multiple hours). The segfault occours when trying to dereference an invalid link. The first link of the parentTile points to a polygon that is out of bounds of the polygon array of the tile pointed to. It is always parentTile->links[parentPoly->firstLink] that causes this error. Most of the time the parents link will point to the correct tile but sometimes the salt of the link does not match the salt of the tile eg the links salt was 11 but that of the tile was 2.

Our server regulary swaps tiles in and out of the navigation mesh to account for destructible geometry. Some of the tiles are built at runtime.

All attempts to reproduce the bug failed thus far. Setting the mesh to the state it was in when segfaulting and calculating the same path will work fine. Randomly swapping in Tiles and calculating the path with multiple threads also works fine so it doesnt seem to be an issue with our multithreading code.

Below is some information of a coredump from such a crash:

(gdb) p parentPoly->firstLink
$1 = 11
(gdb) p parentTile->links[11]
$2 = {ref = 2295592910861, next = 15, edge = 3 '\003', side = 4 '\004', bmin = 0 '\000', bmax = 255 '\377'}
(gdb) p *bestPoly
$3 = {firstLink = 2013265920, verts = {278, 0, 65535, 65535, 1027, 65280}, neis = {1, 30720, 278, 0, 9, 0}, flags = 1025, vertCount = 0 '\000',
  areaAndtype = 255 '\377'}
(gdb) p *bestTile
$4 = {salt = 1, linksFreeList = 18, header = 0x9147cc00, polys = 0x9147cd58, verts = 0x9147cc74, links = 0x9147ce58, detailMeshes = 0x9147d128,
  detailVerts = 0x9147d188, detailTris = 0x9147d3f8 "\021\003$\001\003\004\"\001\004\005&\001\005\006\030\001\006", bvTree = 0x9147d594, offMeshCons = 0x9147
  offMeshSeg = 0x9147d694, data = 0x9147cc00 "VAND\a", dataSize = 2724, flags = 0, next = 0x0, clusters = 0x9147d694, polyClusters = 0x0, dynamicLinksO = {
    m_data = 0x0, m_size = 0, m_cap = 0}, dynamicFreeListO = 4294967295, dynamicLinksC = {m_data = 0x0, m_size = 0, m_cap = 0}, dynamicFreeListC = 4294967295
(gdb) p *bestTile->header
$5 = {magic = 1145979222, version = 7, x = 23, y = 27, layer = 0, userId = 0, polyCount = 8, vertCount = 19, maxLinkCount = 45, detailMeshCount = 8,
  detailVertCount = 52, detailTriCount = 103, bvNodeCount = 16, offMeshConCount = 0, offMeshSegConCount = 0, offMeshBase = 8, offMeshSegPolyBase = 8,
  offMeshSegVertBase = 19, walkableHeight = 55, walkableRadius = 18, walkableClimb = 18, bmin = {-11523.2969, -10357.3135, 1860.67969}, bmax = {-10123.2969,
7801.13477, 3260.67969}, bvQuantFactor = 0.142857149, clusterCount = 0}
(gdb) p i
$6 = 2013265920

tileMask = 16383 polyMask = 67108863 saltMask = 16777215

saltBits = 24 tileBits = 14 polyBits = 26

If you need more i will try to provide it.

Add a guard check against infinite loop occurring in detour, happening when there is a circular reference in m_nodePool, i.e. A -> B -> C -> A.

While this might be caused by another issue in the code, it's better to just fail the path instead of entering an infinite loop.

As every node has only 1 reference to another node, the max number of iteration we can do before we are sure we are in an infinite loop is m_nodePool->getMaxNodes() . This also ensures that we don't accidentally exit too early for huge m_nodePool sizes.

Tested this code in a project where we have been experiencing this issue after upgrading from https://github.com/recastnavigation/recastnavigation/commit/2c85309280dbc9c82029e7ab16dfb01b9235c74e to https://github.com/recastnavigation/recastnavigation/commit/14b2631527c4792e95b2c78ebfa8ac4cd3413363

Ref https://github.com/recastnavigation/recastnavigation/issues/343

We've mentioned in other issues that we should make use of Semantic Versioning (http://semver.org/spec/v2.0.0.html) before we start accepting breaking changes.

I imagine that along with that, we'll also want to start using git tags, GitHub releases, GitHub milestones, generate release descriptions, and perhaps use Travis and AppVeyor to upload built libraries to GitHub releases. And of course... we'll want to actually make our first release.

I propose we follow Semantic Versioning (MAJOR.MINOR.PATCH), starting at 1.5.0 (since the last labelled release was 1.4: https://code.google.com/p/recastnavigation/downloads/list?can=1&q=), tagging new releases when we are in agreement with the version number as it is (no leading 'v' as GitHub suggests). We should create 1.5.0 as soon as we're agreed on how we'll handle versioning - no sense waiting around for some arbitrary set of bugs to be fixed :)

I suggest we create a GitHub milestone for each new version (and for the next version), and label issues and PRs with them. That way we can keep track of when we can merge breaking PRs, without using lots of confusing per-release branches. Some people swear by git-flow but I'm not so sure myself - I think we can get by with just a 'master' branch.

There are projects that can generate release notes automatically but frankly that might be a bit more hassle than it's worth - I suggest we just write release notes ourselves, highlighting the most important changes and providing a link to the list of issues tagged with that release's milestone if users want more detail.

It's also possible to upload binaries with each release, and to do this automatically on new tags from Travis and AppVeyor, but I'm not totally sure of the value of that - personally I would always prefer to download source. If someone else thinks this is worth doing, we can look into it, otherwise let's just leave releases as "git tags with a nice description on GitHub".

Thoughts?

Use flood fill for potentially overlapping polys

This changes the detail sampling to find height data by using the flood fill method for polygons that were merged because of a border vertex removal. This could potentially cause overlapping polygons to receive the same region IDs which would later make the fast-path sampling in getHeightData sample the wrong heights.

Also includes optimizations for this path and getHeightData itself. Previously the seeding was responsible for 25% of the total time spent in getHeightData in these cases. We now use the direction and prune the nodes when we move towards the center cell, instead of doing a full-blown DFS. This makes the overhead of seedArrayWithPolyCenter virtually nonexistent (~2% according to profiling).

In my tests this new path was only reached for about 4% of polygons (although that was with a very large tile size, for smaller tile sizes it will probably be larger). Arguably the optimization is not necessary, but the code is also a fair bit shorter and maybe a bit easier to understand. I ran the new center-finding-algorithm on a huge map with around 3.2 million polygons/heightfields and in no cases did it fail to find the center.

I have also optimized the inner loop of getHeightData. It turns out the 3x rcIntArray::push were accounting for around 11% of time spent in this method, with 5% being function call overhead to rcIntArray::resize (even without doing any resizing - pure function call overhead!), so I changed this slightly to reduce code bloat. I also changed rcIntArray::resize so the common case can be inlined, since rcIntArray::push is used from all over the code base. Finally I changed the lookup tables in rcGetDirOffsetX and rcGetDirOffsetY to be static. MSVC generates much better code for them when they are static.

I got a NULL dereference crash in mergeRegionHoles() called by rcBuildContours() using revision https://github.com/memononen/recastnavigation/commit/eacaa87d9a9059f5fea0064ecd628cc918ceabc3

region.outline is NULL as shown by Visual Studio

callstack:

mmaps_generator.exe!mergeRegionHoles(rcContext * ctx, rcContourRegion & region) Line 751 mmaps_generator.exe!rcBuildContours(rcContext * ctx, rcCompactHeightfield & chf, const float maxError, const int maxEdgeLen, rcContourSet & cset, const int buildFlags) Line 1103

I didn't change any call to Recast to use the new features of https://github.com/memononen/recastnavigation/commit/a89bb843d74a099d0f07cff4d9cb95afdf7afdba . I can reproduce the bug and I'm available to test any crashfix.

I am implementing recast/detour in a module of mine and have now reached the point of adding agents and giving them move targets.

If adding the agent (and setting the move target) works, everything works just fine.

However, agents in some positions simply cannot be added. I dug into the code and the reason for that is that findNearestPoly is unable to find something usable, thus the agents receive an invalid state upon adding.
Similarly, when trying to set a movement target by using findNearestPoly, it will work in some places and not in others.

This would be understandable if I tried to place agents in very remote faraway locations, but that is not the case. The normal extents are about (1/1/1) and the agents are about 0.0-0.2 points away from the navmesh, so this should never be a problem.

Here's an image of the situation (red X = couldn't be added): As you can see, all the agents have the same distance to the ground, there's absolutely no difference in their Y-position. The visible tiles come directly from the detour debug drawing function so they are not faulty, either (and can be traversed just fine by agents that were successfully added).

It also seems to be the case that the closer the agents are to the corner vertices of the tiles, the more likely they are to be successfully added.

I also noticed that when I manually increase the extents used in findNearestPoly to much larger values, it seems to work reliably everywhere, adding every agent to the position they should be at.

Now I could of course just use extreme extent values everywhere, but I'd rather get this fixed.

Besides, you cannot externally set the extents used by dtCrowd when adding an agent. They are just automatically set to 0.5x max agent radius and can never be changed (this should be made accessible, btw.). So I would have to change detour sources themselves, which I would very much like to avoid to be able to just have it as a git submodule.

Added the ability for the user to set a custom function that computes the color of a polygon when debug-drawing a mesh.

This way, the user can get a debug draw that fits his particular situation. He can scan the polygon (mainly flags & area) and determine the color that expresses it best (e.g. green for grass flag, blue for water flag, mud for grass & water flags...).

Default behavior is kept unchanged.

Possible further improvement : color constants defined on the fly in function implementations could be actual global variables that the user could set.

When profiling recast (as part of openmw), I found a large amount of time in RecastMeshDetail is spent in reallocing the same vector.

This is because the resize method always realloc'd on grow. Fixes this by only reallocing when needed.

Comparison for push3 before/after second commit (Debug build though):

Before:

After:

/cc @elsid @psi29a

Hello!

I am needing to get a random point within a specific area.

I already have the area defined and I have its ID. I wanted to create a dtQueryFilter that would allow me to use findRandomPoint() or findRandomPointAroundCircle() to get points that always fall within that area.

How would I have to do to achieve this?

Thanks!!!!!

Currently rcAssert is disabled if NDEBUG is defined. It's often useful, however, to have non-debug builds that have asserts enabled.

To allow for this kind of flexibility in usage, rcAssert should be defined based on a Recast-specific preprocessor declaration, rather than a standardized one like this. Something like RC_ENABLE_ASSERTS

https://github.com/recastnavigation/recastnavigation/blob/b51925bb8720e78a65c77339a532459b96ddfc7e/Recast/Include/RecastAssert.h#L25-L30

There are often cases where implementation-defined limits are hit by users. For example, passing a huge piece of geometry to rasterization can cause things to be clamped (See #594).

For cases where this is easily detectable, Recast should at the very least log that things were clamped.

It's super confusing that there are cases where z coordinate values are used in variables with the name y. The use of the ambiguous height and width rather than a name that indicates the axis to which that size applies is also confusing. There's nothing functionaly wrong about the code, it's just using very misleading variable names.

rcGetDirOffsetY is a great example case https://github.com/recastnavigation/recastnavigation/blob/d0b2ed8ff5d371f375cf49dad7ca96e8b22142d0/Recast/Include/Recast.h#L1093-L1101

We should endevor to name things what they are, and avoid ambiguous terms like "width" and "height".

Since many of these cases are user-facing in the Recast interface, we should take care to not introduce breaking changes to the API outside of a major release.

I've started renaming things in implementations to be more accurate and am making notes of places in the interface that would require a major update to change.

I'm a junior developer, using Recast Navigation for my group's game. I was told that these off-mesh connections won't work with long distances between endpoints, and that the level designer must adjust the tile size manually to make it work.

After some googling and reading through lines of code, I realized that these connections would only work if they are within a single tile, or connecting two adjacent tiles. I presume this is probably to block issues that could emerge when trying to add connection(s) before the two tiles containing two endpoints of said connection are fully loaded.

I was able to produce a working fix, by forcing the code to add connection after all tiles are fully loaded. This fix is impromptu as the title suggests, and if my testing is right, it does not guarantee that the path is optimal. Please take a look at this commit made to a fork, and tell me what you think about it: https://github.com/niji-k/recastnavigation/commit/13eb591b1b752de2e5a78137580b7aeec106eeab

Below are screenshots made while testing, showing some possible cases with modified behavior from this fix. (Pathfinding successfully utilized the off-mesh connection given.)

(Suboptimal path: I have no idea why the connection isn't used.)

(One-way connections can also be used: notice how swapping the start/end pos changes the path.)

P.S. I'm definitely new to this Github stuff, let alone Git, so any advices regarding the Github workflow is highly appreciated.