Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 9 down vote favorite
1

Is there a game design technique I can use so that I completely remove 'No more moves left' situations. ie. the game should contain no impossible scenarios.

As far as I've guess It all depends on what jewel and where you give the user after a jewel group of 3 or 4 dissolves.

Is it possible ? An always infinitely solvable Bejewelled game?

share|improve this question
2  
make all the jewels blue – amb Jun 22 '12 at 13:07
+1 great question. There should be a fairly non-convoluted solution for this, depending on how many new gems you spawn. – ashes999 Jun 22 '12 at 23:14
@ashes999: Thank you, but the only two ideas as of now, I think this removal of illegal situation is possible is by 1.) brute force check and addition of jewels based on the foreseen brute calculation, 2.) introduction of things like bombs or the hyper cube which interacts with any jewel around creating a vast disruption on the board pattern. – Vishnu Jul 6 '12 at 5:43

3 Answers

up vote 1 down vote accepted

It's certainly possible to create an endless Bejeweled game. PopCap have done so themselves with the latest Bejeweled 3 (the mode is called "Zen Mode").

First of all, you need to make sure there's at least one valid move when you first generate the board.

Whenever a player makes a move, you have to calculate the resulting board and search for valid moves. If there are none to be found, you have to control the gems that will be spawned to restore a valid board. Since (at least) 3 gems will be removed with one move and you'll have to spawn 3 replacement gems, you can ensure that these 3 replacement gems will form another valid move with the current board. Endless mode achieved.

Of course it's not ideal that the new move will appear with new gems, but it's a cheap way to always ensure a playable board. And since creating valid moves actually means to swap positions of gems, it won't be long before other moves will become possible.

As already mentioned, bombs and other means to clear large parts of the board will add more variety to the gameplay, but they are not needed to ensure an endless mode.

share|improve this answer
up vote 4 down vote

Yes. This would in fact be possible. This is not a case of the halting problem as the case is defined, not arbitrary. To answer this, two parts must be answered; first if a solution exists can it be found, and second will there always be a valid solution to find.

The first part of is how to find a set of replacement tiles (gems) which would produce a playable board. This can be achieved via brute force methods, just check every possible replacement set until a playable one is encountered (There would be more optimal non-brute force methods as well).

The second part is to determine if there will always be a replacement set which will produce a playable set. Any set of tiles removed in a single move is going to be some superset of sets of three tiles, so if in the minimal case of only three being removed, if a playable set can always be found, then for all possible patterns of removed tiles there will be a playable set, as it will contain all the solutions for each set of three removed tiles which is a subset of the removed tiles.

In the minimal case of clearing only three tiles in a row/column, A replacement set containing two tiles of type A separated by a tile of type B (where type A is the type of a tile above or below the cleared set of three in the case of a column of three, or to the left or right in the case of a row of three). This will yield a move where swapping the center of these three tiles with the appropriate A tile alongside it will produce a set of three. This shows that a set of tiles can always be found which will produce a valid move along the column/row where the original tiles were cleared. Restricting future moves to that column or row would, while being a valid solution for an infinity playable game, would not be very fun. But using all the rules for common bejeweled style games, it’s easy to show that there will always exists a solution which will allow for moves outside of that row/column as well. Assume we drop in three A type tiles, where A is one of the tiles above or below / left or right of the removed set of three. This will produce a “bomb” style tile which will clear an area when removed. If we then drop in another replacement set of tiles which results in a match being made with that bomb an area of tiles will be cleared. This area will contain a number of 3 tile subsets within other rows, which means that that future moves will not necessarily be limited to a single row/column.

share|improve this answer
It only rotates 120 degrees at a time, right? So what happens if you display a board that (due to previous moves) has scoreable distributions elsewhere in the board, requiring 5 moves from a newly placed block, and the player clicks something wrong first? – Clockwork-Muse Jun 22 '12 at 18:41
Rotates 120 degrees? Bejewelled doesn't involve rotations. Are you thinking of Bejewelled Twist? – Matthew R Jun 22 '12 at 18:45
Sorry, no, I was thinking of Hexic. But, with sufficient different gems, it would be possible to enter a situation where the engine would have to generate a matching trio every single time to allow continuous play (because nothing else would score). Which might be interesting to see, but not very playable. – Clockwork-Muse Jun 22 '12 at 20:55
You would always be able to generate a replacement set of three identical tiles of the same type as a tile to the left/right or top/bottom of that set, which would create a larger set which would then be removed. This means that all tiles in the row or column of the original tile can ultimately be removed. In most bejeweled-style games larger sets lead to special tiles which clear areas or all of a given tile type. This could be cascaded as necessary to clear enough tiles that a playable board could be generated regardless of the initial state of the board. – Matthew R Jun 23 '12 at 8:00
up vote 3 down vote

You have touched upon the halting problem in computer science.

Given a description of an arbitrary computer program, can we deduce if it will stop at some point or run forever? There is a reason this is called a "problem".

The short answer is: no, you cannot guarantee that a Bejeweled game will never have any illegal moves. Because to guarantee it would take infinite computing time.

share|improve this answer
4  
Just FYI, the halting problem states that there are impossible problems to solve, not that they all are. For this specific problem I think you just can't do it (or the game will be ridiculously simple, like 2 colours and a 3*3 grid for example), there are too many possible paths in a 'normal sized' game like this . – Valmond Jun 22 '12 at 13:44
1  
Also FYI: The current generation of Bejeweled games (from PopCap) have an endless-mode... so they seem to have solved the problem successfully :) They ensure there's always a valid move by spawning new gems that will guarantee a valid move (only applies when there's currently none available). – bummzack Jun 23 '12 at 9:11
1  
@bummzack: sorry to say that you are wrong bummzack, but in the popcap bejewelled(which i take pride in saying I am the top scorer in both classic and speed) . The classic version halts saying .NO MOVES LEFT and gives you a gameover. – Vishnu Jul 6 '12 at 5:38
@knight666: Well, I do not think that is impossible, like the other post by Mathew R he does give a good idea of using a bomb when the ai foresees that a illegal situation might arise. – Vishnu Jul 6 '12 at 5:40
@Vishnu Well I wrote current generation, which would be Bejeweled 3, and this only applies to the endless-mode (or Zen mode or whatever). I'm aware that this was not the case in the classic version... – bummzack Jul 6 '12 at 6:30
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.