- A* version: [5.3.3] (the purchased version of A* Pathfinding Project Pro)
- Unity version: [2022.3.53f1]
Hello everyone,
I am working on a game with 9 procedurally generated terrain tiles, and I want each tile to have its own A* graph for pathfinding. The challenge I’m facing is that my agents need to be able to traverse across all tiles seamlessly.
There is always one central tile surrounded by 8 others. As the players move, new tiles are loaded and old ones removed. I also handle origin shifting to keep the tiles close to a zero centre (shifting the graph in AStar works well for this).
For A*, I’ve considered using one large graph, but it’s too slow to scan and impractical for my use case, as individual tiles are loaded in and out at runtime.
The Recast graph seems like the best fit for my game because it has a low comparative memory overhead, is relatively fast to scan, and works well with Navmesh cuts. However, from what I can tell so far, grid graphs seem to be easier to join using NodeLinks.
I’ve experimented with the procedurally moving Recast graph, and while it works well across terrain tiles, it doesn’t cover all terrain tiles simultaneously or the entire graph has to be rescanned as tiles come and go. As the main player agent moves away, other agents lose sight of destinations or suddenly end up off a grid graph, but I need coverage across all tiles.
I’m wondering if anyone has any best practice suggestions for my scenario? Ideally, I would like all my terrain tiles to have Recast graphs, as they can be scanned “out of sight” when the tile is loaded, but since they could have different numbers of nodes compared to adjacent terrain tiles, I’m not sure if they would join up easily. Also, should I consider using Off-mesh links instead of NodeLinks?
Any advice or insights would be greatly appreciated!
Thank you!
Hi
The ProceduralGraphMover would be a good approach. But to make it always cover all terrains, you’ll need to make the target of it the centermost terrain tile, and adjust the size of the recast graph to cover all 3x3 terrains (or slightly less, to avoid issues with generating the navmesh right on the edge of the 3x3 terrain)
1 Like
Thanks Aron, this does seem like the best approach. I am trialing this at the moment and will report back here if I get it to work.
1 Like
Thanks @aron_granberg. I found that trying to update the graph at a low rate i.e only when new terrains load, due to the large number of graph tiles needing to be scanned, it was too much of a performance strain, so I’ve gone back to having the ProceduralGraphMover follow my player, which is much more efficient, and I can deal with agents outside of the graph in other ways.
So the ProceduralGraphMover works well for me, just with a small tweak.
When generating my procedural world content, I need to control what’s happening and when a bit closer.
To stop it trying to update every frame, I tried disabling the component, but in OnDisable it calls a AstarPath.active.FlushWorkItems which is something I wanted to avoid, so I then tried writing my own CustomGraphMover (almost identical). Unfortunately it was a bit challenging because UpdateRecastGraph is not publicly accessible, nor is GraphUpdateProcessor even though ProcessGraphUpdatePromises is static.
In the end I just added a
public bool pauseUpdates { get; set; }
property to the stock ProceduralGraphMover so that the update isnt called every frame.
I should note that after running a simple test with a moving agent for a short while, an IndexOutOfRangeException error in Navmesh/Voxels/CompactVoxelField.cs was thrown:
System.IndexOutOfRangeException: Index 2063597568 is out of range in container of ‘6243’ Length.
This Exception was thrown from a job compiled with Burst, which has limited exception support.
0x00007ffa80fdf86e (Unity) burst_abort
0x00007ffa7b8295de (585ac74d0bd0b669d1811b96ebafc8c) burst_Abort_Trampoline
0x00007ffa7b7a1805 (585ac74d0bd0b669d1811b96ebafc8c) Pathfinding.Graphs.Navmesh.Voxelization.Burst.CompactVoxelField.BuildFromLinkedField (at D:/UnityProjects/Atlas/Library/PackageCache/com.unity.burst/.Runtime/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/CompactVoxelField.cs:94)
0x00007ffa7b7add3a (585ac74d0bd0b669d1811b96ebafc8c) Unity.Jobs.IJobExtensions.JobStruct`1<Pathfinding.Graphs.Navmesh.Jobs.JobBuildTileMeshFromVoxels>.Execute(ref Pathfinding.Graphs.Navmesh.Jobs.JobBuildTileMeshFromVoxels data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, ref Unity.Jobs.LowLevel.Unsafe.JobRanges ranges, int jobIndex) → void_0d64390541958b43604801c180219108 from UnityEngine.CoreModule, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null (at D:/UnityProjects/Atlas/Library/PackageCache/com.unity.burst/.Runtime/unknown/unknown:0)
0x00007ffa7b7a059d (585ac74d0bd0b669d1811b96ebafc8c) c7bd43dad8afab74e2910a0eea3eeaf4
0x00007ffa80fdbf45 (Unity) ExecuteJob
0x00007ffa80fdd05d (Unity) ForwardJobToManaged
0x00007ffa80fd9259 (Unity) ujob_execute_job
0x00007ffa80fd864f (Unity) lane_guts
0x00007ffa80fdb294 (Unity) worker_thread_routine
0x00007ffa811d10fd (Unity) Thread::RunThreadWrapper
0x00007ffb214c7374 (KERNEL32) BaseThreadInitThunk
0x00007ffb2251cc91 (ntdll) RtlUserThreadStart
Any ideas what might be causing this?
Huh, I’ve never seen this before. Can you replicate it?
Yes, if I leave it running for a little while (around 10 mins) I get an exception.
I’ve created a new simple scene with a procedural graph mover, a recast graph and just one agent:
System::InvalidOperationException: The UNKNOWN_OBJECT_TYPE has been declared as [ReadOnly] in the job, but you are writing to it.
This Exception was thrown from a job compiled with Burst, which has limited exception support.
0x00007ffabb92fcee (Unity) burst_abort
0x00007ffabbd1f4b3 (Unity) scripting_raise_exception
0x00007ffabaec82d0 (Unity) AtomicSafetyHandle_CUSTOM_CheckWriteAndThrowNoEarlyOut
0x00007ffb135a5ec7 (628eb4e06f5f6dbde898c5d86a96994) Unity.Collections.LowLevel.Unsafe.AtomicSafetyHandle.CheckWriteAndThrowNoEarlyOut (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/unknown/unknown:0)
0x00007ffb135a5e70 (628eb4e06f5f6dbde898c5d86a96994) Unity.Collections.LowLevel.Unsafe.AtomicSafetyHandle.CheckWriteAndThrow (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/unknown/unknown:0)
0x00007ffb135fa7dd (628eb4e06f5f6dbde898c5d86a96994) Unity::Collections::NativeListPathfinding::Graphs::Navmesh::Voxelization::Burst::LinkedVoxelSpan::Unity.Collections.NativeList1<Pathfinding.Graphs.Navmesh.Voxelization.Burst.LinkedVoxelSpan>.set_Item (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/Library/PackageCache/com.unity.collections/Unity.Collections/NativeList.cs:166) 0x00007ffb13630979 (628eb4e06f5f6dbde898c5d86a96994) Pathfinding::Graphs::Navmesh::Voxelization::Burst::LinkedVoxelField::Pathfinding.Graphs.Navmesh.Voxelization.Burst.LinkedVoxelField.AddLinkedSpan (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/LinkedVoxelField.cs:240) 0x00007ffb1362fa56 (628eb4e06f5f6dbde898c5d86a96994) Pathfinding::Graphs::Navmesh::Voxelization::Burst::JobVoxelize::Pathfinding.Graphs.Navmesh.Voxelization.Burst.JobVoxelize.Execute (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelRasterization.cs:243) 0x00007ffb1365b86f (628eb4e06f5f6dbde898c5d86a96994) Pathfinding::Graphs::Navmesh::Jobs::JobBuildTileMeshFromVoxels::Pathfinding.Graphs.Navmesh.Jobs.JobBuildTileMeshFromVoxels.Execute (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs:153) 0x00007ffb136651bb (628eb4e06f5f6dbde898c5d86a96994) Unity.Jobs.IJobExtensions.JobStruct1<Pathfinding.Graphs.Navmesh.Jobs.JobBuildTileMeshFromVoxels>.Execute(ref Pathfinding.Graphs.Navmesh.Jobs.JobBuildTileMeshFromVoxels data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, ref Unity.Jobs.LowLevel.Unsafe.JobRanges ranges, int jobIndex) → void_5126781a4ae49aeaf55e28cc98e6b8dc from UnityEngine.CoreModule, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null (at D:/UnityProjects/AStarTesting/Library/PackageCache/com.unity.burst/.Runtime/unknown/unknown:0)
0x00007ffb1365af17 (628eb4e06f5f6dbde898c5d86a96994) c7bd43dad8afab74e2910a0eea3eeaf4
0x00007ffabb92c3c5 (Unity) ExecuteJob
0x00007ffabb92d4dd (Unity) ForwardJobToManaged
0x00007ffabb9296a9 (Unity) ujob_execute_job
0x00007ffabb928a9f (Unity) lane_guts
0x00007ffabb92b714 (Unity) worker_thread_routine
0x00007ffabbb2157d (Unity) Thread::RunThreadWrapper
0x00007ffb6d0a7374 (KERNEL32) BaseThreadInitThunk
0x00007ffb6d8dcc91 (ntdll) RtlUserThreadStart
Astar Thread Count: Automatic Low Load
Agent:
Seeker
Character Controller
Funnel Modifier
Random Movement Script:
using UnityEngine;
using Pathfinding;
using System.Collections;
public class Agent : MonoBehaviour
{
public float speed = 20;
private Vector3? targetPosition = null;
private NNConstraint areaConstraint;
private Seeker seeker;
private CharacterController controller;
private float nextWaypointDistance = 1.5f;
private float repathRate = 0.5f;
private Path path = null;
private int currentWaypoint = 0;
private float lastRepath = float.NegativeInfinity;
private bool reachedEndOfPath = false;
private bool isWaiting = false;
public void Awake()
{
seeker = GetComponent<Seeker>();
controller = GetComponent<CharacterController>();
areaConstraint = NNConstraint.Walkable;
areaConstraint.constrainArea = true;
}
public void OnPathComplete(Path p)
{
p.Claim(this);
if (!p.error)
{
if (path != null) path.Release(this);
path = p;
// Reset the waypoint counter so that we start to move towards the first point in the path
currentWaypoint = 0;
}
else
p.Release(this);
}
public void Update()
{
if (isWaiting || AstarPath.active.isScanning)
return;
if (reachedEndOfPath || !targetPosition.HasValue)
{
StartCoroutine(WaitAndSetNewTarget());
return;
}
if (Time.time > lastRepath + repathRate && seeker.IsDone())
{
lastRepath = Time.time;
seeker.StartPath(transform.position, targetPosition.Value, OnPathComplete);
}
if (path == null)
{
return; // We have no path to follow yet, so don't do anything
}
PathXZDistanceCheck();
// Direction to the next waypoint.
Vector3 dir = (path.vectorPath[currentWaypoint] - transform.position);
Vector3 moveDirection = new Vector3(dir.x, 0, dir.z).normalized;
// Multiply the direction by our desired speed to get a velocity
Vector3 velocity = moveDirection * speed;
// Move the agent using the CharacterController component
controller.SimpleMove(velocity);
}
private void PathXZDistanceCheck()
{
Vector3 playerPosition = transform.position;
Vector2 playerPos2 = new Vector2(playerPosition.x, playerPosition.z);
while (true)
{
Vector3 currentWaypointVector = path.vectorPath[currentWaypoint];
Vector2 vecNoHeight = new Vector2(currentWaypointVector.x, currentWaypointVector.z);
float distanceToWaypoint = Vector2.Distance(playerPos2, vecNoHeight);
if (distanceToWaypoint < nextWaypointDistance)
{
// Check if there is another waypoint
if (currentWaypoint + 1 < path.vectorPath.Count)
{
currentWaypoint++;
}
else
{
reachedEndOfPath = true; // indicate that the agent has reached the end of the path.
break;
}
}
else
{
break; // Not close enough to waypoint, so exit the loop
}
}
}
private IEnumerator WaitAndSetNewTarget()
{
isWaiting = true;
yield return new WaitForSeconds(0.5f);
path = null;
reachedEndOfPath = false;
targetPosition = GetRandomDestinationInArea(transform.position);
isWaiting = false;
}
public Vector3 GetRandomDestinationInArea(Vector3 start)
{
// Find a valid starting node
NNInfo nninfo1 = AstarPath.active.GetNearest(start, NNConstraint.Walkable);
if (nninfo1.node == null)
{
Debug.LogError($"GetNearest start {start} could not be found!");
return start;
}
areaConstraint.area = (int)nninfo1.node.Area; // make sure area matches
NNInfo sample = AstarPath.active.graphs[0].RandomPointOnSurface(areaConstraint);
if (sample.node == null)
{
Debug.LogError($"RandomPointOnSurface from start {start} could not be found!");
return start;
}
return sample.position;
}
}
Let me know if you need more info.
Thanks.
Would it be possible for you to share this as an example project with us?
Yes no problem - what’s the best way to get it over to you?
@aron_granberg can I email or upload it somewhere?
@GenericJoe Sadly we haven’t been able to replicate this, after running the scene for 20 minutes.
Ah OK. That’s strange how it throws this error for me - I’ll keep an eye on it, and see if there is a better more consistent way to recreate it.
1 Like
