Support Forum

Simplest way to detect 'broken street path'

I have a city builder, and I simply want to detect when the street network has a ‘breach’ (is not fully connected) currently I have 2 pathfinder grids, one in the map sea area for ships and one in the air for planes.

What would be the cheapest way to achieve this simple feature on land with the streets? Could you give me some advice?
PS: last time I worked with your asset was 1 year ago so bear with my possible loss of memory of some concepts.

please? how could I achieve this ? any guidance would be useful

The only way that comes to mind is to create a Graph with the streets as nodes and check ALL nodes connections to all nodes whenever there’s a change on the streets but seems quite heavy and I was just wondering if there’s a more optimal way of achieving this.

Are the red/green tiles walkable in the grid graph? It’s not quite clear from the question.

yes, every colored tile is a walkable street.
When I set them red means the graph (the street network) is broken because Is not ALL connected

When they are not connected the node.Area field will be different.
You can check if they are all connected by checking PathUtilities.IsPathPossible(list of all street tiles).
See https://arongranberg.com/astar/docs/pathutilities.html#IsPathPossible2

YES, this is what I was looking for.
May I ask if this is an expensive operation taking into account my map is 128x128 ?

Or maybe it is possible to call it async ?

It’s very cheap. Basically it just loops through the nodes and checks if their Area field is the same.

See also https://arongranberg.com/astar/docs/graphnode.html#Area
and https://arongranberg.com/astar/docs/hierarchicalgraph.html for the underlaying implementation details.

You might also be interested in the “Check for blocking placements” section on this page: https://arongranberg.com/astar/docs/graph-updates.php#blocking

1 Like

Hi again, I finally could do what I wanted. But I have some doubts about how I achieved it and if its the best way:
Here is how I set up the graph dedicated to the street tiles, the street tiles have the layer “Street”

Here is what I call when a street tile is built or removed, the dictionary posToNode keeps the current street nodes:
Captura de pantalla 2021-04-20 a las 19.38.04

This is how the map looks:
Captura de pantalla 2021-04-20 a las 19.34.53

When I want to check if they are connected I simply do:
PathUtilities.IsPathPossible(postoNode.Values.ToList())

This seems to work fine.

With this setup I create a big amount of nodes depending on the map size, I have 2 graphs more for ships navigation and planes and im worried about performance.
I’m wondering if it would not be easier just to create nodes where the streets are, that should be more optimal since on a big map I would create much less nodes, just where the streets are. Is this a bad idea or not possible?

Also I dont understand is why you suggested me to use the HierarchicalGraph, and how should I use it, I didnt see the option in the A* ui to add any Graph of that type. (im using 4.2.15 pro)

Thanks a lot for your help.
pistoleta

Okay, it doesn’t seem to work fine.
On first start detects well if there’s path or not, but whenever I remove 1 street keeps thinking there is a path.

Remove street:
1.get node from that street tile and set it to walkable false
2. remove node from street node dictionary
3. call again PathUtilities.IsPathPossible(posToNode.Values.ToList())

Am I doing something wrong?

Hi

If you set A* Inspector -> Settings -> Graph Coloring to “Areas”, can you see if the streets get different colors?

Thanks I didnt know I could color the areas but debugging the nodes I see what’s happening now.
Whenever I add 1 street the areas get updated well. But when I remove they dont. Im not sure why…

Example I have 2 areas 60 and 61… if I add 1 street that unites them then all nodes turn area 63

But if I do the opposite… having 1 area all same and I remove, the nodes dont get updated and all have still the same area.

Hm, if you are changing the walkability of a node you should also recalculate its connections. Maybe that’s the issue here. Try calling

node.Walkable = false;
AstarPath.active.data.CalculateConnectionsForCellAndNeighbours(node.XCoordinateInGrid, node.ZCoordinateInGrid)

This is what I tried, but still not updating the areas when removing.

    public void RemoveStreet(Vector3 tile, Bounds bounds)
    {
	    AstarPath.active.AddWorkItem(new AstarWorkItem(ctx =>
	    {
		    var node = streetGraph.GetNearest(tile).node as GridNode;
		    RemoveNodes(Utils.V3WorldToV2UnitInt(tile),node);
		    node.Walkable = false;
		    streetGraph.CalculateConnectionsForCellAndNeighbours(node.XCoordinateInGrid, node.ZCoordinateInGrid);
		    ctx.QueueFloodFill();
	    }));
	    
    }

Hmm, that’s very strange.

Btw, I think the QueueFloodFill method is deprecated even in your version. Do you not get a deprecation warning in your editor? (I’m not quite sure when it was deprecated, might only be deprecated in the beta).

Could you send me a screenshot of your map (with the area visualization) after you have removed some nodes?

I just removed them because there were warnings you are right.

Just loaded:
2 areas,
IsPathPossible returns false (Correct)

Captura de pantalla 2021-04-21 a las 16.30.21

Street added.
1 area
IsPathPossible returns true (Correct)
Captura de pantalla 2021-04-21 a las 16.31.42

Street removed
1 area
IsPathPossible returns true (Incorrect)

Captura de pantalla 2021-04-21 a las 16.33.00

More streets removed
(same)
Captura de pantalla 2021-04-21 a las 16.35.32

After pushing scan again in scene:

If I push scan again the areas seems to be right but IsPathPossible returns true (which in this case is wrong) because the dictionary im using to keep the street nodes is keeping the old areas after the scan.

Captura de pantalla 2021-04-21 a las 16.37.10

Hi

In your street removed pictures it doesn’t seem like the nodes have been made unwalkable. According to the graph visualization they are still walkable (they would turn into red cubes otherwise).

Yeah i know but what im doing wrong? check this out:
Captura de pantalla 2021-04-21 a las 16.51.27

I call to update the graph on the boundary of the removed street 1 second later and all works fine.
Is this how is supposed to be?

If I call it with no delay it doesnt work.