A* Pathfinding Project

Streamed World With Recast Graph


#1

Hi there,

I am a bit new to using this asset, but I am quite liking it so far! I had a couple of questions regarding streaming terrains and having the recast data load specifically for each terrain.

So my world is about 15km x 15km, and I have split each terrain tile into about 500m x 500m. My idea was to generate a recast graph for each terrain tile, and then have the data for each recast graph load with the terrain the player moved around the world. I also was hoping to cache the recast data into a file so that I could reduce the load times when the different tiles are loaded.

I have been having several issues with this. Each terrain is organized in separate scenes which I load async into the world. My original plan was to have each different scene have an A* component in it, which would contain the grid cache which I could load dynamically from the hard drive like the terrain. This did not work, as I have learned we cannot have more than one A* Path component per scene.

Is there a best practice for this sort of thing? I am a bit unsure as how to approach this, so a little bit of guidance would be great! Would there be any negative performance impacts to have the whole 15km x 15km graph loaded into the world even though a very small portion of it is being used? I realize there would probably be a much greater amount of memory used if I had the graph of the whole world loaded at once, but is there anything beyond that? The recast graph is quite detailed as well, with it having a cell size of 0.25 and tile size of 50.

Any help regarding this would be greatly appreciated :slight_smile:

Thank you, and have a great day!

Matthew


#2

Hi

The recommended practice is to have a single AstarPath component and load/unload graphs on that single component.
Here is the documentation page about how to do that: https://www.arongranberg.com/astar/docs/save-load-graphs.php

There will be barely any negative effects (other than memory usage) unless you are updating the graph during runtime. If you are updating it, there are some things which scale with the size of the graph.
Also make sure that you are using a single tiled recast graph, not multiple recast graphs. With a single graph it knows the layout of the tiles in the world and can optimize the nearest node searches for that. If you would be using (15/0.5)^2 = 900 graphs it would have to search for the closest node in each graph which would be quite slow.

The memory usage of the graph is determined by the number of nodes in it (click on the info button in the graph header, it looks like an italic ‘i’), not the cell size. Though having a lower cell size does usually increase the number of nodes as well.


#3

Thanks for the reply!

I think I will go with the single graph then, as I would not really need to be updating it.

I had another question, if you don’t mind.

I have some water in my game, and would like to make any areas that it covers unwalkable by any units. How would I go about this? I have taken a look at the terrain demo scene, but the Graph Update Scene component seems to require me to place each individual point where it should be unwalkable, and it would not be possible with the size of my world.

I went into this recast scene to test out a scenario. I was hoping that I could get a situation where I could just place the mesh like this cube here, and have all areas that are touching this cube mesh to be unwalkable. Right now the borders are just unwalkable, but this wouldn’t work in my situation as the water doesn’t cover a cube like shape. I noticed that if I adjust the cube so that the bottom of the mesh touches the plane, the bottom part becomes unwalkable. This would work, however the height of the terrain I would want to be unwalkable is not flat in all areas.

Is there a way to do this that I am not seeing yet?

Sorry if this is a silly question, I am still pretty new to this asset.

Thanks!

Matthew


#4

@aron_granberg Just wanted to add a small question here… is there a certain point at which it makes sense to start splitting your graphs due to total graph size, or is going all the way to 200x200km or larger not much of an issue? I mean… generally how large of a graph would we be talking before we start considering the memory usage as an issue on a PC game?


#5

Sorry for the late answer.

For worlds that large, the problem starts to become floating point precision. Above around 15000 world units the floating point precision is not longer higher than 0.001 world units, and at 200 km the precision is about 0.015 world units. This can cause some real issues in some cases when converting between floating point and integer representations. With a precision as low as 0.015 world units (1.5 cm) you might even get graphics glitches or stuttering in object movement. I would not recommend using coordinate values larger than around ±10000 to be sure that doesn’t cause a problem (floating point precision issues are horrible when you run into them, so best try to avoid them when possible).

It’s really hard to say at what size the memory of a recast graph starts to become a problem because it depends a lot on the graph complexity.