CODEWITHSUNDEEP
c#unity-game-enginea-starnavmesh
Rob
Rob

Reputation: 61

Can Unity NavMesh be used to implement an A* algorithm?

I'm looking forward to use A* pathfinding for a game I'm working on. (I'm actually making a game for myself to learn about this). I am wondering how the Unity NavMesh can be used with a custom A* algorithm, instead of using a NavMeshAgent.

Upvotes: 6

Views: 2299

Answers (3)

Kastan Styrax
Kastan Styrax

Reputation: 11

I wanted to leave this as a comment on the other answer, but it seems you need 50 rep to do so. The other answer is mostly right, but after struggling for a few hours I realized that that's not actually how the polygon data is formatted.

polygons:
0 0
1 1
2 3
3 1
4 2
5 4

This is more like what you'd actually see, the number on the right isn't the polygon's number, but the vertice's index. The polygons are ordered by threes, so the first three entries are for polygon 1, the second three for polygon 2, etc. etc.

So this would indicate that polygon 1 consists of vertices 0, 1 and 3, polygon 2 consists of vertices 1, 2 and 4, etc. etc.

I have no idea if other meshes structure their data this way, but the navmesh definitely does. Once I realized it was ordered like this and adjusted my code accordingly, my attempts to visually recreate the navmesh went from a chaotic, scrambled mess to perfect order, so I'm 99% confident in this.

I hope someone finds that useful!

Edit:

For completeness sake, this is the code to convert navmesh data into a dictionary of Vector3 values you can use to very easily map out connections.

    var navMesh = NavMesh.CalculateTriangulation(); // get baked Navigation Mesh Data;
    Vector3[] vertices = navMesh.vertices;
    int[] polygons = navMesh.indices;

    Dictionary<Vector3, List<Vector3>> verticeConnections = new Dictionary<Vector3, List<Vector3>>();

    for (int i = 2; i < polygons.Length; i+=3)
    {
        //Polygons come clumped in threes
        Vector3 vert1 = vertices[polygons[i - 2]];
        Vector3 vert2 = vertices[polygons[i-1]];
        Vector3 vert3 = vertices[polygons[i]];

        if (!verticeConnections.ContainsKey(vert1))
        {
            verticeConnections.Add(vert1, new List<Vector3>());
        }
        verticeConnections[vert1].Add(vert2);
        verticeConnections[vert1].Add(vert3);

        if (!verticeConnections.ContainsKey(vert2))
        {
            verticeConnections.Add(vert2, new List<Vector3>());
        }
        verticeConnections[vert2].Add(vert1);
        verticeConnections[vert2].Add(vert3);

        if (!verticeConnections.ContainsKey(vert3))
        {
            verticeConnections.Add(vert3, new List<Vector3>());
        }
        verticeConnections[vert3].Add(vert2);
        verticeConnections[vert3].Add(vert1);
}

Upvotes: 1

Sinan Onur ALTINU&#199;
Sinan Onur ALTINU&#199;

Reputation: 31

You can do the following:

var navMesh = NavMesh.CalculateTriangulation() // get baked Navigation Mesh Data;
Vector3[] vertices = navMesh.vertices;
int[] polygons = navMesh.indices;

vertices (obviously) are the vertices of your navigation mesh indicated by their position in unity space. The meshes are defined by polygons. The polygon array shows which vertice belongs to which polygon.

polygons:
0 0
1 0
2 1
3 1
4 0
5 1

This array would indicate that vertices with indices 0,1,4 belongs to polygon number 0 and vertices with indices 2,3,5 belongs to polygon number 1.

There you have your navmesh as polygons. You can define your search graph and run the search algorithm of your choice.

Upvotes: 3

Draco18s no longer trusts SE
Draco18s no longer trusts SE

Reputation: 15951

No

Or at least, not easily (why would you want to?).

Unity's builtin NavMesh is intended to be used by Unity's builtin NavMeshAgent utilizing a builtin pathfinder. I don't know what algorithm it uses, but A* implementations typically operate on networks. That is, nodes connected by edges. It does not consider the interior volume (the mesh 'faces').

As Unity's builtins are intended to be used as such, it is very difficult to get access to any of the information directly for use with your own pathfinding algorithms.

If you want to write your own pathfinder, then I recommend writing your own mesh as well.

Upvotes: 3

Related Questions