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?