1
\$\begingroup\$

I want to make a clone of an Amiga 500 game, Pick A Brick, a 2D game where the goal is to clear a table of bricks by matching them up, following certain rules. I am getting nowhere when it comes to the algorithm for generating the layout of the bricks. I have added the rules of the game (as I remember them) below.

  • The player wins the game by clearing all tiles before the time runs out.
  • Tiles are cleared by clicking on a pair of them and if the following is true:
    • The tiles must be of the same type (there is only one pair of each type).
    • There is a clear path between them (more on path in the points below).
    • The path from a tile must always start towards an (clear) edge of the screen.
    • The path between the tiles must be u-shaped.

(edit) NOTE: In the video the path is not always the u-shaped. I do not recall if the path shown is just a shortcut or not, but regardless, in my version I do not want to allow removing tiles "from inside out".

I have done some manual testing/prototyping using both outside in and inside out approaches, with variations on both. So far, nothing I have come up with has really come close. I kind of dislike asking a question like this since it is so specific, probably not of general interest and may take up more than a little time for anyone interested in helping out. That being said, some people enjoy coming up with algorithms and "solving stuff", and the community may learn something from the answer, so, a post it is.

(edit) Clarification. The algorithm must provide a solvable solution.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ On the video there are path that are not u-shaped, just to say. And what exactly is the problem? Totally random placement does not work? \$\endgroup\$
    – wondra
    Sep 16, 2014 at 16:47
  • \$\begingroup\$ @wondra Ah, I see now. As I recall it both tiles had to be in the "outer layer" for them to be able to removed. The "shortcut" path shown in the video makes sense in terms of showing the shortest path, but, unless I'm mistaken you could not remove two tiles "inside" the playing field, so to speak. Either way, that's what I'm after. As for random placement, I'm pretty sure you quite easily will end up with a field that is unsolvable. \$\endgroup\$
    – user1323245
    Sep 16, 2014 at 17:02
  • \$\begingroup\$ You probably should say it should be always solvable, from the rules is it not clear whether every state has a solution. How about pexeso shuffling, have you tried? \$\endgroup\$
    – wondra
    Sep 16, 2014 at 17:12
  • \$\begingroup\$ @wondra Thanks for the pexeso tip. Having taken a look at it I can't see how it would guarantee a solvable layout though? \$\endgroup\$
    – user1323245
    Sep 16, 2014 at 19:49
  • \$\begingroup\$ You could also try BFS(graph search algorithm), at start add all border tiles to stack(or priority queue), then choose two random tiles from stack. Tile(color) them and add their undiscovered neighbours to the stack, repeat until empty. This should be always solvable and better shuffled(2d mixing instead of 1d below). \$\endgroup\$
    – wondra
    Sep 16, 2014 at 22:08

1 Answer 1

Reset to default
1
\$\begingroup\$

Start with an empty board.

........
........
........
........
........
........

Add 2 tiles with the same image to different columns on the the left. Add 2 tiles with the same image to different columns on the right.

........
A.......
.......B
........
A.......
.......B

Repeat this pattern until the board is filled.

........
AC.....D
.......B
C.......
A......D
.......B

........
AC....FD
E......B
C......F
A......D
E......B

.......A
ACG...FD
E......B
C.....AF
AG.....D
E......B

B.....CA
ACG...FD
E.....CB
CB....AF
AG.....D
E......B

BD....CA
ACG..EFD
ED....CB
CB....AF
AG.....D
E.....EB

BDF...CA
ACGFGEFD
ED....CB
CB....AF
AG....GD
E.....EB

BDF..BCA
ACGFGEFD
EDA...CB
CB....AF
AG...BGD
EA....EB

BDFC.BCA
ACGFGEFD
EDA..DCB
CBC..DAF
AG...BGD
EA....EB

BDFCEBCA
ACGFGEFD
EDA.FDCB
CBCE.DAF
AG...BGD
EA...FEB

BDFCEBCA
ACGFGEFD
EDAAFDCB
CBCE.DAF
AGG..BGD
EAG.AFEB

BDFCEBCA
ACGFGEFD
EDAAFDCB
CBCEBDAF
AGGBCBGD
EAGCAFEB

You just have to make sure you don't leave the last 2 tiles in the same row. The puzzle is going to be solvable by making the same moves as you did to generate it.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I will mark this as an answer, because it does indeed solve the original question. Unfortunately I now realize I should've included a constraint; the player should not be able to work from one side to the other without changing "side" at some point, either to "unlock" new tiles for the previous side or because the previous side is, well, "locked/unsolvable" until at least a couple of other tiles have been removed. You have given me something to work with here though, maybe I can figure out a tweak. Thanks. \$\endgroup\$
    – user1323245
    Sep 16, 2014 at 19:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .