Pipe connection game algorithm - Java/Andengine

Question

I am creating a game based on Pipe Dream/Pipe Mania using java/andengine for android. I have a square grid of tiles each representing a type of pipe. The player needs to swap tiles to connect the pipes from point A to B.

How do I determine if the pipes are connected to starting point A? How do I then find how far a connected path goes? How do I determine if the path connects point A to point B? How do I handle the switching of tiles which may be in the middle of the path?

This functionality will be almost the same as the pipe mini game in the first Bioshock game.

I am looking for advice on how to go about tackling this problem.

Answer 1

You are indeed working with a "graph" here and are looking at a connected component problem.

I would suggest keeping track of a source and continuing connection variable for each pipe point. Each piece has a variable noting if it is connected to point A, and which pieces depend on it for connection to A.

When you add a piece, check if its connecting neighbours are connected to A. If they are, mark this piece as connected to A, and mark each neighbour on which it may depend as having this piece depend on them and their neighbours too. Upon removal of a piece, you check the pieces dependant on it and procedurally mark them as disconnected from the source.

You can also keep track of the number of parent pieces all the way back to A. When you add a piece, you just take the smallest/largest parent, add 1 and store it.

When something connects to B, you can check if that connection goes all the way back to A and the largest/smallest path.