Mass Updating of Grid Graph

#1

Hi,

I have a grid graph and the “small” map in my game has it at 320x320 nodes. The user can paint the terrain in my game with a brush that is 10x10 world units and that is updating 50x50=2500 nodes every frame. The slowest parts of this update is RecalculateCell() which is doing ray casts for the heights and the capsule casts.

I have the height data in a heightmap and so i don’t need to do raycasts, even without this bit it’s quite slow. Am i able to parallelise any of these node updates with jobs in the GraphUpdateObject callback?

Thanks,

#2

Hi

That’s a lot of updates every frame. I’d recommend that you at least do some batching to combine updates for say 10 frames and update the total bounding box that could have changed in those 10 frames (just do Bounds.Encapsulate).

You can also upgrade to the beta version which has significantly faster grid graph scanning (it uses burst and the unity jobs system, among other things all raycasts are parallelized). It is also possible to write your own grid graph rules (to for example read from a custom heightmap). See this tutorial: https://www.arongranberg.com/astar/documentation/dev_4_3_43_939d7455/gridrules.html

#3

Hi Aron,

Thanks. I would definitely upgrade to the latest but I’m not not sure which Unity account i purchased it against and i can’t seem to find that. I have an internal Unity licence (because I work there) and i have a personal one.

Are you able to help with this? If i can sort that out I can atleast upgrade.

Thanks,

#4

Ah ok I’ve found the account where i bought it.

#5

Hi Again,

So since updating my graph updater object is no longer being run. I’ve had a go at debugging the package but can’t see anything obvious. Is there documentation on anything that’s changed in this regard?

Thanks

#6

Ah so i’m supposed to implemented ApplyJob<>() it seems :). Is there an example of this somewhere?

Thanks,

#7

So I’ve successfully got this working with ApplyJob. I only seem to get one ApplyJob callback though, i was hoping that it might divid the nodes to be updated over many threads.

Is this possible?

#8

Hi

In that function you are supposed to schedule a job, not do the work itself. You can for example schedule a batch job if you want, to be able to parallelize it even more. You are passed an instance of a JobDependencyTracker (https://www.arongranberg.com/astar/documentation/dev_4_3_43_939d7455/jobdependencytracker.html) which you can use to schedule the job. See https://www.arongranberg.com/astar/documentation/dev_4_3_43_939d7455/ijobextensions.html. For example you can use myjob.ScheduleBatch (making sure to pass the dependency tracker).

You can find an example of the implementation in the GraphUpdateObject class.

#9

Hi Aron,

Thanks. So at first glance ScheduleBatch is just about raycasting. I can avoid doing any raycasts at all because i already know the node heights from my heightmap. The work i am doing (incorrectly it seems) in ApplyJob is as follows:

		public override void ApplyJob<T>(T mapper, GraphUpdateData data, JobDependencyTracker dependencyTracker)
		{
			base.ApplyJob(mapper, data, dependencyTracker); 

			dependencyTracker.AllWritesDependency.Complete();

			TerrainGenerator generator = m_terrain.m_terrainGenerator;
			int courseSubTilesWidth = generator.GetCourse().GetDims().x * CourseCell.s_subTilesWidth;
			int heightMapWidth = courseSubTilesWidth + 1;

			for (int idx = 0; idx < data.nodePositions.Length; ++idx)
			{
				Vector3 position = data.nodePositions[idx];

				position -= new Vector3(0.5f, 0.0f, 0.5f);
				position += new Vector3(heightMapWidth / 2, 0.0f, heightMapWidth / 2);

				float height = GameStateManager.Instance.GetGameState().m_courseGameState.m_heights[(int)position.z * heightMapWidth + (int)position.x].m_height;
				data.nodePositions[idx] = new Vector3(data.nodePositions[idx].x, height, data.nodePositions[idx].z);
				data.nodeWalkable[idx] = !GameStateManager.Instance.GetGameState().m_courseGameState.m_occupancy[(int)position.z * courseSubTilesWidth + (int)position.x].m_occupied;
			}
		}

To speed this up I basically want to jobify the loop contents into batches without doing casts. One thing i couldn’t figure out here was how i was supposed to know where in the ‘data’ member i was indexing. I couldn’t get at the GridIndexMapper. Instead I did this based on knowing where the nodes would be in the scene relative to my terrain. It’s a total hack but works.

Can i just spawn myself some jobs without using the dependency tracker?

Thanks

#10

Ah after a deeper look I can see more general batch scheduler in the base class.

Ill try this.

Thanks

#11

Hi Aron,

I’m now in the optimisation phase of my game. I am using the approach discussed above and am finding that my update job is now the fastest part of the astar update in my frame. The job is being given a GraphUpdateObject.GraphUpdateData that contains about 2100 nodes. This is the profile:

image
image2167×959 275 KB

As you can see for the third column with the jobs called NavigationBuilder.Job are pretty quick now but the rest of the work item is 8ms. I fear that all of this logic is deep within the AStar code.

Do you have any advice for what i can do to improve this time? 8ms is pretty much halving my framerate at this point and it’s not really acceptable for release.

Thanks in advance,

#12

Hmm, are you sure that’s only 2100 nodes?
I tried to replicate it, but for me an update of that size takes only about 3ms. Though admittedly my computer is quite beefy.

image
image997×585 51.9 KB

What is your erosion iterations setting set to?

Also which version of the package are you using?

#13

Hi,

Thanks for getting back. I’m pretty sure it’s around 2100 but i’ll double check. The version i’m on is 4.3.43.

Here is a bit more info - this is a capture without capsule checking, without height checking and by calling UpdateGraphs directly with the bounds rather than my updater object. I’m not doing any of my own logic in this case.

I realised that i don’t need capsule checking or height checking as i have all the nav-blocking and height data calculated already so that’s why i’ve disabled that (but not replaced it yet, i’ll try rules for that).

image
image3071×1026 295 KB

image
image777×1008 30.3 KB

Thanks,

#14

Hi

Your allocating buffers step is taking a suprisingly long time. Do you have leak tracking enabled in the burst compiler settings by anny chance? You can also get somewhat better performance by disabling burst safety checks.

#15

Should i see Burst in the package manager or do you bring it in as a dep?

#16

Got it, yes full stacks were and safety checks, now testing.

#17

That has fixed the buffer allocation cost:

image
image3058×1232 378 KB

1 Like
#18

I’m pulling nav penalties, node navigable state and height from my terrain data - is it quicker to add a rule for each of these things or use a monolithic update object as im doing now?

#19

Probably the cost is about the same unless there is some significant amount of shared code. Do whatever is easiest for you.

#20

Are you doing one of these updates per frame? What makes you have to update the graph that often?