how to create a dynamic area cast in navmesh

Mortalanimal · Dec 11, 2019

Hi,

How do I Increase the area cost of my navmesh in a radius under my navmeshagent at runtime. Ideally I would also like the ability to remove this area cost back to default also.

Thanks in advance

Abbrew · Dec 12, 2019

I made a Monobehaviour that dynamically assigns area types to sections of the navmesh. You do this by calling NavMesh.UpdateAsync, which accepts a list of NavMeshBuildSource. NavMeshBuildSource are volumes that, when intersecting with a NavMesh, modify that area type within the intersection plane. Each Update loop, create a NavMeshBuildSource that's a ModifierBox type centered on the NavMeshAgent. Call NavMesh.UpdateAsync using this ModifierBox, and the NavMesh will weigh the area around the NavMeshAgent accordingly. You can either write your own implementation, or you can use this code:

Code (CSharp):

using UnityEngine;

using UnityEngine.AI;

using Unity.Entities;

using Unity.Jobs;

using Unity.Collections;

using Unity.Mathematics;

using System.Collections.Generic;

using Unity.Burst;

using Unity.Physics;

using Unity.Physics.Systems;

using UnityEngine.Experimental.AI;

public class NavMeshBuilderGrid : MonoBehaviour

{

[Header("User")]

[SerializeField]

private int agentType;

[SerializeField]

private float agentRadius;

[SerializeField]

private float agentStepHeight;

[SerializeField]

private float agentSlope;

[SerializeField]

private float agentHeight;

[Header("Map")]

[SerializeField]

private LayerMask includedLayers;

[SerializeField]

private Bounds gridBounds;

[SerializeField]

private int tileSize;

[SerializeField]

private float voxelRadius;

[SerializeField]

private float chunkLength;

[Header("Debug")]

[SerializeField]

private bool showBounds = true;

private bool ready;

private float heightOfEnvironment;

private float middleOfEnvironment;

private PhysicsConverter chunkConverter;

private int xChunkGridLength;

private int yChunkGridLength;

private EntityManager em;

private NavMeshChunk[,] grid;

private NavMeshLinkInstance[] links;

private Dictionary<int, List<NavMeshBuildSource>> chunkToCells;

private NavMeshBuildSettings buildSettings;

private static NavMeshBuilderGrid instance;

public static List<AsyncOperation> AllocateModifiers(

NativeMultiHashMap<int, float2x2> areaTypeModifierVolumes

)

{

// clear the reusable data structure

var chunkToCellLength = instance.chunkToCells.Count;

for (var i = 0; i < chunkToCellLength; i++)

{

instance.chunkToCells[i].Clear();

}

var physicsData = Physics.GetPhysics().GetData();

var topOfEnvironment = physicsData.GetBottomLeftCorner().y + physicsData.GetDimensions().y;

var bottomOfEnvironment = physicsData.GetBottomLeftCorner().y;

var middleOfEnvironment = (topOfEnvironment + bottomOfEnvironment) / 2;

var heightOfEnvironment = topOfEnvironment - bottomOfEnvironment;

var cellDefinitions = new List<CellDefinition>();

for (var i = 0; i < NavMeshAreas.GetNumAreaTypes(); i++)

{

var areaType = i;

if (areaTypeModifierVolumes.TryGetFirstValue(

areaType,

out var volumeDim,

out var it

))

{

var ll = volumeDim.c0;

var ur = volumeDim.c1;

instance.AddToChunk(

areaType,

ll,

ur

);

while (areaTypeModifierVolumes.TryGetNextValue(out volumeDim, ref it))

{

ll = volumeDim.c0;

ur = volumeDim.c1;

instance.AddToChunk(

areaType,

ll,

ur

);

}

}

}

var operations = new List<AsyncOperation>();

var chunkGridDimX = instance.grid.GetLength(0);

var chunkGridDimY = instance.grid.GetLength(1);

for (var i = 0; i < chunkGridDimX; i++)

{

for (var j = 0; j < chunkGridDimY; j++)

{

var currentSources = instance.chunkToCells[(i * chunkGridDimY) + j];

// only update if cells are in the chunk

if(currentSources.Count == 0)

{

continue;

}

var currentChunk = instance.grid[i,j];

var currentAllSources = new List<NavMeshBuildSource>();

currentAllSources.AddRange(currentSources);

currentAllSources.AddRange(currentChunk.staticSources);

operations.Add(

NavMeshBuilder.UpdateNavMeshDataAsync(

currentChunk.data,

instance.buildSettings,

currentAllSources,

currentChunk.data.sourceBounds

)

);

}

}

return operations;

}

private void AddToChunk(int areaType, float2 ll, float2 ur)

{

var cellLocation = (ll + ur) / 2;

var cellLocation4x4 = Matrix4x4.Translate(cellLocation.To3D(middleOfEnvironment));

var cellRadii = (ur - ll) / 2;

var cellDiameter = cellRadii * 2;

var cell = new NavMeshBuildSource

{

size = new Vector3(cellDiameter.x, heightOfEnvironment, cellDiameter.y),

area = areaType,

transform = cellLocation4x4,

shape = NavMeshBuildSourceShape.ModifierBox

};

var llChunk = chunkConverter.ToGridCoord(ll);

var urChunk = chunkConverter.ToGridCoord(ur);

var top = urChunk.y;

var bottom = llChunk.y;

var right = urChunk.x;

var left = llChunk.x;

var gridHeight = grid.GetLength(1);

for (var i = left; i <= right; i++)

{

for (var j = bottom; j <= top; j++)

{

chunkToCells[(i * gridHeight) + j].Add(cell);

}

}

}

private struct CellDefinition

{

public float2 location;

public float2 radii;

public int areaType;

}

private void Awake()

{

instance = this;

em = World.Active.EntityManager;

}

private void OnEnable()

{

var topOfEnvironment = gridBounds.center.y + gridBounds.extents.y;

var bottomOfEnvironment = gridBounds.center.y - gridBounds.extents.y;

middleOfEnvironment = (topOfEnvironment + bottomOfEnvironment) / 2;

heightOfEnvironment = topOfEnvironment - bottomOfEnvironment;

xChunkGridLength = (int)Mathf.Ceil(gridBounds.size.x / chunkLength);

yChunkGridLength = (int)Mathf.Ceil(gridBounds.size.z / chunkLength);

buildSettings = NavMesh.CreateSettings();

buildSettings.agentTypeID = agentType;

buildSettings.overrideVoxelSize = true;

buildSettings.voxelSize = voxelRadius;

buildSettings.overrideTileSize = true;

buildSettings.tileSize = tileSize;

buildSettings.agentRadius = agentRadius;

buildSettings.agentClimb = agentStepHeight;

buildSettings.agentSlope = agentSlope;

buildSettings.agentHeight = agentHeight;

GenerateNavMeshGrid(buildSettings);

GenerateLinks(buildSettings);

}

private void GenerateNavMeshGrid(NavMeshBuildSettings settings)

{

var nodeRadius = chunkLength / 2;

chunkConverter = new PhysicsConverter(

gridBounds.center - gridBounds.extents,

nodeRadius

);

grid = new NavMeshChunk[xChunkGridLength, yChunkGridLength];

var gridArea = xChunkGridLength * yChunkGridLength;

for(var i = 0; i < xChunkGridLength; i++)

{

for (var j = 0; j < yChunkGridLength; j++)

{

var staticSources = new List<NavMeshBuildSource>();

var currentCenter =

chunkConverter.ToWorldCoord(

new int2(i, j)

).To3D(middleOfEnvironment);

var currentBounds = new Bounds

{

center = Vector3.zero,

size = new Vector3(chunkLength, heightOfEnvironment, chunkLength)

};

NavMeshBuilder.CollectSources(

currentBounds,

includedLayers,

NavMeshCollectGeometry.RenderMeshes,

0,

new List<NavMeshBuildMarkup>(),

staticSources

);

var data = NavMeshBuilder.BuildNavMeshData(

settings,

staticSources,

currentBounds,

currentCenter,

Quaternion.identity

);

var reference = NavMesh.AddNavMeshData(data);

grid[i, j] = new NavMeshChunk

{

data = data,

reference = reference,

staticSources = staticSources

};

}

}

var cellDiameter = NavMeshQueryScheduler.GetAgentModifierCellRadius() * 2;

var xCellGridDim = (int)(gridBounds.size.x / cellDiameter);

var yCellGridDim = (int)(gridBounds.size.z / cellDiameter);

var maxCells = xCellGridDim * yCellGridDim;

var reasonableMaxCellsPerChunk = (maxCells /(gridArea * 50));

chunkToCells = new Dictionary<int, List<NavMeshBuildSource>>(gridArea);

for(var i = 0; i < gridArea; i++)

{

chunkToCells.Add(i, new List<NavMeshBuildSource>(reasonableMaxCellsPerChunk));

}

}

private struct NavMeshChunk

{

public NavMeshData data;

public NavMeshDataInstance reference;

public List<NavMeshBuildSource> staticSources;

}

private void GenerateLinks(

NavMeshBuildSettings settings

)

{

var physics = Physics.GetPhysics().GetData();

var world = World.Active.GetOrCreateSystem<BuildPhysicsWorld>().PhysicsWorld.CollisionWorld;

var horizontalDistanceBetweenLinks =

(settings.agentRadius * 2) + (PhysicsMeasurements.METER * .1f);

var horizontalConverter = new PhysicsConverterAsymmetrical(

gridBounds.center - gridBounds.extents,

horizontalDistanceBetweenLinks / 2,

chunkLength / 2

);

var horizontalLinkWidthRadius = settings.agentRadius - (PhysicsMeasurements.METER * .1f);

var horizontalLinkLengthRadius = PhysicsMeasurements.METER * 2f;

var linksPerHorizontal =

(int)((gridBounds.center.x + gridBounds.extents.x) / horizontalDistanceBetweenLinks);

var numHorizontalLinks = yChunkGridLength * linksPerHorizontal;

var horizontalLinkStarts = new NativeArray<float3>(numHorizontalLinks, Allocator.TempJob);

var horizontalLinkEnds = new NativeArray<float3>(numHorizontalLinks, Allocator.TempJob);

var horizontalValidLinks = new NativeArray<bool>(numHorizontalLinks, Allocator.TempJob);

var horizontalHandle = new GenerateLinksHorizontalJob

{

linkLengthRadius = horizontalLinkLengthRadius,

converter = horizontalConverter,

linksPerHorizontal = linksPerHorizontal,

linkStarts = horizontalLinkStarts,

linkEnds = horizontalLinkEnds,

linkIsValid = horizontalValidLinks,

walkableLayers = includedLayers,

world = world,

topOfEnvironment = physics.GetTopOfEnvironment(),

bottomOfEnvironment = physics.GetBottomOfEnvironment()

}.Schedule(numHorizontalLinks, 128, default);

JobHandle.ScheduleBatchedJobs();

var verticalDistanceBetweenLinks =

(settings.agentRadius * 2) + (PhysicsMeasurements.METER * .1f);

var verticalConverter = new PhysicsConverterAsymmetrical(

gridBounds.center - gridBounds.extents,

chunkLength / 2,

verticalDistanceBetweenLinks / 2

);

var verticalLinkWidthRadius = settings.agentRadius - (PhysicsMeasurements.METER * .1f);

var verticalLinkLengthRadius = PhysicsMeasurements.METER * 2f;

var linksPerVertical =

(int)((gridBounds.center.y + gridBounds.extents.y) / verticalDistanceBetweenLinks);

var numVerticalLinks = xChunkGridLength * linksPerVertical;

var verticalLinkStarts = new NativeArray<float3>(numVerticalLinks, Allocator.TempJob);

var verticalLinkEnds = new NativeArray<float3>(numVerticalLinks, Allocator.TempJob);

var verticalValidLinks = new NativeArray<bool>(numVerticalLinks, Allocator.TempJob);

var verticalHandle = new GenerateLinksVerticalJob

{

linkLengthRadius = verticalLinkLengthRadius,

converter = verticalConverter,

linksPerVertical = linksPerVertical,

linkStarts = verticalLinkStarts,

linkEnds = verticalLinkEnds,

linkIsValid = verticalValidLinks,

walkableLayers = includedLayers,

world = world,

topOfEnvironment = physics.GetTopOfEnvironment(),

bottomOfEnvironment = physics.GetBottomOfEnvironment()

}.Schedule(numVerticalLinks, 128, default);

var inputDeps = JobHandle.CombineDependencies(horizontalHandle, verticalHandle);

NavMeshWorld.GetDefaultWorld().AddDependency(inputDeps);

inputDeps.Complete();

links = new NavMeshLinkInstance[numHorizontalLinks + numVerticalLinks];

for (var i = 0; i < numHorizontalLinks; i++)

{

if (horizontalValidLinks[i])

{

links[i] = NavMesh.AddLink(new NavMeshLinkData

{

width = horizontalLinkWidthRadius * 2,

startPosition = horizontalLinkStarts[i],

endPosition = horizontalLinkEnds[i],

agentTypeID = agentType,

area = 0,

bidirectional = true,

});

}

}

for (var i = 0; i < numVerticalLinks; i++)

{

if (verticalValidLinks[i])

{

links[numHorizontalLinks + i] = NavMesh.AddLink(new NavMeshLinkData

{

width = verticalLinkWidthRadius * 2,

startPosition = verticalLinkStarts[i],

endPosition = verticalLinkEnds[i],

agentTypeID = agentType,

area = 0,

bidirectional = true,

});

}

}

verticalLinkStarts.Dispose();

verticalLinkEnds.Dispose();

verticalValidLinks.Dispose();

horizontalLinkStarts.Dispose();

horizontalLinkEnds.Dispose();

horizontalValidLinks.Dispose();

}

[BurstCompile]

private struct GenerateLinksHorizontalJob : IJobParallelFor

{

public float linkLengthRadius;

public int linksPerHorizontal;

[WriteOnly]

public NativeArray<float3> linkStarts;

[WriteOnly]

public NativeArray<float3> linkEnds;

[WriteOnly]

public NativeArray<bool> linkIsValid;

[ReadOnly]

public CollisionWorld world;

public LayerMask walkableLayers;

public PhysicsConverterAsymmetrical converter;

public float topOfEnvironment;

public float bottomOfEnvironment;

public void Execute(int index)

{

var nodeX = index % linksPerHorizontal;

var nodeY = index / linksPerHorizontal;

var linkCenter = converter.ToWorldCoordNoOffset(new int2(nodeX, nodeY));

var linkTop = linkCenter + new float2(0, linkLengthRadius);

var linkTopLOSRequest = new LineOfSightRequest

{

start = linkTop.To3D(topOfEnvironment),

end = linkTop.To3D(bottomOfEnvironment),

};

var linkTopLOSResult = LineOfSightHelper.FindOne(

linkTopLOSRequest,

walkableLayers,

world

);

var linkBottom = linkCenter - new float2(0, linkLengthRadius);

var linkBottomLOSRequest = new LineOfSightRequest

{

start = linkBottom.To3D(topOfEnvironment),

end = linkBottom.To3D(bottomOfEnvironment),

};

var linkBottomLOSResult = LineOfSightHelper.FindOne(

linkBottomLOSRequest,

walkableLayers,

world

);

if (linkTopLOSResult.exists == 0 && linkBottomLOSResult.exists == 0)

{

linkIsValid[index] = true;

linkStarts[index] = linkTopLOSResult.point;

linkEnds[index] = linkBottomLOSResult.point;

}

}

}

[BurstCompile]

private struct GenerateLinksVerticalJob : IJobParallelFor

{

public float linkLengthRadius;

public int linksPerVertical;

[WriteOnly]

public NativeArray<float3> linkStarts;

[WriteOnly]

public NativeArray<float3> linkEnds;

[WriteOnly]

public NativeArray<bool> linkIsValid;

[ReadOnly]

public CollisionWorld world;

public LayerMask walkableLayers;

public PhysicsConverterAsymmetrical converter;

public float topOfEnvironment;

public float bottomOfEnvironment;

public void Execute(int index)

{

var nodeX = index / linksPerVertical;

var nodeY = index % linksPerVertical;

var linkCenter = converter.ToWorldCoordNoOffset(new int2(nodeX, nodeY));

var linkTop = linkCenter + new float2(linkLengthRadius, 0);

var linkTopLOSRequest = new LineOfSightRequest

{

start = linkTop.To3D(topOfEnvironment),

end = linkTop.To3D(bottomOfEnvironment),

};

var linkTopLOSResult = LineOfSightHelper.FindOne(

linkTopLOSRequest,

walkableLayers,

world

);

var linkBottom = linkCenter - new float2(linkLengthRadius, 0);

var linkBottomLOSRequest = new LineOfSightRequest

{

start = linkBottom.To3D(topOfEnvironment),

end = linkBottom.To3D(bottomOfEnvironment),

};

var linkBottomLOSResult = LineOfSightHelper.FindOne(

linkBottomLOSRequest,

walkableLayers,

world

);

if (linkTopLOSResult.exists == 0 && linkBottomLOSResult.exists == 0)

{

linkIsValid[index] = true;

linkStarts[index] = linkTopLOSResult.point;

linkEnds[index] = linkBottomLOSResult.point;

}

}

}

public static PhysicsConverter GetModifierGridConverter()

{

return

new PhysicsConverter(

instance.gridBounds.center - instance.gridBounds.extents,

NavMeshQueryScheduler.GetAgentModifierCellRadius()

);

}

public static int GetUserAgentType()

{

return instance.agentType;

}

private void OnDrawGizmos()

{

if(showBounds)

{

Gizmos.DrawWireCube(gridBounds.center, gridBounds.size);

}

}

private void OnDestroy()

{

var gridDimX = grid.GetLength(0);

var gridDimY = grid.GetLength(1);

for (var i = 0; i < gridDimX; i++)

{

for (var j = 0; j < gridDimY; j++)

{

NavMesh.RemoveNavMeshData(grid[i,j].reference);

}

}

var numLinks = links.Length;

for(var i = 0; i < numLinks; i++)

{

NavMesh.RemoveLink(links[i]);

}

}

}

This code contains some junk that divides the NavMesh into "chunks", and if a NavMeshBuildSource is confined within a subset of the chunks, only those chunks are updated. I'm not sure if it actually improves performance, so feel free to remove that portion of the code. Anyways, AllocateModifiers is the method you want to be calling. It accepts NativeMultiHashMap<int, float2x2> areaTypeModifierVolumes, which maps an int representing the area type to an unordered list of float2x2, which represents the upper-right and lower-left of a cell. On the caller side, do yield return asyncOperation; to block the main thread until the NavMesh is updated. Alternatively, start a coroutine and do

Code (CSharp):

while(!asyncOperation.isComplete){

yield return new WaitForEndOfFrame();

}

so that the main thread is not blocked and the update completes at its own pace.

Mortalanimal · Dec 12, 2019

Abbrew said: ↑

I made a Monobehaviour that dynamically assigns area types to sections of the navmesh. You do this by calling NavMesh.UpdateAsync, which accepts a list of NavMeshBuildSource. NavMeshBuildSource are volumes that, when intersecting with a NavMesh, modify that area type within the intersection plane. Each Update loop, create a NavMeshBuildSource that's a ModifierBox type centered on the NavMeshAgent. Call NavMesh.UpdateAsync using this ModifierBox, and the NavMesh will weigh the area around the NavMeshAgent accordingly. You can either write your own implementation, or you can use this code:

Code (CSharp):

using UnityEngine;

using UnityEngine.AI;

using Unity.Entities;

using Unity.Jobs;

using Unity.Collections;

using Unity.Mathematics;

using System.Collections.Generic;

using Unity.Burst;

using Unity.Physics;

using Unity.Physics.Systems;

using UnityEngine.Experimental.AI;

public class NavMeshBuilderGrid : MonoBehaviour

{

[Header("User")]

[SerializeField]

private int agentType;

[SerializeField]

private float agentRadius;

[SerializeField]

private float agentStepHeight;

[SerializeField]

private float agentSlope;

[SerializeField]

private float agentHeight;

[Header("Map")]

[SerializeField]

private LayerMask includedLayers;

[SerializeField]

private Bounds gridBounds;

[SerializeField]

private int tileSize;

[SerializeField]

private float voxelRadius;

[SerializeField]

private float chunkLength;

[Header("Debug")]

[SerializeField]

private bool showBounds = true;

private bool ready;

private float heightOfEnvironment;

private float middleOfEnvironment;

private PhysicsConverter chunkConverter;

private int xChunkGridLength;

private int yChunkGridLength;

private EntityManager em;

private NavMeshChunk[,] grid;

private NavMeshLinkInstance[] links;

private Dictionary<int, List<NavMeshBuildSource>> chunkToCells;

private NavMeshBuildSettings buildSettings;

private static NavMeshBuilderGrid instance;

public static List<AsyncOperation> AllocateModifiers(

NativeMultiHashMap<int, float2x2> areaTypeModifierVolumes

)

{

// clear the reusable data structure

var chunkToCellLength = instance.chunkToCells.Count;

for (var i = 0; i < chunkToCellLength; i++)

{

instance.chunkToCells[i].Clear();

}

var physicsData = Physics.GetPhysics().GetData();

var topOfEnvironment = physicsData.GetBottomLeftCorner().y + physicsData.GetDimensions().y;

var bottomOfEnvironment = physicsData.GetBottomLeftCorner().y;

var middleOfEnvironment = (topOfEnvironment + bottomOfEnvironment) / 2;

var heightOfEnvironment = topOfEnvironment - bottomOfEnvironment;

var cellDefinitions = new List<CellDefinition>();

for (var i = 0; i < NavMeshAreas.GetNumAreaTypes(); i++)

{

var areaType = i;

if (areaTypeModifierVolumes.TryGetFirstValue(

areaType,

out var volumeDim,

out var it

))

{

var ll = volumeDim.c0;

var ur = volumeDim.c1;

instance.AddToChunk(

areaType,

ll,

ur

);

while (areaTypeModifierVolumes.TryGetNextValue(out volumeDim, ref it))

{

ll = volumeDim.c0;

ur = volumeDim.c1;

instance.AddToChunk(

areaType,

ll,

ur

);

}

}

}

var operations = new List<AsyncOperation>();

var chunkGridDimX = instance.grid.GetLength(0);

var chunkGridDimY = instance.grid.GetLength(1);

for (var i = 0; i < chunkGridDimX; i++)

{

for (var j = 0; j < chunkGridDimY; j++)

{

var currentSources = instance.chunkToCells[(i * chunkGridDimY) + j];

// only update if cells are in the chunk

if(currentSources.Count == 0)

{

continue;

}

var currentChunk = instance.grid[i,j];

var currentAllSources = new List<NavMeshBuildSource>();

currentAllSources.AddRange(currentSources);

currentAllSources.AddRange(currentChunk.staticSources);

operations.Add(

NavMeshBuilder.UpdateNavMeshDataAsync(

currentChunk.data,

instance.buildSettings,

currentAllSources,

currentChunk.data.sourceBounds

)

);

}

}

return operations;

}

private void AddToChunk(int areaType, float2 ll, float2 ur)

{

var cellLocation = (ll + ur) / 2;

var cellLocation4x4 = Matrix4x4.Translate(cellLocation.To3D(middleOfEnvironment));

var cellRadii = (ur - ll) / 2;

var cellDiameter = cellRadii * 2;

var cell = new NavMeshBuildSource

{

size = new Vector3(cellDiameter.x, heightOfEnvironment, cellDiameter.y),

area = areaType,

transform = cellLocation4x4,

shape = NavMeshBuildSourceShape.ModifierBox

};

var llChunk = chunkConverter.ToGridCoord(ll);

var urChunk = chunkConverter.ToGridCoord(ur);

var top = urChunk.y;

var bottom = llChunk.y;

var right = urChunk.x;

var left = llChunk.x;

var gridHeight = grid.GetLength(1);

for (var i = left; i <= right; i++)

{

for (var j = bottom; j <= top; j++)

{

chunkToCells[(i * gridHeight) + j].Add(cell);

}

}

}

private struct CellDefinition

{

public float2 location;

public float2 radii;

public int areaType;

}

private void Awake()

{

instance = this;

em = World.Active.EntityManager;

}

private void OnEnable()

{

var topOfEnvironment = gridBounds.center.y + gridBounds.extents.y;

var bottomOfEnvironment = gridBounds.center.y - gridBounds.extents.y;

middleOfEnvironment = (topOfEnvironment + bottomOfEnvironment) / 2;

heightOfEnvironment = topOfEnvironment - bottomOfEnvironment;

xChunkGridLength = (int)Mathf.Ceil(gridBounds.size.x / chunkLength);

yChunkGridLength = (int)Mathf.Ceil(gridBounds.size.z / chunkLength);

buildSettings = NavMesh.CreateSettings();

buildSettings.agentTypeID = agentType;

buildSettings.overrideVoxelSize = true;

buildSettings.voxelSize = voxelRadius;

buildSettings.overrideTileSize = true;

buildSettings.tileSize = tileSize;

buildSettings.agentRadius = agentRadius;

buildSettings.agentClimb = agentStepHeight;

buildSettings.agentSlope = agentSlope;

buildSettings.agentHeight = agentHeight;

GenerateNavMeshGrid(buildSettings);

GenerateLinks(buildSettings);

}

private void GenerateNavMeshGrid(NavMeshBuildSettings settings)

{

var nodeRadius = chunkLength / 2;

chunkConverter = new PhysicsConverter(

gridBounds.center - gridBounds.extents,

nodeRadius

);

grid = new NavMeshChunk[xChunkGridLength, yChunkGridLength];

var gridArea = xChunkGridLength * yChunkGridLength;

for(var i = 0; i < xChunkGridLength; i++)

{

for (var j = 0; j < yChunkGridLength; j++)

{

var staticSources = new List<NavMeshBuildSource>();

var currentCenter =

chunkConverter.ToWorldCoord(

new int2(i, j)

).To3D(middleOfEnvironment);

var currentBounds = new Bounds

{

center = Vector3.zero,

size = new Vector3(chunkLength, heightOfEnvironment, chunkLength)

};

NavMeshBuilder.CollectSources(

currentBounds,

includedLayers,

NavMeshCollectGeometry.RenderMeshes,

0,

new List<NavMeshBuildMarkup>(),

staticSources

);

var data = NavMeshBuilder.BuildNavMeshData(

settings,

staticSources,

currentBounds,

currentCenter,

Quaternion.identity

);

var reference = NavMesh.AddNavMeshData(data);

grid[i, j] = new NavMeshChunk

{

data = data,

reference = reference,

staticSources = staticSources

};

}

}

var cellDiameter = NavMeshQueryScheduler.GetAgentModifierCellRadius() * 2;

var xCellGridDim = (int)(gridBounds.size.x / cellDiameter);

var yCellGridDim = (int)(gridBounds.size.z / cellDiameter);

var maxCells = xCellGridDim * yCellGridDim;

var reasonableMaxCellsPerChunk = (maxCells /(gridArea * 50));

chunkToCells = new Dictionary<int, List<NavMeshBuildSource>>(gridArea);

for(var i = 0; i < gridArea; i++)

{

chunkToCells.Add(i, new List<NavMeshBuildSource>(reasonableMaxCellsPerChunk));

}

}

private struct NavMeshChunk

{

public NavMeshData data;

public NavMeshDataInstance reference;

public List<NavMeshBuildSource> staticSources;

}

private void GenerateLinks(

NavMeshBuildSettings settings

)

{

var physics = Physics.GetPhysics().GetData();

var world = World.Active.GetOrCreateSystem<BuildPhysicsWorld>().PhysicsWorld.CollisionWorld;

var horizontalDistanceBetweenLinks =

(settings.agentRadius * 2) + (PhysicsMeasurements.METER * .1f);

var horizontalConverter = new PhysicsConverterAsymmetrical(

gridBounds.center - gridBounds.extents,

horizontalDistanceBetweenLinks / 2,

chunkLength / 2

);

var horizontalLinkWidthRadius = settings.agentRadius - (PhysicsMeasurements.METER * .1f);

var horizontalLinkLengthRadius = PhysicsMeasurements.METER * 2f;

var linksPerHorizontal =

(int)((gridBounds.center.x + gridBounds.extents.x) / horizontalDistanceBetweenLinks);

var numHorizontalLinks = yChunkGridLength * linksPerHorizontal;

var horizontalLinkStarts = new NativeArray<float3>(numHorizontalLinks, Allocator.TempJob);

var horizontalLinkEnds = new NativeArray<float3>(numHorizontalLinks, Allocator.TempJob);

var horizontalValidLinks = new NativeArray<bool>(numHorizontalLinks, Allocator.TempJob);

var horizontalHandle = new GenerateLinksHorizontalJob

{

linkLengthRadius = horizontalLinkLengthRadius,

converter = horizontalConverter,

linksPerHorizontal = linksPerHorizontal,

linkStarts = horizontalLinkStarts,

linkEnds = horizontalLinkEnds,

linkIsValid = horizontalValidLinks,

walkableLayers = includedLayers,

world = world,

topOfEnvironment = physics.GetTopOfEnvironment(),

bottomOfEnvironment = physics.GetBottomOfEnvironment()

}.Schedule(numHorizontalLinks, 128, default);

JobHandle.ScheduleBatchedJobs();

var verticalDistanceBetweenLinks =

(settings.agentRadius * 2) + (PhysicsMeasurements.METER * .1f);

var verticalConverter = new PhysicsConverterAsymmetrical(

gridBounds.center - gridBounds.extents,

chunkLength / 2,

verticalDistanceBetweenLinks / 2

);

var verticalLinkWidthRadius = settings.agentRadius - (PhysicsMeasurements.METER * .1f);

var verticalLinkLengthRadius = PhysicsMeasurements.METER * 2f;

var linksPerVertical =

(int)((gridBounds.center.y + gridBounds.extents.y) / verticalDistanceBetweenLinks);

var numVerticalLinks = xChunkGridLength * linksPerVertical;

var verticalLinkStarts = new NativeArray<float3>(numVerticalLinks, Allocator.TempJob);

var verticalLinkEnds = new NativeArray<float3>(numVerticalLinks, Allocator.TempJob);

var verticalValidLinks = new NativeArray<bool>(numVerticalLinks, Allocator.TempJob);

var verticalHandle = new GenerateLinksVerticalJob

{

linkLengthRadius = verticalLinkLengthRadius,

converter = verticalConverter,

linksPerVertical = linksPerVertical,

linkStarts = verticalLinkStarts,

linkEnds = verticalLinkEnds,

linkIsValid = verticalValidLinks,

walkableLayers = includedLayers,

world = world,

topOfEnvironment = physics.GetTopOfEnvironment(),

bottomOfEnvironment = physics.GetBottomOfEnvironment()

}.Schedule(numVerticalLinks, 128, default);

var inputDeps = JobHandle.CombineDependencies(horizontalHandle, verticalHandle);

NavMeshWorld.GetDefaultWorld().AddDependency(inputDeps);

inputDeps.Complete();

links = new NavMeshLinkInstance[numHorizontalLinks + numVerticalLinks];

for (var i = 0; i < numHorizontalLinks; i++)

{

if (horizontalValidLinks[i])

{

links[i] = NavMesh.AddLink(new NavMeshLinkData

{

width = horizontalLinkWidthRadius * 2,

startPosition = horizontalLinkStarts[i],

endPosition = horizontalLinkEnds[i],

agentTypeID = agentType,

area = 0,

bidirectional = true,

});

}

}

for (var i = 0; i < numVerticalLinks; i++)

{

if (verticalValidLinks[i])

{

links[numHorizontalLinks + i] = NavMesh.AddLink(new NavMeshLinkData

{

width = verticalLinkWidthRadius * 2,

startPosition = verticalLinkStarts[i],

endPosition = verticalLinkEnds[i],

agentTypeID = agentType,

area = 0,

bidirectional = true,

});

}

}

verticalLinkStarts.Dispose();

verticalLinkEnds.Dispose();

verticalValidLinks.Dispose();

horizontalLinkStarts.Dispose();

horizontalLinkEnds.Dispose();

horizontalValidLinks.Dispose();

}

[BurstCompile]

private struct GenerateLinksHorizontalJob : IJobParallelFor

{

public float linkLengthRadius;

public int linksPerHorizontal;

[WriteOnly]

public NativeArray<float3> linkStarts;

[WriteOnly]

public NativeArray<float3> linkEnds;

[WriteOnly]

public NativeArray<bool> linkIsValid;

[ReadOnly]

public CollisionWorld world;

public LayerMask walkableLayers;

public PhysicsConverterAsymmetrical converter;

public float topOfEnvironment;

public float bottomOfEnvironment;

public void Execute(int index)

{

var nodeX = index % linksPerHorizontal;

var nodeY = index / linksPerHorizontal;

var linkCenter = converter.ToWorldCoordNoOffset(new int2(nodeX, nodeY));

var linkTop = linkCenter + new float2(0, linkLengthRadius);

var linkTopLOSRequest = new LineOfSightRequest

{

start = linkTop.To3D(topOfEnvironment),

end = linkTop.To3D(bottomOfEnvironment),

};

var linkTopLOSResult = LineOfSightHelper.FindOne(

linkTopLOSRequest,

walkableLayers,

world

);

var linkBottom = linkCenter - new float2(0, linkLengthRadius);

var linkBottomLOSRequest = new LineOfSightRequest

{

start = linkBottom.To3D(topOfEnvironment),

end = linkBottom.To3D(bottomOfEnvironment),

};

var linkBottomLOSResult = LineOfSightHelper.FindOne(

linkBottomLOSRequest,

walkableLayers,

world

);

if (linkTopLOSResult.exists == 0 && linkBottomLOSResult.exists == 0)

{

linkIsValid[index] = true;

linkStarts[index] = linkTopLOSResult.point;

linkEnds[index] = linkBottomLOSResult.point;

}

}

}

[BurstCompile]

private struct GenerateLinksVerticalJob : IJobParallelFor

{

public float linkLengthRadius;

public int linksPerVertical;

[WriteOnly]

public NativeArray<float3> linkStarts;

[WriteOnly]

public NativeArray<float3> linkEnds;

[WriteOnly]

public NativeArray<bool> linkIsValid;

[ReadOnly]

public CollisionWorld world;

public LayerMask walkableLayers;

public PhysicsConverterAsymmetrical converter;

public float topOfEnvironment;

public float bottomOfEnvironment;

public void Execute(int index)

{

var nodeX = index / linksPerVertical;

var nodeY = index % linksPerVertical;

var linkCenter = converter.ToWorldCoordNoOffset(new int2(nodeX, nodeY));

var linkTop = linkCenter + new float2(linkLengthRadius, 0);

var linkTopLOSRequest = new LineOfSightRequest

{

start = linkTop.To3D(topOfEnvironment),

end = linkTop.To3D(bottomOfEnvironment),

};

var linkTopLOSResult = LineOfSightHelper.FindOne(

linkTopLOSRequest,

walkableLayers,

world

);

var linkBottom = linkCenter - new float2(linkLengthRadius, 0);

var linkBottomLOSRequest = new LineOfSightRequest

{

start = linkBottom.To3D(topOfEnvironment),

end = linkBottom.To3D(bottomOfEnvironment),

};

var linkBottomLOSResult = LineOfSightHelper.FindOne(

linkBottomLOSRequest,

walkableLayers,

world

);

if (linkTopLOSResult.exists == 0 && linkBottomLOSResult.exists == 0)

{

linkIsValid[index] = true;

linkStarts[index] = linkTopLOSResult.point;

linkEnds[index] = linkBottomLOSResult.point;

}

}

}

public static PhysicsConverter GetModifierGridConverter()

{

return

new PhysicsConverter(

instance.gridBounds.center - instance.gridBounds.extents,

NavMeshQueryScheduler.GetAgentModifierCellRadius()

);

}

public static int GetUserAgentType()

{

return instance.agentType;

}

private void OnDrawGizmos()

{

if(showBounds)

{

Gizmos.DrawWireCube(gridBounds.center, gridBounds.size);

}

}

private void OnDestroy()

{

var gridDimX = grid.GetLength(0);

var gridDimY = grid.GetLength(1);

for (var i = 0; i < gridDimX; i++)

{

for (var j = 0; j < gridDimY; j++)

{

NavMesh.RemoveNavMeshData(grid[i,j].reference);

}

}

var numLinks = links.Length;

for(var i = 0; i < numLinks; i++)

{

NavMesh.RemoveLink(links[i]);

}

}

}

This code contains some junk that divides the NavMesh into "chunks", and if a NavMeshBuildSource is confined within a subset of the chunks, only those chunks are updated. I'm not sure if it actually improves performance, so feel free to remove that portion of the code. Anyways, AllocateModifiers is the method you want to be calling. It accepts NativeMultiHashMap<int, float2x2> areaTypeModifierVolumes, which maps an int representing the area type to an unordered list of float2x2, which represents the upper-right and lower-left of a cell. On the caller side, do yield return asyncOperation; to block the main thread until the NavMesh is updated. Alternatively, start a coroutine and do

Code (CSharp):

while(!asyncOperation.isComplete){

yield return new WaitForEndOfFrame();

}

so that the main thread is not blocked and the update completes at its own pace.
Click to expand...

Thank you so much for this, I was beginning to think it was impossible.

I will have to study your code, its a bit advanced for me but I am happy never the less!

Thanks again

Abbrew · Dec 14, 2019

Mortalanimal said: ↑

Thank you so much for this, I was beginning to think it was impossible.

I will have to study your code, its a bit advanced for me but I am happy never the less!

Thanks again
Click to expand...

Please ping me if you need help with your own implementation, the code I provided is admittedly spaghettish and lacks context

Mortalanimal · Dec 14, 2019

Abbrew said: ↑

Please ping me if you need help with your own implementation, the code I provided is admittedly spaghettish and lacks context
Click to expand...

Thank you so much

Problem is, I Have only started programming around 3 months ago, so I asked a friend to help me study this script who has been programming for a few years, and he couldn't understand it either haha. I mean, I have written Scripts 5000 lines long (not saying this is a good thing lol), but this was so advanced to me that I could only read 10% of it haha.

My questions:

1) will this be able to work in run-time?, because thats what I need. I need to constantly change the cost of the navmesh withing a small radius during runtime.

2) the way I would use it, once my unit has a velocity of 0 for 3 seconds, he will increase the mavMesh Cost under him, (this is for an RTS game so this should apply to all my units).

3) if my unity starts moving I would need that area cost to go back to default.

4) I am not Using ACS / Any Burst Compilers / JOB system, because I have not learned it. And I was wondering if its possible to do it without.

5) I still want to continue using the In-Game navmesh / navmeshAgent, because my scripts are written around them (would this be a problem while using your method).

6) Basically, Unless you fully spoon feed me this, I dont think I can Understand it lol. A video on this would be great coz no one has covered this at all, and if you dont make videos, I will do it for you if you manage to teach me this and I will give you full credit.

7) how taxiing is this process, I have been told that this is very taxing, which doesnt make sense to me because you can make a dynamic navmesh obstacle with carve and its not that taxing, in my eyes this feels like it should be just as simple. (ofc I could be wrong)

Abbrew · Dec 14, 2019

Mortalanimal said: ↑

Thank you so much

Problem is, I Have only started programming around 3 months ago, so I asked a friend to help me study this script who has been programming for a few years, and he couldn't understand it either haha. I mean, I have written Scripts 5000 lines long (not saying this is a good thing lol), but this was so advanced to me that I could only read 10% of it haha.

My questions:

1) will this be able to work in run-time?, because thats what I need. I need to constantly change the cost of the navmesh withing a small radius during runtime.

2) the way I would use it, once my unit has a velocity of 0 for 3 seconds, he will increase the mavMesh Cost under him, (this is for an RTS game so this should apply to all my units).

3) if my unity starts moving I would need that area cost to go back to default.

4) I am not Using ACS / Any Burst Compilers / JOB system, because I have not learned it. And I was wondering if its possible to do it without.

5) I still want to continue using the In-Game navmesh / navmeshAgent, because my scripts are written around them (would this be a problem while using your method).

6) Basically, Unless you fully spoon feed me this, I dont think I can Understand it lol. A video on this would be great coz no one has covered this at all, and if you dont make videos, I will do it for you if you manage to teach me this and I will give you full credit.

7) how taxiing is this process, I have been told that this is very taxing, which doesnt make sense to me because you can make a dynamic navmesh obstacle with carve and its not that taxing, in my eyes this feels like it should be just as simple. (ofc I could be wrong)
Click to expand...

I don't think my script fits your use case. My script was made for a game that batches together NavMesh queries that are created over time, then takes a few dozen milliseconds to asynchronously update the NavMesh, then executes those queries. In your use case, the updates must occur every frame, which means using the asynchronous API won't work. I would say that you could batch pathfinding requests the way my game does, but because the NavMesh could change halfway through a path, that won't work either. However, I'll try my best to answer your questions and formulate a solution

1) You could use the synchronous API to update the NavMesh, but updating a huge map typical of RTS games would cause huge lag spikes in the framerate.

2) You could keep track of all units that are affecting the NavMesh, and once other units want to trace a path, update the NavMesh asynchronously, and when done, compute paths for all pending units

3) Same thing as above, batch together units that have moved's last locations, and when other units want to trace a path, update the NavMesh taking into account the deleted modified costs.

4) It can be done, and for now it is recommended that you use the MonoBehaviour way of doing things. However, Unity recently announced that they are planning on providing a ECS/Jobs API for NavMesh. This would speed up performance significantly. If you have time I suggest learning Unity's DOTS so that once that is released you'd be ready to take advantage of it

5) You can still update the NavMesh asynchronously, and once done, use NavMeshAgent and NavMesh to find and traverse a path. There will be delays though

6) Try following some Youtube tutorials, and build a simple NavMesh system to toy around with. Once you've gotten the hang of it slowly add features until you reach the point you want.

7) Updating the NavMesh takes, for a large map with lots of modifiers, around 200ms for my game. This sounds bad, but because it's being done asynchronously, the latency is spread evenly across multiple frames. This means that while there will be a ~200ms delay between the batch of NavMesh queries being created, and the NavMesh queries being executed, there will be no frame rate hiccups.

In the end, you should profile first. One thing about gamedev that I hate but is necessary is that to ensure that you are doing things the most performant way, you'd have to build prototypes that, if they fail, must be discarded. Try building the simplest one where you synchronously update the NavMesh every time a NavMesh query is made. To reduce latency, increase the tile size and voxel size, effectively making your NavMesh less "detailed", but more performant. If this implementation causes lag spikes, then try more complicated alternatives.

Some other ideas are:

1. Use NavMeshObstacles. Instead of changing an area's areatype, this will make the area unwalkable. Attach a NavMeshObstacle to each agent. You might not want this as it will cause cluttering

2. Learn the Job and Burst systems. NavMeshQuery is an API that allows you to calculate paths asynchronously inside of a Job, and is fully Burst-able. This way you can batch together NavMesh queries, update the entire map asynchronously once, and then execute those queries efficiently. One weakness is that once you've calculated a path and somewhere on the map an agent remains still long enough to create an area cost modifier, that path would be considered "stale", since it was calculated without that new area cost modifier in mind.

Good luck, and you're doing very well for someone who has been programming for only 3 months. When I was at that stage I was still trying to compare Strings with ==. Good luck!

Mortalanimal · Dec 14, 2019

@Abbrew,

Thank you for taking your time to write a detailed reply!

1. Use NavMeshObstacles. Instead of changing an area's areatype, this will make the area unwalkable. Attach a NavMeshObstacle to each agent. You might not want this as it will cause cluttering
Click to expand...

I thought about this, but it makes it look even worse than my current temporary solution (I will make a video on this and show you once I tweak it, this might explain to you where I am coming from)

2. Learn the Job and Burst systems. NavMeshQuery is an API that allows you to calculate paths asynchronously inside of a Job, and is fully Burst-able. This way you can batch together NavMesh queries, update the entire map asynchronously once, and then execute those queries efficiently. One weakness is that once you've calculated a path and somewhere on the map an agent remains still long enough to create an area cost modifier, that path would be considered "stale", since it was calculated without that new area cost modifier in mind.
Click to expand...

I tried, but I Could not understand it, at least I found it hard, And i thought this is a result of my ignorance, so I though I would try to learn it when I have more experience in general. Worse part is when I get stuck for over 2+ days on something and lose motivation, which is exactly what happened when I tried to learn this.

Good luck, and you're doing very well for someone who has been programming for only 3 months. When I was at that stage I was still trying to compare Strings with ==. Good luck
Click to expand...

Haha, I always compare things with == or != , ppl say its costly but how else am I suppose to compare. But I dont compare strings, I hardly ever use them outside of invokes.

Thanks again bro, I will make a youtube video and and show my prototyping. The thing is, I personally believe this is the most important part of an RTS game, thats why I have spent over a months on this script.

Abbrew · Dec 14, 2019

Mortalanimal said: ↑

I tried, but I Could not understand it, at least I found it hard, And i thought this is a result of my ignorance, so I though I would try to learn it when I have more experience in general. Worse part is when I get stuck for over 2+ days on something and lose motivation, which is exactly what happened when I tried to learn this.
Click to expand...

Yeah learning Jobs was hard for me as well - it took me 6 months to learn enough to start conceptualizing and writing code efficiently. However, it's well worth it because of the massive performance benefits. Your style of video game (RTS) is perfectly suited for Jobs, and maybe even ECS. Try to learn them in a way that complements your learning style. For example, if you like reverse-engineering, poke around the forums looking for code snippets or Github links, and learn from those examples.

vhman · Dec 15, 2019

@Abbrew

Do you have this part on GitHub or your other Components?

Abbrew · Dec 16, 2019

vhman said: ↑

@Abbrew

Do you have this part on GitHub or your other Components?
Click to expand...

I do, but the repository is likely to change and even become private in the coming months. You're free to clone the repository and use code in the meantime as long as you give credit. Note that there are likely errors in play mode due to my bad git habits. Here it is:

https://github.com/KontosTwo/DidymosECS

NavMesh-specific code is in:

https://github.com/KontosTwo/DidymosECS/tree/master/Assets/MyAssets/Src/Environment/NavMesh

BinaryEclipse · Oct 11, 2020

Abbrew said: ↑

I made a Monobehaviour that dynamically assigns area types to sections of the navmesh. You do this by calling NavMesh.UpdateAsync, which accepts a list of NavMeshBuildSource. NavMeshBuildSource are volumes that, when intersecting with a NavMesh, modify that area type within the intersection plane. Each Update loop, create a NavMeshBuildSource that's a ModifierBox type centered on the NavMeshAgent. Call NavMesh.UpdateAsync using this ModifierBox, and the NavMesh will weigh the area around the NavMeshAgent accordingly. You can either write your own implementation, or you can use this code:

Code (CSharp):

using UnityEngine;

using UnityEngine.AI;

using Unity.Entities;

using Unity.Jobs;

using Unity.Collections;

using Unity.Mathematics;

using System.Collections.Generic;

using Unity.Burst;

using Unity.Physics;

using Unity.Physics.Systems;

using UnityEngine.Experimental.AI;

public class NavMeshBuilderGrid : MonoBehaviour

{

[Header("User")]

[SerializeField]

private int agentType;

[SerializeField]

private float agentRadius;

[SerializeField]

private float agentStepHeight;

[SerializeField]

private float agentSlope;

[SerializeField]

private float agentHeight;

[Header("Map")]

[SerializeField]

private LayerMask includedLayers;

[SerializeField]

private Bounds gridBounds;

[SerializeField]

private int tileSize;

[SerializeField]

private float voxelRadius;

[SerializeField]

private float chunkLength;

[Header("Debug")]

[SerializeField]

private bool showBounds = true;

private bool ready;

private float heightOfEnvironment;

private float middleOfEnvironment;

private PhysicsConverter chunkConverter;

private int xChunkGridLength;

private int yChunkGridLength;

private EntityManager em;

private NavMeshChunk[,] grid;

private NavMeshLinkInstance[] links;

private Dictionary<int, List<NavMeshBuildSource>> chunkToCells;

private NavMeshBuildSettings buildSettings;

private static NavMeshBuilderGrid instance;

public static List<AsyncOperation> AllocateModifiers(

NativeMultiHashMap<int, float2x2> areaTypeModifierVolumes

)

{

// clear the reusable data structure

var chunkToCellLength = instance.chunkToCells.Count;

for (var i = 0; i < chunkToCellLength; i++)

{

instance.chunkToCells[i].Clear();

}

var physicsData = Physics.GetPhysics().GetData();

var topOfEnvironment = physicsData.GetBottomLeftCorner().y + physicsData.GetDimensions().y;

var bottomOfEnvironment = physicsData.GetBottomLeftCorner().y;

var middleOfEnvironment = (topOfEnvironment + bottomOfEnvironment) / 2;

var heightOfEnvironment = topOfEnvironment - bottomOfEnvironment;

var cellDefinitions = new List<CellDefinition>();

for (var i = 0; i < NavMeshAreas.GetNumAreaTypes(); i++)

{

var areaType = i;

if (areaTypeModifierVolumes.TryGetFirstValue(

areaType,

out var volumeDim,

out var it

))

{

var ll = volumeDim.c0;

var ur = volumeDim.c1;

instance.AddToChunk(

areaType,

ll,

ur

);

while (areaTypeModifierVolumes.TryGetNextValue(out volumeDim, ref it))

{

ll = volumeDim.c0;

ur = volumeDim.c1;

instance.AddToChunk(

areaType,

ll,

ur

);

}

}

}

var operations = new List<AsyncOperation>();

var chunkGridDimX = instance.grid.GetLength(0);

var chunkGridDimY = instance.grid.GetLength(1);

for (var i = 0; i < chunkGridDimX; i++)

{

for (var j = 0; j < chunkGridDimY; j++)

{

var currentSources = instance.chunkToCells[(i * chunkGridDimY) + j];

// only update if cells are in the chunk

if(currentSources.Count == 0)

{

continue;

}

var currentChunk = instance.grid[i,j];

var currentAllSources = new List<NavMeshBuildSource>();

currentAllSources.AddRange(currentSources);

currentAllSources.AddRange(currentChunk.staticSources);

operations.Add(

NavMeshBuilder.UpdateNavMeshDataAsync(

currentChunk.data,

instance.buildSettings,

currentAllSources,

currentChunk.data.sourceBounds

)

);

}

}

return operations;

}

private void AddToChunk(int areaType, float2 ll, float2 ur)

{

var cellLocation = (ll + ur) / 2;

var cellLocation4x4 = Matrix4x4.Translate(cellLocation.To3D(middleOfEnvironment));

var cellRadii = (ur - ll) / 2;

var cellDiameter = cellRadii * 2;

var cell = new NavMeshBuildSource

{

size = new Vector3(cellDiameter.x, heightOfEnvironment, cellDiameter.y),

area = areaType,

transform = cellLocation4x4,

shape = NavMeshBuildSourceShape.ModifierBox

};

var llChunk = chunkConverter.ToGridCoord(ll);

var urChunk = chunkConverter.ToGridCoord(ur);

var top = urChunk.y;

var bottom = llChunk.y;

var right = urChunk.x;

var left = llChunk.x;

var gridHeight = grid.GetLength(1);

for (var i = left; i <= right; i++)

{

for (var j = bottom; j <= top; j++)

{

chunkToCells[(i * gridHeight) + j].Add(cell);

}

}

}

private struct CellDefinition

{

public float2 location;

public float2 radii;

public int areaType;

}

private void Awake()

{

instance = this;

em = World.Active.EntityManager;

}

private void OnEnable()

{

var topOfEnvironment = gridBounds.center.y + gridBounds.extents.y;

var bottomOfEnvironment = gridBounds.center.y - gridBounds.extents.y;

middleOfEnvironment = (topOfEnvironment + bottomOfEnvironment) / 2;

heightOfEnvironment = topOfEnvironment - bottomOfEnvironment;

xChunkGridLength = (int)Mathf.Ceil(gridBounds.size.x / chunkLength);

yChunkGridLength = (int)Mathf.Ceil(gridBounds.size.z / chunkLength);

buildSettings = NavMesh.CreateSettings();

buildSettings.agentTypeID = agentType;

buildSettings.overrideVoxelSize = true;

buildSettings.voxelSize = voxelRadius;

buildSettings.overrideTileSize = true;

buildSettings.tileSize = tileSize;

buildSettings.agentRadius = agentRadius;

buildSettings.agentClimb = agentStepHeight;

buildSettings.agentSlope = agentSlope;

buildSettings.agentHeight = agentHeight;

GenerateNavMeshGrid(buildSettings);

GenerateLinks(buildSettings);

}

private void GenerateNavMeshGrid(NavMeshBuildSettings settings)

{

var nodeRadius = chunkLength / 2;

chunkConverter = new PhysicsConverter(

gridBounds.center - gridBounds.extents,

nodeRadius

);

grid = new NavMeshChunk[xChunkGridLength, yChunkGridLength];

var gridArea = xChunkGridLength * yChunkGridLength;

for(var i = 0; i < xChunkGridLength; i++)

{

for (var j = 0; j < yChunkGridLength; j++)

{

var staticSources = new List<NavMeshBuildSource>();

var currentCenter =

chunkConverter.ToWorldCoord(

new int2(i, j)

).To3D(middleOfEnvironment);

var currentBounds = new Bounds

{

center = Vector3.zero,

size = new Vector3(chunkLength, heightOfEnvironment, chunkLength)

};

NavMeshBuilder.CollectSources(

currentBounds,

includedLayers,

NavMeshCollectGeometry.RenderMeshes,

0,

new List<NavMeshBuildMarkup>(),

staticSources

);

var data = NavMeshBuilder.BuildNavMeshData(

settings,

staticSources,

currentBounds,

currentCenter,

Quaternion.identity

);

var reference = NavMesh.AddNavMeshData(data);

grid[i, j] = new NavMeshChunk

{

data = data,

reference = reference,

staticSources = staticSources

};

}

}

var cellDiameter = NavMeshQueryScheduler.GetAgentModifierCellRadius() * 2;

var xCellGridDim = (int)(gridBounds.size.x / cellDiameter);

var yCellGridDim = (int)(gridBounds.size.z / cellDiameter);

var maxCells = xCellGridDim * yCellGridDim;

var reasonableMaxCellsPerChunk = (maxCells /(gridArea * 50));

chunkToCells = new Dictionary<int, List<NavMeshBuildSource>>(gridArea);

for(var i = 0; i < gridArea; i++)

{

chunkToCells.Add(i, new List<NavMeshBuildSource>(reasonableMaxCellsPerChunk));

}

}

private struct NavMeshChunk

{

public NavMeshData data;

public NavMeshDataInstance reference;

public List<NavMeshBuildSource> staticSources;

}

private void GenerateLinks(

NavMeshBuildSettings settings

)

{

var physics = Physics.GetPhysics().GetData();

var world = World.Active.GetOrCreateSystem<BuildPhysicsWorld>().PhysicsWorld.CollisionWorld;

var horizontalDistanceBetweenLinks =

(settings.agentRadius * 2) + (PhysicsMeasurements.METER * .1f);

var horizontalConverter = new PhysicsConverterAsymmetrical(

gridBounds.center - gridBounds.extents,

horizontalDistanceBetweenLinks / 2,

chunkLength / 2

);

var horizontalLinkWidthRadius = settings.agentRadius - (PhysicsMeasurements.METER * .1f);

var horizontalLinkLengthRadius = PhysicsMeasurements.METER * 2f;

var linksPerHorizontal =

(int)((gridBounds.center.x + gridBounds.extents.x) / horizontalDistanceBetweenLinks);

var numHorizontalLinks = yChunkGridLength * linksPerHorizontal;

var horizontalLinkStarts = new NativeArray<float3>(numHorizontalLinks, Allocator.TempJob);

var horizontalLinkEnds = new NativeArray<float3>(numHorizontalLinks, Allocator.TempJob);

var horizontalValidLinks = new NativeArray<bool>(numHorizontalLinks, Allocator.TempJob);

var horizontalHandle = new GenerateLinksHorizontalJob

{

linkLengthRadius = horizontalLinkLengthRadius,

converter = horizontalConverter,

linksPerHorizontal = linksPerHorizontal,

linkStarts = horizontalLinkStarts,

linkEnds = horizontalLinkEnds,

linkIsValid = horizontalValidLinks,

walkableLayers = includedLayers,

world = world,

topOfEnvironment = physics.GetTopOfEnvironment(),

bottomOfEnvironment = physics.GetBottomOfEnvironment()

}.Schedule(numHorizontalLinks, 128, default);

JobHandle.ScheduleBatchedJobs();

var verticalDistanceBetweenLinks =

(settings.agentRadius * 2) + (PhysicsMeasurements.METER * .1f);

var verticalConverter = new PhysicsConverterAsymmetrical(

gridBounds.center - gridBounds.extents,

chunkLength / 2,

verticalDistanceBetweenLinks / 2

);

var verticalLinkWidthRadius = settings.agentRadius - (PhysicsMeasurements.METER * .1f);

var verticalLinkLengthRadius = PhysicsMeasurements.METER * 2f;

var linksPerVertical =

(int)((gridBounds.center.y + gridBounds.extents.y) / verticalDistanceBetweenLinks);

var numVerticalLinks = xChunkGridLength * linksPerVertical;

var verticalLinkStarts = new NativeArray<float3>(numVerticalLinks, Allocator.TempJob);

var verticalLinkEnds = new NativeArray<float3>(numVerticalLinks, Allocator.TempJob);

var verticalValidLinks = new NativeArray<bool>(numVerticalLinks, Allocator.TempJob);

var verticalHandle = new GenerateLinksVerticalJob

{

linkLengthRadius = verticalLinkLengthRadius,

converter = verticalConverter,

linksPerVertical = linksPerVertical,

linkStarts = verticalLinkStarts,

linkEnds = verticalLinkEnds,

linkIsValid = verticalValidLinks,

walkableLayers = includedLayers,

world = world,

topOfEnvironment = physics.GetTopOfEnvironment(),

bottomOfEnvironment = physics.GetBottomOfEnvironment()

}.Schedule(numVerticalLinks, 128, default);

var inputDeps = JobHandle.CombineDependencies(horizontalHandle, verticalHandle);

NavMeshWorld.GetDefaultWorld().AddDependency(inputDeps);

inputDeps.Complete();

links = new NavMeshLinkInstance[numHorizontalLinks + numVerticalLinks];

for (var i = 0; i < numHorizontalLinks; i++)

{

if (horizontalValidLinks[i])

{

links[i] = NavMesh.AddLink(new NavMeshLinkData

{

width = horizontalLinkWidthRadius * 2,

startPosition = horizontalLinkStarts[i],

endPosition = horizontalLinkEnds[i],

agentTypeID = agentType,

area = 0,

bidirectional = true,

});

}

}

for (var i = 0; i < numVerticalLinks; i++)

{

if (verticalValidLinks[i])

{

links[numHorizontalLinks + i] = NavMesh.AddLink(new NavMeshLinkData

{

width = verticalLinkWidthRadius * 2,

startPosition = verticalLinkStarts[i],

endPosition = verticalLinkEnds[i],

agentTypeID = agentType,

area = 0,

bidirectional = true,

});

}

}

verticalLinkStarts.Dispose();

verticalLinkEnds.Dispose();

verticalValidLinks.Dispose();

horizontalLinkStarts.Dispose();

horizontalLinkEnds.Dispose();

horizontalValidLinks.Dispose();

}

[BurstCompile]

private struct GenerateLinksHorizontalJob : IJobParallelFor

{

public float linkLengthRadius;

public int linksPerHorizontal;

[WriteOnly]

public NativeArray<float3> linkStarts;

[WriteOnly]

public NativeArray<float3> linkEnds;

[WriteOnly]

public NativeArray<bool> linkIsValid;

[ReadOnly]

public CollisionWorld world;

public LayerMask walkableLayers;

public PhysicsConverterAsymmetrical converter;

public float topOfEnvironment;

public float bottomOfEnvironment;

public void Execute(int index)

{

var nodeX = index % linksPerHorizontal;

var nodeY = index / linksPerHorizontal;

var linkCenter = converter.ToWorldCoordNoOffset(new int2(nodeX, nodeY));

var linkTop = linkCenter + new float2(0, linkLengthRadius);

var linkTopLOSRequest = new LineOfSightRequest

{

start = linkTop.To3D(topOfEnvironment),

end = linkTop.To3D(bottomOfEnvironment),

};

var linkTopLOSResult = LineOfSightHelper.FindOne(

linkTopLOSRequest,

walkableLayers,

world

);

var linkBottom = linkCenter - new float2(0, linkLengthRadius);

var linkBottomLOSRequest = new LineOfSightRequest

{

start = linkBottom.To3D(topOfEnvironment),

end = linkBottom.To3D(bottomOfEnvironment),

};

var linkBottomLOSResult = LineOfSightHelper.FindOne(

linkBottomLOSRequest,

walkableLayers,

world

);

if (linkTopLOSResult.exists == 0 && linkBottomLOSResult.exists == 0)

{

linkIsValid[index] = true;

linkStarts[index] = linkTopLOSResult.point;

linkEnds[index] = linkBottomLOSResult.point;

}

}

}

[BurstCompile]

private struct GenerateLinksVerticalJob : IJobParallelFor

{

public float linkLengthRadius;

public int linksPerVertical;

[WriteOnly]

public NativeArray<float3> linkStarts;

[WriteOnly]

public NativeArray<float3> linkEnds;

[WriteOnly]

public NativeArray<bool> linkIsValid;

[ReadOnly]

public CollisionWorld world;

public LayerMask walkableLayers;

public PhysicsConverterAsymmetrical converter;

public float topOfEnvironment;

public float bottomOfEnvironment;

public void Execute(int index)

{

var nodeX = index / linksPerVertical;

var nodeY = index % linksPerVertical;

var linkCenter = converter.ToWorldCoordNoOffset(new int2(nodeX, nodeY));

var linkTop = linkCenter + new float2(linkLengthRadius, 0);

var linkTopLOSRequest = new LineOfSightRequest

{

start = linkTop.To3D(topOfEnvironment),

end = linkTop.To3D(bottomOfEnvironment),

};

var linkTopLOSResult = LineOfSightHelper.FindOne(

linkTopLOSRequest,

walkableLayers,

world

);

var linkBottom = linkCenter - new float2(linkLengthRadius, 0);

var linkBottomLOSRequest = new LineOfSightRequest

{

start = linkBottom.To3D(topOfEnvironment),

end = linkBottom.To3D(bottomOfEnvironment),

};

var linkBottomLOSResult = LineOfSightHelper.FindOne(

linkBottomLOSRequest,

walkableLayers,

world

);

if (linkTopLOSResult.exists == 0 && linkBottomLOSResult.exists == 0)

{

linkIsValid[index] = true;

linkStarts[index] = linkTopLOSResult.point;

linkEnds[index] = linkBottomLOSResult.point;

}

}

}

public static PhysicsConverter GetModifierGridConverter()

{

return

new PhysicsConverter(

instance.gridBounds.center - instance.gridBounds.extents,

NavMeshQueryScheduler.GetAgentModifierCellRadius()

);

}

public static int GetUserAgentType()

{

return instance.agentType;

}

private void OnDrawGizmos()

{

if(showBounds)

{

Gizmos.DrawWireCube(gridBounds.center, gridBounds.size);

}

}

private void OnDestroy()

{

var gridDimX = grid.GetLength(0);

var gridDimY = grid.GetLength(1);

for (var i = 0; i < gridDimX; i++)

{

for (var j = 0; j < gridDimY; j++)

{

NavMesh.RemoveNavMeshData(grid[i,j].reference);

}

}

var numLinks = links.Length;

for(var i = 0; i < numLinks; i++)

{

NavMesh.RemoveLink(links[i]);

}

}

}

This code contains some junk that divides the NavMesh into "chunks", and if a NavMeshBuildSource is confined within a subset of the chunks, only those chunks are updated. I'm not sure if it actually improves performance, so feel free to remove that portion of the code. Anyways, AllocateModifiers is the method you want to be calling. It accepts NativeMultiHashMap<int, float2x2> areaTypeModifierVolumes, which maps an int representing the area type to an unordered list of float2x2, which represents the upper-right and lower-left of a cell. On the caller side, do yield return asyncOperation; to block the main thread until the NavMesh is updated. Alternatively, start a coroutine and do

Code (CSharp):

while(!asyncOperation.isComplete){

yield return new WaitForEndOfFrame();

}

so that the main thread is not blocked and the update completes at its own pace.
Click to expand...

should this work out of the box? I get errors on many things that don't seem to exist. I doubt a few months would be enough for all of these to not exist?
I got the burst, physics, entities, dots packages. all the "using" lines at the top are recognized.

Abbrew · Oct 11, 2020

This script assumes you have NavMeshComponents in your project. However, looking back the script is just over-engineered and horribly bad performance-wise. I recommend you try instead to dynamically weigh the destinations instead of the paths. To better explain: split one large pathfind (a start/destination pair) into multiple smaller pathfinds. For each smaller pathfind, find the destination with the lowest cost (the heuristic for doing so could be how hidden the destination is from enemies, etc), and trace a path with normal, static weights. Keep doing this until you reach the initial destination. As a result you'll simulate dynamically weighted paths. You'll have to balance the size of the smaller pathfinds though - too small and while it will be very close to dynamically weighted paths the agent will get lost in dead ends. Too large and the path will be naive.

BinaryEclipse · Oct 12, 2020

Abbrew said: ↑

This script assumes you have NavMeshComponents in your project. However, looking back the script is just over-engineered and horribly bad performance-wise. I recommend you try instead to dynamically weigh the destinations instead of the paths. To better explain: split one large pathfind (a start/destination pair) into multiple smaller pathfinds. For each smaller pathfind, find the destination with the lowest cost (the heuristic for doing so could be how hidden the destination is from enemies, etc), and trace a path with normal, static weights. Keep doing this until you reach the initial destination. As a result you'll simulate dynamically weighted paths. You'll have to balance the size of the smaller pathfinds though - too small and while it will be very close to dynamically weighted paths the agent will get lost in dead ends. Too large and the path will be naive.
Click to expand...

No, I have that as well. I seem to be missing "PhysicsConverter", "LineOfSightRequest", "World.Active", "PhysicsMeasurements", "NavMeshQueryScheduler", "Physics.GetPhysics", "NavMeshAreas"

Abbrew · Oct 12, 2020

BinaryEclipse said: ↑

No, I have that as well. I seem to be missing "PhysicsConverter", "LineOfSightRequest", "World.Active", "PhysicsMeasurements", "NavMeshQueryScheduler", "Physics.GetPhysics", "NavMeshAreas"
Click to expand...

Those are also scripts I wrote. Again, I recommend you implement what I described in my previous comment. My initial implementation of dynamic path weights is EXTREMELY inefficient. The game literally hangs for an entire second every time the navmesh is recalculated. I can post my newer implementation if you'd like

BinaryEclipse · Oct 12, 2020

Ah I see. Well, I haven't used navmesh all that much in the past besides simple navmesh. There doesn't seem to be a whole lot of documentation regarding modifying a navmesh at runtime. I'm making a city builder and I need to modify the navmesh after the player places a road so that agents can prefer walking along the road but can still walk on terrain when necessary. I'm using the navmesh components system and I've worked off of the plank drop example. I set the LocalNavMeshBuilder to only run on command and made it's bounds only encompass the new road area because I have a very large terrain and I am concerned for performance. The issue is that when placing the second road, when the navmesh updates, it loses the info from the first road. I've tried different things to make that work, but I seem to be out of my element. I'd appreciate any advice you can offer or resources you could point me to. Otherwise, my next step is to split my terrain into smaller chunks of meshes, each with their own LocalNavMeshBuilder. What you were describing sounds like it would be ideal though

Abbrew · Oct 12, 2020

BinaryEclipse said: ↑

Ah I see. Well, I haven't used navmesh all that much in the past besides simple navmesh. There doesn't seem to be a whole lot of documentation regarding modifying a navmesh at runtime. I'm making a city builder and I need to modify the navmesh after the player places a road so that agents can prefer walking along the road but can still walk on terrain when necessary. I'm using the navmesh components system and I've worked off of the plank drop example. I set the LocalNavMeshBuilder to only run on command and made it's bounds only encompass the new road area because I have a very large terrain and I am concerned for performance. The issue is that when placing the second road, when the navmesh updates, it loses the info from the first road. I've tried different things to make that work, but I seem to be out of my element. I'd appreciate any advice you can offer or resources you could point me to. Otherwise, my next step is to split my terrain into smaller chunks of meshes, each with their own LocalNavMeshBuilder. What you were describing sounds like it would be ideal though
Click to expand...

I don't think the entire navmesh is recalculated every time you update a small section of it. Wild guess but maybe the reason the navmesh is first divided into a grid is so that only grid cells that contain updates are recalculated.

When you talk about "losing info" do you mean that the agents stop moving after you update a section of the navmesh that agent was moving through?

BinaryEclipse · Oct 12, 2020

Abbrew said: ↑

I don't think the entire navmesh is recalculated every time you update a small section of it. Wild guess but maybe the reason the navmesh is first divided into a grid is so that only grid cells that contain updates are recalculated.

When you talk about "losing info" do you mean that the agents stop moving after you update a section of the navmesh that agent was moving through?
Click to expand...

Allow me to explain. So the navmesh, originally is all of area type 0. I place road A and that area becomes type 2. After placing road B, that section becomes type 2, but the section under road A is type 0

Tion-Gaming · Jul 5, 2022

Abbrew said: ↑

I do, but the repository is likely to change and even become private in the coming months. You're free to clone the repository and use code in the meantime as long as you give credit. Note that there are likely errors in play mode due to my bad git habits. Here it is:

https://github.com/KontosTwo/DidymosECS

NavMesh-specific code is in:

https://github.com/KontosTwo/DidymosECS/tree/master/Assets/MyAssets/Src/Environment/NavMesh
Click to expand...

Hey, you wouldnt happen to have a copy of that code laying around you can toss onto something like github gists? Ive become really interested in navmesh stuff recently and would love to see how you tackled some of those problems. Or if anyone in this post ended up cloning the repo i would love a link to check it out.

Abbrew · Jul 6, 2022

Tion-Gaming said: ↑

Hey, you wouldnt happen to have a copy of that code laying around you can toss onto something like github gists? Ive become really interested in navmesh stuff recently and would love to see how you tackled some of those problems. Or if anyone in this post ended up cloning the repo i would love a link to check it out.
Click to expand...

The original code is at https://github.com/Unity-Technologies/NavMeshComponents. I think I made a mistake linking my old project's copy of that, but maybe I made local modifications to those files

Search Unity

Unity ID

Useful Searches

how to create a dynamic area cast in navmesh