Algo for Minimum no of solving in a level like Bubble Blast2

Is their any way to make a algo to know minimum no of way to solve in Bubble Blast 2. I am trying to make a clone of it. My real problem is only to determine the minimum no of tap to finish the game. I can play and find them but if level are more then 100 , it is time consuming . In Bubble Blast 2 there are 10000+ levels. So is there any way to solve this problem?

• white space is free! Can you do some formatting stuff on your question. It's hard to read. – Emadpres Dec 31 '14 at 12:45
• I think you need to describe the game functionality a bit. Many of us are not familiar with it. – ashes999 Dec 31 '14 at 12:49
• I agree. your question should be self-contained ! Many people didn't play that game. – Emadpres Dec 31 '14 at 12:51
• what about pre-computing those numbers (time taken matters little), and storing them, like, in a JSON array ? – GameAlchemist Dec 31 '14 at 13:04

One way to do it with puzzle games is to start from the end and create the level in reverse.

This has the added bonus that all your puzzles are guaranteed solvable.

Finding the absolute minimum number of steps might be good for a university paper but you don't need to find it for a good game. Players love finding better ways to solve the puzzle. The ego boost adds to the fun.

Sounds like I'm dodging the question but since this is game development rather than computational science (https://scicomp.stackexchange.com/) the most important thing for games is "Is it going to be fun?" over "Is this the perfect solution?".

Cheers,

It seems to me that you could simply have your program brute-force this at level creation time, and save the answer with the level description.

If your grid is 5 x 6 as in Bubble Blast, there are at most 30 choices for the first tap, and the number of options drops rapidly past that (outside of pathological cases, that is). No chain can possibly use more than 30 taps, and in practice most will take far fewer. So you can try every sequence of valid taps (ie. taps on non-empty cells) and note the shortest sequence to an empty board.

Once you have a sequence of length x, you can abandon any sequence of length x that is still ongoing - it can't possibly give you a shorter path.

You can gain a bit of efficiency by taking a recursive dynamic programming approach, caching recently used game states. Each time a tap from state A would result in a particular game state B, you check to see if state B is already in your cache. If so, the number of taps for completion of A is the number for B + 1. If not, you recurse on B and add it to your cache with the number you find. This way you avoid repeated work for game states that appear frequently in the game tree.

You can also optimize this cache by aliasing similar states. eg. every state with only a single item, or up to three items of the same colour in a row/column, can always be cleared in one tap, so they can be treated as one. Similarly, the orientation/reflection of the board or particular colour identities don't matter, only colour differences, so you can make your cache indexing insensitive to these irrelevant details.

The maximum cache size could still theoretically exceed your total memory (depending on how varied your levels are), so you'll want to throw out entries that haven't been referenced recently.

If you run this program as a batch over all your levels at once, and persist the cache from one to the next, you'll get additional savings anytime a group of levels shares some intermediate states.