robmaister / sharpnav Goto Github PK

Hi,

I'm looking to load a file to Sharnav, but the demo project keep crashing at parsing the file.
I have tryed do modify the way it parses, but no lock with it, It still crashes when drawing the triangles.

obj file :
https://mega.co.nz/#!HdZDnBKB!bqMTKoxDiy9TLZIT8y8Prt3v-hXPQjdL8evQjRTqdzg

Consider a situation: a bot wants to move away (or step back) from a dangerous place. He knows that he should go somewhere back but no exact point is specified. The task is not about reaching a target but about finding a walkable path to approximately desired direction. We can't just search for random points behind the bot because path to those points actually can lead through the point that the bot wants to avoid. Can you implement something that will help in such scenarios?

I think it's related to #15 but still not duplicate because there could be a better way than just checking many many directions with Raycast method.

Are you going to add the possibility to use multiple obj models as a "Compouned Mesh" or somehow? I also need the possibility to specify position, rotation and scale when adding meshes to it.

        for (int i = 0; i < 10; i++)
        {

            SVector3 startPt = new Vector3();
            int startRef = 0;
            while (!navMeshQuery.FindRandomPoint(ref startRef, ref startPt))
                Debug.WriteLine("Can't find random point");

            SVector3 endPt = new Vector3();
            int endRef = 0;

            while (!navMeshQuery.FindRandomPoint(ref endRef, ref endPt))
                Debug.WriteLine("Can't find random point");


            Debug.WriteLine("Testing finding path from " + startPt + " (" + startRef + ") to " + endPt + " (" + endRef + ")");
        }

Outputs:
Testing finding path from (-5,907467; 12,95738; 68,52042) (424) to (-5,907467; 12,95738; 68,52042) (424)
Testing finding path from (44,68903; 10,97468; 38,93972) (415) to (44,68903; 10,97468; 38,93972) (415)
Testing finding path from (44,68903; 10,97468; 38,93972) (415) to (44,68903; 10,97468; 38,93972) (415)
Testing finding path from (44,68903; 10,97468; 38,93972) (415) to (44,68903; 10,97468; 38,93972) (415)...

If I use different instances:

    for (int i = 0; i < 10; i++)
    {
            var navMeshQuery = new NavMeshQuery(_tiledNavMesh, 2048);

            SVector3 startPt = new Vector3();
            int startRef = 0;
            while (!navMeshQuery.FindRandomPoint(ref startRef, ref startPt))
                Debug.WriteLine("Can't find random point");

            navMeshQuery = new NavMeshQuery(_tiledNavMesh, 2048);

            SVector3 endPt = new Vector3();
            int endRef = 0;

            while (!navMeshQuery.FindRandomPoint(ref endRef, ref endPt))
                Debug.WriteLine("Can't find random point");


            Debug.WriteLine("Testing finding path from " + startPt + " (" + startRef + ") to " + endPt + " (" + endRef + ")");
        }

Testing finding path from (59,62428; 10,5812; 48,15485) (411) to (59,62428; 10,5812; 48,15485) (411)
Testing finding path from (59,62428; 10,5812; 48,15485) (411) to (59,62428; 10,5812; 48,15485) (411)
Testing finding path from (59,62428; 10,5812; 48,15485) (411) to (59,62428; 10,5812; 48,15485) (411)
Testing finding path from (59,62428; 10,5812; 48,15485) (411) to (59,62428; 10,5812; 48,15485) (411)
Testing finding path from (4,317558; 10,78998; 4,080609) (294) to (4,317558; 10,78998; 4,080609) (294)
Testing finding path from (4,317558; 10,78998; 4,080609) (294) to (4,317558; 10,78998; 4,080609) (294)
Testing finding path from (4,317558; 10,78998; 4,080609) (294) to (4,317558; 10,78998; 4,080609) (294)
...

You shouldn't create new Random object in every call because it uses Environment.TickCount seed.

Some models cause this: http://c2n.me/3BTyeGd.png

I'll email you the obj file.

We use the latest version from master.

How do you load Collada data and generate a Mesh?

Can you add
Q to zoom in
Z to zoom out

Shift+Q to zoom in faster
Shift+Z to zoom out faster

Shift+Z to move forward faster
Shift+S to move down faster
Shift+A to move left faster
Shift+D to move right faster.

Some calls to those can return false periodically while others work for the same navmesh. This depends on Random.Next value I think.

The type or namespace name 'Tasks' does not exist in the namespace 'System.Threading'.
File: Source\SharpNav\Heightfield.cs line 6

The type or namespace name 'Tasks' does not exist in the namespace 'System.Threading'.
File: Source\SharpNav\Heightfield.Rasterization.cs line 6

The type or namespace name 'Tuple<,>' could not be found.
File: Source\SharpNav\AreaGenerator.cs line 28

I created a test, where an agent has to travel over an OffMeshConnection in order to reach the goal, but a path cannot be calculated to the goal.
I think no link between the OffMesh polygon and the destination polygon is created when the BoundarySide of the OffMeshConnection is Internal.

Does this fully support the OBJ specification?
I tried custom meshes (instead of the recast sample) and they don't load.

Is there a possibility to perform something like navmesh raycasting in Unity?

If I wanted to offset the path from obstacles / edges, what would be the easiest way to accomplish it?

Any help with this would be greatly appreciated. Also, it might be helpful to put up a developers forum to encourage end-users to help each other via samples and other potentially helpful resources.

Thanks.

The readme.md contains a link https://github.com/Robmaister/SharpNav/tree/master/Examples
This page does not exists (404). I'm guessing it should be https://github.com/Robmaister/SharpNav/tree/master/Source/SharpNav.Examples

A mesh with 524,000 triangles used up 2.6GB of ram to generate.

Same mesh in recastnavigation never went above 80mb ram usage.

I was using basically the same code on the front wiki page, starting with my own array of triangles and then calling TriangleEnumerable.FromTriangle, etc..

Navmesh.Generate is where it blew up the memory.

I've just started with SharpNav and hit either a misconfiguration or issue.

I've got a 2D map consisting of 2400+ triangles after conversion to SharpNav. The bounding area for it is { Min : (-100, -100, -100), Max : (169732.2, 144519.6, 101) }.

When I attempt to generate the navigation mesh, the PolyMesh doesn't have any polygons or vertices. I'm not really certain of the best way to determine the settings I should use or how to properly implement SharpNav for only a 2D environment.

Could you provide some insight into both properly implementing SharpNav for 2D environments as well as how to deal with different units of measure with the settings?

BTW, Thanks for providing such an awesome project. I'm extremely excited to get going with it.

Your ObjLoader misses some important features like combining models and import-flipping so we use own model loader http://pastebin.com/pd5xjc6L

This throws IndexOufOfRangeException:

var parameters = NavMeshGenerationSettings.Default;
parameters.AgentHeight = 2.0;
parameters.AgentWidth = 1;
parameters.MaxClimb = 0.2f;
SharpNav.NavMesh.Generate(TriangleEnumerable.FromTriangle(level.GetTriangles(), 0, level.GetTriangles().Length), parameters);

Obj: https://www.dropbox.com/s/jymf3n0oqwfhidr/Fighting_scene_navmesh.obj?dl=0

It worked with old SharpNav API: http://pastebin.com/yYWL3Xxp

Comment if you're interested in seeing an integration for any of these engines (or suggest a new one):

• XNA
• SlimDX
• Paradox
• WaveEngine

Also if you'd like to see better integration (asset pipeline, etc):

• MonoGame

If you are going to submit a pull request with engine integration, please reference this issue. This should be considered an ongoing issue.

When a new target is requested via RequestMoveTarget on the agent and the given target is on the same polygon of the navmesh as the agent, then the agent does not move.

Now I'm trying random points in a cycle until I find any for which I can calculate a path but could you have any better solution? This is required for patrol AI where NPC choose a random point on map and walk there. I also need a variation of this to walk to a random point within range.

I sent the obj file by mail.

It would be nice to pull this straight from nuget. Lib looks cool!

Sometimes it throws

FindRandomPointAroundCircle problem: System.IndexOutOfRangeException: Index was outside the bounds of the array.
at SharpNav.Pathfinding.PathfindingCommon.RandomPointInConvexPoly(Vector3[] pts, Int32 npts, Single[] areas, Single s, Single t, Vector3& pt) in D:\Dropbox\DotNet Resources\SharpNav\Source\SharpNav\Pathfinding\PathfindingCommon.cs:line 45
at SharpNav.NavMeshQuery.FindRandomPointOnPoly(MeshTile tile, Poly poly, PolyId polyRef, Vector3& randomPt) in D:\Dropbox\DotNet Resources\SharpNav\Source\SharpNav\NavMeshQuery.cs:line 121
at SharpNav.NavMeshQuery.FindRandomPointAroundCircle(NavPoint center, Single radius, NavPoint& randomPoint) in D:\Dropbox\DotNet Resources\SharpNav\Source\SharpNav\NavMeshQuery.cs:line 410

I don't have a specific point logged, only range (99999) and it's very rare but still could you check the code?

private AgentTrail[] trails = new AgentTrail[AGENT_MAX_TRAIL];

should be

private AgentTrail[] trails = new AgentTrail[MAX_AGENTS];

So I want to find random point around (0;0;0). And FindRandomPointAroundCircle throws exception when PolyId from FindNearestPoly is passed there.

But it seems like PolyId.Null is considered a valid return from FindNearestPoly for (0; 0; 0).

While debugging FindNearestPoly I noticed that QueryPolygons returns like 52 polys and one of them was that PolyId.Null poly (which I pass later to the FindRandomPointAroundCircle).

I load the navmesh from json so it could be serialization problem.

Is it possible to save/load navigation mesh on disk after it is built or is it necessary to build it from geometry input every time?
Or is it in plans for future?
I see there's some json serialization code commented out.

In the example you retrieve the start point ref like this:
navMeshQuery.FindRandomPoint(ref startRef, ref startPos);

I can find a random point and its ref but I can't simple use a concrete point and find the closest point and ref.

Basically, I need a possibility to find the path from point A to point B, not from one random point to another...

After I updated SharpNav in our project all the bots are trying now to go outside of the physics map. I presume that X coordinate is now inverted. But previously the same code worked fine! So did you introduce some changes on this?

Can you add please some setting for deserializer or somewhere else so we can have the same X axis as before?

Hi, first thanks for your work on trying to bring navmesh generation to the c# sharp world. I hope you continue converting recast (and detour) to managed code including all the neat features of the c++ code like dynamic obstacles.

Now to my problems (I currently only use the recast part as I have my own working navmesh ai):

1. There are some problems with (at least) the generation of the mesh detail. Some polygons are not triangulated correctly (e.g. missing triangles in the detail mesh). The problem is not so visible if VertsPerPoly is set to 3 for generating the PolyMesh and then creating the PolyDetailMesh from there. But it's still there on complexer source meshes (I can send you one ... (1)).
2. An exception may be thrown in GetHeightData (in PolyMeshDetail.cs) as "compactField.Cells[ay * compactField.Width + ax]" gets out of range if ay (or ax) gets negative - and it sometimes will.
   I get around this error by checking if the calculated array position fits inside the array - but I think thats not the source of the problem but only a workaround to hide it (a bit) ;-)

I can send you a simple *.obj file (and a more complex one (1)) if you want to check the code and the problems I descibed.

BTW: both obj files have no problems in the original c++ version ...

Keep up the good work,
Lars

I picked up the SharpNav only some time ago and I have little insight in what's going on, but I think I found a bug that prevented my agent from travelling over an OffMeshConnection.

The first while loop in PathCorridor.MoveOverOffMeshConnection sets the local variables PolyId prevRef and PolyId polyRef.
Before the first iteration the variables have the following values:
prevRef = PolyId.Null
polyRef = path[0]

After first iteration:
prevRef = path[0]
polyRef = path[0]

After second iteration:
prevRef = path[0]
polyRef = path[1]

The problem is, that the npos variable needs to be incremented before setting the new value to polyRef, so prevRef and polyRef do not have the same value after the first iteration.

PolyId prevRef = PolyId.Null, polyRef = path[0];
int npos = 0;
while (npos < pathCount && polyRef != offMeshConRef)
{
    prevRef = polyRef;
    npos++;
    polyRef = path[npos];
}

EDIT: PullRequest: #56

Recently, I use SharpNav as navigation module in a Unity web project. When I try to
display poly detail mesh in scene, I use data in PolyMeshDetail Object in the middle generating process, there is no problem. But when I switch to use data in TiledNavMesh, an IndexOutOfRangeException is throw out. I research the code, I find out that process in NavMeshBuilder constructor have some problem. You adjust var
navDVerts , navDVerts is not the same with parameters.detailVerts ; But you don't adjust navDTris, navDTris is the same with parameters.detailTris. Should those vars
adjust consistence?

Adding OffMeshConnections to the NavMeshBuilder results in an NullReferenceException, at Line 273, because there is no instance of the Poly class at this position in the navPoly array.
Was Poly a struct some time ago?

I copied your pathfinding code from the example app and sometimes it throws IndexOutOfRangeException: Index was outside the bounds of the array in FixupCorridor. I don't have a specific line, unfortunately. I will email you an snb and coordinates.

Here is the method:

        int FixupCorridor(PolyId[] path, int npath, int maxPath, List<PolyId> visited)
        {
            int furthestPath = -1;
            int furthestVisited = -1;

            //find furhtest common polygon
            for (int i = npath - 1; i >= 0; i--)
            {
                bool found = false;
                for (int j = visited.Count - 1; j >= 0; j--)
                {
                    if (path[i] == visited[j])
                    {
                        furthestPath = i;
                        furthestVisited = j;
                        found = true;
                    }
                }

                if (found)
                    break;
            }

            //if no intersection found, return current path
            if (furthestPath == -1 || furthestVisited == -1)
                return npath;

            //concatenate paths
            //adjust beginning of the buffer to include the visited
            int req = visited.Count - furthestVisited;
            int orig = Math.Min(furthestPath + 1, npath);
            int size = Math.Max(0, npath - orig);
            if (req + size > maxPath)
                size = maxPath - req;
            for (int i = 0; i < size; i++)
                path[req + i] = path[orig + i];

            //store visited
            for (int i = 0; i < req; i++)
                path[i] = visited[(visited.Count - 1) - i];

            return req + size;
        }


        [CanBeNull]
        public SlimVector3[] FindPath(SlimVector3 from, SlimVector3 to)
        {
            try
            {
                var navMeshQuery = _navMeshQuery;
                //Find random start and end points on the poly mesh
                NavPoint startPt;
                if (!GetClosestPoint(navMeshQuery, from, out startPt))
                    return null;
                //Debug.WriteLine("Finding path from " + startPos.Position);
                NavPoint endPt;
                if (!GetClosestPoint(navMeshQuery, to, out endPt))
                    return null;

                //Debug.WriteLine("             to " + endPos.Position);

                //calculate the overall path, which contains an array of polygon references
                int MAX_POLYS = 256;
                var path = new List<PolyId>(MAX_POLYS);
                if (startPt.Position == endPt.Position)
                    return new[] { to };
                navMeshQuery.FindPath(ref startPt, ref endPt, path);
                if (path.Count == 0)
                    return new[] { from, to };

                //find a smooth path over the mesh surface
                int npolys = path.Count;
                PolyId[] polys = path.ToArray();
                SVector3 iterPos = new SVector3();
                SVector3 targetPos = new SVector3();
                navMeshQuery.ClosestPointOnPoly(startPt.Polygon, startPt.Position, ref iterPos);
                navMeshQuery.ClosestPointOnPoly(polys[npolys - 1], endPt.Position, ref targetPos);
                if ((targetPos - endPt.Position).LengthSquared() > 25f)
                    return null;
                var smoothPath = new List<SVector3>(2048);
                smoothPath.Add(iterPos);

                float STEP_SIZE = 0.5f;
                float SLOP = 0.01f;
                while (npolys > 0 && smoothPath.Count < smoothPath.Capacity)
                {
                    //find location to steer towards
                    SVector3 steerPos = new SVector3();
                    int steerPosFlag = 0;
                    PolyId steerPosRef = PolyId.Null;

                    if (!GetSteerTarget(navMeshQuery, iterPos, targetPos, SLOP, polys, npolys, ref steerPos, ref steerPosFlag, ref steerPosRef))
                        break;

                    bool endOfPath = (steerPosFlag & PathfindingCommon.STRAIGHTPATH_END) != 0 ? true : false;
                    bool offMeshConnection = (steerPosFlag & PathfindingCommon.STRAIGHTPATH_OFFMESH_CONNECTION) != 0 ? true : false;

                    //find movement delta
                    SVector3 delta = steerPos - iterPos;
                    float len = (float)Math.Sqrt(SVector3.Dot(delta, delta));

                    //if steer target is at end of path or off-mesh link
                    //don't move past location
                    if ((endOfPath || offMeshConnection) && len < STEP_SIZE)
                        len = 1;
                    else
                        len = STEP_SIZE / len;

                    SVector3 moveTgt = new SVector3();
                    VMad(ref moveTgt, iterPos, delta, len);

                    //move
                    SVector3 result = new SVector3();
                    List<PolyId> visited = new List<PolyId>(16);
                    navMeshQuery.MoveAlongSurface(new NavPoint(polys[0], iterPos), moveTgt, ref result, visited);
                    npolys = FixupCorridor(polys, npolys, MAX_POLYS, visited);
                    float h = 0;
                    navMeshQuery.GetPolyHeight(polys[0], result, ref h);
                    result.Y = h;
                    iterPos = result;

                    //handle end of path when close enough
                    if (endOfPath && InRange(iterPos, steerPos, SLOP, 1.0f))
                    {
                        //reached end of path
                        iterPos = targetPos;
                        if (smoothPath.Count < smoothPath.Capacity)
                        {
                            smoothPath.Add(iterPos);
                        }
                        break;
                    }

                    //store results
                    if (smoothPath.Count < smoothPath.Capacity)
                    {
                        smoothPath.Add(iterPos);
                    }
                }
                return smoothPath.Select(v => new SlimVector3(v.X, v.Y, v.Z)).ToArray();
            }
            catch (Exception e)
            {
                string message = string.Format("FindPath problem: {0}\r\n\r\nMap = {1}\r\nFrom = {2}\r\nTo = {3}", e, _navMeshQuery, @from, to);
                Log.Error(message);
                Debug.WriteLine(e);
                return null;
            }
        }


        bool InRange(SVector3 v1, SVector3 v2, float r, float h)
        {
            float dx = v2.X - v1.X;
            float dy = v2.Y - v1.Y;
            float dz = v2.Z - v1.Z;
            return (dx * dx + dz * dz) < (r * r) && Math.Abs(dy) < h;
        }


        /// <summary>
        /// Scaled vector addition
        /// </summary>
        /// <param name="dest">Result</param>
        /// <param name="v1">Vector 1</param>
        /// <param name="v2">Vector 2</param>
        /// <param name="s">Scalar</param>
        void VMad(ref SVector3 dest, SVector3 v1, SVector3 v2, float s)
        {
            dest.X = v1.X + v2.X * s;
            dest.Y = v1.Y + v2.Y * s;
            dest.Z = v1.Z + v2.Z * s;
        }

        bool GetSteerTarget(NavMeshQueryWrapper navMeshQuery, SVector3 startPos, SVector3 endPos, float minTargetDist, PolyId[] path, int pathSize,
             ref SVector3 steerPos, ref int steerPosFlag, ref PolyId steerPosRef)
        {
            int MAX_STEER_POINTS = 3;
            SVector3[] steerPath = new SVector3[MAX_STEER_POINTS];
            int[] steerPathFlags = new int[MAX_STEER_POINTS];
            PolyId[] steerPathPolys = new PolyId[MAX_STEER_POINTS];
            int nsteerPath = 0;
            navMeshQuery.FindStraightPath(startPos, endPos, path, pathSize,
                steerPath, steerPathFlags, steerPathPolys, ref nsteerPath, MAX_STEER_POINTS, 0);

            if (nsteerPath == 0)
                return false;

            //find vertex far enough to steer to
            int ns = 0;
            while (ns < nsteerPath)
            {
                if ((steerPathFlags[ns] & PathfindingCommon.STRAIGHTPATH_OFFMESH_CONNECTION) != 0 ||
                    !InRange(steerPath[ns], startPos, minTargetDist, 1000.0f))
                    break;

                ns++;
            }

            //failed to find good point to steer to
            if (ns >= nsteerPath)
                return false;

            steerPos = steerPath[ns];
            steerPos.Y = startPos.Y;
            steerPosFlag = steerPathFlags[ns];
            steerPosRef = steerPathPolys[ns];

            return true;
        }

Related to #52

Can I suggest you use MeshOMatic to load the OBJ files:
http://www.opentk.com/project/Meshomatic

Hi, in your object importer you are using "float.TryParse".
(ObjModel.cs Line 57 for example)
// if (!float.TryParse(line[1], out v.X)) continue;

You forgot to specify InvariantCulture.
I live in germany and we use ',' as separator for the decimal places.

Use this line to fix the bug and make it work for English and German cultures:

if (!float.TryParse(line[1], NumberStyles.Any, CultureInfo.InvariantCulture, out v.X)) continue;

I tried to adjust parameters but this is the best I've got:

Can you please look at the model?
https://www.dropbox.com/s/49drj4kjjrz6e43/nav_saga_problem.obj?dl=1

I see there are a lot of processing going on around FindPath in ExampleWindow.GeneratePathfinding. For now we are just copy-paste that code but why wouldn't you integrate it into NavMeshQuery?

I use sharpnav in pc standalone, it's works fine. But when i deploy the app in webplayer,
Exception " System.MethodAccessException: Attempt to access a private/protected method failed " was throw.

Code “public static readonly int SizeInBytes = Marshal.SizeOf(new Vector3())” in Vector3.cs lead to this problem. it is unmanaged code. I comment the code line, it work fine.

How would you do this?

When there is a mesh loaded, given that X and Z is given, how would you find the nearest Y axis position for the mesh?

Will it be implemented? As I googled recast currently doesn't support it.

can you provide an option to load multiple meshes into the same scene?

The same old obj: https://www.dropbox.com/s/jymf3n0oqwfhidr/Fighting_scene_navmesh.obj?dl=0

Sometimes (perhaps in multithread environment) it throws:
http://clip2net.com/clip/m203122/86185-clip-78kb.png?nocache=1

I'll try to investigate this further...

We are looking for a deterministic path finding library to get same path query result on both servers and clients. Since float-point numbers are not deterministic, we are thinking of replacing float-point numbers (and vectors) with fixed-point version. May come up with something like:

#if FIXEDPOINT
using Single = Fixed;
using Vector3 = FixedVector3;
#elif MONOGAME
using Single = System.Single;
using Vector3 = Microsoft.Xna.Framework.Vector3;
...
#endif

Is it possible to be done in SharpNav? Do you have any suggestion?

height = 5
span.Minimum = 5
span.Maximum = 6
After clamping minimum=maximum=5

    Cell.AddSpan(Span span):
        //clamp the span to the cell's range of [0, maxHeight]
        MathHelper.Clamp(ref span.Minimum, 0, height);
        MathHelper.Clamp(ref span.Maximum, 0, height);

        if (span.Minimum == span.Maximum)
            throw new ArgumentException("Span has no thickness.");
        else if (span.Maximum < span.Minimum)
            throw new ArgumentException("Span is inverted. Maximum is less than minimum.");

Any workarounds?

Set certain meshes as walkable and non-walkable.

With the newest version of SharpDX that came out in December 2015, we are now unable to use some functions of the current NuGet (0.9.2) version of SharpNav.SharpDX without downgrading SharpDX.

The reason behind that is that Vector3 and many different types are now in a different assembly, namely SharpDX.Mathematics.

This causes, for example, TriangleEnumerable.FromVector3, to not compile due to it referencing types that are in another assembly than the one it is looking in.

Obviously downgrading isn't that much of a problem but it would be greatly appreciated if this was fixed.

Thanks for looking into this!

Note: Using 1.0.0-alpha2 does not help.

We want our designers to make navmeshes manually but it looks like there is no way to pass it directly to SharpNav without generation step. What can you suggest? Can you add a feature for our case?

How would I use SharpNav with an A* algorithm?