+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Smart Field Initializers (/thread-895.html)
Smart Field Initializers - IckyThump - Aug 6, 2009 04:33 AM
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.
Smart Field Initializers - Skorche - Aug 6, 2009 09:58 AM
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.
Smart Field Initializers - Fenris - Aug 8, 2009 04:14 AM
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...
Smart Field Initializers - IckyThump - Aug 9, 2009 09:39 AM
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.
Smart Field Initializers - Fenris - Aug 10, 2009 09:30 AM
Yeah, "provably solvable" is a mantra that keeps puzzle designers (e.g. me) soundly asleep at night...
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.
Smart Field Initializers - TomorrowPlusX - Aug 10, 2009 10:46 AM
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...
I did this to initialize mahjong solitaire boards. Works great, if your game works this way.
Smart Field Initializers - IckyThump - Aug 11, 2009 03:58 PM
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.