Smart Field Initializers

Apprentice
Posts: 11
Joined: 2009.07
Post: #1
Hey.

I was making up my mind about this topic these days. I think you all know the Game Bejeweled or one of its clones. In Bejeweled, you have a squared field, filled with Gems, each one colored in one of 6 or 7 possibilities. The idea is to swap two neighbours and thus reach at least 3 stones in a row, colored the same way, that way the match and new stones come from the top.

I was thinking, that they had to program a smart initializer method, so that the initial field, when created by starting the game, would

a) have not 3 or more matching stones - that way the user would have to be wondering, why anything was going on while he/she hadnt done a thing

b) have at least (!) one possibility of finding a matching triple - otherwise the game would be over.....


I couldnt come up with a method other than brute force:

create a field, put new stone in, give it a color, check that there is no matching, when finished, find a random spot and create a possibility for the user to make a matching.


That can't be the way, can it? I mean, i don't like to solve stuff brute force. I would want some smart, elegant way to initialize the field.

Have you ever tried something like that ?

Greetz.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #2
I guess I wouldn't try to be too smart about it. Fill it with random values. Look for a match, replace one of the matched colors with a different color. Repeat until there are no matches and be done. I would guess that the chances of not having any moves available at the beginning of the game is astronomically small given a random playing field. Otherwise the game would have to make sure that there are lots of matches and to add matchable pieces when inserting replacements.

It's a game of odds and random chances, people like those. I would guess that not all Solitaire games and variants are provably solvable, and people play those all the time.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #3
Another solution, which might or might not be applicable, is to do it backwards. Take a 4x4 sliding puzzle - there are many unsolvable starting positions. (http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability) The best way to make sure that you find a solvable start is to start with the solved puzzle, and then apply a number of random moves.

In effect, this means that the computer plays the game "backwards" at first, and the player is asked to reverse the sequence of moves.

A Bejeweled version, heck, I don't know. Perhaps start with an empty field, add in three adjacent jewels and then apply 2-3 random moves. Add in another three, jumble the gems a bit, and repeat. After you can't fit in any more "threes", fill the remaining spaces with adjacent colors and jumble them a bit.

This would give a provably solvable starting state, although it would have to be a bit more sophisticated to spit out interesting states... Wink
Quote this message in a reply
Apprentice
Posts: 11
Joined: 2009.07
Post: #4
I like the idea of starting with a solved solution. It gives me the feeling, I have stuff under control. It can always happen that if u gamble around and never do the counter-check, bad situations occur.

In an initial state, a field should be flawless. This cannot be solved without checking for it.
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #5
Yeah, "provably solvable" is a mantra that keeps puzzle designers (e.g. me) soundly asleep at night... Wink Let me know how you move forward, I'd be intrigued to hear your solution.

Another example: how I proved Galder instances to be solvable. After trying the above "backwards" approach, I realized that all that I needed to prove was that it was possible to get two of each color into the innermost ring - which I could construct from the get-go. So I put two red, green, blue and black stones into the innermost, shuffled it, and then randomized the rest of the field. Smile
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
Fenris Wrote:Another solution, which might or might not be applicable, is to do it backwards. Take a 4x4 sliding puzzle - there are many unsolvable starting positions. (http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability) The best way to make sure that you find a solvable start is to start with the solved puzzle, and then apply a number of random moves.

In effect, this means that the computer plays the game "backwards" at first, and the player is asked to reverse the sequence of moves.

A Bejeweled version, heck, I don't know. Perhaps start with an empty field, add in three adjacent jewels and then apply 2-3 random moves. Add in another three, jumble the gems a bit, and repeat. After you can't fit in any more "threes", fill the remaining spaces with adjacent colors and jumble them a bit.

This would give a provably solvable starting state, although it would have to be a bit more sophisticated to spit out interesting states... Wink

I did this to initialize mahjong solitaire boards. Works great, if your game works this way.
Quote this message in a reply
Apprentice
Posts: 11
Joined: 2009.07
Post: #7
to hear from me. It's just that I need to focus on some other methods first.
So far, I have helped out myself with an algorithm I had in use already.

The field is generated randomly with a different color a piece.
I then brute-force check each tile for being in a match-3 or greater situation - if it is, i change the color to the next one (i.e. add 1, since i reference the colors by numbers).

Thats it, works great, and so far there are nearly no initial match-3 situations (except for rare occurences) and - dont ask me why - but I always had at least 1 , usually averagely 5-6 possible situations to create a match-3.

That sufficed so far, since I just needed this for testing. I guess I'll start working on a better algo next week. I'll update this here.

So long.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Thread-Safe reference counted smart pointers in c++ JeroMiya 1 3,267 Nov 21, 2006 12:28 PM
Last Post: OneSadCookie
  Trouble Calculating Height Field Normals Nick 15 6,073 Jul 21, 2005 07:27 AM
Last Post: Nick