Navigation-mesh Toolset for Games

Overview

Recast & Detour

Travis (Linux) Build Status Appveyor (Windows) Build  Status

Issue Stats Issue Stats

screenshot of a navmesh baked with the sample program

Recast

Recast is state of the art navigation mesh construction toolset for games.

  • It is automatic, which means that you can throw any level geometry at it and you will get robust mesh out
  • It is fast which means swift turnaround times for level designers
  • It is open source so it comes with full source and you can customize it to your heart's content.

The Recast process starts with constructing a voxel mold from a level geometry and then casting a navigation mesh over it. The process consists of three steps, building the voxel mold, partitioning the mold into simple regions, peeling off the regions as simple polygons.

  1. The voxel mold is built from the input triangle mesh by rasterizing the triangles into a multi-layer heightfield. Some simple filters are then applied to the mold to prune out locations where the character would not be able to move.
  2. The walkable areas described by the mold are divided into simple overlayed 2D regions. The resulting regions have only one non-overlapping contour, which simplifies the final step of the process tremendously.
  3. The navigation polygons are peeled off from the regions by first tracing the boundaries and then simplifying them. The resulting polygons are finally converted to convex polygons which makes them perfect for pathfinding and spatial reasoning about the level.

Detour

Recast is accompanied with Detour, path-finding and spatial reasoning toolkit. You can use any navigation mesh with Detour, but of course the data generated with Recast fits perfectly.

Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows you to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes.

Recast Demo

You can find a comprehensive demo project in RecastDemo folder. It is a kitchen sink demo containing all the functionality of the library. If you are new to Recast & Detour, check out Sample_SoloMesh.cpp to get started with building navmeshes and NavMeshTesterTool.cpp to see how Detour can be used to find paths.

Building RecastDemo

RecastDemo uses premake5 to build platform specific projects. Download it and make sure it's available on your path, or specify the path to it.

Linux

  • Install SDL2 and its dependencies according to your distro's guidelines.
  • run premake5 gmake from the RecastDemo folder.
  • cd Build/gmake then make
  • cd RecastDemo/Bin and then run ./RecastDemo

OSX

  • Grab the latest SDL2 development library dmg from here and place SDL2.framework in /Library/Frameworks/
  • Navigate to the RecastDemo folder and run premake5 xcode4
  • Open Build/xcode4/recastnavigation.xcworkspace
  • Select the "RecastDemo" project in the left pane, go to the "BuildPhases" tab and expand "Link Binary With Libraries"
  • Remove the existing entry for SDL2 (it should have a white box icon) and re-add it by hitting the plus, selecting "Add Other", and selecting /Library/Frameworks/SDL2.framework. It should now have a suitcase icon.
  • Set the RecastDemo project as the target and build.

Windows

  • Grab the latest SDL2 development library release from here and unzip it RecastDemo\Contrib. Rename the SDL folder such that the path RecastDemo\Contrib\SDL\lib\x86 is valid.
  • Run "premake5" vs2019 from the RecastDemo folder
  • Open the solution, build, and run.

Running Unit tests

  • Follow the instructions to build RecastDemo above. Premake should generate another build target called "Tests".
  • Build the "Tests" project. This will generate an executable named "Tests" in RecastDemo/Bin/
  • Run the "Tests" executable. It will execute all the unit tests, indicate those that failed, and display a count of those that succeeded.

Integrating with your own project

It is recommended to add the source directories DebugUtils, Detour, DetourCrowd, DetourTileCache, and Recast into your own project depending on which parts of the project you need. For example your level building tool could include DebugUtils, Recast, and Detour, and your game runtime could just include Detour.

Contributing

See the Contributing document for guidelines for making contributions.

Discuss

License

Recast & Detour is licensed under ZLib license, see License.txt for more information.

Comments
  • Looking for new maintainers for the project

    Looking for new maintainers for the project

    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.

    question 
    opened by memononen 25
  • Recurring System.AccessViolationException

    Recurring System.AccessViolationException

    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()
    
    opened by mmalka 20
  • find path enters an infinite loop.

    find path enters an infinite loop.

    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

    opened by betterdenger 18
  • Segfault in dtNavMeshQuery::findPath

    Segfault in dtNavMeshQuery::findPath

    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.

    bug 
    opened by 0x0ACB 15
  • Add guard check against infinite loop in detour.

    Add guard check against infinite loop in detour.

    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

    opened by jackpoz 14
  • Discuss versioning, and release a 'first new version'

    Discuss versioning, and release a 'first new version'

    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?

    question 
    opened by hymerman 14
  • Use flood fill for potentially overlapping polys

    Use flood fill for potentially overlapping polys

    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.

    opened by jakobbotsch 14
  • NULL dereference crash in rcBuildContours()

    NULL dereference crash in rcBuildContours()

    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 image

    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.

    bug 
    opened by jackpoz 14
  • findNearestPoly fails to find anything despite being very close to the navmesh

    findNearestPoly fails to find anything despite being very close to the navmesh

    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): xV1trSZ 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.

    opened by TheSHEEEP 12
  • Debug draw duPolyToCol custom function

    Debug draw duPolyToCol custom function

    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.

    opened by domalb 12
  • Avoid reallocs of temp vectors

    Avoid reallocs of temp vectors

    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: Screenshot from 2021-01-24 02-17-47

    After: Screenshot from 2021-01-24 02-28-14

    /cc @elsid @psi29a

    opened by glebm 11
  • Fix macOS CMake SDL linking

    Fix macOS CMake SDL linking

    • Set the C++ language version correctly for each project (C++98 for everything but Tests which uses C++20)
    • Set SDL2_ROOT_DIR default on macOS to the RecastDemo/Bin/ folder to match where premake also expects SDL.
    • Added CI script for macOS CMake builds in both debug and release
    • Added the ./build cmake intermediate directory to .gitignore

    The issue here is that the FindSDL2.cmake script was trying to dissect SDL2.framework and treat it like a normal dylib library. Specifically, FindSDL2.cmake was causing CMake to just add -ISDL2.framework/Headers and link with the Mach-O dylib SDL2.framework/SDL.

    The include path is actually still necessary because we (probably incorrectly) include SDL headers in our code with #include "SDL.h" rather than the framework-prefixed #include <SDL2/SDL.h>. Framework-prefixed includes are the convention on macOS when including headers from a framework. Because of this the framework-prefixed version is what SDL uses internally when a header includes another header. The builds were failing because the include paths generated for the RecastDemo code that referenced SDL were valid, but the include paths weren't valid for SDL headers including other SDL headers.

    The proper clang flags that cmake should be passing are -F ./RecastDemo/Bin/ and -framework SDL2. CMake's find_library does the right thing if it finds a framework, but we were using find_package with this FindSDL2.cmake script which was preventing that from happening.

    This fix skips the FindSDL2.cmake script and just uses find_library directly, specifying SDL2_ROOT_DIR as an additional search path. The fix is limited to just Apple platforms, so other platforms continue to work as they have been.

    While fixing this I also noticed that the C++ language version wasn't being set correctly in the cmake scripts, so I've also fixed that.

    Fixes #577

    CMake 
    opened by grahamboree 0
  • CMake SDL2 include paths missing on macOS

    CMake SDL2 include paths missing on macOS

    Setup:

    m1 MacBook Pro macOS 13.0 SDL2.framework installed to /Library/Frameworks

    Repro:

    build with the following commands run from the root of a clean copy of the repo

    cmake -B ./build -DCMAKE_BUILD_TYPE=Debug
    cmake --build ./build --config Debug
    

    results in:

    ...
    [ 60%] Building CXX object RecastDemo/CMakeFiles/RecastDemo.dir/Source/ConvexVolumeTool.cpp.o
    In file included from /Users/grahampentheny/workspace/recastnavigation/RecastDemo/Source/ConvexVolumeTool.cpp:24:
    /Library/Frameworks/SDL2.framework/Headers/SDL.h:32:10: fatal error: 'SDL2/SDL_main.h' file not found
    #include <SDL2/SDL_main.h>
             ^~~~~~~~~~~~~~~~~
    1 error generated.
    make[2]: *** [RecastDemo/CMakeFiles/RecastDemo.dir/Source/ConvexVolumeTool.cpp.o] Error 1
    make[1]: *** [RecastDemo/CMakeFiles/RecastDemo.dir/all] Error 2
    make: *** [all] Error 2
    

    I suspect this line in RecastDemo/CMakeLists.txt is to blame, though I'm not sure how frameworks are handled by cmake.

    include_directories(Contrib/SDL/include)
    

    Fix Requirements:

    We ultimately need the cmake script to invoke clang with the -framework SDL2 and -I/Library/Frameworks/SDL2.framework/Headers options.

    It would also be nice to be able to specify the SDL framework path (via -F clang flag) so it's not just hardcoded to /Library/Frameworks. Specifying the framework path like this is useful for CI processes that might not want to or be able to muck about in /Library.

    CMake help wanted 
    opened by grahamboree 2
  • rcConfig Improvements

    rcConfig Improvements

    The values width and height are generally derived from other config values, but they're part of rcConfig which implies that they're meant to be user inputs to the rasterization process and should be set before creating the heightfield.

    When building using the solo mesh process, the values width and height are derived from cs and bmin/bmax using rcCalcGridSize.

    When building tile meshes, these values are simply defined as m_cfg.tileSize + m_cfg.borderSize*2.

    These should just be computed from the other config values at the point they're needed.

    Simple naming improvements

    height: this is the z-axis size of the rasterized area. In every other case "height" refers to the y axis (e.g. ch) so this should be changed to something like depth cs : rename to cellSize ch: rename to cellHeight

    🚨 These changes will create breaking API changes. We should be very deliberate about our release process for incorporating breaking API changes like this.

    enhancement 
    opened by grahamboree 0
  • pkg-config file is broken when CMAKE_INSTALL_{INCLUDE,LIB}DIR is absolute

    pkg-config file is broken when CMAKE_INSTALL_{INCLUDE,LIB}DIR is absolute

    As per title: CMakeLists.txt has

    set(prefix ${CMAKE_INSTALL_PREFIX})
    set(exec_prefix "\${prefix}")
    set(libdir "\${exec_prefix}/${CMAKE_INSTALL_LIBDIR}")
    set(bindir "\${exec_prefix}/${CMAKE_INSTALL_BINDIR}")
    set(includedir "\${prefix}/${CMAKE_INSTALL_INCLUDEDIR}")
    

    and so can’t handle absolute paths in CMAKE_INSTALL_{INCLUDE,LIB}DIR (whereas bindir is set but does not seem to be used anywhere?). This leads to broken .pc files on NixOS in particular.

    See “Concatenating paths when building pkg-config files” for a thorough discussion of the problem and a suggested fix, or KDE’s extra-cmake-modules for a simpler approach.

    (Pkg-config files seem to be installing fine for me, so I’d guess that means #472 is fixed?)

    bug CMake 
    opened by alexshpilkin 1
  • A small bug in DetourNavMeshQuery/findStraightPath

    A small bug in DetourNavMeshQuery/findStraightPath

    An extremely subtle problem I discovered while working with findStraightPath was that if 'portalApex', 'portalLeft', 'portalRight', and 'right' were on the same line, both two area calculations would be equal to zero, in this way, portalLeft will be added to the vertexList, but in reality this is incorrect. I solved the problem by changing > to >=. Is this correct? Will there be any new problems? thanks

    // Right vertex.
    if (dtTriArea2D(portalApex, portalRight, right) <= 0.0f)
    {
        if (dtVequal(portalApex, portalRight) || dtTriArea2D(portalApex, portalLeft, right) >= 0.0f) // Only change > to >=
        {
            dtVcopy(portalRight, right);
            rightPolyRef = (i+1 < pathSize) ? path[i+1] : 0;
            rightPolyType = toType;
            rightIndex = i;
        }
        else
        {
            // Append portals along the current straight path segment.
            if (options & (DT_STRAIGHTPATH_AREA_CROSSINGS | DT_STRAIGHTPATH_ALL_CROSSINGS))
            {
                stat = appendPortals(apexIndex, leftIndex, portalLeft, path, result, options);
                if (stat != DT_IN_PROGRESS)
                    return stat;
            }
    
            dtVcopy(portalApex, portalLeft);
            apexIndex = leftIndex;
    
            unsigned char flags = 0;
            if (!leftPolyRef)
                flags = DT_STRAIGHTPATH_END;
            else if (leftPolyType != DT_POLYTYPE_GROUND)
                flags = DT_STRAIGHTPATH_OFFMESH_CONNECTION;
            dtPolyRef ref = leftPolyRef;
    
            // Append or update vertex
            stat = appendVertex(portalApex, flags, ref, result);
            if (stat != DT_IN_PROGRESS)
                return stat;
    
            dtVcopy(portalLeft, portalApex);
            dtVcopy(portalRight, portalApex);
            leftIndex = apexIndex;
            rightIndex = apexIndex;
    
            // Restart
            i = apexIndex;
    
            continue;
        }
    }
    
    bug 
    opened by Aganhui 0
Releases(1.5.1)
  • 1.5.1(Feb 22, 2016)

    Patch release; one bug has been fixed, which would cause silent failure if too many nodes were requested and used in a dtNavMeshQuery.

    • #179: Fail when too many nodes are requested
    Source code(tar.gz)
    Source code(zip)
  • 1.5.0(Jan 24, 2016)

    This is the first release of the Recast and Detour libraries since August 2009, containing all fixes and enhancements made since then. As you can imagine, this includes a huge number of commits, so we will forego the list of changes for this release - future releases will contain at least a summary of changes.

    We have decided to use Semantic Versioning for version numbers from now onwards - beginning at 1.5.0 rather than 1.0.0 since the last old release on Google Code was 1.4.

    Source code(tar.gz)
    Source code(zip)
Owner
null
Episodic Transformer (E.T.) is a novel attention-based architecture for vision-and-language navigation.

Episodic Transformer (E.T.) is a novel attention-based architecture for vision-and-language navigation. E.T. is based on a multimodal transformer that encodes language inputs and the full episode history of visual observations and actions.

Alex Pashevich 61 Nov 17, 2022
Fast, Attemptable Route Planner for Navigation in Known and Unknown Environments

FAR Planner uses a dynamically updated visibility graph for fast replanning. The planner models the environment with polygons and builds a global visi

Fan Yang 334 Nov 25, 2022
Code for "Photometric Visual-Inertial Navigation with Uncertainty-Aware Ensembles" in TRO 2022

Ensemble Visual-Inertial Odometry (EnVIO) Authors : Jae Hyung Jung, Yeongkwon Choe, and Chan Gook Park 1. Overview This is a ROS package of Ensemble V

Jae Hyung Jung 91 Nov 18, 2022
An Efficient Implementation of Analytic Mesh Algorithm for 3D Iso-surface Extraction from Neural Networks

AnalyticMesh Analytic Marching is an exact meshing solution from neural networks. Compared to standard methods, it completely avoids geometric and top

Jiabao Lei 42 Nov 27, 2022
An Efficient Implementation of Analytic Mesh Algorithm for 3D Iso-surface Extraction from Neural Networks

AnalyticMesh Analytic Marching is an exact meshing solution from neural networks. Compared to standard methods, it completely avoids geometric and top

null 41 Sep 8, 2022
Swapping face using Face Mesh with TensorFlow Lite

demo.mp4 Aiine Transform (アイン変換) Swapping face using FaceMesh. (could be used to unveil masked faces) Tested Environment Computer Windows 10 (x64) + V

iwatake 17 Apr 26, 2022
RXMesh - A GPU Mesh Data Structure - SIGGRAPH 2021

RXMesh About RXMesh is a surface triangle mesh data structure and programming model for processing static meshes on the GPU. RXMesh aims at provides a

null 134 Nov 27, 2022
null 5.2k Nov 26, 2022
HMS Core Scene Kit Slim Mesh Demo sample code demonstrates how to invoke external interfaces of SlimMesh to perform mesh simplification.

HMS Core Scene Kit Slim Mesh Demo English | 中文 Table of Contents Introduction Environments Requirements Result License Introduction The Slim Mesh is a

HMS 8 Jul 28, 2022
DG-Mesh-Optimization - Discontinuous Galerkin (DG) solver coupled with a Quasi-Newton line-search algorithm to optimize the DG mesh.

Date written: December 2020 This project was pursued as my final project for MECH 579 (Multidisciplinary Design Optimization) at McGill University, ta

Julien Brillon 8 Sep 18, 2022
Rizin - UNIX-like reverse engineering framework and command-line toolset.

Rizin - UNIX-like reverse engineering framework and command-line toolset.

Rizin Organization 1.7k Nov 29, 2022
A program and toolset to analyze iDevice USB sessions

A program and toolset to analyze iDevice USB sessions

T2 Development Team 24 Nov 12, 2022
CMake module for building Windows Installer packages with WiX toolset

FindWiX CMake module for building Windows Installer packages with WiX toolset Introduction Requirements Usage find_package() wix_add_project() WiX com

Apriorit Inc. 11 Aug 5, 2022
Code and Data for our CVPR 2021 paper "Structured Scene Memory for Vision-Language Navigation"

SSM-VLN Code and Data for our CVPR 2021 paper "Structured Scene Memory for Vision-Language Navigation". Environment Installation Download Room-to-Room

hanqing 34 Aug 24, 2022
Episodic Transformer (E.T.) is a novel attention-based architecture for vision-and-language navigation.

Episodic Transformer (E.T.) is a novel attention-based architecture for vision-and-language navigation. E.T. is based on a multimodal transformer that encodes language inputs and the full episode history of visual observations and actions.

Alex Pashevich 61 Nov 17, 2022
A ROS robot supporting voice control, autonomous navigation and robot arm motion.

ROS Service Robot Project Due to the GitLab restrictions, only screenshot is displayed here. Warehouse Overview robot: The development source code is

SilenceJiang 53 Nov 22, 2022
Fast, Attemptable Route Planner for Navigation in Known and Unknown Environments

FAR Planner uses a dynamically updated visibility graph for fast replanning. The planner models the environment with polygons and builds a global visi

Fan Yang 334 Nov 25, 2022
A global planner plugin for ROS navigation stack, in which A* search on a discrete gneralized Voronoi diagram (GVD) is implemented.

voronoi_planner This repo contains a global planner plugin for ROS navigation stack, in which A* search on a discrete gneralized Voronoi diagram (GVD)

Jian Wen 16 Nov 1, 2022
A robot simulation that reads QR codes and uses it for navigation through a grid system.

PathingRobotSim This bad boy gonna read QR code to navigate through a grid system in a simulated enviroment. This is part of my Bachelor's conclusion

Renato Ferreira 2 Nov 17, 2021
An Open Source tripmaster for navigation rallies

Open Rally Computer An open source tripmaster for navigation rallies Description The Open Rally Computer (previously known as Baja Pro) is a complete

Matias Godoy 47 Sep 7, 2022