Custom Nav Mesh

[RyanMitchellGamesParticipant]

Hello all I am investigating using RAIN as Unity does not allow run-time nav mesh generation. I have a collection of rooms that are assembled randomly at run-time. I want to construct the nav mesh from nav meshes that are stored with the rooms. I have been looking really hard and I cannot find out if this is possible in RAIN or any other package. The run-time autogen from RAIN is a far to slow in my tests and I would prefer run-time generation of pre-calculated. Does anyone know if this is possible or have a direction I can turn. I have rolled my own before, however the tools provided in RAIN would be really nice to use.

So bullet points:
1. Can I create a mesh to feed into the navmesh gen to save generation time?
2. Can I create my own nav mesh for Rain to use?
3. If no to the above any ideas?

THANKS!

• This topic was modified 1 year, 10 months ago by  RyanMitchellGames.

[primeKeymaster]

Hmm. I suspect something can be done. One of the things that makes pre-generated navmeshes tough to work with in RAIN is that we don’t currently automatically support translation/rotation/scaling of navmeshes. So you could pre-create navmeshes for rooms, halls, and other components, but you would have to manually update the mesh points after the room is placed in the level.

We have this on our roadmap - to support arbitrary (and even dynamic) positioning of navmeshes at runtime, but haven’t been able to get to it just yet.

I’ll ask @sigil to jump in and answer this one - he’s the navmesh guru.

[RyanMitchellGamesParticipant]

That would be GREAT thanks! … . Yes positioning the meshes myself would be extremely simple. If I could just inject my mesh somewhere in the generation pipeline as I know the lion share of the auto gen time is in the mesh discovery or at least it was with my Nav Mesh systems I have written.

Thanks again!

[SigilKeymaster]

So a few things here. For RAIN, the break down of time with navigation mesh generation is about this: 50% rasterizing meshes to voxels, 50% tracing those voxels into meshes. There is a small amount of time at the beginning where I collect and generate collision meshes, and a little bit of time at the end where the navigation mesh data is all put together, but it is really small comparatively. It is possible to skip the first step if you already have your data in voxel form (the Terrain does this), but you’d have to let the second step run for auto generation and it still takes time.

Now if you already have a convex polygon mesh created (suitable for navigating) you could generate a navigation mesh out of this on the fly with the following code:

using RAIN.Navigation.NavMesh;
using RAIN.Navigation.NavMesh.RecastNodes;
using UnityEngine;
public class ManualNavMesh : MonoBehaviour
{
    [SerializeField]
    private NavMeshRig _navMeshRig;
    [SerializeField]
    private GameObject _meshObject;
    void Start()
    {
        // I'm not going to assume anything about the graph
        _navMeshRig.NavMesh.ClearNavigationGraph();
        // In my case I had a plane rotated and scaled in my scene (whatever it is
        // the mesh must make sense as a navigation graph or this is all pointless)
        MeshFilter tFilter = _meshObject.GetComponent<MeshFilter>();
        ContourMeshData tData = new ContourMeshData();
        tData.Vertices = tFilter.sharedMesh.vertices;
        // Need to transform our vertices to match our game objects position, rotation, and scale
        for (int i = 0; i < tData.Vertices.Length; i++)
            tData.Vertices[i] = _meshObject.transform.TransformPoint(tData.Vertices[i]);
        // have to do a little work around our triangles
        int[] tAllTriangles = tFilter.sharedMesh.triangles;
        // In this simple case, one contour equals one triangle, so we can use the same info for both
        // they need to be copied data though
        tData.Contours = new int[tAllTriangles.Length / 3][];
        tData.Triangles = new int[tAllTriangles.Length / 3][];
        for (int i = 0; i < tAllTriangles.Length; i += 3)
        {
            tData.Contours[i / 3] = new int[] { tAllTriangles[i], tAllTriangles[i + 1], tAllTriangles[i + 2] };
            tData.Triangles[i / 3] = new int[] { tAllTriangles[i], tAllTriangles[i + 1], tAllTriangles[i + 2] };
        }
        // Add the data
        _navMeshRig.NavMesh.Graph.AddContourVertices(tData);
        // And reregister
        _navMeshRig.NavMesh.RegisterNavigationGraph();
        // This may not be necessary, but I didn't check and it won't hurt
        // Resize our nav mesh rig to the size of our graph with a little extra
        Bounds tVertexBounds = _navMeshRig.NavMesh.Graph.VertexBounds;
        tVertexBounds.Expand(1);
        _navMeshRig.transform.position = tVertexBounds.center;
        _navMeshRig.transform.localScale = tVertexBounds.size;
        _navMeshRig.NavMesh.Size = 1;
    }
}

Let me know if that helps, or at least gives you some ideas. Note that this example expects convex data (which is what takes so long to generate normally) so its assuming you’ve done that work for it.

It is also possible to take another, pregenerated, navigation mesh and dump its data into a new larger mesh. There is some difficulty in joining the meshes though so that you can path between them. If that is more along the lines of what you need let me know and I can throw an example up of that.

[RyanMitchellGamesParticipant]

That would be great to see the methods to combine pre-generated meshes. I could just auto generate then have some method of crossing between meshes which I do not see as a big issue at all. I would love to see that code as it seems providing a mesh would only save a small portion of the generation time. I am trying to keep load times to a minimum as I already take enough time to generate the characters dynamically from a pool of parts on load. Most of them being skeletal meshes that takes some copy time.

Thanks again!

[RyanMitchellGamesParticipant]

BTW thanks again for the example I am storing that snippet away for later.. I look forward to seeing the combining method and not fumbling through like a 2 year old in a jello house… =)

[SigilKeymaster]

OK, I expanded the example. I changed the previous one to be a combine so it doesn’t clear the original graph anymore, and I added a new one that copies the data out of another graph that is assumed to be in the right position (I commented a section where you could move them if needed).

Just to note, this involves a lot of old stuff from RAIN and I think it is due for a change. In a future release you may find that this example is deprecated, or in the worst case it doesn’t work anymore. By the time that happens though there will either be an easier way to support what you are doing, or it will be officially supported through other channels. As prime said we have movable Navigation Meshes and Mesh Links in the roadmap, which would do everything you need without any crazy code.

That said:

using RAIN.Navigation.NavMesh;
using RAIN.Navigation.NavMesh.RecastNodes;
using System.Collections.Generic;
using UnityEngine;
public class ManualNavMesh : MonoBehaviour
{
    [SerializeField]
    private GameObject _meshObject = null;
    [SerializeField]
    private NavMeshRig _otherNavMesh = null;
    private NavMeshRig _navMeshRig = null;
    public void Awake()
    {
        _navMeshRig = GetComponent<NavMeshRig>();
    }
    public void Start()
    {
        if (_navMeshRig == null)
            return;
        if (_meshObject != null)
            CombineMesh();
        if (_otherNavMesh != null)
            CombineNavMesh();
    }
    private void CombineMesh()
    {
        // In my case I had a plane rotated and scaled in my scene (whatever it is
        // the mesh must make sense as a navigation graph or this is all pointless)
        MeshFilter tFilter = _meshObject.GetComponent<MeshFilter>();
        ContourMeshData tData = new ContourMeshData();
        tData.Vertices = tFilter.sharedMesh.vertices;
        // Need to transform our vertices to match our game objects position, rotation, and scale
        for (int i = 0; i < tData.Vertices.Length; i++)
            tData.Vertices[i] = _meshObject.transform.TransformPoint(tData.Vertices[i]);
        // have to do a little work around our triangles
        int[] tAllTriangles = tFilter.sharedMesh.triangles;
        // In this simple case, one contour equals one triangle, so we can use the same info for both
        // they need to be copied data though
        tData.Contours = new int[tAllTriangles.Length / 3][];
        tData.Triangles = new int[tAllTriangles.Length / 3][];
        for (int i = 0; i < tAllTriangles.Length; i += 3)
        {
            tData.Contours[i / 3] = new int[] { tAllTriangles[i], tAllTriangles[i + 1], tAllTriangles[i + 2] };
            tData.Triangles[i / 3] = new int[] { tAllTriangles[i], tAllTriangles[i + 1], tAllTriangles[i + 2] };
        }
        // Add the data
        _navMeshRig.NavMesh.Graph.AddContourVertices(tData);
        // This may not be necessary, but I didn't check and it won't hurt
        Bounds tVertexBounds = _navMeshRig.NavMesh.Graph.VertexBounds;
        tVertexBounds.Expand(1);
        // Resize our nav mesh rig to the size of our graph with a little extra
        _navMeshRig.transform.position = tVertexBounds.center;
        _navMeshRig.transform.localScale = tVertexBounds.size;
        _navMeshRig.NavMesh.Size = 1;
    }
    private void CombineNavMesh()
    {
        // Vertices is an IList, so we're going to copy it here
        List<Vector3> tOtherVertices = new List<Vector3>(_otherNavMesh.NavMesh.Graph.Vertices);
        // If you need to transform the vertices to a new location, now would be the time
        //for (int i = 0; i < tOtherVertices.Count; i++)
        //    tOtherVertices[i] = (do stuff to the vertices)
        // Our contours and triangles have been turned into NavMeshPolys so we have to do
        // some work to get them back
        List<int[]> tOtherContours = new List<int[]>();
        List<int[]> tOtherTriangles = new List<int[]>();
        for (int i = 0; i < _otherNavMesh.NavMesh.Graph.Size; i++)
        {
            NavMeshPoly tPoly = _otherNavMesh.NavMesh.Graph.GetNode(i) as NavMeshPoly;
            if (tPoly == null)
                continue;
            // Some helpers to make some quick arrays, going to change this in the future
            tOtherContours.Add(GetContour(tPoly));
            tOtherTriangles.Add(GetTriangles(tPoly));
        }
        // Don't need the old graph anymore
        _otherNavMesh.NavMesh.ClearNavigationGraph();
        // Create the new data
        ContourMeshData tNewData = new ContourMeshData()
        {
            Vertices = tOtherVertices.ToArray(),
            Contours = tOtherContours.ToArray(),
            Triangles = tOtherTriangles.ToArray()
        };
        // Add it in
        _navMeshRig.NavMesh.Graph.AddContourVertices(tNewData);
        // This may not be necessary, but I didn't check and it won't hurt
        Bounds tVertexBounds = _navMeshRig.NavMesh.Graph.VertexBounds;
        tVertexBounds.Expand(1);
        // Resize our nav mesh rig to the size of our graph with a little extra
        _navMeshRig.transform.position = tVertexBounds.center;
        _navMeshRig.transform.localScale = tVertexBounds.size;
        _navMeshRig.NavMesh.Size = 1;
    }
    private int[] GetContour(NavMeshPoly aPoly)
    {
        int[] tContour = new int[aPoly.ContourCount];
        for (int i = 0; i < tContour.Length; i++)
            tContour[i] = aPoly.GetContour(i);
        return tContour;
    }
    private int[] GetTriangles(NavMeshPoly aPoly)
    {
        int[] tTriangles = new int[aPoly.TriangleCount * 3];
        for (int i = 0; i < tTriangles.Length; i++)
            tTriangles[i] = aPoly.GetTriangle(i);
        return tTriangles;
    }
}

Let me know if you have any issues.

[urpro-basParticipant]

This is pretty interesting I have been busy with generating my own navmesh as well. When I started working on this I looked at the forums to see if there was anything of help for me. At that time I only found the runtime generation example which just does the same as the generate button but at runtime (this helped me a little bit), but it was way too slow to use for my application. My generated level actually is pretty simple, so I could define the mesh myself if I had to so I tried that. Besides I am not sure how the stitching in the example above would work if the navmeshes do not exacly line up, but have some overlapping space.

I came across some facts that to my knowledge are not documented but are good to know when you are getting into manually messing around with navmeshes. Maybe Sigil could validate those discoveries for correctness and completeness.

Some of the info I show could be derived from the code sample from Sigil.

• NavMesh definitions can be made with ContourMeshData (using RAIN.Navigation.NavMesh.RecastNodes.ContourMeshData)
• Contours are Polygons
• Contours have to be convex
• Contours and Triangles have to be defined with left turns (the ordering of vertex indices)
• ContourMeshData.Triangles and ContourMeshData.Contours are 2d int arrays
• ContourMeshData.Triangles and ContourMeshData.Contours are vertex indices
• The first dimension of ContourMeshData.Triangles and ContourMeshData.Contours is the Contour
1. So ContourMeshData.Contours[x] defines the border of the Contour with vertex indices
2. So ContourMeshData.Triangles[x] defines all triangles of the Contour (triangulation of the polygon defined by the contour)
• The second ContourMeshData.Triangles contains all triangles for the contour in set of three (so you could actually imagine it as a 3d array where ContourMeshData.Triangles[contour][triangle][vertex], but this [triangle][vertex] part is merged)

I think I have summed up my discoveries now, I hope this can be useful for other people working with the navmesh, but unfortunately, this is all going to change as Sigil already mentioned.

• This reply was modified 1 year, 10 months ago by  urpro-bas.
• This reply was modified 1 year, 10 months ago by  urpro-bas. Reason: oops ul inside ul doesn't work

[RyanMitchellGamesParticipant]

Great guys thanks! I will now get down to some working code!.. Very simple indeed just knowing where the buttons and knobs are is half the battle!..

Thanks Sigil, Prime, and Urpro-bas.

[SigilKeymaster]

Answering/confirming Urpro-bas (I’m just going to go per bullet instead of quoting):

1. Yes, currently you can add additional nav mesh data to a graph using ContourMeshData, I also plan on having some easier to use functions in the next release
2. Yes, contours are polygons, this name is a holdover from the recast process used to create them
3. Yes, contours have to be convex for a most of the path finding functionality to work properly
4. Er, contours and triangles should have clockwise winding, which should be right turns. This should be the same as Unity’s meshes, which I’m pretty sure are clockwise
5. The rest is correct, I tried to right up something to sum it up but it was confusing, the code shows it better

You are right that there isn’t a clear way to connect nearly connecting parts of the navigation meshes after you are add them. There is an example here of a poor mans mesh link that could be used to connect sections at runtime.

[RyanMitchellGamesParticipant]

Great stuff I have every normal rain thing working…. love the behavior trees very good design… When I get my code complete I will share it here.. Going to be a bit as this is after hours work now that I left the AAA game industry =)

[urpro-basParticipant]

Sigil Thanks for the validation, you are right they are clockwise so right turns, for some reason I wrote my first triangle wrong and I used this to validate my statement…

[RyanMitchellGamesParticipant]

Thank you a ton Sigil with your sample code I had it up and running in 30 minutes and adapted to my generation systems… GREAT! I was expecting hours and hours of testing debugging figuring things out. Most helpful post ever in the saving time category.

Thanks!

One Last Question, do you guys have a logo I can drop in my standard screen shot? I would love to advertise RAIN so far I love it.

I looked for one and could not find one.. I could make one if there is not one available…

RyanMitchellGames.WordPress.Com is where I reside most of the time

• This reply was modified 1 year, 10 months ago by  RyanMitchellGames.

[JesterKeymaster]

Hello Ryan!

Jester, here. Thanks so much for offering to place Rival Theory logo in your game!

Here is where we post our Rival Theory Media Kit for you to use.

http://rivaltheory.com/media-kit/

Let me know if you need anything else. We look forward to seeing your game as it progresses.

Best,
Jester

[RyanMitchellGamesParticipant]

Thanks again for all the hard work!

[Author]

Posts