My first thought for your algorithm is to essentially follow the solution
path that your user might end up taking. Your user will be clearing areas
out, opening them up. Your algorithm could start with an empty grid and
fill in around a starting seed, growing the tile array outward.
1) empty grid
2) generate random sequence of pairs with the blank embedded in it, such as
4,4,27,27,1,1,36,<blank>,36, etc
3) choose random location for first tile, and place it there, and take it
off the pair queue.
4) choose an unfilled location which is 4-connected to any filled location,
and put the next tile from the queue in it.
5) repeat 4) until the queue is empty.
In this system, putting the "blank" in a location counts as filling that
location, so the value for "blank" needs to be different than the initial
values in the grid.
So for example, if -1 means uninitialized and 0 means blank:
-1,-1,-1
-1,-1,-1
-1,-1,-1
then
-1,-1,-1
-1,-1,04
-1,-1,-1
then
-1,-1,04
-1,-1,04
-1,-1,-1
then
-1,-1,04
-1,27,04
-1,-1,-1
then
-1,-1,04
-1,27,04
-1,27,-1
then
-1,-1,04
01,27,04
-1,27,-1
then
-1,-1,04
01,27,04
-1,27,01
then
36,-1,04
01,27,04
-1,27,01
then
36,00,04
01,27,04
-1,27,01
then
36,00,04
01,27,04
36,27,01
This guarantees that a solution exists, because the algorithm essentially
traces out the solution as it generates the level.
This presumes that players are not allowed to move tiles around yet leave
them on the board while solving the puzzle - it assumes that tiles just
disappear from the grid when the user selects a pair which has a clear path
between it, and that's the only interaction allowed. If they can slide them
around, my algorithm will still produce solve-able puzzles, but they won't
be as difficult as they could be, I think. :)
Interesting problem!
Dave
On Wed, Mar 11, 2009 at 6:09 AM, Glen Pike <[email protected]>wrote:
Jobe Makar's book about Flash Games Demystified has a wordsearch that
shuffles words in a grid - it will keep shuffling upto a point, then decide
that it is getting nowhere and try again. There may be some examples of
this sort of thing online - I have the book at home if not :)
Paul Steven wrote:
I am trying to write the code to populate a 9 by 9 grid of tiles with 40
pairs of matching tiles.
I have 4 different types of tiles and I want to create a grid that has 40
matching pairs and 1 blank tile.
I do not want the pairs all to be next to each other but there needs to be
at least one solution that enables a player to match each and every pair.
To
match a pair there needs to be a clear path between each member of the
pair.
1,2,1
2,0,3
4,4,3
In this simple example, a user could clear all tiles by matching in the
following order:
4 - 4
3 - 3
2 - 2
1 - 1
Note that until they have matched the pair of 2's they cannot match the
1's
as there would be no clear path between them.
All my attempts so far to create this grid is resulting in script errors
due
to my code being unable to find a solution. My code basically gets about
60%
of the board created then finds it cannot any more clear paths to create
the
remainder of the grid.
I would really appreciate any help cracking this function.
Thanks
Paul
_______________________________________________
Flashcoders mailing list
[email protected]
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
_______________________________________________
Flashcoders mailing list
[email protected]
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
_______________________________________________
Flashcoders mailing list
[email protected]
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
