Search code examples
c++algorithmbox2dsfmlpath-finding

Checking connectivity of two bodies through open space

The title is a little vague, but I'll explain better here.

The Setup

I'm trying to program a little water level simulator, much like the water levels in the game, LIMBO. When an opening is made, allowing water to flow between two bodies of water, the levels equalize. The setup I have now is two containers, with blue blocks inside representing water levels. My mouse removes chunks of terrain away, and so, when an opening is made between the bodies, they should adjust and their Y values should move to match.

Image examples:

Semi-filled tanks: Tanks

Equalized tanks: Equalized

Now, I know some maths could be done to figure out how much to adjust the levels and the ratios between different sized tanks. That part I think is pretty straight forward. But I can't figure out a good method of determining if and when the two bodies of water are connected.

Any algorithm, pseudo-code, or references would be much appreciated!

If you need more clarification, please, don't hesitate to ask. I look forward to all feedback and will edit my post for specific clarification.

Thanks!

~ natebot13

BTW: I'm using C++, SFML, and Box2D (Box2D is for some other physics related things I need, not necessarily needed for this example).

Solution

  • You need to check whether the edge of the container1 is connected to container2 at any point of time if so then adjust the water level. I guess you are working on a image so you can use the connected components algorithm to check if any of the edge pixels of container1 is connected to any of edge pixels of container2 and also get their positions.

    Algorithm :-

    1. puts edges of container1 in one set which is connected to a dummy parent1.
    2. puts edges of container2 in another set which is connected to another dummy parent2.
    3. say after every one second add the new added pixels to sets using connected components
    4. check at end of every union whether dummy parent1 and parent2 are connected.
    5. You can use DFS to check the exacts points of connection by starting from one edge set1 and reaching the other. The last pixel and the previous first pixel in edge set1 are connection end points.

    Note:-

    There is a implementation of disjoint set in c++ boost lib which might be useful in implementation of connected components.