First of all, I have to say I am pretty amazed with the A* Pathfinding Project. It took me less than half an hour of coding and reading to have an agent working on my area.
Now to my question:
In the game I am making, the player gets to build structures (walls, place furniture etc). What I am trying to do is see if placing a wall would result in an unreachable island and warn the player of this by turning the blueprint red.
When I switch on the grid in the editor view and make a blocked off area - for instance a room that is blocked off - I see that the area inside is darkened to red, I assume it’s to indicate a non-walkable area.
Is there a way to find if the grid contains any non-reachable but walkable areas, and is it at all possible to check if the placement I’m trying to do will result in one (without having to update the graph, preferably)?
There is an API for a similar thing here: https://arongranberg.com/astar/docs/graph-updates.php#blocking (bottom of page). Though it isn’t exactly what you want to do unfortunately. Below I have adapted the code for that method to work for your use-case.
The red area that you see is just an indication that it is a separate connected component of the graph that cannot be reached by paths from anywhere else. You should be able to get it working like this:
public static bool UpdateGraphsNoBlock (GraphUpdateObject guo, bool alwaysRevert = false) {
// Track changed nodes to enable reversion of the guo
guo.trackChangedNodes = true;
bool worked = true;
// Pause pathfinding while modifying the graphs
var graphLock = AstarPath.active.PausePathfinding();
try {
AstarPath.active.UpdateGraphs(guo);
// Update the graphs immediately
AstarPath.active.FlushGraphUpdates();
// Check if all nodes are in the same area
uint area = uint.MaxValue;
foreach (var graph in AstarPath.active.data.graphs) {
if (graph != null) graph.GetNodes(node => {
if (node.Walkable) {
if (area == uint.MaxValue) {
area = node.Area;
} else if (area != node.Area) {
// Found at least 2 different areas (connected components)
worked = false;
}
}
});
}
// If it did not work, revert the GUO
if (!worked || alwaysRevert) {
guo.RevertFromBackup();
// The revert operation does not revert ALL nodes' area values, so we must flood fill again
AstarPath.active.FloodFill();
}
} finally {
graphLock.Release();
}
// Disable tracking nodes, not strictly necessary, but will slightly reduce the cance that some user causes errors
guo.trackChangedNodes = false;
return worked;
}
This code above works for an update that will be released today or possibly tomorrow. For the current version I think this should work:
public static bool UpdateGraphsNoBlock (GraphUpdateObject guo, bool alwaysRevert = false) {
// Track changed nodes to enable reversion of the guo
guo.trackChangedNodes = true;
bool worked = true;
// Pause pathfinding while modifying the graphs
AstarPath.active.BlockUntilPathQueueBlocked();
try {
AstarPath.active.UpdateGraphs(guo);
// Update the graphs immediately
AstarPath.active.FlushGraphUpdates();
// Check if all nodes are in the same area
uint area = uint.MaxValue;
foreach (var graph in AstarPath.active.astarData.graphs) {
if (graph != null) graph.GetNodes(node => {
if (node.Walkable) {
if (area == uint.MaxValue) {
area = node.Area;
} else if (area != node.Area) {
// Found at least 2 different areas (connected components)
worked = false;
}
}
return true;
});
}
// If it did not work, revert the GUO
if (!worked || alwaysRevert) {
guo.RevertFromBackup();
// The revert operation does not revert ALL nodes' area values, so we must flood fill again
AstarPath.active.FloodFill();
}
}
// Disable tracking nodes, not strictly necessary, but will slightly reduce the cance that some user causes errors
guo.trackChangedNodes = false;
return worked;
}
Alternatively this method is slightly slower, but has a bit less code and uses fewer low level functions
public static bool UpdateGraphsNoBlock (GraphUpdateObject guo, GameObject objectCausingTheBlock) {
AstarPath.active.UpdateGraphs(guo);
// Update the graphs immediately
AstarPath.active.FlushGraphUpdates();
bool worked = true;
// Check if all nodes are in the same area
uint area = uint.MaxValue;
foreach (var graph in AstarPath.active.data.graphs) {
if (graph != null) graph.GetNodes(node => {
if (node.Walkable) {
if (area == uint.MaxValue) {
area = node.Area;
} else if (area != node.Area) {
// Found at least 2 different areas (connected components)
worked = false;
}
}
return true;
});
}
// If it did not work, revert the GUO
if (!worked) {
GameObject.Destroy(objectCausingTheBlock);
AstarPath.active.UpdateGraphs(guo);
// Update the graphs immediately
AstarPath.active.FlushGraphUpdates();
}
return worked;
}
I haven’t tested any of these methods, but I think they should work.
Many thanks for a VERY quick answer - I am going to give it a whirl, but it isn’t something that I need to get done right away, so I can wait for the update to land.
The first option looks good for my use case, though I’m a bit worried about the graph update time. I am using a node size of 0.25 due to my scale (1x1 unit per tile) and last i checked my world was about 600x600 or 800x800 nodes. It takes a bit of time to do the graph update - I’m using UpdateGraphs with a bounds objects, are GUOs faster?
UpdateGraphs(bounds) is just a convenience method for UpdateGraphs(new GraphUpdateObject(bounds)) so they should perform similarly.
For a graph that large I would suspect the time it takes to complete an update is dominated by the time it takes to calculate the connected components (areas) in the graph. So I would expect the above code would be around 2 to 2.5 times slower than a normal graph update.
Maybe you can create the UI for your game in such a way that you only need to check if the object would block when the user clicks the ‘build’ button as you would have to update the graph anyway in that case.
Thankfully I won’t have any pathing agents in the world while I’m doing te building (it’s all done in a paused mode without any agents whatsoever), so I’ll definitely be doing the graph update only on “build” when the update would be run anyway.
I’ll probably also change the node size, I might get away with a node size of 0.5, though it’ll leave quite large areas around the items unwalkable…
Perhaps another graph would be better for my use case?
Another graph could work. In particular a recast graph might be doable. This would only be faster if you could use navmesh cutting however. You can only use navmesh cutting if you are only removing walkable surfaces from the game, not adding any new ones (e.g on top of the objects that were built).
If you would use a recast graph then the way you would have to update the graph would be (instead of using GraphUpdateObjects):
// Create an object which has a NavmeshCut component
tileHandlerHelper.ForceUpdate();
AstarPath.active.FlushWorkItems();
// The graphs have now been updated
