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

When a balloon finds an anchor, have it tell its anchor(s) that it is anchoring. Keep a list of anchored balloons on the anchor Keep a list of anchors on the balloon that found an anchor(s) when the anchor goes away tell the anchored balloons that its gone. Then you can use the list of anchors to determine if you need to move up.

Assuming you can have more than two balloons stacked, you should also probably traverse down and just move the last one the right amount of spaces up instead of moving each one individually.

Answer 2

Why didn't you just tell us you are making a Frozen Bubbles clone? Would have made the question way shorter :)

If you want to avoid a search, do some sort of reference counting scheme:

For each ballon, mantain the list of child (attached) ballons and an integer counting the number of parent (anchoring) baloons. When a ballon pops, go through all its children and decrement their anchor count. If the child ballon is left with no parents left after this then pop it as well (do it recursively or add it to some queue...)

This should work as long as no circular dependences are possible. (I think this is the case. However, if there are circular dependences the graph search is the only solution)

---

By the way - doing an exaustive search to find the connected ballons is only O(number of ballons). I seriously doubt your game has so many ballons that this will become a real problem. After all, rendering the ballons in the first place should have the same complexity...

Answer 3

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).