Random Navmesh coordinate?

Hey, peeps.

I’m looking into updating my AI to make it less predictable. A key component to make this work is to get random navmesh positions, and then check if they’re inside trigger boxes that define zones.

Now, the question is… how do I get random navmesh positions?

As far as i know Unity doesn’t have a built-in function for choosing a random point on a navmesh. However you can use [NavMesh.CalculateTriangulation][1] to get the actual triangle mesh data and do it yourself. Since the triangles are not necessarily of equal size to get a uniform distribution you would first choose one triangle based on the relative area. Once a triangle is selected use the 3 corners and create a random point inside that triangle.

To calculate the area of a triangle just use the cross product between two side vectors, take the magnitude of the result and divide it in half. Sum up the area of all triangles to get the area of the whole nav mesh. Now simply roll a random number between 0 and the total area. Iterate through the triangle areas and keep subtracting the area of each triangle from the random number until the number is smaller or equal to 0. The current triangle will be our selected triangle

To get a random point inside the triangle just calculate two random numbers between 0 and 1. If the sum of those numbers is greater than 1, subtract both numbers from 1 to ensure their sum is below or equal to 1. Now just use the two number to scale two of the side vectors of the triangle.

Something like this:

var meshData = NavMesh.CalculateTriangulation();
var verts = meshData.vertices;
var indices = meshData.indices;
int triCount = indices.Length / 3;
float[] triArea = new float[triCount];
float totalArea = 0f;
for(int i = 0; i < triArea.Length; i++)
    var v1 = verts[indices[i*3]];
    var v2 = verts[indices[i*3 + 1]];
    var v3 = verts[indices[i*3 + 2]];
    float a = Vector3.Cross(v2-v1, v3-v1).magnitude * 0.5f;
    triArea *= a;*

totalArea += a;

// choose weighted triangle
float num = Random.Range(0f, totalArea);
int triangle = 0;
while(triangle < triArea.Length && num >= 0)
num -= triArea[triangle];
triangle–; // undo last increment

// choose random point
var p1 = verts[indices[triangle*3]];
var p2 = verts[indices[triangle*3 + 1]];
var p3 = verts[indices[triangle*3 + 2]];

float f1 = Random.Range(0f,1f);
float f2 = Random.Range(0f,1f);
if (f1 + f2 > 1f) // map the second half of the parallelogram into the first half
f1 = 1f - f1;
f2 = 1f - f2;

var point = p1 + (p2-p1)*f1 + (p3-p1)*f2;
Of course if you plan to get a random point more than once you may want to cache the mesh and area data. Keep in mind that a Navmesh might have seperate areas. The mesh data contains the [areas array][2] which contains an area index for each triangle. If you want to get a random point in just one area you have to calculate the total area of only those triangles you want to include.
[1]: Unity - Scripting API: AI.NavMesh.CalculateTriangulation
[2]: Unity - Scripting API: AI.NavMeshTriangulation.areas