Efficiently determining which buildings are connected by roads

Question

I have a question about the most effective way to detect road connection in a tile based world. Some time ago I already asked for "How to improve performance for expensive functions in 2d city builder" which was about building radius. Those hints were quite useful and worked great. But now in this case I don't see I could use the same way as mentioned in that post. Let's start with my problem by a first image:

You can see 5 buildings on this little map. One on the left/the beginning of the map and four at the end of the long road on the right. All road tiles (separated in the black squares) are connected with each other.

Since I have to check if a building is still connected to the building on the left (which is the city entrance) it's needed to do regular road checks. To avoid doing expensive pathfinding stuff for each building I store the connection information in each road tile to have faster access. In the next image you can see those information. All road tiles have the same information since they are all connected to each other):

That works quite fast in smaller maps but if the map gets bigger, it's getting more expensive. My proceeding is the following: if a building is placed on a map it looks for surrounding roads. For these roads (could be up to 4 - for each direction) I check on and on if the next tile also has surrounding roads and so on. So finally I get an array of road tiles and update the road object information in all of them (whether building has been placed or removed). Do you know any optimization for this procedure already?

Since in a larger map I get an even bigger problem with the following situation:

Now I have a lot of objects on the right part of the map (this can be much, much bigger of course with hundreds of roads and buildings). If the player now disconnects the long road next to the building on the left, a lot of roads need to be updated.

Do you have any idea how I could improve handling this situation?

Answer 1

I'd be tempted to approach this with a Disjoint Set data structure.

This can efficiently answer "are these two items in the same connected set?" (to see if two buildings are connected by roads, for instance) and join two connected sets (like when a new road bridges a gap).

Detecting when a connected set gets disconnected is a bit more involved, but we can use the features of the data structure to cut down on redundant work.

The basic idea is that each element of the set (ie. each road tile) refers to a "parent" element. You can do this with a pointer, or an index/ID, and it can be stored either in the road itself or a parallel array.

To check which connected set an element is in, we follow these references up to the root of the set they're in (a road whose parent is itself):

Road FindRoot(Road road) {
    while ( road.parent != road )
        road = road.parent;

    return road;
}

(This can be optimized with path compression / splitting / halving, where we update these parent references during the lookup process, so future lookups have fewer hops)

We can then check if two items are in the same connected set by checking if they're under the same root:

bool IsConnected(Road a, Road b) {
    return FindRoot(a) == FindRoot(b);
}

So instead of maintaining lists of connected buildings to search through, you can instead check if a road adjacent to your source building and a road adjacent to your destination building are connected. Using the optimizations mentioned above, this approaches a constant-time operation when queried repeatedly.

To build these connected sets, we initialize a road's parent to point to itself. Then, each time two road tiles meet (as when parsing a map on load, or online as the player places new roads), we use the Union function:

void Union(Road a, Road b) {
    Road rootA = FindRoot(a);
    Road rootB = FindRoot(b);

    if(rootA == rootB)
       return; // Already in the same connected set.

    // Join sets under a common root.
    rootB.parent = rootA;
}

(Again, there are optimizations we can apply called Union by Rank or by Size, which help us get flatter trees for faster queries.)

It might look like a lot of pointer-chasing, but if you use the optimizations described in the linked articles then this structure is blazingly fast, with union & find operations taking nearly constant time on average.

When a road tile is removed, we might need to split a group into multiple parts, or fix up parent references that were referencing the removed road. But we can do this in time linear in the number of roads in the connected set:

Clear the parent reference of each road adjacent to the new gap.

Then, run a depth-first search along the road network, using the first of these stubs as a starting point. For each road encountered along the way (including the starting point), set that road's parent to the starting point.

Next, inspect the next road stub bordering the gap. If its parent reference has been set, then it's already connected to the other side via some other route and we don't need to search it again. Otherwise, repeat the search, setting roads in this connected component to have this stub as their parent.

Repeat until all road tiles bordering the removed tile have been updated in this way, and we're back to a valid disjoint set data structure.

For large road networks, you can speed this up by chunking spans of connected road tiles into a "road segment", and operating on segments instead of individual tiles.

Answer 2

You should be using some form of Graph structure. Instead of every road storing information for every other road connected, it should only store the roads that directly connect to it. Or a better way would be to store only the junctions (nodes) and which other junctions connect to it (a dead end should count as a "junction", as should corners), as well as the number of tiles (or cost if you have different road types) between them.

This will give you a graph you can pathfind on. You can then use Dijkstra's algorithm to find the shortest distance back to the start for all nodes; any which have not had a distance set at the end are unconnected.

Buildings and/or individual road tiles should store the nearest junction to them that they are connected to. Then, knowing which junctions are not connected, any of the buildings that are closest to those junctions can be flagged as not being connected.

The main thing to do would be keeping the graph up to date. For adding tiles, this is simple; when a new junction or connection is made, check and add any distances, and then update distances produced by the Dijkstra's algorithm if they are less than the current distance.

When removing roads, flag the Dijkstra's algorithm to recalculate (probably after, say, X seconds after the last delete, in case they are doing large scale remodeling).

Another advantage of having a graph for the roads is you can run A* on it if you want things like cars.