Best method to set a random position on NavMesh? (c#)

Hello!

Some time ago, I wrote a little method that finds and returns a random point on a plane or terrain the renderer.bounds.size-way. I use it to randomize my navMeshAgents destinations, to make them move here and there for mecanim calibration purposes, but the problem with this method is, that it is cumbersome to set up non-quadratic (and soon randomly generated) areas, so, a way to return a random position directly from the navmesh itself would be a true relief!

After a little research, I found this in the internet (unaltered copy):

 import UnityEngine
     
    class NavMeshVis (MonoBehaviour):
     
        [SerializeField] meshFilter as MeshFilter
     
        def Start ():
            verts as (Vector3)     
            ids as (int)
           
            NavMesh.Triangulate(verts, ids)
           
            mesh = Mesh()
            mesh.vertices = verts
            mesh.triangles = ids
            meshFilter.mesh = mesh

To see what’s going on, I translated it to c#:

using UnityEngine;

public class NavMeshManager : MonoBehaviour {

    [SerializeField]
    MeshFilter meshFilter;

    void Start()
    {
        Vector3[] verts = NavMesh.CalculateTriangulation().vertices;
        int[] ids = NavMesh.CalculateTriangulation().indices;

        Mesh mesh = new Mesh();
        mesh.vertices = verts;
        mesh.triangles = ids;
        meshFilter.mesh = mesh;
    }
}

I must admit, I don’t have a clue on what this script does, but I guess it creates a mesh in the shape of the currently baked navmesh dimensions and makes it editable? And do I need to attach it to a gameobject?

Or does anyone know a better way to get a random point on the navmesh during runtime?

Any help is greatly appreciated!

Greetings!

The code that you found and translated to C# essentially converts a NavMesh into a regular [Mesh][1], and puts that Mesh in any MeshFilter. Whichever MeshFilter this object holds as a reference will then display the converted NavMesh (assuming it has a MeshFilterer).

Converting this to a Mesh could still be a useful first step, as you can use this to calculate a random point on the mesh. This would also be a random point on the NavMesh.

There is a thread on gamedev.net about [evenly distributing points on a triangle mesh][2]. This thread is fairly relevant for you, since you have a triangle mesh and want to generate a random point. It’s not perfectly relevant, since the Katachi’s question is actually about generating something close to a regular structure. For a random point I’d recommend following osmanb’s advice:

  1. Compute the area of each triangle in the mesh, sum them to get the complete surface area.
  2. Construct a list of normalized area weights for each triangle: (AreaOfTriangle / TotalSurfaceArea).
  3. For each point you generate
  4. Generate a random number ‘r’ (float) in [0,1]
  5. Walk through the list of weights, accumulating weight until the total is <= r
  6. Generate a random point on the surface of the selected triangle. (Via randomized barycentric coordinates or similar).

Here’s a quick code sample I threw together that does will generate a random point on a given Mesh that follows osmanb’s approach. I’ve written the code here focused especially on simplicity and understandability, rather than performance. If you’re going to be doing this a lot every frame, you’ll probably want to think a little bit about the performance (there are, for example, a lot of float array copies that aren’t needed).

private Vector3 GenerateRandomPoint(Mesh mesh)
	{
		// 1 - Calculate Surface Areas
		float[] triangleSurfaceAreas = CalculateSurfaceAreas(mesh);

		// 2 - Normalize area weights
		float[] normalizedAreaWeights = NormalizeAreaWeights(triangleSurfaceAreas);

		// 3 - Generate 'triangle selection' random #
		float triangleSelectionValue = Random.value;

		// 4 - Walk through the list of weights to select the proper triangle
		int triangleIndex = SelectRandomTriangle(normalizedAreaWeights, triangleSelectionValue);

		// 5 - Generate a random barycentric coordinate
		Vector3 randomBarycentricCoordinates = GenerateRandomBarycentricCoordinates();

		// 6 - Using the selected barycentric coordinate and the selected mesh triangle, convert
		//     this point to world space.
		return ConvertToLocalSpace(randomBarycentricCoordinates, triangleIndex, mesh);
	}

	private float[] CalculateSurfaceAreas(Mesh mesh)
	{
		int triangleCount = mesh.triangles.Length / 3;

		float[] surfaceAreas = new float[triangleCount];


		for (int triangleIndex = 0; triangleIndex < triangleCount; triangleIndex++)
		{
			Vector3[] points = new Vector3[3];
			points[0] = mesh.vertices[mesh.triangles[triangleIndex * 3 + 0]];
			points[1] = mesh.vertices[mesh.triangles[triangleIndex * 3 + 1]];
			points[2] = mesh.vertices[mesh.triangles[triangleIndex * 3 + 2]];

			// calculate the three sidelengths and use those to determine the area of the triangle
			// http://www.wikihow.com/Sample/Area-of-a-Triangle-Side-Length
			float a = (points[0] - points[1]).magnitude;
			float b = (points[0] - points[2]).magnitude;
			float c = (points[1] - points[2]).magnitude;

			float s = (a + b + c) / 2;

			surfaceAreas[triangleIndex] = Mathf.Sqrt(s*(s - a)*(s - b)*(s - c));
		}

		return surfaceAreas;
	}

	private float[] NormalizeAreaWeights(float[] surfaceAreas)
	{
		float[] normalizedAreaWeights = new float[surfaceAreas.Length];

		float totalSurfaceArea = 0;
		foreach (float surfaceArea in surfaceAreas)
		{
			totalSurfaceArea += surfaceArea;
		}

		for (int i = 0; i < normalizedAreaWeights.Length; i++)
		{
			normalizedAreaWeights _= surfaceAreas */ totalSurfaceArea;*_

* }*

* return normalizedAreaWeights;*
* }*

* private int SelectRandomTriangle(float[] normalizedAreaWeights, float triangleSelectionValue)*
* {*
* float accumulated = 0;*

* for (int i = 0; i < normalizedAreaWeights.Length; i++)*
* {*
_ accumulated += normalizedAreaWeights*;*_

* if (accumulated >= triangleSelectionValue)*
* {*
* return i;*
* }*
* }*

* // unless we were handed malformed normalizedAreaWeights, we should have returned from this already.*
* throw new System.ArgumentException(“Normalized Area Weights were not normalized properly, or triangle selection value was not [0, 1]”);*
* }*

* private Vector3 GenerateRandomBarycentricCoordinates()*
* {*
* Vector3 barycentric = new Vector3(Random.value, Random.value, Random.value);*

* while (barycentric == Vector3.zero)*
* {*
* // seems unlikely, but just in case…*
* barycentric = new Vector3(Random.value, Random.value, Random.value);*
* }*

* // normalize the barycentric coordinates. These are normalized such that x + y + z = 1, as opposed to*
* // normal vectors which are normalized such that Sqrt(x^2 + y^2 + z^2) = 1. See:*
* // Barycentric coordinate system - Wikipedia*
* float sum = barycentric.x + barycentric.y + barycentric.z;*

* return barycentric / sum;*
* }*

* private Vector3 ConvertToLocalSpace(Vector3 barycentric, int triangleIndex, Mesh mesh)*
* {*
* Vector3[] points = new Vector3[3];*
_ points[0] = mesh.vertices[mesh.triangles[triangleIndex * 3 + 0]];
points[1] = mesh.vertices[mesh.triangles[triangleIndex * 3 + 1]];
points[2] = mesh.vertices[mesh.triangles[triangleIndex * 3 + 2]];_

_ return (points[0] * barycentric.x + points[1] * barycentric.y + points[2] * barycentric.z);
* }
[1]: http://docs.unity3d.com/Documentation/ScriptReference/Mesh.html*_

_*[2]: http://www.gamedev.net/topic/602405-evenly-distribute-points-on-a-triangle-mesh/*_

Or, you could use your old method to generate a random point on a plane “the renderer.bounds.size-way”, based on the extents of your NavMesh. Then, use NavMesh.SamplePosition to return the closest point on the NavMesh to the chosen point.

Something like:

position = new Vector3(Random.Range(-1000f,1000f), 0, Random.Range(-1000f, 1000f));
NavMeshHit hit;
NavMesh.SamplePosition(position, out hit, 10, 1);
position = hit.position;

Well, this is my solution, pretty simple and very functional, at least for my needs, maybe other gets help with this:

public Vector3 RandomPoint()
{
    if(navMesh == null)
    {
        NavMeshTriangulation triangulatedNavMesh = NavMesh.CalculateTriangulation();
        navMesh = new Mesh();
        navMesh.vertices = triangulatedNavMesh.vertices;
    }
    Debug.Log(navMesh.triangles.Length+" "+navMesh.vertexCount);
    Vector3 point1 = navMesh.vertices[Random.Range(0,navMesh.vertexCount)];
    Vector3 point2 = navMesh.vertices[Random.Range(0, navMesh.vertexCount)];

    return Vector3.Lerp(point1, point2, Random.value);
}