Let's say that I have a 2D grid size that can hold either a zero or one at each index. The grid starts off as full of zeros and then ones are progressively added. At each step, I want to verify that adding the next one will not prevent the zeros from forming one connected component (using a 4-connected grid with north, east, south, and west neighbors).
What is a fast algorithm that will iteratively test a 2D grid for connectedness?
Currently I am using a flood fill at each iteration, but I feel there should be a faster algorithm that uses information from previous iterations.
Additionally, the method that places the ones will sometimes unplace the ones even if they don't disconnect the grid, so the algorithm I'm looking for needs to be able to handle that.
This is inspired by Kruskal's algorithm for maze generation.
I am defining the neighborhood of a square as its 8 surrounding squares, including the outside of the grid (the neighborhood of a corner square is its 3 surrounding squares plus the outside, so 4 "squares" total).
Put the 1s in sets so that any two neighboring 1s belong to the same set. Treat the outside of the grid as one big 1 (which means the first set contains it). When adding a 1, you only need to check its neighbors.
Below are all the possible cases. To make it easier to visualize, I'll number the sets starting from 1 and use the set number instead of the 1 in each square that contains a 1. The outside belongs to the set numbered 1. You can also use this to simplify the implementation. The brackets indicate the newly placed 1.
If the new 1 has no neighboring 1, then it belongs to a new set.
0 0 0 0 0
0 2 0 0 0
0 0 0[3]0
0 0 0 0 0
0 0 1 0 0
If it has one neighboring 1, then it belongs to the same set.
0 0 0 0 0
0 2 0 0 0
0 0[2]0 0
0 0 0 0 0
0 0 1 0 0
If it has multiple neighboring 1s, and all neighbors belonging to the same set are direct neighbors, then you can merge the sets and the new 1 belongs to the resulting set. You don't need to check for a disconnection.
0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 1 0 0 0
0 0[3]1 0 -> 0 0[1]1 0
0 0 1 1 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 1 0 0 0
0 2 0 1 0 -> 0 1 0 1 0
[3]0 0 1 0 [1]0 0 1 0
1 1 1 0 0 1 1 1 0 0
If it has multiple neighboring 1s of the same set, but they are not all direct neighbors, then you have a disconnection.
0 0 0 0 0 0 0 0 0 0 <- first group of 0s
0 2 0 0 0 0 1 0 0 0
0 0[3]1 0 -> 0 0[1]1 0
0 1 0 1 1 0 1 0 1 1
1 0 0 0 0 1 0 0 0 0 <- second group of 0s
0 0 0 0 0 <- first group of 0s
0 0 1 0 0
0 1 0 1 1
[1]1 0 0 0
0 0 0 0 0 <- second group of 0s
0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 1 0 0 0
0 2 0 1 0 -> 0 1 0 1 0
[3]0 0 1 0 [1]0 0 1 0
0{1}1 0 0 lone 0 -> 0{1}1 0 0
In this last example, the 1 marked {1} and the outside technically are neighbors, but not from the point of view of the newly placed 1.
In the general case, when removing a 1 that has multiple neighboring 1s, you need to check whether they are still connected after the removal (for example, by running a pathfinder between them). If not, separate them in different sets.
If you know the 0s are all connected, then you can check locally: removing a 1 will not split the set it belongs to if its neighbors are all direct neighbors (careful with the outside, though). It will if there is are multiple "gaps" in its neighborhood.
In the special case where you only remove the 1s in the reverse order you added them, you can keep track of which newly added 1s join multiple sets (and even what the sets are at that moment, if you need). These will split their set when you remove them later on.