Android Game Development (Programming/Algorithm) Question

Question

I have a bunch of objects (balloons) that move upwards, hit the roof (i.e. object.yPos <= 0), and stop. Balloons that follow them hit the existing balloons and stop. Now, I shoot at balloons and remove those that are hit ... easy enough if they are already on the bottom. However, I also have to remove those balloons that are left hanging after their supporting Anchor is hit and removed i.e. they are not attached to the roof OR any of the other balls anymore. Relevant to this, I have following supporting methods in my Balloon Object:

balloon.getAdjacentList() -> Returns ArrayList of all the Balloons that are attached to balloon

balloon.getX() -> Returns X Pos of balloon

balloon.getY() -> Returns Y Pos of balloon

One way of detecting "hanging in the air" balloon that I can think of is to use "Graph traversal" with DFS or BFS where origin would be all adjacent balls of the one that is hit (and removed) and destination would be ... if any of the adjacent ball (or "adjacent's adjacent" ball OR "adjacent's adjacent's adjacent" and so on) has getY() <= 0 i.e. find path to the roof.

This check seems very expensive to run especially when, to remove one or two hanging balls, I have to run dozens of searches. Also keep in mind that, in theory, a balloon might have many others attached to it and still have its Anchor (the one supporting them all to roof) hit and removed and therefore all of them have to go ... so ... if ( getAdjacent().size() == 0) would not work.

1- Any better idea of something that seems so easy to visualize and is implemented in so many games? 2- Any supporting methods that I can add to help me detect the balls?

Thanks in advance for any help

Answer 1

Here's a simple algorithm that probably performs decently for your purposes: just start at the anchor, and mark each node you get to from the anchor as reachable. When you're done, pop all the balloons that haven't been marked reachable. The cost of this will be linear in the number of balloons plus connections, which I think is close to optimal for this problem (since a shot could possibly pop every balloon in the graph, you at least need to do O(balloons) work).