Coder Social home page Coder Social logo

recastnavigation / recastnavigation Goto Github PK

View Code? Open in Web Editor NEW
6.5K 385.0 1.6K 22.14 MB

Industry-standard navigation-mesh toolset for games

Home Page: http://recastnav.com/

License: zlib License

C++ 91.33% C 7.54% Lua 0.25% CMake 0.88%
ai crowd-simulation game-development navigation navmesh pathfinding game gamedev game-ai game-dev

recastnavigation's Introduction

Recast Navigation

State-of-the-art navmesh generation and navigation for games.

Recast Demo

πŸš€ Features

  • πŸ€– Automatic - Recast can generate a navmesh from any level geometry you throw at it
  • 🏎️ Fast - swift turnaround times for level designers
  • 🧘 Flexible - detailed customization options and modular design let you tailor functionality to your specific needs
  • 🚫 Dependency-Free - building Recast & Detour only requires a C++98-compliant compiler
  • πŸ’ͺ Industry Standard - Recast powers AI navigation features in Unity, Unreal, Godot, O3DE and countless AAA and indie games and engines

Recast Navigation is divided into multiple modules, each contained in its own folder:

  • Recast/ - Navmesh generation
  • Detour/ - Runtime loading of navmesh data, pathfinding, navmesh queries
  • DetourTileCache/ - Navmesh streaming. Useful for large levels and open-world games
  • DetourCrowd/ - Agent movement, collision avoidance, and crowd simulation
  • DebugUtils/ - API for drawing debug visualizations of navigation data and behavior
  • Tests/ - Unit tests
  • RecastDemo/ - Standalone, comprehensive demo app showcasing all aspects of Recast & Detour's functionality

⚑ Getting Started

Check out BuildingAndIntegrating.md for information on how to build the comprehensive RecastDemo project, as well as guidance on integrating Recast & Detour into your own project.

If you are new to Recast & Detour, check out Sample_SoloMesh.cpp in RecastDemo to get started with building navmeshes and NavMeshTesterTool.cpp for building paths with Detour.

βš™ How it Works

Recast constructs a navmesh through a multi-step mesh rasterization process.

  1. First Recast rasterizes the input triangle meshes into voxels.
  2. Voxels in areas where agents would not be able to move are filtered and removed.
  3. The walkable areas described by the voxel grid are then divided into sets of polygonal regions.
  4. The navigation polygons are generated by re-triangulating the generated polygonal regions into a navmesh.

You can use Recast to build a single navmesh, or a tiled navmesh. Single meshes are suitable for many simple, static cases and are easy to work with. Tiled navmeshes are more complex to work with but better support larger, more dynamic environments. Tiled meshes enable advance Detour features like re-baking, heirarchical path-planning, and navmesh data-streaming.

πŸ“š Documentation & Links

Official documentation is available at recastnav.com

Docs are generated via Doxygen from source file comments and from markdown files in the Docs/ directory.

❀ Community

Ask questions, voice ideas, or request new features over on Github Discussions or on our old Google Group list.

Check out the Development Roadmap to see what features and functionality you might be able to help with, and the Contribution Guidelines for information on how to make contributions.

Our Code of Conduct applies to all Recast Navigation community channels.

βš– License

Recast & Detour is licensed under the ZLib license. See License.txt for more.

recastnavigation's People

Contributors

andriydev avatar axelrodr avatar aymarfisherman avatar bitshifter avatar bromeon avatar dante-666 avatar darthgandalf avatar dpull avatar elsid avatar grahamboree avatar hgaiser avatar hymerman avatar illwieckz avatar jackpoz avatar jakobbotsch avatar jimmyjames707 avatar kromster80 avatar learko avatar mbabinski-at-google avatar memononen avatar mendsley avatar psi29a avatar richard-fine avatar roboschmied avatar sandern avatar someoneserge avatar spaceim avatar twoscomplement avatar wbierman avatar za139 avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

recastnavigation's Issues

Compilation Error in RecastDemo

When compiling with Ubuntu 14.04 (g++-4.8.2), compilation fails in RecastDemo/Source/CrowdTool.cpp

  • l.158: error: no matching function for call to β€˜dtCrowd::getEditableFilter()’
  • l.710: error: no matching function for call to β€˜dtCrowd::getFilter()’

Adding a parameter (0) to these function workaround the issue.

Prefer the area of clearly above span when merging spans

https://github.com/memononen/recastnavigation/blob/master/Recast/Source/RecastRasterization.cpp#L123-L131

// Prefer larger area type when almost parallel to aliasing, else choose top-most area.
if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr)
    s->area = rcMax(s->area, cur->area);
else if (cur->smax > s->smax)
    s->area = cur->area;

// Merge spans.
if (cur->smin < s->smin)
    s->smin = cur->smin;
if (cur->smax > s->smax)
    s->smax = cur->smax;

As per discussion in https://groups.google.com/forum/#!topic/recastnavigation/X5suWbWvutE

off mesh connection segments

one feature of http://www.navpower.com/ that I've used in the past that I'd love to see come to detour is the concept of off mesh connection segments.

In navpower, you could add links as lines from a start and end point. This was useful for representing the traversal of long obstacles or long straight segments of 'jump down' areas as a single link. This type of link consisted of a start line segment and end line segment, so the takeoff and land segments could be sized differently.

From the search perspective it was a very simple traversal mechanism iirc where the ratio that was entered along the entry segment was also the ratio along the destination edge, and I think the entry segment was just the nearest point on the segment from the parent node before.

Missing error handling on allocation failure

In RecastRasterization.cpp the function addSpan does not handle the case when allocSpan returns nullptr. It does so when no memory rcAlloc fails.

This results in a crash on the following line in addSpan.

The addSpan function should probably have a return value to signal allocation failure to callers.

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.

dynamic off mesh links

As someone who has used Navpower in the past and some other pathing middleware libraries, one of the things that still bothers me a bit about the off mesh connections in detour are the fact that they are static and one must rebuild one or more tiles in order to add or remove links. I would love to see that functionality refactored so that links can be added and removed at runtime with out rebuilding tiles.

Implement DT_FINDPATH_LOW_QUALITY_FAR option.

#109 removed the flag from the dtFindPathOptions enum, however @jackpoz pointed out that the flag was indeed something we want, but it just hasn't been implemented yet.

The description from #109 is "trade quality for performance far from the origin. The idea is that by then a new query will be issued". Maybe someone who knows more about how this should work can add some more descriptive details here?

As a first step, you'll want to revert 43a20cc

Wrong detail mesh sampling with layer partitioning

The following case happens in the default nav_test.obj with Max Climb = 1.6 and Partitioning = Layers:
bad sampling
This only affects the detail mesh; the regular poly mesh does not have the problem.
However, the problem originates in rcBuildPolyMesh, not rcBuildPolyMeshDetail. These
are the regions created beforehand:
bad sampling regions
And this is the poly mesh:
bad sampling polys
The problem is that all polys in the poly mesh have the same region ID, even though the
compact heightfield has two different regions here. This causes the detail sampling
to sample the wrong height.

It appears the region ID of the stair-poly disappears when one of the border vertices are
removed during the build of the poly mesh. The vertex is removed, and when the hole
created is later converted to a polygon again, the wrong region ID is used.
I haven't been able to debug it any further - I got kind of stuck in the hole triangulation. πŸ˜„

dtNavMeshQuery::findPath might not always generate the shortest path

Question about the termination condition of the findPath function.

if (bestNode->id == endRef)
{
    lastBestNode = bestNode;
    break;
}

Isn't it possible in certain circumstances that the first node to reach the end area ref might not be the shortest path by virtue of that nodes distance to the endPos not having been accounted for?

Raycast Crash

DetourNavMeshQuery.cpp:2429

hit->path[n++] = curRef;

Any idea why this is happening?

Compilation error in RecastDemo: multiple BuildContext

multiple definition of `BuildContext::~BuildContext()':

Linking executable: ....\Bin\RecastDemo.exe
lib\Debug/libDetourTileCache.a(DetourTileCache.o):DetourTileCache.cpp:(.text$_ZN12BuildContextD1Ev[BuildContext::~BuildContext()]+0x0): multiple definition of `BuildContext::~BuildContext()'
obj\Debug\RecastDemo\Source\SampleInterfaces.o:RecastDemo/Source/SampleInterfaces.cpp:26: first defined here
using master branch.

Indeed BuildContext is declared twice;

  • once in the lib DetourCacheTile
  • once in SampleInterfaces.cpp/h

Example of solution: rename BuildContext struct in the DetourCacheTile lib by dtcDetourCacheTile or use a namespace.

Contributor License Agreement

This is just a discussion that may lead to adding a CLA to the project. I'm splitting it out from #123 to make it easier to keep track of.

Here's what has been said so far:

@hymerman

I think we also need a Contributor License Agreement - having been on the other side of the fence I know the legal protection is more than superficial! Either CLAHub (https://www.clahub.com/) or CLA assistant (https://cla-assistant.io/) look like good options to get this done easily.

Next I'd love to get Continuous Integration set up - I've actually already got a pull request open for this :) (#89). I see you've got a really nice AppVeyor setup in your fork, @rwindegger - let's get that merged in if it's easy to separate from the other things merged into your fork, and we'll use my Travis setup. I updated to premake5, and I see you've updated the way lots of dependencies work with submodules, which is also cool.

One more thing, I've just bought recastnavigation.com just in case we want to do something with it - perhaps to host documentation, or just for project-specific email. So nobody freak out if you notice it's not available :)

@dougbinks

I had a discussion with @memononen about the CLAs @hymerman recommended: https://twitter.com/dougbinks/status/674544666264539136, and he asked me to post my points here.

Basically most CLAs are complex enough to require a lawyer to understand the implications, in particular whether there is any potential liability exposure for the contributor. These issues tend to be more complex than they appear. For example guaranteeing that something is your original creation means you could be exposed to liability if someone later claims your code is a copy of theirs; litigation defence in some regions is extremely expensive.

In my view Apache 2.0 covers the main issue many companies have - a guarantee that a contributor won't sue for patent infringement for use of their contribution. This seems reasonable and fair, and doesn't expose the contributor to needing to guarantee that they own the patent rights nor infringe others. Going Apache 2.0 would need all prior contributors to agree, or a dual license. But then adding a CLA won't protect the current code either without getting all prior contributors to sign.

Note that I'm not a lawyer, but that's the real problem here - putting a legal barrier in place really requires people to have or be one.

Spherical navmesh

Hi!
Has recast/detour this feature for generating planet navmesh for implementing in blender game engine. blenderartis forum members said No!
They suggest node pathfinding as a solution.
But spherical navmesh can solve some challenges.

[Question] Are you open to flags and area id being typedef-ed?

In some uses I have wanted to support more flags / areas than are supported with the variable size for area ID or flags. In my local copy in these cases I have changed flags and area to be typedef-ed types of dtFlags and dtArea.

Locally I am on an older version of recast, and I'd love to update to master, and I am wondering if I were to make these changes on a more recent version if you would be open to accepting that change if I were to create a pull request? While I think keeping them the same size by default makes sense (smaller is better), having them be defined as a typedef makes changing them if one wishes to for a project trivial, vs the current scattered instances of unsigned short etc..

The only place I had to make any significant changes to allow this was in dtPoly where being able to resize the area variable size meant I could not pack the type and area in the variable areaAndType. Locally I just store them separately, though there may be a better way.

Upgrade to SDL 2.0

There's currently issues in SDL 1.2 preventing it from linking with RecastDemo when using Visual Studio 2015. Given this, it's probably time to upgrade to 2.0. There shouldn't be a whole lot of issues in the process, as RecastDemo mostly just relies on it for input events and creating a window with a gl context.

Off-mesh connection links not removed between layers in the same tile location

I've been running into some crashes during path finding and after some digging I found some of my tiles ended up with invalid links. This happens when neighboring tiles in the same layer were rebuild, but only for tiles with off-mesh connections between them.

Looking in unconnectExtLinks I found the following check:

            if (tile->links[j].side != 0xff &&
                decodePolyIdTile(tile->links[j].ref) == targetNum)

side only seems to be set to 0xff when off-mesh connections are created between tiles in the same layer.

It seems neighboring tiles in the same layer are skipped when removing links. Is there any reason for doing so? I removed the check from my code and don't see any side effects.

findNearestPoly may return wrong results

if you pass in the same position pointer for your 'center' parameter as you do the nearestPt 'out' parameter, you will likely get bad results for nearest polygon because the distance metrics while searching for polygons will change since each iteration where a potential result is found will modify the data pointer to by center as well.

recommend using a temporary inside the function and copying the results at the end to allow the same object to be passed in for both.

dtStatus findNearestPoly(const float* center, const float* extents,
                             const dtQueryFilter* filter,
                             dtPolyRef* nearestRef, float* nearestPt) const;

Unit Testing

We've talked about adding unit tests to some core components of the project. I thought I'd open a thread to discuss what areas should be prioritized for unit testing and what framework we should use.

Which framework should we use?
Personally, my experiences unit testing C++ haven't been as smooth as in other environments, though it's certainly better than nothing. I've enjoyed using Catch for other projects, as it's lightweight, straightforward, and easy to integrate and work with. Google Test is another reasonable alternative, but it's probably a bit too heavy handed for what we'd need. There are tons of other options as well. Wikipedia has a huge list of C++ unit testing frameworks.

Where do the tests live?
The tests should not interfere at all with the actual library code or the current integration process. This probably means that they should probably be in a location that is completely separate from the codebase so that integration doesn't involve a "remove the tests" step.

The tests should be easy to write and run. This is important in encouraging test creation and maintenance. If the unit test suite is hard to run, they'll be ignored. This assertion is subservient to the current codebase's integration experience. When in doubt, it's better to make the unit testing experience more tedious if in doing so, the experience of using using recast is maintained or improved.

What should we be testing (first)?

A few parts of the codebase are pretty straightforward to test, and would benefit from knowing they're a solid foundation. In particular the majority of geometry and math helper functions are already pure, making testing them trivial. e.g. distancePtSeg, dividePoly, etc...

There are also a lot of small helper functions like insertSortthat are pretty easy to test.

Beyond that, it starts getting into low-level recast functions, which are definitely testable, but might require a bit more domain-knowledge.

Temporary Obstacles of arbitrary geometry in Detour

Hello,
I have been trying to implement the TileCache functionality in a project that does not use layered tiles, but the objects that I need to input into the mesh can have any geometry (read at runtime), from what I can see Detour only allows for cylindrical obscales, I read about a patch in the google group but it apparently doesn't erode the obstacle polygons by the agent radius, is there any way to achieve this?

Another question I've been concerned about lately is if TileCache will indeed suit my needs as my obstacles will be added / removed from several tiles several times per second, is TileCache really what I need or are there other alternatives better suited for this task?
Thank you very much,

Sorry if this wasn't the right place to ask these questions.

feature req: dtNavMeshQuery::findPathToNearest

Would be very useful to have a function that takes an arbitrary number of positions and poly refs and finds runs a Dijkstra to find the nearest one.

As a bonus, would also be very useful if this function or a variation of this function can generate complete solutions to every destination requested, in order to avoid doing multiple searches when you want to get path distance estimates to many different goals.

No guard on dtCrowd::getAgent

getAgent doesn't have a guard on it, while the other functions that address agents do.

const dtCrowdAgent* dtCrowd::getAgent(const int idx)
{
return &m_agents[idx];
}

void dtCrowd::updateAgentParameters(const int idx, const dtCrowdAgentParams* params)
{
if (idx < 0 || idx >= m_maxAgents)
return;
memcpy(&m_agents[idx].params, params, sizeof(dtCrowdAgentParams));
}

Issue tagging

I noticed @grahamboree started tagging some issues as bugs - which is cool because it's something I was going to suggest! Should we pick a nice common set of tags to standardise on?

There are loads of articles about issue tagging best practices:

I don't think we need to go quite as far as they do (I don't think functional areas or the milestones feature are useful for us, for example) but it would be nice to have some of it. At least category (bug/feature/discussion etc), and perhaps a status (resolved/wontfix etc). Thoughts?

NULL dereference crash in rcBuildContours()

I got a NULL dereference crash in mergeRegionHoles() called by rcBuildContours() using revision eacaa87

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 a89bb84 .
I can reproduce the bug and I'm available to test any crashfix.

Determining off mesh directionality

In dtNavMeshQuery where it determines the right and left poly type I want to determine the directionality of the off mesh link if it's big directional so that I can handle it differently in my custom off mesh code. The problem is that there doesn't appear to be a good way to determine directionality within this function.

I tried to copy the mechanism that dtNavMesh::getOffMeshConnectionEndPoint uses, but it's not working consistently.

Bug in dtNavMeshQuery::moveAlongSurface

In our game we use moveAlongSurface for most of our entity movements, which works well in most situations. The fact that it uses the closest point to the destination works very well for us in allowing us to 'slide' along a wall of the nav mesh as long as the inputted movement is on a angle to the wall.

However, I had a few bug reports from people saying occasionally (pretty rare in our game) there would be a section of the map which they could not slide along the edge. They would be stuck in the same location as long as there was any delta off the wall edge. After some extensive debugging I have found what seems to be happening, and have a fix for the scenario, but I wanted to first discuss to make sure what I am seeing is correct.

At a high level what seems to be happening is that not all edges that need to be checked for closest points are being checked. Specifically on tile boundaries. When the edge is a tile border (found with DT_EXT_LINK) the linked poly ref gets added, but the edge is not checked for distance. While this makes sense for internal edges (as they will always have a poly on the other side which shares that edge completely) on tile boundaries it does not seem to be the case. I am seeing a tile boundary edge that links to a poly in the adjacent tile with an edge not covering the full span of the source edge. (say the source edge is 100 units, the shared edge in another tile is for example only 50). As the source edge is not checked against for nearest distance, and the full length of the edge does not exist in the adjacent tile, there is a portion of a wall which is never checked against. In the case where that portion is where the closest point would lie, I am instead getting a result of the closest point is the origin point, and thus the player can not move.

When i change the function to also check for nearest distance on tile boundary edges, everything works as expected and it finds the correct closest point.

I'll happily create a pull request with the changes I have done to resolve this scenario, but I wanted to first make sure that its a valid scenario to have a tile boundary edge not fully shared by their linked poly in another tile. If this is normal then I suspect there may be other rare cases where similar errors could be hit such as in dtNavMeshQuery::findDistanceToWall where tile border edges are not considered walls if they link to an adjacent tile's poly. If the adjacent tile's poly only partially covers the edge, then a portion of that edge should be considered a 'wall'.

I've attached a marked up screenshot illustrating the situation (which i used to debug my issue once i found a repo case). The dashed orange line shows where a tile boundary is. The small red line inside the red circle is the startPos to endPos (the res circle being the searchPos and searchRad as determined in moveAlongSurface): Player starting on the poly vertex, and trying to move down left (which is expected to slide downwards along that vertical wall). The pink line (under the orange dotted one) highlights the boundary edge of the origin poly which is NOT checked for closest distance. Please note the poly which that boundy edge links to on the left side of the orange line shares only a portion of the edge.

detourbug

Bryan McConkey

Crash caused by modulo zero

In DetourNavMeshQuery.cpp function getPortalPoints line 2216:

const int v1 = fromPoly->verts[(link->edge+1) % (int)fromPoly->vertCount];

my program crashed because the value of fromPoly->vertCount is zero:

Program terminated with signal 8, Arithmetic exception.
#0  0x00007f6a460f8c7b in dtNavMeshQuery::getPortalPoints (this=0x7f6a2b246de0, from=4414683, fromPoly=0x7886660,
    fromTile=0x7f6a2b1e2518, to=8608777, toPoly=0x7884c20, toTile=0x7f6a2b1e2518, left=0x7f6a49580460,
    right=0x7f6a49580450) at /home/recode/recode_systems/src/navigation/Detour/Source/DetourNavMeshQuery.cpp:2216

It is called by getEdgeMidPoint and this is called by findPath.

findPath is passing the parameter "bestPoly" as "fromPoly" to getEdgeMidPoint. bestPoly->vertCount is zero.

The issue seems to be that the navmesh generation build a mesh that contains polygons with size zero.

I just have the core dump, but if you need further information please ask.

Moving multiple agents in CrowdToolState::setMoveTarget broken

Something doesn't look right in this code. I know its just for the demo, but in

void CrowdToolState::setMoveTarget(const float* p, bool adjust)

At this line:

const dtQueryFilter* filter = crowd->getFilter(0);

You negate the purpose of each agent having a queryFilterType, when m_agentDebug.idx != -1

So I'd suggest something along these lines:

void CrowdToolState::setMoveTarget(const float* p, bool adjust)
{
    if (!m_sample) return;

    // Find nearest point on navmesh and set move request to that location.
    dtNavMeshQuery* navquery = m_sample->getNavMeshQuery();
    dtCrowd* crowd = m_sample->getCrowd();
    const float* ext = crowd->getQueryExtents();

    if (adjust)
    {
        float vel[3];
        // Request velocity
        if (m_agentDebug.idx != -1)
        {
            const dtCrowdAgent* ag = crowd->getAgent(m_agentDebug.idx);
            if (ag && ag->active)
            {
                calcVel(vel, ag->npos, p, ag->params.maxSpeed);
                crowd->requestMoveVelocity(m_agentDebug.idx, vel);
            }
        }
        else
        {
            for (int i = 0; i < crowd->getAgentCount(); ++i)
            {
                const dtCrowdAgent* ag = crowd->getAgent(i);
                if (!ag->active) continue;
                calcVel(vel, ag->npos, p, ag->params.maxSpeed);
                crowd->requestMoveVelocity(i, vel);
            }
        }
    }
    else
    {       
        if (m_agentDebug.idx != -1)
        {
            const dtCrowdAgent* ag = crowd->getAgent(m_agentDebug.idx);
            if (ag && ag->active)
            {
                const dtQueryFilter* filter = crowd->getFilter(ag->params.queryFilterType);
                navquery->findNearestPoly(p, ext, filter, &m_targetRef, m_targetPos);
                crowd->requestMoveTarget(m_agentDebug.idx, m_targetRef, m_targetPos);
            }
        }
        else
        {
            const dtQueryFilter* filter = crowd->getFilter(0);
            navquery->findNearestPoly(p, ext, filter, &m_targetRef, m_targetPos);

            for (int i = 0; i < crowd->getAgentCount(); ++i)
            {
                const dtCrowdAgent* ag = crowd->getAgent(i);
                if (!ag->active) continue;
                crowd->requestMoveTarget(i, m_targetRef, m_targetPos);
            }
        }
    }
}

Wrong mesh when building from a scen that has a big y range

Follow this you will get the same result

  1. Compile the demo
  2. edit Bin\Meshes\Dungeon.obj, add a triangle with very low y value at the end, as below:
    v 324 -2000 378
    v 319 -2000 233
    v 310 -2000 81
    f -1 -2 -3
  3. Save the .obj file and run Recast.exe
  4. Choose Sample_TiledMesh and load this .obj file
  5. Build the mesh

The navmesh of the origional dungeon will be in a plane below the real model.

error

off-mesh connections only make link with neighbors in tiled mesh.

if off-mesh start-point end-point in different tile,
and the tiles are not neighbors,
the off-mesh connection does not work.
(start-point is correct, end-point is drawn in red circle )

in dtNavMesh::addTile
// Connect with neighbour tiles.
connectExtOffMeshLinks

in DetourDebugDraw.drawMeshTile
endSet is false

rcTriangleMesh Enhancement

Hello everyone, I'm proposing an enhancement to simplify usage of Recast. A rcTriangleMesh object. This object would hold the Vertices, NumVertices, Triangles, NumTriangles and any other related data which could then be passed to any Recast functions that require the data, such as rcMarkWalkableTriangles and rcRasterizeTriangles. The data would be added into the object simply by calling a method such as "void AddTriangle()" which you would then pass the three vertices that make up the triangle.

rcTriangleMesh tMesh;
tMesh.AddTriangle(0,1,0,
    -1,0,0,
    0,0,-1);

This would reduce a lot of code and complexity for beginners moving Recast towards your goal of it "just working out of the box" allowing easy iterate through mesh buffers etc.

Thank you very much for your time. I can elaborate more if needed.

findNearestPoly should handle > 128 polygons

findNearestPoly currently uses an internal buffer size of 128 polygons. When this is not enough, it still succeeds silently without any indication of an error occurring.

I want to submit a PR to fix this, but I am not sure of the best way to indicate this error. findNearestPoly can be changed to return DT_FAILURE | DT_INVALID_PARAM immediately after queryPolygons indicates that the buffer was too small; this, however, is a breaking change.

Another option could be to return DT_SUCCESS | DT_INVALID_PARAM or DT_SUCCESS | DT_BUFFER_TOO_SMALL, and still find the nearest poly among the polygons returned by queryPolygons. This would not be a breaking change.

Which solution do you think would be the best?

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.

Found a heap corrupting bug in RecastLayers.cpp

Hey,

I had some hours of fun right now because of a heap corruption. Those are always a bitch to track, but I managed with DUMA ( duma.sourceforge.net/ ).

I noticed the error in these lines in RecastLayers.cpp (lines 315 - 322):

                        const int nneis = (int)reg.nneis;
            for (int j = 0; j < nneis; ++j)
            {
                const unsigned char nei = reg.neis[j];
                rcLayerRegion& regn = regs[nei];
                // Skip already visited.
                if (regn.layerId != 0xff)
                    continue;

The problem is that nneis can happen to be larger than RC_MAX_NEIS. In my case, nneis was 21 (while the default max is 16), so it was crashing when j became 17 (funny enough, j=16 worked, pure luck IMO).

My fix was to simply increase RC_MAX_NEIS to 32, and it works for now, but that likely does not solve the problem.

No idea how, where or why nneis is set to a number higher than RC_MAX_NEIS, but I just don't have the time to dig into this right now. Just wanted to let you know.

ios crash use recastnavigation

I try to use recastnavigation in IOS devices
When while accessing const void method() const will crash
But andorid and windows will not appear.

Timing code in the library

I noticed there is code to time the navmesh building process inside some library calls. I was thinking this would not be desirable, if the navmesh is being built dynamically during a game.

Temporary obstacles not working under some circumstances?

I had a look at the demo on how to add a temporary obstacle:

m_tileCache->addObstacle(p, radius, height, 0);
m_tileCache->update(timePassed, m_navMesh);

// Call functions to redraw the navmesh

This is exactly what I do in my own DetourTileCache. The navmesh itself is looking good. But there is no hole in the navmesh where I put the obstacle.

I thought at first the cylinder was at a wrong position or something like that, but if I understand it correctly when this line (1999, DetourTileCacheBuilder.cpp) in dtMarkCylinderArea is reached, the area is marked as unwalkable:

layer.areas[x+z*w] = areaId;   // with areaId = 0, which means unwalkable

And when stepping through the code at runtime, that line is indeed reached multiple times, so it does mark some areas as unwalkable, as it should!

However, when displaying the navmesh, no hole is shown. I always redraw the complete navmesh (performance waste, I know), so it is not possible that some old mesh is being displayed.

When I modify the input geometry for the affected tile with a cylinder mesh of the same dimensions as the obstacle, and then rebuild the entire tile, a hole is displayed just fine. But that also takes much longer than the temp obstacles should.

My only guess is that there must be some bug that leads to temp obstacles not creating actual holes in the navmesh under some circumstances.

Limit agent maximum rotation rate

Hello !

First of all, I'm super happy that you guys took the reins of the further development of recast :)
Since you are gathering ideas for new features this is my propose: new types of agent position intergration.

Right now it uses simple velocity blending. My suggestion is to add some switch in there:

static void integrate(dtCrowdAgent* ag, const float dt)
{
    // Fake dynamic constraint.
    const float maxDelta = ag->params.maxAcceleration * dt;
    float dv[3];
    dtVsub(dv, ag->nvel, ag->vel);
    float ds = dtVlen(dv);
    if (ds > maxDelta)
        dtVscale(dv, dv, maxDelta/ds);
    dtVadd(ag->vel, ag->vel, dv);

    // Integrate
    if (dtVlen(ag->vel) > 0.0001f)
        dtVmad(ag->npos, ag->npos, ag->vel, dt);
    else
        dtVset(ag->vel,0,0,0);
}

https://github.com/recastnavigation/recastnavigation/blob/master/DetourCrowd/Source/DetourCrowd.cpp#L59-L75

    // ...
    dtVsub(dv, ag->nvel, ag->vel);
    float ds = dtVlen(dv);
    if (ds > maxDelta)
        dtVscale(dv, dv, maxDelta/ds);

    switch( ag->params.integrationType )
    {
    case AGENT_POSITION_BLEND:
        dtVadd(ag->vel, ag->vel, dv);
        break;
    case AGENT_POSITION_ROTATE:
        // new implementation here, ag->params.maxAngularRotate
        break;
    // and so on ...
    }

    // ...

*) Naming is just quick guess

By rotate I mean angular constrain for agent. Sometimes, when agent has low velocity and then takes quick turn back, vectors are just blended and there is a place when agent rotates super fast that breaks any natural motion behaviors and there must be some supperior system to control it (this is how I had to did it). This is simple limited rotator integrator:

const Vec3& CVectorRotator::Integrate( const Vec3& target, float dt )
{
    if( false == enable )
    {
        currentVector = target;
        return currentVector;
    }

    // Calc vector length
    const float length2DSq = target.x*target.x + target.z*target.z;

    float lengthScale = 1.0f;

    // If length is somehow significant
    if( length2DSq > lengthTreshold )
    {
        const float targetAngle = GetAngle( target );

        // Distance between two angles
        const float diff = Abs( AngleDiff( targetAngle, currentAngle ) ); 
        const float angleSpeed = Max( diff / dt , 0.001f );

        // If angular speed is too much
        if( angleSpeed > maxAngularRotate )
        {
            // Get max blend 
            const float coef = Clamp( maxAngularRotate / angleSpeed , 0.0f, 0.5f );

            currentAngle = MixRad( currentAngle, targetAngle, coef );

            // lengthScale = Min( coef * speedReduction , 1.0f );
        }
        else
        {
            currentAngle = targetAngle;
        }

        currentVectorNorm.x = cosf( currentAngle );
        currentVectorNorm.z = sinf( currentAngle );

    }

    currentVector = currentVectorNorm * (sqrtf( length2DSq ) * lengthScale);

    return currentVector;
}

Those are just proporsals. What do You think about this kind of change ? It would require to add some enum and additional params in agent param struct.

support for larger index ranges

Tile indices and vertex indices are currently limited based on the width of bits available to represent them. Please add support(through conditional compilation?) to compile and use recast/detour with 64 bit values that would greatly expand the supported range of tiles and vertices.

Continuous Integration

We should absolutely get some kind of CI set up! Let's talk about how we should go about doing this. This conversation is split out from #123, here's what's previously been said:

@hymerman

Next I'd love to get Continuous Integration set up - I've actually already got a pull request open for this :) (#89). I see you've got a really nice AppVeyor setup in your fork, @rwindegger - let's get that merged in if it's easy to separate from the other things merged into your fork, and we'll use my Travis setup. I updated to premake5, and I see you've updated the way lots of dependencies work with submodules, which is also cool.

@rwindegger

The CI should be easy to port over, I've uploaded VS Solutions to the repo, I should have adjusted the premake file.

Most of the Submodule stuff I did is for the dependencies of the Demo. The rendering of the UI was completly adjusted to use https://github.com/ocornut/imgui. I've updated to SDL2 instead of SDL. And did a gh-pages push for the doxygen documentation. FastLZ is pulled in from https://github.com/ariya/FastLZ and stb is pulled in from https://github.com/nothings/stb.

All in all the Demo changes will be a fast port too. Just need to do it a little more structured than i did it in the first place.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    πŸ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❀️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.