A* Pathfinding Project

Remove unconnected areas?


#1

We are planning on using A* Pathfinding Project with the Recastgraph in a multiplayer game.
So far we have been using Unity’s built in NavMesh as the source of truth for where players can go or no. This has the issue of people being able to sometimes get into areas (via “sloppy” custom movement logic) that should not be connected to anything.

With A* Pathfinding Project we were hoping there would be a way to remove unconnected areas

The relevant graph surface looked very promising, but either it does not work as I thought it would or I’m doing something wrong, since it does not seem to do anything when using “Only for completely inside tile” or remove everything when using “Require For All”, even the tile with the relevant graph surface object in it

Is there any way to do this out of the box or is there a simple way to write a “post processing” script to get rid of everything that isnt connected to relevant areas?


#2

Little update on this
This is my current solution which seems to work fine, just marks an areas that are not connected to any of the points as unwalkable:

public class PathfindingExcludeUnconnected : GraphModifier {
    public Transform[] ConnectedPoints;

    public override void OnPostScan() {
        RecastGraph graph = AstarPath.active.data.recastGraph;
        HashSet<GraphNode> connected = new HashSet<GraphNode>();
        List<GraphNode> toSearch = new List<GraphNode>();
        foreach (var t in ConnectedPoints) {
            var n = graph.PointOnNavmesh(t.position, NNConstraint.Default);
            if (n != null) {
                connected.Add(n);
                toSearch.Add(n);
            }
        }

        while (toSearch.Count > 0) {
            var node = toSearch[toSearch.Count - 1];
            toSearch.RemoveAt(toSearch.Count - 1);
            node.GetConnections(n => {
                if (n.Walkable && !connected.Contains(n)) {
                    toSearch.Add(n);
                    connected.Add(n);
                }
            });
        }
        graph.GetNodes(node => {
            if (!connected.Contains(node)) {
                node.Walkable = false;
            }
        });
    }
}

This script is also super helpful to quickly see what areas are actually accessible from the places players can go :wink:


#3

Hi

Sorry for the late answer.
You seem to have already found a solution, but here is another one that is a bit easier as the system already calculates all the information you need.

[EDIT] Actually, this solution will not work inside a GraphModifier.OnPostScan because the relevant info is calculated after that step. I will leave this here because it might be useful context, but your method is pretty good in this case.

RecastGraph graph = AstarPath.active.data.recastGraph;
List<int> validAreas = new List<int>();
foreach (var t in ConnectedPoints) {
	var n = graph.PointOnNavmesh(t.position, NNConstraint.Default);
	if (n != null) {
		if (!validAreas.Contains(n.Area)) validAreas.Add(n.Area);
	}
}

graph.GetNodes(node => {
	if (!validAreas.Contains(node.Area)) node.Walkable = false;
});

You can also visualize the area information in the editor by changing the A* Inspector -> Settings -> Graph Coloring mode to Area.

There is also the RelevantGraphSurface component, but if you are using a tiled recast graph it is a bit annoying to use. If you are not using a tiled recast graph however, it should work well.


#4

I’m trying to use either of the above solutions and am a little bit confused by this comment:

Is this meant to say that only your solution won’t work on OnPostScan or that neither solution will?

I’m able to use OP’s solution in editor mode just fine but I’m finding that it’s not working for me at runtime. However, if I use OnGraphsPostUpdate instead of OnPostScan, that the solution works just fine at runtime. Is executing OnGraphsPostUpdate a sensible thing to do, or am I missing something?

I also tried OnLatePostScan but had the same result as with OnPostScan.


#5

Only my solution. It uses the .Area property, however that is only filled in with correct information after the OnPostScan step.

If OnGraphsPostUpdate works for you, then go for it.


#6

Awesome, thank you very much!