Sign in to follow this  

block drop game problem

Recommended Posts

hi. i've got a problem and don't really know the best way to solve it. maybe someone can help. here goes: i've got a block drop game where the board consists of empty blocks, solid blocks and game piece blocks. the game piece blocks are different colors and the goal of the game is to get rid of all game peices. You can move a game piece either left or right if it is next to an empty block (once moved, all blocks shit down to fill in the gaps). And if two or more game piece blocks of the same color are touching, they dissapear. This game was created by James McCombe and is called Vexed. So, my problem is, I want to find an algorithm to solve any solvable puzzle and in doing so find the minimum number of moves needed to solve it. So, i figured I would simply go through all possible move combinations, determine if each one results in a solution or not (some moves may result in dead locks), and then pick the one with the least number of moves. However, once I started to code, I realized that wasn't quite sure how to make a list of all possible moves. Anyone have any suggestions or ideas on how to get a list of all possible sequences of moves? Thanks!

Share this post

Link to post
Share on other sites
I'm not sure I understand the idea completely. One thing for sure, I think I'd need a picture of this :)

Anyway, I think your answer lies in recursivity. You'd have to start from a point, try every combination possible, but always keep track of your previous moves so you can always unwind your stack and continue form another point. I'm not sure if I'm clear, but this is a way to achieve all possible combinations.

I'd need a clearer picture of the game to picture a solution :)

Share this post

Link to post
Share on other sites
I'm pretty sure I know the mechanics of the game you're speaking of--much like 'Brix', right?

Anyway, your problem is solvable, but it doesn't sound like there's a reasonably fast solution to it. A list of all possible move combinations would be simply enourmous, definitely on an exponential scale.

However, if you wanted to try it anyway, it would be a relatively simple recursive algorithm:

1. Save the state of the board
2. Begin a loop from 1 to numPieces
3. Move the piece left and recursively call the function with the new state
4. Restore the state
5. Move the piece up and recursively call the function with the new state.
6. Restore the state; etc for moving the piece right and down
7. End the loop. If it hasn't 'won' by then, it's impossible.

Of course this clearly has a ridiculous size, considering it makes a whopping numPieces*4 recursive calls.

Hope this helps; sorry, I think you're going to need to personally ensure that levels can be completed!

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this