Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty

by Limbic~Region (Chancellor)
on Aug 30, 2013 at 01:10 UTC ( #1051536=perlquestion: print w/ replies, xml ) Need Help??
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
I am going to write a clone of an Android game called Bubble Blast 2 in Scratch. The game board is initialized on a 5x6 grid. Each point on the grid, there can be one of 5 possible states:
  • No bubble
  • 1-hit bubble
  • 2-hit bubble
  • 3-hit bubble
  • 4-hit bubble
You are also given a certain number of hits/touches to clear the board. When a bubble has no more hits, it explodes and sends shrapnel at 0, 90, 180 and 270 degrees on Cartesian coordinate system. When shrapnel hits another bubble its trajectory is stopped but the hit count of the bubble it collided with is reduced by 1 and if that bubble reaches 0 it in turn explodes creating a chain reaction.

I want to be able to generate puzzles of increasing difficulty but can't seem to land on an algorithm that feels right. I think it ends up being some relationship between:

  • Minimum number of hits by a human to clear the board
  • Number of ways to clear the board using the minimum number of hits
  • Number of hits given to the human
  • Number of ways to clear the board using any/all of the available hits

Perhaps it may be better to reduce the number of ways to lose rather than maximize the number of ways to win. Imagine a board with a single 1-hit bubble. There is only 1 way to win but 0 ways to lose.

Your challenge, should you choose to accept it is to create an algorithm that can generate a user defined number of boards that span the spectrum of difficulty (easiest being there is no way to lose and hardest being there is only 1 way to win and it requires all of your available hits). I believe that the maximum number of available hits I have ever seen a game board initialized with is 7 or 8 which should greatly reduce the number of possible game boards.

Cheers - L~R

Comment on Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
Re: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by QM (Vicar) on Aug 30, 2013 at 09:50 UTC
    Does it make sense to do this in reverse? That is, generate boards at random, then "play" the boards. Board play is along 2 lines -- mean number of random touches to clear, and minimum number of touches in best play.

    Easy boards will have less variation between random and best play, compared to hard boards. As the board difficulty rises, then given number of touches gets closer to best play. (It's up to you whether you use the "infallible" level, where allowed touches == best play.)

    Thanks for the diversion today!

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

      If you are going to build a number of random games and score them for difficulty, you could have an auto-challenge balancing routine.

      1. Save 11 random boards and sort them by difficulty rating.
      2. Have the user play the (easymode=3rd, medium=6th, hardmode=9th) ranked one.
      3. If the user wins, delete the games easier than the one just beaten, if they lost, delete the harder games.
      4. Generate replacement boards and sort them by difficulty again.
      5. Goto 2 until bored
      QM,
      I considered this. Every game I have ever played, my starting move has always been where I can get the biggest chain reaction or set a chain reaction. In other words, it may make sense to create algorithms that mimic real strategies to play the games rather than exhaustively brute forcing all possible ways to play the board.

      I just can't find anything I am happy with and I knew that the amazing monks at the Monastery would point out something obvious (probably having to do with recursion) that I completely missed.

      Cheers - L~R

      QM,
      So, here is the problem:

      It takes too long to figure out all the ways to play a game. I am thinking I need to lower the number of possible moves and limit how much time can be spent playing a single game. What do you think?

      Update: I can complete approximately 40,000 games every 5 seconds. What I have done is impose a 6 hit limit along with randomly shuffling the return of possible_hits() and limited each board to 40,0000 games. I have manually tested this against a handful of boards and it appears to give a pretty good approximation of the results if all of them had been played. I would prefer a C based version of this which could likely do far more per second but my C is rusty (was never very good) and I can't remember how to manage a dynamic array.

      Update 2: I turned the problem upside down and it became much easier. Instead of scoring how difficult the game was, I instead scored how easy the game was. I used a combined score of things like win to loss ratio, number of initial 1-hit moves to 1-hit wins, etc. The ones with the lowest score were the most difficult. Now I just need to code the actual game.

      Cheers - L~R

        All,
        I have ported the code to C (figured out how to avoid a dynamically managed array) and am making it available here for your critique/suggestions. I have never been a C programmer so there are probably a number of ways to write this more elegantly and efficiently.

        Even in my neophyte C, I have realized an enormous performance increase. Even in C, it still takes too long to exhaustively play all possible games for a board when you allow the player to use up to 9 hits. For this reason, I duplicated the same changes I did to the original Perl (play a limited number of distinct but random games). The difference is that I am now able to use up to 9 hits and play 500K games in less time then it was taking me to play 6 hits for 40K games.

        Cheers - L~R

Re: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by Yary (Scribe) on Aug 30, 2013 at 16:06 UTC
    Think of the problem in reverse: start with an empty field- the "win" state- and play it backwards, with shrapnel coalescing into bubbles, sometimes leaving bubbles at the shrapnel source. By tweaking the rules-in-reverse, you can generate different levels of complexity.

    I haven't thought it through in your particular case, just hope it gives you new ideas.

      Yary,
      I have thought of that and even generated a few boards this way. The problem is they only end up with the same outcome if game play starts the way your board generation ended. What I thought would be a "hard" board ended up being easy simply by picking a different starting position.

      Cheers - L~R

Re: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by choroba (Abbot) on Sep 01, 2013 at 07:32 UTC
    What happens if a bubble is hit from different directions at the same time? Imagine a situation like this:
    1 2 1 2 1 1 1
    The player clicks on the middle 1 at the bottom.
    1 2 1 2 ^ 1 < 0 > 1
    _
    1 2 1 1 ^ ^ 0 > < 0
    _
    0 > 2 < 0 v v 1
    Does the 2 become 1 or 0?

    Update: Also, what happens in the following scenario?

    1 < 0 > 1 v 3 1 1 3
    _
    < 0 > < 0 > v v 3 1 1 3
    _
    3 < 0 > < 0 > 3

    What happens next? Do the shrapnels explode when they meet each other in the middle?

    لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
      choroba,
      In your first scenario, it becomes a 0 and explodes. Shrapnel doesn't explode when it meets each other so the 3s become 2s. You can actually play the game in "test drive mode" on Amazon here.

      Cheers - L~R

        I am not able to run the game (perhaps I need an account or an Android device?)

        However, I wrote my own implementation. You can feed it a starting setup from a file, too. I am still not sure about situations like

        v >1< ^

        but it is fun, anyway. I am still not sure how to generate "tough" initial setups, though.

        A screencast.

        لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1051536]
Approved by Ratazong
Front-paged by MidLifeXis
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (7)
As of 2014-10-22 02:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (112 votes), past polls