We are using A* for one of our projects and we are currently facing a major obstacle. i’ll give a brief over view of our work flow and hopefully u can assist us in finding a solution.
the agents are spawned by a manager on spawn points.
we then add a 20x20 grid graph to each agent.
afterwards we add the procedural grid mover script to each agent
the path finding loop is the following:
each agent is given a target position outside their grid graph.
we get the closest node on the grid to the target position (usually on the edge of the grid)
agent moves to the nearest node on thier graph, grid position is updated and so on till it reaches the actual target.
both the seeker and the grid have the “Terrain” layer on thier mask only.
here’s the path searching bit.
public override void SearchPath()
{
if (target == null) throw new System.InvalidOperationException(“Target is null”);
lastRepath = Time.time;
//This is where we should search to
var nearestNode = AstarPath.active.graphs[GraphIndex].GetNearest(target.position);
Vector3 targetPosition = nearestNode.clampedPosition;
canSearchAgain = false;
//Alternative way of requesting the path
// ABPath p = ABPath.Construct (GetFeetPosition(),targetPosition,null);
//seeker.StartPath (p);
//We should search from the current position
seeker.StartPath(GetFeetPosition(), targetPosition);
}
Graph index is set by the scripts that spawns the grid graph underneath the agent. the code snippet for that is here:
foreach (var agent in AgentsList)
{
var spawnedGraph = AstarPath.active.astarData.AddGraph(typeof (GridGraph)) as GridGraph; //Debug.Log(“Spawned Graph is…”+spawnedGraph);
THE PROBLEM: path failure, if more than 1 agent is
spawned with the procedure i mentioned above, we get random path failures and the more the agents the less likely any seeker will successfully navigate to the target point.
below is a screenshot of the seeker settings.
I cannot write a long reply right now as I am only using my phone, but for a start I think you should add the graphMask parameter to the seeker.StartPath call to specify which graph each agent should use when pathfinding. If graphs overlap, this could be the cause.
Also, make sure the inspector - > Settings - max nearest node distance field is set sufficiently high.
What exact error are you getting from the path requests when they fail?
I’ve followed your feedback by increasing the max nearest node distance. it has resulted in allowing up to 5 agents with this setup to reach the target relatively with no problems. but i still get the path failure error, below is a screenshot of the agents with my log.
i still have not added a graph mask parameter as i am not quite sure if am using a layermask correctly.
but for example, if wanted the agent to search on his graph, the mask would be: 1 << GraphIndex, is this correct?
So the error is “Could not find a node close to the end point” so I would guess that you would want to increase the “Max Nearest Node Distance” further, and also try to add the graph mask parameter.
Hello Aaron, so i added the graph mask parameter and tweaked the max nearest node distance to a crazy number 3.402823e+38. i had significantly better result, now up to 8+ agents navigate to the target without any problem and even with 27 graphs & agents no path failures. however, the agents get stuck below is a screen shot.
Furthemore, i was debugging the graph mask and by the 27th agent it gave me a big value. could this be the cause? below is a screen shot.
below is the code snippet for getting GraphIndex:
foreach (var agent in AgentsList)
{
var spawnedGraph = AstarPath.active.astarData.AddGraph(typeof (GridGraph)) as GridGraph; //Debug.Log(“Spawned Graph is…”+spawnedGraph);
public override void SearchPath()
{
if (target == null) throw new System.InvalidOperationException(“Target is null”);
lastRepath = Time.time;
//This is where we should search to
var nearestNode = AstarPath.active.graphs[GraphIndex].GetNearest(target.position);
Vector3 targetPosition = nearestNode.clampedPosition;
canSearchAgain = false;
//Alternative way of requesting the path
// ABPath p = ABPath.Construct (GetFeetPosition(),targetPosition,null);
//seeker.StartPath (p);
//We should search from the current position
int graphMask = 1 << GraphIndex;
Debug.Log("Graph mask is...."+graphMask);
seeker.StartPath(GetFeetPosition(), targetPosition,null,graphMask);
}
I cannot see any errors in the console, so pathfinding seems to work fine.
However you should know that you have quite a lot of graphs, and updating them all is not cheap. I would not be surprised if a large portion of the time is spent updating the graph and during that time the pathfinding threads need to be paused.
Since the graph mask is an int, you will not be able to have more than 32 units at any time. The graph mask can be extended to allow more graphs, but be wary of the performance implications of so many graphs that you update constantly.
The graph mask will be a big number. 1 << N means the Nth bit is set or the number 2^N. And 2^27 is 134217728.
The reason for the large amount graphs partially due to having a run-time procedurally generated terrain. i cannot bake the graph at editor time and the terrain is 1000 * 1000 so it’s quite expensive to have one massive graph. if you can provide some advice on how to approach the matter i would be very grateful.
because in our game we will have quite a lot of agents, and the reason i chose the small graph per agent is that allows for freedom of path finding so any agent can move to any point. while in the case of a larger graph there could be the situation of agents getting stuck.
Update: i integrated a large re-cast graph for testing, the agents now seem to get stuck if there is no direct edge between them and the target point or so i assume. below is a screen shot. the agent just returns path completed
I am not sure why the agent is getting stuck. If you are using a character collider, make sure the max slope is set to a high enough value.
It’s hard to say how large the tiles should be, but generally you want to break up huge triangles. In your screenshot there are definitely huge triangles, so I would suggest to lower the tile size to maybe 1/3 of the current value in order to avoid very suboptimal paths from being calculated.
Also, you don’t seem to have any obstacles on the terrain? Are those going to be added later?
Today i will be implementing the solutions you suggested, i’ll let you know how that goes. However, as for the obstacles yes those shall be included later.
Furthermore, i was wondering if it’s possible to scan only a section of a very large graph or update only that section. since you recommended to avoid smaller graphs per agent, my alternative is to use a large recast graph for the terrain. however, the time to scan such a graph is quite a lot. and i see you recommended to use even smaller tiles which will add up in the scan time. so what are the performance aware alternatives if i cannot afford to scan a 2000 * 2000 recast graph? also the graph will be generated on run-time that’s why scan time is quite critical.
Sure, take a look at this documentation page: http://arongranberg.com/astar/docs/graph-updates.php
Also, in the latest beta you can scan graphs over multiple frames, that could allow you to show a non-freezing loading screen if it is done at the start of the game.
Smaller tiles will increase the scan time a bit, but not that much.
Let me rephrase my question: can i control which tiles get scanned in a recast graph? the reason i would like to be able to do this is that the player wont need the whole 2000 * 2000 graph scanned and ready at the start so if he only uses lets 300 * 300 i’d like to scan a specific region only around the player for example.
First, you want to disable Scan On Awake (A* Inspector -> Settings) because otherwise the graph will already have been scanned when you apply the settings.
Which will now yield a completely empty graph.
You can now use graph updates (see link in previous post) to recalculate the specific tiles you want. These updates will even run in a separate thread (assuming multithreading is enabled).
