Xbox LIVE Indie Games
Sort Discussions: Previous Discussion Next Discussion
Page 1 of 2 (29 posts) 1 2 Next >

C# Port of Recast Detour Navigation Mesh for XNA, A* Pathing

Last post 7/13/2013 1:59 AM by rmm5. 28 replies.
  • 12/21/2012 11:32 AM

    C# Port of Recast Detour Navigation Mesh for XNA, A* Pathing

    I'm releasing Sick Kreations C# port of 'Recast/Detour by Mikko Mononen' to the community and hope it helps others solve complex AI path finding.

    To get zombies following the player in our game End of Days: Survivor was a big challenge, we have 3 story buildings, a subway and complex geometry for props through out the level. Our target was to get 32 zombies pathing after the player along with another hundred zombies randomly pathing through the streets, a huge load for any CPU.

    I have some experience with A* path finding and worked for a game company were we broke levels up into 2D grids and implemented a clever technique to represent more than one level in a byte, but even this compact representation of a complex level resulted in millions of bytes of data for path finding. We had some efficient code to run A* type route finding on the data that works on a PC but was less than idea for something like the Power PC on the Xbox360.

    I implemented my own version of this for the End Game Engine and could barley path 4 zombies after the player at 30 updates a second, and that would drop to 4-10  updates a second if a path failed to get a route from the start node to the end node.

    So began the search for something that would work for us and thankfully I found Recast Detour by Mikko Mononen.
    Check out his blog here, his stuff is insane and way beyond anything we at Sick Kreations could have come up with and he's released this as open source for any and all to use.

    The only issue was that the source is C++ and I believe the only port to C# is for the Unity Engine and its nothing we could use for our engine.

    The fact that I was able to port his code to C# just goes to show how good a programmer Mikko Mononen is.

    Our build of Recast/Detour can be downloaded from our website, here.

    I am not a technical writer so please bare with me as I try to explain how to use the port:
     
    Here's is a link to Recast and Detour 1.21 by Mikko Mononen on his 'Digesting Duck' blog, here.
    Here's is the project with modified code to export navigation mesh in a format compatible with Xbox360 Big Endian, Download
    Here is the files to add to your game for run time loading and getting routesDownload. This code requires you check 'Allow unsafe code' in your games build properties because I used pointers in the port.


    To compile the Recast/Detour navigation mesh generation tool:

    I downloaded C++ 2010 Express to build the Recast/Detour project, you can get it free from Microsoft.
    After unzipping our version of 'Recast Detour Project' you should find the solution file at '..RecastDemo\Build\VC9\Recast.sln'.

    You'll probably have to set the include, source and library paths for your build.

    In addition to that you'll have to set 'Additional Library Directories' in the C++ Express environment to point to were you downloaded and unzipped the Recast/Detour files from Mikko Mononen's blog.

    example:

    ..\Recast\Recast-1.4\SDL-1.2.15\lib\x86

    ..\..\Contrib\SDL\lib

    To load a navigation mesh in game:

    dtStatNavMesh NavigationMesh = new dtStatNavMesh();
    NavigationMesh.LoadNavigationMesh( AssetDirectory + NavigationMeshName + "NavMeshXbox360");


    To get a route in game:

    int NavMeshStart = 0;  
    int NavMeshCount = NavigationMesh.GetPath(ref Vector3 Start, ref Vector3 End, ushort[] routePolys, Vector3[] NavMeshRoute, true); 

     


    To walk through the route:
     

    while (NavMeshStart < NavMeshCount)  
    {  
        Vector3 RouteNode = NavMeshRoute[NavMeshStart++]; 

     

    My implementation of Recast/Detour was quick and dirty and there is room to optimize the code, the first place to look for optimizing would be file 'DetourNode.cs'.

    If I left out any files from the End Game Engine that are referenced please leave a commit and I'll get those included asap.


    How to build the navigation mesh:
    You'll have to export your level in .OBJ format for the Recast tool to load it.
    The tool expects to find source .OBJ geometry in the folder:
    '..\Recast Detour Project\RecastDemo\Bin\Meshes\yourLevelName.obj'

    There are defualt Meshes you can test with, 'dungeon.obj' and 'nav_test.obj'

    To load your level in the tool and generate a navigation mesh:
    Click->'Choose Builder...'->'Static Mesh (Simple)' (this is the only type of mesh I used and my code is not tested with any other format)
    Click->'Choose Mesh...' and click your mesh's name from the 'Meshes' directory.
    Scrolldown and click 'Build'

    NOTE: If you have problems generating a navigation mesh tweek the values in the 'Sample::resetCommonSettings()' function in the file '..\Recast Detour Project\RecastDemo\Source\Sample.cpp'. The Min and Max for those values can be tweeked in the function 'Sample::handleCommonSettings()' in the same file.

    The 3 buttons, 'Load NavMesh', 'Save NavMesh For PC' and 'Save NavMesh For Xbox360' were added by me and do what they say.
    When you save to Xbox360 I format the data for Big Endian Xbox360 compatibility. The navigation mesh will be saved to the 'Meshes' directory your source mesh was in, with 'NavMeshXbox360' concatenated to the name. Just add this file to your game content and set 'Build Action' to None and 'Content Processor' to No Processing Required.

    I'll try to answer any question you have or help resolve any issues you run into and by all means share optimizations and fixes you add :-)

    The navigation mesh generated by this tool for the End of Days: Survivor level is a mere 133kb, and we can plot 16 routes in one update with time to spare. Thats just insane fast path finding for a complex level!

    Mikko Mononen stuff works flawlessly for our engine and we are grateful to him for sharing his navigation mesh code. All the original code is by Mikko Mononen and I have clearly marked my changes, please do the same with the code when you get it.

    Kevin.

     

  • 12/21/2012 1:42 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Kevin

    Thanks for releasing that code.  Shame it's too late for me, I have already come up with my own design to generate navigation meshes however I know how much research and work I had to do to come up with a solution that could work with larger spaces.  The navigation mesh generation was one of the hardest bits of the AI, so you are likely to save people a lot of time.

    It may not look difficult because when you look at a map by eye it is obvious what areas can be navigated but I know from experience that coming up with an algorithm to get the computer to understand the spaces was a lot harder going than I had expected.

    Regards


  • 12/21/2012 7:45 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    John

    I watched your video on AI not long ago, its looking good and I look forward to playing Diabolical when its released.

    I thought I would share more about Mikko Mononen in case any one was wondering who he is:

    "Mikko was the Lead AI on Crysis, and worked as a Programmer at Crytek for multiple years.
     He’s also an independent developer, AI consultant and leading open-source developer
    ", source.

    I also included some screen shots to help visualize how powerful his navigation mesh tool is.

    This is the End of Days: Survivor level loaded in the tool from a .OBJ file.
    Right-click and select 'Set Image Properties'


    This is the level with the navigation mesh generated.
    Right-click and select 'Set Image Properties'


    And heres a test of the 'Detour' code getting a route from the top floor of a 3 story building into another building.
    Right-click and select 'Set Image Properties'


    Navigation mesh on complex geometry, 2 flights of stairs.
    Right-click and select 'Set Image Properties'



    The Recast Demo tool only took about 30 seconds to generate the navigation mesh data for the level. To use the data to find routes in a game only requires adding 2 files to your game project and the navigation mesh output to your content pipeline.


  • 2/12/2013 8:15 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hey Kevin,

    Thanks so much for releasing this.  I was just working on a better AI pathing solution and had though about using collision models in some fashion.  I started doing research and found this was call navigation meshes and ran across your port while researching info on them.  This worked great and has saved me a lot of time right now.

    On thing though, your port of the recast demo tool crashed when building a path for my level but the original version didn't.  I found it was due to the default settings for the cell size and cell height.  It seems you changed the default and my model's dimensions lined up more with the settings for the original version.  Just thought I would mention it in case anyone has a similar issue.

    Thanks again, this has been a huge help.
    Reggie
  • 2/13/2013 12:25 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Reggie, thanks for letting me know. I'll set those back to the default settings in the ported download.

    Mikko Mononen's stuff is the money! I think this is the actual stuff used for original Crysis game.

  • 3/7/2013 10:19 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    This actually sounds pretty easy to implement but im still having problems..

    So if im on the right track; you use recast to create a navigational mesh, which outputs in the source folder. Along with the two classes you import the 
    newly created navmesh and then load that up along with the mesh file( .obj? or can you use fbx? Does that matter too much? Can you just use the file as is?),
    then with a couple of lines in your game class that declare the class variables and 



    Here is where im at right now,



     Vector3 start = new Vector3(0,0,0); // last place mouse clicked 

     Vector3 end = new Vector3(ppos.X,ppos.Y, ppos.Z); // new goal 

     ushort[] routePolys = navMesh.?? //What should this be?

     Vector3[] NavMeshRoute = new Vector3[0]; // what should this be? 

     int NavMeshCount = navMesh.GetPath(ref start, ref end, routePolys, NavMeshRoute, true);


    I don't really understand the routePolys or navMeshRoute array variable..Any help?

    Thanks
  • 3/7/2013 11:25 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    clckwrkc creations,

    You use the file output by 'Recast' as is. The navigation mesh will be saved to the 'Meshes' directory your source mesh was in, with 'NavMeshXbox360' concatenated to the name. Just add this file to your game content and set 'Build Action' to None and 'Content Processor' to No Processing Required.

    NavMeshRoute and routePolys should be allocated with size 'dtStatNavMesh.MAX_POLYS', found in file DetourStatNavMesh.cs, example: 

    Vector3

     

     

    [] NavMeshRoute = new Vector3[dtStatNavMesh.MAX_POLYS];

     

     

     

    ushort[] routePolys = new ushort[dtStatNavMesh.MAX_POLYS];

    To get a route in game:

     

    int NavMeshStart = 0;
    int NavMeshCount = NavigationMesh.GetPath(ref Vector3 Start, ref Vector3 End, ushort[] routePolys, Vector3[] NavMeshRoute, true);

     

     


    To walk through the route:

    while (NavMeshStart < NavMeshCount)
    {
    Vector3 RouteNode = NavMeshRoute[NavMeshStart++];
    }

    "routePolys" can be used to get detial about each polygon the route passes through.

    "NavMeshRoute" will be filled with Vector3 positions the route follows, from NavMeshRoute[0] ( the start ) to NavMeshRoute[NavMeshCount - 1] ( the end ).

    Let me know if this helps.

    Kevin

  • 3/8/2013 7:03 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Edit:

    So after some debugging i've found that the problem is the file reader wasn't reading my navmesh file, but i set it to copy to the output directory so now im reading a file.

    I can read a 
         navMesh.getPolyCount(); 

    but navmeshroute and routepolys remain as 0. I find this really odd. Im passing through random vector3 values, could that be it?


    Im building on the pc btw.






    Hi Kevin,


    Thanks for your prompt reply.

    I've been working on this for a day and a half now and i still can't quite get my head around it.  I implemented A* pathfinding a few days back and the way i would do it is create a conceptual 10x1x10(or whatever) grid and then mouse unproject onto the z/x plane and explicitly convert the values into vector3. 

    Now, for this i assume we're working with world space or object space? If i am to unproject mouse coordinates into 3d space then how do i tell the agent where to go? Do i need to do mouse picking on the object? 



    So what i've done here is move my obj model to a position where its directly in line with 0,0,0 in world space, the code compiles but nothing happens. I cant get any values printed via writeline on console either. Everything is 0(aside from the end vector3 which was my input)



                    start = new Vector3(0,0,0);
                    end = new Vector3(10, 0, 0);

                    routePolys = new ushort[dtStatNavMesh.MAX_POLYS];
                    navMeshRoute = new Vector3[dtStatNavMesh.MAX_POLYS];

                int navMeshCount = navMesh.GetPath(ref start, ref end, routePolys, navMeshRoute, true);
           
                while (navMeshStart < navMeshCount)
                {

                   routeNode = navMeshRoute[navMeshStart++];

                }

                navMesh.getPolyCount();



                _box.World = Matrix.CreateTranslation(routeNode.X, routeNode.Y, routeNode.Z);  // or _box.World = Matrix.CreateTranslation(navMeshRoute[1].X, navMeshRoute[1].Y, navMeshRoute[1].Z); doesnt work either
      
                
                Console.Out.WriteLine("routeNode : " + routeNode);
                Console.Out.WriteLine("navmeshPolyCount" + navMesh.getPolyCount());
  • 3/10/2013 3:18 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Yes, you have to give "int navMeshCount = navMesh.GetPath(ref start, ref end, routePolys, navMeshRoute, true);" a valid start and end.
    The positions have to lie on mesh the 'Recast' tool created. There is a maximum and minimum extents from the start and end position the detour code will test within, those values are defaulting to (20,80,20), but should be set to the same values the recast tool are using (my error in the code I uploaded), The recast tool defaults to (2,4,2).

    You can find the values in the detour code in file "DetourStatNavMesh.cs" at line 69.
    You can find the values in the recast build in the file "Recast Detour Project\RecastDemo\Source\Sample_StatMesh.cpp" at lines 33, 34, 35.

    Having 0,0,0 as center of your world space is correct.

    One issue you may have is scaling, you might create a simple flat, square world, generate the mesh and check the extents of the navigation your code loads.

    Your building for the PC,  I only tested on the Xbox.

    I didn't include any debug drawing in the file "DetourStatNavMesh.cs" because the my engine draws would be useless to anyone else.
    You might want to implement your own debug drawing so you can see on your render target were the detour code thinks your navigation mesh is located in world space and its scaling.

  • 3/10/2013 4:15 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Heres how I implemented debug drawing. I added two methods to the 'dtStatNavMesh' class in the file '"DetourStatNavMesh.cs", i got the core of the drawing routines from the Recast tool.

    Sorry for the formatting, i pasted this code from my game engine and deleted the triangle drawing.

    You call the routines like this, from your main 'Draw()'
    DebugDrawNavMesh();        // draw polygons
    DebugDrawNavMesh(true);     // draw inner polygon edges  
    DebugDrawNavMesh(false);    // draw outer polygon edges

    #if DEBUG
    static int triCountDraw = (180 * 3);

    Vector3[] m_TmpBuff = new Vector[triCountDraw];

    public void DebugDrawNavMesh()

    {

        Color triClr = new Color(0, 196, 255, 64);

        int curVert = 0;

        Vector3 pos = Vector3.Zero;

        for (int i = 0; i < getPolyDetailCount(); ++i)

        {

            dtStatPoly p = getPoly(i);

            dtStatPolyDetail pd = getPolyDetail(i);

            for (int j = 0; j < pd.ntris; ++j)

            {

                byte[] t = getDetailTri(pd.tbase + j);

                for (int k = 0; k < 3; ++k)

                {

                    if (t[k] < p.nv)

                    {

                        pos.X = getVertex((int)p.v[t[k]]).X;

                        pos.Y = getVertex((int)p.v[t[k]]).Y;

                        pos.Z = getVertex((int)p.v[t[k]]).Z;

                    }

                    else

                    {

                        pos.X = getDetailVertex(pd.vbase + (t[k] - p.nv)).X;

                        pos.Y = getDetailVertex(pd.vbase + (t[k] - p.nv)).Y;

                        pos.Z = getDetailVertex(pd.vbase + (t[k] - p.nv)).Z;

                    }

                    m_TmpBuff[curVert] = pos;

                    curVert++;

                }

                //

                // render if buffer full

                //

                if (curVert >= (triCountDraw - 3))

                {    
                    //
                    // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives 
                   //

     

                    curVert = 0;

                }

            }

        }

        //

        // render if buffer full

        //

        if (curVert > 3)

        {

            //
            // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives
            //

            curVert = 0;

        }

    }

    //
    // Draw navigation mesh for debug purposes

    //
    unsafe public struct TempTV

    {

        public float* p;

    }

    public void DebugDrawNavMesh(bool inner)

    {

        Color triClr = Color.White;

        Vector3 vrt0 = Vector3.Zero;

        Vector3 vrt1 = Vector3.Zero;

        Vector3 vrt2 = Vector3.Zero;

        Vector3 vrt3 = Vector3.Zero;

        Vector3 vrtn = Vector3.Zero;

        Vector3 posStart = Vector3.Zero;

        Vector3 posEnd = Vector3.Zero;

     

        if (inner)

        {

            triClr = new Color(0, 48, 64, 64);

        }

        else

        {

            triClr = new Color(0, 28, 44, 180);

        }

     

        int curVert = 0;

        for (int i = 0; i < getPolyCount(); ++i)

        {

            dtStatPoly p = getPoly(i);

            dtStatPolyDetail pd = getPolyDetail(i);

            for (int j = 0, nj = (int)p.nv; j < nj; ++j)

            {

                if (inner)

                {

                    // Skip non-connected edges.

                    if ((int)p.n[j] == 0) continue;

                }

                else

                {

                    // Skip connected edges.

                    if ((int)p.n[j] != 0) continue;

                }

                Vector3 v0 = Vector3.Zero;

                Vector3 v1 = Vector3.Zero;

                v0 = getVertex((int)p.v[ j ]);

                v0 = getVertex((int)p.v[ (j + 1) % nj ]);

                // Draw detail mesh edges which align with the actual poly edge.

                // This is really slow.

                for (int k = 0; k < pd.ntris; ++k)

                {

                    byte[] t = getDetailTri(pd.tbase + k);

                    Vector3[] tmpTv = new Vector3[3];

                    for (int m = 0; m < 3; ++m)

                    {

                        tmpTv[m] = Vector3.Zero;

                        if (t[m] < p.nv)

                        {

                            tmpTv[m] = getVertex((int)p.v[t[m]]);

                        }

                        else

                        {

                            tmpTv[m] = getDetailVertex(pd.vbase + (t[m] - p.nv));

                        }

                    }

                    for (int m = 0, n = 2; m < 3; n=m++)

                    {

                        if (((t[3] >> (n*2)) & 0x3) == 0) continue; // Skip inner edges.

                        if (distancePtLine2d(ref tmpTv[n], ref v0, ref v1) < thr && distancePtLine2d(ref tmpTv[m], ref v0, ref v1) < thr)

                        {

                            posStart.X = tmpTv[n].X;

                            posStart.Y = tmpTv[n].Y;

                            posStart.Z = tmpTv[n].Z;

                            posEnd.X = tmpTv[m].X;

                            posEnd.Y = tmpTv[m].Y;

                            posEnd.Z = tmpTv[m].Z;

                            vrtn = (posEnd - posStart);

                            if (vrtn.LengthSquared() > (2 * 2))

                            {

                                vrtn.Normalize();

                                vrtn = Vector3.Cross(vrtn, Vector3.UnitY);

                                vrt0 = posStart + (vrtn * -10.0f);

                                vrt1 = posStart + (vrtn * 10.0f);

                                vrt2 = posEnd + (vrtn * -10.0f);

                                vrt3 = posEnd + (vrtn * 10.0f);

                                m_TmpBuff[curVert++] = vrt0;

                                m_TmpBuff[curVert++] = vrt1;

                                m_TmpBuff[curVert++] = vrt2;

                                m_TmpBuff[curVert++] = vrt1;

                                m_TmpBuff[curVert++] = vrt3;

                                m_TmpBuff[curVert++] = vrt2;

                                if (curVert >= (triCountDraw - 6))

                                {

                                    //
                                    // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives AND 'triClr' color
                                    //

                                    curVert = 0;

                                }

                            }

                        }

                    }

                }

            }

        }

        if (curVert > 3)

        {

            //
            // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives AND 'triClr' color
            //

            curVert = 0;

        }    

    }

    #endif // DEBUG

    Let me know if this helps, if it does i might add it to the download.

    Kevin

  • 3/10/2013 5:52 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hi Kevin,


    I've changed the values back to 2,4,2 so the extents should be default now.

    Im trying to use your debugdraw code but a little bit confused about ;

        // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives 

        // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives AND 'triClr' color

            
                   
       
    Do you have an example code i can see? 

    Im currently trying to make this work 

    graphics.DrawUserPrimitives(PrimitiveType.TriangleList, m_TmpBuff, 0, curVert/3, VertexPositionColor.VertexDeclaration); 



  • 3/11/2013 5:06 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Are you getting a value > 0 when calling navMesh.GetPath() now ?

    You can use 'DrawUserPrimitives' for the debug drawing, you just have to set your current shader technique to 'BasicEffect' and copy the positions from 'm_TmpBuff' into a structure compatible with the 'BasicEffect'.

    Heres a tutorial on how to use the 'BasicEffect'.

    http://msdn.microsoft.com/en-us/library/bb203926(v=xnagamestudio.10).aspx


  • 3/12/2013 12:22 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hi,


    So i've got debug drawing working now but it kills my game speed..Im not sure why, im doing everything inside the debugdraw method and then calling it from my main draw.



      if (curVert >= (triCountDraw - 3)) 
                        { 
                            
                            for (int k = 0; k < m_TmpBuff.Length-1; k++) 
                            { 
                                vertices[k] = new VertexPositionColor(new Vector3(m_TmpBuff[k+1].X, m_TmpBuff[k+1].Y, m_TmpBuff[k+1].Z), triClr); 
                            } 
                            
                           
     
                            vertexBuffer = new VertexBuffer(graphicsD, typeof(VertexPositionColor), 600, BufferUsage.WriteOnly); 
                            vertexBuffer.SetData(vertices); 
     
     
                            graphicsD.SetVertexBuffer(vertexBuffer); 
     
                            RasterizerState rasterizerState = new RasterizerState(); 
                            rasterizerState.CullMode = CullMode.None; 
                            graphicsD.RasterizerState = rasterizerState; 
     
                            foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes) 
                            { 
                                pass.Apply(); 
                                //graphicsD.DrawPrimitives(PrimitiveType.TriangleList, 0, curVert/3); 
     
                                graphicsD.DrawUserPrimitives(PrimitiveType.TriangleList, vertices, 0, curVert/3); 
                               
                            } 
                               
                            // TODO: Add your code to draw 'm_TmpBuff' as a triangle list with (curVert / 3) number of primitives 
                         
                             
     
                            curVert = 0; 
                        } 
                    } 
                } 
                // 
                // render if buffer full 
                // 
                if (curVert > 3) 
                { 
                    // 
     
                    for (int k = 0; k < m_TmpBuff.Length - 1; k++) 
                    { 
                        vertices[k] = new VertexPositionColor(new Vector3(m_TmpBuff[k + 1].X, m_TmpBuff[k + 1].Y, m_TmpBuff[k + 1].Z), triClr); 
                    } 
     
     
     
                    vertexBuffer = new VertexBuffer(graphicsD, typeof(VertexPositionColor), 600, BufferUsage.WriteOnly); 
                    vertexBuffer.SetData(vertices); 
     
     
                    graphicsD.SetVertexBuffer(vertexBuffer); 
     
                    RasterizerState rasterizerState = new RasterizerState(); 
                    rasterizerState.CullMode = CullMode.None; 
                    graphicsD.RasterizerState = rasterizerState; 
     
                    foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes) 
                    { 
                        pass.Apply(); 
                        //graphicsD.DrawPrimitives(PrimitiveType.TriangleList, 0, curVert/3); 
     
                        graphicsD.DrawUserPrimitives(PrimitiveType.TriangleList, vertices, 0, curVert / 3); 
     
                    } 




    Heres what the navMesh looks like at the moment when debug drawn. Kinda looks like there are gaps in it. 



    Right-click and select 'Set Image Properties'


    and this is what happens when i run my debug to see if the values are being drawn or pathfound. I get a value > 0 but no pathfinding occurs, it fills up 3 in the navmeshRoute array and stops there.
    Again im picking Vector3 values from world space. 



     How do i pick 2D control points off the navmesh to pathfind in? Surely the values in tmp_buff cant me the ones i need to use ?


    Right-click and select 'Set Image Properties'



    To draw the mesh i put vertexData from m_TmpBuff to vertices,
    are these the values i am limited to using when i search with start and end?


    Right-click and select 'Set Image Properties'

    When i do that, i get the same exact result, it fills up 3 values in the array and its not really searching anything. 


    Right-click and select 'Set Image Properties'

  • 3/12/2013 2:27 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Update: 17:53

    Could it be this line thats causing all the trouble?  "((ushort*)&header->bvtree[i].bmin)[j]; " Line + 417-418 & 436-437 on DetourStatNavMesh

          /*
                 * 
                 * navigation mesh polygons
                 * 
                 */ 
                for (int i = 0; i < mHeader.npolys; i++) 
                { 
                    mHeader.polys[i] = new dtStatPoly(DT_STAT_VERTS_PER_POLYGON); 
     
                    mHeader.polys[i].nv = header->polys[i].nv; 
                    mHeader.polys[i].flags = header->polys[i].flags; 
     
                    for (int j = 0; j < DT_STAT_VERTS_PER_POLYGON; j++) 
                    { 
                        mHeader.polys[i].v[j] = (&header->polys[i].v)[j]; 
                        mHeader.polys[i].n[j] = (&header->polys[i].n)[j]; 
                    } 
                } 
     
     
                /*
                 * 
                 * navigation mesh BV tree
                 * 
                 */ 
                for (int i = 0; i < (mHeader.npolys * 2); i++) 
                { 
                    mHeader.bvtree[i] = new dtStatBVNode(3); 
     
                    mHeader.bvtree[i].i = header->bvtree[i].i; 
     
                    for (int j = 0; j < 3; j++) 
                    { 
                        mHeader.bvtree[i].bmin[j] = ((ushort*)&header->bvtree[i].bmin)[j]; 
                        mHeader.bvtree[i].bmax[j] = ((ushort*)&header->bvtree[i].bmax)[j]; 
                    } 
                } 



    It could be resharper just being picky but when i highlight ((ushort*)&header->bvtree[i].bmin)[j]; it tells me that "&" is a problem and that "you can only take the address of an unfixed expression inside of a fixed statement intitializer"

    It still compiles and runs but im thinking this could actually be an issue.





    Update 15:08
    Sorry for bombing this thread with updates lol. 

    Fixed it. It seems it was my debug drawing code that was making it draw everything funny. Now the mesh is absolutely fine.


    This line here in my debugging.

     for (int k = 0; k < m_TmpBuff.Length - 1; k++) 
                    { 
                        vertices[k] = new VertexPositionColor(new Vector3(m_TmpBuff[k].X, m_TmpBuff[k].Y, m_TmpBuff[k].Z), triClr); 
                    } 
     
     


    Thought i would post that for anyone wondering. 


    Im still having trouble getting it to accept Vector3 values, on different meshes it returns 0 and if i fiddle with the values it gives me something but never more than 3-4 values as per the pics before this post. 

    Ill update once again once ive made progress





    So i tried out the debugDrawing the navMesh on a few different ones and iam getting some weird results. This could be why the search is messed up.

    The navMesh looks like this and the Recast tool shows nothing like that.



    Right-click and select 'Set Image Properties'



    Right-click and select 'Set Image Properties'




    And again i tested this out on the OBJ nav test mesh that came with recast, that again is giving me really funky results. 


    Right-click and select 'Set Image Properties'


    I dont really get what i could be doing wrong.

    Right-click and select 'Set Image Properties'
  • 3/12/2013 8:01 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Sorry for taking so long to respond, been feeling under the weather for sometime.
    1) Not suprised it draws slow with debuging on, happens in my game engine too.
    2) Glad you cuaght the [k+1] before i responded :-)

  • 3/12/2013 8:12 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    I think i see an issue with your debug draw:

    This line here in my debugging.

    for (int k = 0; k < m_TmpBuff.Length - 1; k++)
    {
    vertices[k] = new VertexPositionColor(new Vector3(m_TmpBuff[k].X, m_TmpBuff[k].Y, m_TmpBuff[k].Z), triClr);
    }


    For loop should be:
    for (int k = 0; k < curVert; k++) 

    Let me know if this cleans up your debug draw ?
  • 3/13/2013 5:23 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hey Kevin,

    I guess i should tell you what im trying to achieve with this navigational mesh and you can tell me whether that is a possibility and if you can, a few pointers on where i could go to achieve it.

    So im trying to implement point and click movement with the navigational mesh, what i want to be able to do is unproject mouse coordinates onto the 3d nav mesh and be able to tell it what to do, what im stumped about is how i could go about doing this, aside from triangle picking, which seems to be a little bit...innacurate?

    Anyway, 

    My draw is absolutely fine, thanks for the suggestion, it works either way, so what you just posted is good to include in the download.

    My problem now is that the values wont do any pathfinding finding past 3 values... Am i doing something wrong here perhaps? Or am i completely misunderstanding whats going on..


    when i put in a start and end it kinda just jumps between values and doesn't do any pathfinding, I think the values are fine, something might be going wrong inside DetourStatNavMesh.CS? 


    When i pathfind between two routes that are meant to be at a distance between each other, is it not supposed to give me the values in between? Or am i supposed to do linear interpolation between 70, 0, 3.9 and 10, 0, 5???? it gives me the start as a start, and the value in between comes in twice as the 2nd and last.



    Right-click and select 'Set Image Properties'


  • 3/13/2013 3:59 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    clckwrkc creations,

    Good to hear the drawing is working. I might take that code and add support for 'BasicEffect' and include it with the download.

    I want to find out if there is a problem with running the code on PC, my game engine is currently broken for PC build so I cant test it my self.

    To start lets run 'Recast' in debug and look at your sample level:
    Right-click and select 'Set Image Properties'


    Set a break point so we can look at the return route data:
    File "..\RecastDemo\Source\Sample_StatMesh.cpp" at Line 126
    Right-click and select 'Set Image Properties'


    Lets add a sample route in ONE polygon:
    Right-click and select 'Set Image Properties'

    This should fill 'm_straightPath' with 2 valid positions, the start and end X, Y, Z.


    Lets do a route across multiple polygons:
    Right-click and select 'Set Image Properties'

    This should fill 'm_straightPath' with the start position, all the X,Y,Z positions in the route at polygon edges and the end position.

    To test this in your game engine I would suggest setting a couple break points in File "..\RecastDemo\Source\Main.cpp" at Line 360 and Line 362.
    Then select a start point and end point, record those positions and hard code them into your game to test what C# ported file "DetourStatNavMesh.cs" is returning from GetPath().

    This should answer if the issue is in "DetourStatNavMesh.cs", the imported data file for the PC is corrupt, or the positions your passing the GetPath() method are invalid.

    Let me know the results, Kevin
  • 3/13/2013 6:44 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    I've done some debugging tests on recast and im getting 6 values when i check m_straightPath and getting 2 values on the same polygon so all is normal there.

    When i run debug tests in my game, here are the figures i get from within detourstatNavmesh.cs 

    Notice nPath and nStraightPath, both very different values: 

    You can also see that straightPolys fills up with the values but goes no further than 3.



    Right-click and select 'Set Image Properties'


    Same is exemplified here, routePolys returns the correct amount of pathfinding, with 37 values, like nPath, and navMeshRoute only returns 3 as per nStraightPath

    Right-click and select 'Set Image Properties'


    Ill hardcode some coordinates from recast to see if the same happens in my program, at this point i actually think detourStatNavMesh.cs is corrupt.


    Results from the recast debug this is from a path very similar to the 2nd one you posted(over a few polygons):
    Note the first and last values, i will use that to pathfind and see if i get any results within my game.

    Right-click and select 'Set Image Properties'


    Right-click and select 'Set Image Properties'




    So HERE is what happens when i use hardcoded values from the recast debug, straight from Sample_StatMesh.cpp : As you can see, same problem. Values are valid but no pathfinding, recast doesnt seem to be the problem either.

    Right-click and select 'Set Image Properties'

  • 3/15/2013 7:35 AM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hi Kevin,


    You can test it out on PC by the way, would be easier if someone else was testing this to see if there is a problem on my end, as you can use it in an empty XNA project and just debug test. Following your guide usually does it. Just make sure you copy the navmesh file to the output directory(debug/release).



  • 3/15/2013 12:40 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    I've got it working finally.


    Thanks for all your help Kevin,  I'll write up a guide on what i came across and what kind of problems people could come across when using your c# port.

    The problem in the end was because i had used 'static Mesh simple' in recast instead of static mesh tiled, that sorted it.



  • 3/19/2013 6:17 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Good to hear you got it working. I was away from my office from the Thursday 14 until today.
    Would appreciate your guide, I'll make any changes you found to the code and get it into the download.

    Kevin.
  • 3/25/2013 10:41 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hi again Kevin,

    Im now trying to work out what could be the best way to implement crowd behaviour with this tool? Is there a c# port for the crowd component of recast or did you write that entirely seperately in your engine? 

    I am also having trouble with the .obj importer dll im using that i got off the http://xbox.create.msdn.com/en-US/education/catalog/sample/custom_model_importer, but as it states it doesn't entirely support all .objs, for this reason im unable to put textures on my models.  When i try to load the .obj with a .MTL file it gives me an error "unsupported or invalid line type 'ni'", if i load up the file that comes with the sample it works just fine. Is there a better converter? Im currently using 3ds Max

    Any help would be appreciated.


  • 3/26/2013 8:22 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    hey clckwrkc creations

    i didn't do any type of crowd behavior or flocking, each bot in my game just tries to path directly to the player with only simple bounding sphere collision with other bots. if you want a crowd behavior for your game you might want to check into flocking.
    http://3carrotsonastick.wordpress.com/2012/11/01/boids-in-c-xna/

    i am also using 3ds max, i export my level in .obj for the navigation mesh tool, Recast, and i export it in .fbx for my game engine. i've never used the custom_model_importer example.


    Kevin.
  • 3/26/2013 10:34 PM In reply to

    Re: C# Port of Recast/Detour Navigation Mesh for XNA

    Hi Kevin,



    I think it is much simpler to just use bounding sphere collisions, i will do that instead lol.

    How do you walk your agent through the path? Do you physically push the agent through or use matrix translation with a bounding sphere?

    I am currently using Vector3.lerp and this allows me to translate my agent but this does not work out well as the agent goes through other agents/non-static objects in the way instead of bumping into them. 

Page 1 of 2 (29 posts) 1 2 Next > Previous Discussion Next Discussion