Finding Paths between a Series of Points

Question

For use in a simple project of mine, I've hit a bit of a blockade.

I have a series of points in a grid, "walls" and "open space." Space outside the grid is assumed to be walls. I have an arbitrary number of points in this grid which are open, and I must determine if which ones are connected will change if I make one specific block in the grid change from open space to a wall.

What's an efficient way of doing this?

.

Example: Determine whether the presence/absence of paths between the red squares will change if the green square is a wall or open space. (PS: I sincerely apologize for my terrible grid)

Right now, I'm assuming some sort of cellular automata is best, but I'm not sure. I've looked at pathfinding before, but never really saw anything that got into this sort of problem.

Please note: I don't care how long the paths are, (I know their maximum length) they just MUST EXIST. So finding the BEST path between points is not necessary.

Oh, and while it shouldn't matter, I'm writing this project in Java, but any language (or pseudo-code) or an English description of an algorithm will suffice. (I know most of the Curly Bracket languages, and limited Haskell and LISP, they'll all do.)

Answer 1

This might not be the best solution, but a solution would be the following:

• Start by flood-filling the grid until all points that are connected are assigned the same number (by connected I mean adjacent or on the same number 'island'). There are many ways to do this, none of which need to be too complicated. Simply running through the grid from first to last node and filling it if it hasn't been filled already is an option.
• A path between nodes that are adjacent to or on the same number can only be broken IF you put in a wall that splits the island into two. So, when you add a wall, check if that's the case. You can check this reasonably efficiently by using A*: From all 4 nodes that are adjacent to the new wall, check that if they had the same number, they can still reach each other.
• If the wall didn't cause a split: no paths were broken, all is the same.
• If the wall did cause a split: Flood-fill the grid again, and again check whether two nodes are adjacent to or on the same numbers (If the blocks you are checking are always open, it'll always be adjacent).

Checking for all nodes is reasonably efficient in this way (checking n*n/2-n/2 paths will take O(n^2) I think), but adding new walls might be made more efficient if only the necessary islands are created without flood-fill, but that could be more difficult to implement.