A* Pathfinding Project

Scanning recast graph for procedural runner game


#1

I’m working on a project (a runner game) where segments are added in and removed as one would expect for this type of game. I have a player object that will basically always be the world center. I tried updating my graphs doing the following:

RecastGraph recastGraph = AstarPath.active.data.recastGraph;
        recastGraph.forcedBoundsSize = new Vector3(150f, 8f, 150f);
        recastGraph.forcedBoundsCenter = runnerFollower.cameraTarget.transform.position;
        recastGraph.Scan();

The problem is that this causes a very noticeable lag in gameplay. Would there be a better way to go about this? I’m calling this code whenever a section is added or removed from my world.

Thanks!


#2

Hey,

Due to the nature of how Recasts graphs work, I wouldn’t recommend it for procedural levels.
I’d recommend looking into the procedural grid mover (example scene), to get you started.


#3

Thanks! I tried the procedural grid mover but it was throwing a lot of errors. I’ll give it another shot.


#4

@alanmthomas Let me know which errors you are getting if they still show up.


#5

Here’s what I’m getting:

IndexOutOfRangeException: Index was outside the bounds of the array.
Pathfinding.ProceduralGridMover+d__12.MoveNext () (at Assets/AstarPathfindingProject/ExampleScenes/Example12_Procedural/ProceduralGridMover.cs:254)
Pathfinding.ProceduralGridMover+<>c__DisplayClass11_0.b__0 (Pathfinding.IWorkItemContext context, System.Boolean force) (at Assets/AstarPathfindingProject/ExampleScenes/Example12_Procedural/ProceduralGridMover.cs:136)
UnityEngine.Debug:LogException(Exception, Object)
Pathfinding.<>c__DisplayClass11_0:b__0(IWorkItemContext, Boolean) (at Assets/AstarPathfindingProject/ExampleScenes/Example12_Procedural/ProceduralGridMover.cs:141)
Pathfinding.WorkItemProcessor:ProcessWorkItems(Boolean) (at Assets/AstarPathfindingProject/Core/Misc/WorkItemProcessor.cs:299)
AstarPath:PerformBlockingActions(Boolean) (at Assets/AstarPathfindingProject/Core/AstarPath.cs:881)
AstarPath:Update() (at Assets/AstarPathfindingProject/Core/AstarPath.cs:864)


#6

Huh. With the default configuration?
That’s odd.

You can try to download the latest beta which has a fix for the procedural grid mover when used with non-square grid graphs.


#7

I’m still running 2019.2.13f, so I’m not sure, based on the notes, that the beta will work.


#8

I opted to try something different. I’m curious to see if you think there is anything wrong with this approach. I have an object (my camera’s focus point, being tracked by a CineMachine Virtual Camera) that is responsible for causing new path segments to be generated. My path is long and narrow, so I set my grid graph based on that. Players will always be in close proximity to that focus object. The level starts, I generate the initial level components, and then call this to generate my grid graph:

GridGraph gridGraph = AstarPath.active.data.gridGraph;
gridGraph.center = runnerFollower.cameraTarget.transform.position;
gridGraph.rotation = runnerFollower.cameraTarget.transform.eulerAngles;
gridGraph.Scan();

Whenever a new segment is generated, I call this again. This seems to be working well, but, again, I’m wondering if this is not an ideal approach for some reason. I had initially been attempting to use the recast graph as I couldn’t get smooth movement from using a grid graph. I think that comes down to the RVO Controller settings I had. Grid Graph is giving smooth movement everything SEEMS okay. The graph scans are taking about 10 to 15ms to complete, so I’m not seeing any lag.


#9

Hi

That will work. This is close to what the procedural grid mover does, but it is more optimized to only recalculate the nodes that really need to be recalculated.

I am guessing that your error came from you using a non-square grid graph with the ProceduralGridMover. It will work if you upgrade to Unity 2019.3 and use the beta. Otherwise you can use your current approach if that works well, and then maybe later in your game’s development you can upgrade and improve the performance.


#10

I actually am using a square grid graph. I found that if I decrease the size of it to the default values I stop getting those errors, however, I need it to be larger than the default size, so I’m not sure what could be causing the errors.


#11

Also, and perhaps I’m handling something incorrectly, but when I use a recast graph I have no issues with keeping agents constrained within the graph. However, with grid graphs, they are routinely being pushed out or even walking out on their own.

When additively loading a saved recast graph, is it possible to specify its position in the world or does that take me back to the initial issue that I started this whole thread with?


#12

There is an option on the agents to constrain them to graph. Unless some external forces push them off.

The graphs relative position to the A* object is what’s being serialized. But you might be able to bake each tile type, and load it in, modify the position to match.


#13

If you’re able to share the graph settings you used Ill try to reproduce the errors for you, and we can get it fixed :slight_smile:


#14


I’m including 2 images. First is one of the graph settings I am using that cause issues with the procedural grid mover. I’ve been able to overcome that somewhat but it is clearly not optimal. The next images shows some of why I am probably encountering the other issues (with agents being pushed off of meshes). I was able to fix that by putting invisible walls around the path that they follow. As you can see, it is a long corridor type of path. Using the RVO Navmesh component is, for the most part, keeping the agents from falling off. However, since it is a grid graph, you wind up with those corners and occasionally (actually, frequently) the agents are colliding with them.


#15

Ah, ye but like Aron said, you’re running in the non square issue. ( we meant the grid being square in shape, not the nodes being set to squares :stuck_out_tongue: ). There is a fix available for that in the a more recent version (4.1.10). If you don’t want to do a full upgrade you could just take the script from the new version. Should work.

You could probably reduce the node size to get more data to play with. Adding Erosion Tag to keep agents further from the edges,…

Agents also have the constrainInsideGraph option to prevent them from falling off entirely.


#16


AHHH! I see now about the squares! D’oh! Thanks! I’m currently running version 4.3.1 (Pro). I’ll try reducing the node size and playing with erosion as well. My agents already have the constrainInGraphOption set. I think the problem is that there are so many of them in such a tight space. Using the RVO navmesh has helped with that some.


#17

Also, I realized now in watching the playback at slower speed that the bumping issue I’m running into is coming from the graph being scanned entirely and an obstacle essentially being dropped right in from of an agent. If I could get the moving grid working it would quite likely fix this.


#18

I can confirm that setting the grid size to a square resolves those issues with the Procedural Grid Mover. However (another however. Sorry.) it causes other issues for me. The agents on the mesh have snappy movement and still manage to fall off the mesh.


#19

Hi

With a procedurally updated graph I would actually recommend not using the RVONavmesh component. It will be quite slow as it has to rebuild a ton of things every time the graph changes.
Using the ‘constrain to inside graph’ checkbox on the movement script should snap the agents to be inside the graph every frame. Is this not working for you?


#20

They do not stay constrained inside the graph for some reason.

On the other issue, if I wanted local avoidance on a procedural update graph, what should I do? I looked at Unity’s navmesh surface components. I didn’t realize that they had been updated at some point. They have a local navmesh builder in that package that works well, however their local avoidance is rubbish. Is there any way that AStar would work with that?