robmaister / sharpnav Goto Github PK
View Code? Open in Web Editor NEWAdvanced Pathfinding for C#
Home Page: sharpnav.com
License: Other
Advanced Pathfinding for C#
Home Page: sharpnav.com
License: Other
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?
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):
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
Does this fully support the OBJ specification?
I tried custom meshes (instead of the recast sample) and they don't load.
Some models cause this: http://c2n.me/3BTyeGd.png
I'll email you the obj file.
We use the latest version from master.
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):
Also if you'd like to see better integration (asset pipeline, etc):
If you are going to submit a pull request with engine integration, please reference this issue. This should be considered an ongoing issue.
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?
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?
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.
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...
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.
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
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;
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.
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.
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
How would I use SharpNav with an A* algorithm?
Set certain meshes as walkable and non-walkable.
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?
It would be nice to pull this straight from nuget. Lib looks cool!
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...
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 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.
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?
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.
How do you load Collada data and generate a Mesh?
can you provide an option to load multiple meshes into the same scene?
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.
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?
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?
Some calls to those can return false periodically while others work for the same navmesh. This depends on Random.Next value I think.
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.
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
Can I suggest you use MeshOMatic to load the OBJ files:
http://www.opentk.com/project/Meshomatic
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?
Is there a possibility to perform something like navmesh raycasting in Unity?
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.
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?
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
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.
Will it be implemented? As I googled recast currently doesn't support it.
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.
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.
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 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
private AgentTrail[] trails = new AgentTrail[AGENT_MAX_TRAIL];
should be
private AgentTrail[] trails = new AgentTrail[MAX_AGENTS];
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.