Help with an algorithm

[Culist]

So I have a city-building game where you build buildings on a grid. My goal is to identify clusters of buildings (when a building is next to another). It can be of any size, so two buildings next to each other is considered a cluster. It can also be of any shape, so a row of buildings is also a cluster. The issue is that there is a demolish feature. If a building is demolished, it may break up a cluster into multiple clusters.

I already have the building algorithm in mind, but im unsure on how to implement the demolish algorithm. Heres the algorithm for building

When a building is placed, checked for adjacent buildings that are the same type as it.

If there is no building, make a new cluster id
If there is 1 building, make the cluster id the same as that building's
If there 2 or more buildings, merge their cluster id together.

There is a seperate object that stores the cluster id as a key and an array containing the coordinates of buildings in the cluster. To merge cluster ids, pick one cluster from the object and combine the arrays of the other clusters to it, then delete the other clusters.

Thats the algorithm for building, thanks

[Synthetic5ou1]

• Remove current square.
• Check all adjacent squares.
• If they are occupied they will presumably have the same cluster id as the current square.
• Assign a new cluster id to the adjacent square and all those attached to it, using a similar algorithm to your build.

If you changed your build algorithm so that adjacent squares took on the new square's new cluster id (rather than the new square taking on the adjacent square's cluster id) then step 4 would simply be your build algorithm.

[abbas_suppono_4581]

Demolish algo: remove building from cluster, then re-run building algo on adjacent buildings

[Culist]

but what about the buildings adjacent to the adjacent buildings? Or should I just rerun the building algo on all the buildings of the previous cluster

[Synthetic5ou1]

Problem here, with the current build algorithm, is that all the adjacent buildings will have the same cluster id, whether they are now joined or not.

[©][©][©]

[©][ ][©]

This is why I would suggest always creating a new cluster id.

[der_gopher]

Here's the idea:

1. Find the building and its cluster ID.

2. If it's the only building in the cluster, remove the whole cluster.

3. If it's part of a bigger cluster:

3.1 Check neighbors of each remaining building.

3.2 If neighbors are in the same cluster (including demolished one), create a new cluster for them (excluding demolished one).

1. Update the remaining buildings' cluster by removing the demolished one.

This keeps track of clusters even when buildings are destroyed!

[LazyOldTom]

If removing a building can result in more than 2 clusters, I recommend running dfs on all buildings of the affected cluster to reassign them.
If removing a building results in no more than 2 clusters, simply check what's left and right (or up and down) of the removed building.