AI navigation in randomly generated level

[CriticalMammalParticipant]

Hi, I’m trying to work out from other posts here on the forums how to get my navigation mesh working in a random generated layout. I looked through the existing questions and found this helpful post: Strategy for randomly generated levels

I’ve read through both that and the supplemental links provided by Sigil and feel like I’m going the right direction, but can’t quite seem to get it functioning. Basically, right now I have some rooms pre-made and I spawn them side-by-side so their exits/entrances line up. I want the AI to be able to navigate across each room like its all one mesh essentially. I have the Rain navigation meshes already generated on each room prefab, and when I create the layout I use the code provided Here to merge the other room meshes into the first room’s navmesh. I updated the depreciated ContourMeshData stuff with PolyMeshData stuff and that part seems to work. So I have one big mesh attached to the first room’s “Navigation” child object.

The large mesh has gaps between, because of the walkable radius with the generated meshes. So I tried to implement the “poor man’s mesh link” found Here. But I started getting some errors that I’m not entirely sure how to fix, which seem to stem from depreciated/old code.

Here’s an image to show off the current progress.
There’s the navmesh gap, the navlinks are pretty difficult to make out, but they’re on each edge of the gap. And the temporary AI blockman of course, timidly peering over. You’ll notice I have an error for a null reference exception which I get on this line of the code:

int tNodeTwo = _ourNavMesh.NavMesh.Graph.QuantizeToNode(_otherLink.gameObject.transform.position, 0).NodeIndex;

The NodeIndex part is apparently now obsolete, but this does work for the first node. I only get the null ref error on the second node, the one that’s supposed to be connecting to the second navmesh link. So I’m guessing that even though I stitched together the nav meshes previously the navlink doesn’t recognize the new area or something. Or maybe its just the obsolete NodeIndex not functioning correctly anymore.

I’d appreciate any help I can get with this. I’ve spent the past two days fiddling with it and referencing the forum posts but I think this problem has gone a bit over my head at this point. I hope there are enough details here to pick apart some kind of answer, if any more info is needed I’d be glad to tack on more details.

[SigilKeymaster]

I’m happy to see you got as far as you did. Definitely not easy code for the most part, and some of it is pretty old.

I’m in the middle of something at the moment, but I’ll take a quick look at the link code and see if I can’t bring it up to the latest RAIN later tonight.

[CriticalMammalParticipant]

Sounds great, thanks for dropping in real quick to let me know.

[SigilKeymaster]

Here is an updated Link to work with the RAIN out there today (just a heads up its changing some more, but I’ll make sure this still works outside of deprecations):

using UnityEngine;
using System.Collections;
using RAIN.Navigation.NavMesh;
using RAIN.Navigation.Graph;
public class Link : MonoBehaviour
{
    [SerializeField]
    private NavMeshRig _ourNavMesh = null;
    [SerializeField]
    private Link _otherLink = null;
    private bool _connected = false;
    void Start()
    {
        if (_ourNavMesh == null || _otherLink == null)
        {
            Debug.LogWarning("Navigation mesh or other link is unassigned");
            return;
        }
        if (_connected)
            return;
        _connected = true;
        _otherLink._connected = true;
        NavigationGraphNode tNodeOne = _ourNavMesh.NavMesh.Graph.QuantizeToNode(gameObject.transform.position, 0);
        NavigationGraphNode tNodeTwo = _ourNavMesh.NavMesh.Graph.QuantizeToNode(_otherLink.gameObject.transform.position, 0);
        if (tNodeOne == null || tNodeTwo == null)
        {
            Debug.LogWarning("Links not on navigation mesh");
            return;
        }
        NavMeshPoly tPolyOne = (NavMeshPoly)tNodeOne;
        NavMeshPoly tPolyTwo = (NavMeshPoly)tNodeTwo;
        NavMeshEdge tEdgeOne = GetClosestEdge(tPolyOne, tPolyTwo);
        NavMeshEdge tEdgeTwo = GetClosestEdge(tPolyTwo, tPolyOne);
        if (tEdgeOne == null || tEdgeTwo == null)
        {
            Debug.LogWarning("Couldn't find edge to connect");
            return;
        }
        float tConnectCost = (tEdgeOne.Center - tEdgeTwo.Center).magnitude;
        NavigationGraphEdge tOneWay = new NavigationGraphEdge(tEdgeOne, tEdgeTwo, tConnectCost);
        tEdgeOne.AddEdgeOut(tOneWay);
        tEdgeTwo.AddEdgeIn(tOneWay);
        NavigationGraphEdge tOtherWay = new NavigationGraphEdge(tEdgeTwo, tEdgeOne, tConnectCost);
        tEdgeTwo.AddEdgeOut(tOtherWay);
        tEdgeOne.AddEdgeIn(tOtherWay);
        Debug.Log("Added connection from node " + gameObject.name + " to " + _otherLink.gameObject.name);
    }
    void OnDrawGizmos()
    {
        Gizmos.matrix = Matrix4x4.identity;
        Gizmos.color = Color.white;
        Gizmos.DrawWireSphere(gameObject.transform.position, 0.5f);
        if (_ourNavMesh != null && _otherLink != null)
            Gizmos.DrawLine(gameObject.transform.position, _otherLink.gameObject.transform.position);
    }
    void OnValidate()
    {
        if (_otherLink != null)
        {
            _otherLink._otherLink = this;
            _otherLink._ourNavMesh = _ourNavMesh;
        }
    }
    NavMeshEdge GetClosestEdge(NavMeshPoly aNodeOne, NavMeshPoly aNodeTwo)
    {
        float tClosestDist = float.MaxValue;
        NavMeshEdge tClosestEdge = null;
        for (int i = 0; i < aNodeOne.EdgeCount; i++)
        {
            NavMeshEdge tEdge = aNodeOne.GetEdgeNode(i);
            if (tEdge.PolyCount == 2)
                continue;
            float tDist = (tEdge.Center - aNodeTwo.Center).magnitude;
            if (tDist < tClosestDist)
            {
                tClosestDist = tDist;
                tClosestEdge = tEdge;
            }
        }
        return tClosestEdge;
    }
}

The error you were getting in the Start() call likely was stopping the code from finishing the graph connection, which would explain the AI stopping. If this throws another error come back and post it so that I can see what line is causing the problem.

[CriticalMammalParticipant]

Alright, so now it’s just throwing me a warning “Links not on navigation mesh”, which is pretty much telling me something is going on with the meshes themselves that’s causing one of the links to not recognize that they are merged. I tested it further and created both of the navigation links in the original room’s mesh area and I don’t get any warnings or anything. So it seems like the code you posted above is working perfectly fine!

I also set up a test in-scene with no randomly spawned objects and just one big mesh to figure out if I could get something simple working. I was getting strange results (without using the navigation links at all) where the AI would try to navigate through areas that were supposed to be non-navigable. This was bizarre because it was taking into consideration the other boundaries of the navmesh like the walls of the room.

I think I’m going to try and create a simplified version of what I’m doing and send over those files tomorrow so that you can have a more hands on look at things. I may also find a partially working solution in the process, who knows.

• This reply was modified 8 months, 3 weeks ago by  CriticalMammal.

[SigilKeymaster]

Yes, let me know. A sample project always makes things easier to figure out on my end.

The “Links not on navigation mesh” might be a timing issue. The link attempts to connect itself on Start() so if your Navigation Mesh combines itself afterwards you would likely see this issue. You could change the Start() to an Update() instead and have it try to connect forever. You’d have to rework the code a little bit, move the check for it being on a Navigation Mesh above _connect = true part at the least.

[CriticalMammalParticipant]

Okay, so I put together a little example project of what’s going on. The scene is in Assets/Scenes.

Navigation example project

Yeah so I did change that navlink code previously so that I call an init() function whenever I had everything setup so I don’t think that was the issue. I changed it in this example so they try to connect in the Update() loop as you suggested, just to be super extra sure haha.

Hopefully it’s not too hard to pick apart and figure out. I put in both a randomly generated example and a manually put together test, the manual test is in a empty game object that’s deactivated initially. Make sure you disable the random gen test if you activate the manual one. I couldn’t get either to function correctly, so the problem could be something I’m doing outside of the code.

Also the randomly generated test really isn’t very random, I only spawn in one kind of room here and there are some values in the LevelGen.cs code that are specific to this setup… like offset values and whatnot.

[SigilKeymaster]

Sorry it took me awhile to get back to this. I’ll take a look at the scene in the morning and see if I can figure out what’s happening.

[CriticalMammalParticipant]

There’s no rush, I’ve gotten busy this past week and haven’t had a ton of time to put into this project I’m working on so the delay hasn’t been holding me up or anything. Still excited to figure out this navmesh stuff though, it’s been on my mind a lot.

[SigilKeymaster]

Well I’m glad it hasn’t held you up, as I also got very busy and couldn’t get back to this until now. I took a look at the project, and found some bugs/issues with the navigation mesh creation that was causing the last problems.

You can remove the init from your update loop as well, given the way you changed it you have guaranteed that you don’t add links until after the fact, so it should start to work after these changes. I removed some of the things it didn’t need for this post, and commented up what I did. All the real changes happened in CombineNavMesh though, so if you just grab that you should be good:

using RAIN.Navigation.NavMesh;
using RAIN.Navigation.NavMesh.RecastNodes;
using System.Collections.Generic;
using UnityEngine;
// This class manually stitches together two navigation meshes, it also
// creates a navigation link between the two meshes from the original's exitAnchor
// to the second mesh's entranceAnchor.
public class ManualNavMesh : ScriptableObject
{
    public GameObject _meshObject = null;
    public NavMeshRig _otherNavMesh = null;
    public Vector3 exitAnchor;
    public Vector3 entranceAnchor;
    private NavMeshRig _navMeshRig = null;
    public ManualNavMesh(GameObject mesh, NavMeshRig otherNav)
    {
        _meshObject = mesh;
        _otherNavMesh = otherNav;
    }
    public void Init()
    {
        _navMeshRig = _meshObject.GetComponent<NavMeshRig>();
        if (_navMeshRig == null)
            return;
        if (_otherNavMesh != null)
        {
            CombineNavMesh();
            AddNavLink();
        }
    }
    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);
        // Transforms were added since the original of this, so vertices are always in local space, so you need to
        // transform them to world space (first MultiplyPoint) then back into the local space of the navigation mesh
        // we are heading to (second MultiplyPoint). I will likely change the AddPolyMesh to transform those points
        // in the next release of RAIN, so the second half of this won't be necessary at that point.
        for (int i = 0; i < tOtherVertices.Count; i++)
        {
            tOtherVertices[i] = _otherNavMesh.NavMesh.Graph.MountTransform.MultiplyPoint(tOtherVertices[i]);
            tOtherVertices[i] = _navMeshRig.NavMesh.Graph.MountInverseTransform.MultiplyPoint(tOtherVertices[i]);
        }
        // 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(GetPoly(tPoly));
            tOtherTriangles.Add(GetTriangles(tPoly));
        }
        // Don't need the old graph anymore
        _otherNavMesh.NavMesh.ClearNavigationGraph();
        PolyMeshData tNewData = new PolyMeshData()
        {
            Vertices = tOtherVertices.ToArray(),
            Polys = tOtherContours.ToArray(),
            Triangles = tOtherTriangles.ToArray()
        };
        // Here we also need to compact the navigation mesh, I can't recall why this wasn't
        // necessary in the previous version, but it is now.  Compacting removes any duplicate
        // vertices (none in this case since they were both valid navigation meshes) and also
        // consolidates all of the edges of the recently added polys.
        _navMeshRig.NavMesh.Graph.AddPolyMesh(tNewData);
        _navMeshRig.NavMesh.Graph.CompactNavMesh();
        // This is an issue.  The current mesh has been initialized, which means it has connections
        // on its current polys, we need those to go away.  Duplicate connections won't break the
        // graph, just eat up memory for the most part.  Better to handle it here.  Will probably
        // fix this in the next version as well.
        for (int i = 0; i < _navMeshRig.NavMesh.Graph.Size; i++)
        {
            NavMeshPoly tPoly = _navMeshRig.NavMesh.Graph.GetNode(i) as NavMeshPoly;
            if (tPoly == null)
                continue;
            tPoly.DisconnectAllEdges();
        }
        // Another missing point, once the graph has been initialized nothing will cause it to
        // be initialized again (even though the graph has changed).  This is a bug though so 
        // it will also be fixed in the next version (likely)
        _navMeshRig.NavMesh.Graph.Init();
        // 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;
    }
    public void AddNavLink()
    {
        GameObject navLink1 = new GameObject();
        GameObject navLink2 = new GameObject();
        navLink1.name = "NavLink1";
        navLink2.name = "NavLink2";
        Vector3 exitOffset = exitAnchor;
        Vector3 entranceOffset = entranceAnchor;
        exitOffset.z -= 1.5f; // 1.5f
        entranceOffset.z += 1.5f;
        navLink1.transform.position = exitOffset;
        navLink2.transform.position = entranceOffset;
        navLink1.AddComponent<Link>();
        navLink2.AddComponent<Link>();
        navLink1.GetComponent<Link>()._ourNavMesh = _navMeshRig;
        navLink2.GetComponent<Link>()._ourNavMesh = _navMeshRig;
        navLink1.GetComponent<Link>()._otherLink = navLink2.GetComponent<Link>();
        navLink2.GetComponent<Link>()._otherLink = navLink1.GetComponent<Link>();
        Debug.Log("navlink1 starting init");
        navLink1.GetComponent<Link>().init();
        Debug.Log("navlink1 initialized");
        Debug.Log("navlink2 starting init");
        navLink2.GetComponent<Link>().init();
        Debug.Log("navlink2 initialized");
    }
    private int[] GetPoly(NavMeshPoly aPoly)
    {
        int[] tWinding = new int[aPoly.ContourCount];
        for (int i = 0; i < tWinding.Length; i++)
            tWinding[i] = aPoly.GetContour(i);
        return tWinding;
    }
    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;
    }
}

A few things were just growing pains (transforms were added to navigation meshes, some changes to the way the mesh is put together, etc). A couple things were bugs/issues with this kind of creation, that I have noted for fixing.

Let me know how it works out for you.

[CriticalMammalParticipant]

Wow, well I just quickly swapped out the old code with your newly posted stuff and it seems to be working! I haven’t really looked at the code in detail yet, just did a quick dump to see if it’d work with the current setup and everything seems to be going smoothly. I’ll post back if something else crops up or if I have trouble expanding it, though I feel like this should do the trick and get me going.

Thanks a ton for taking out all the time to figure out a solution for this. And your timing was excellent too btw, I just decided to pick up work on the project again today haha.

[RyanMitchellGamesParticipant]

I just wanted to say thanks for this code Sigil it helped me immensely. I was able to plop it right in and add about 6 lines of code and it just magically worked!… Back to testing!

Thanks again you guys are awesome.

[Author]

Posts