Jigsaw Puzzle Piece Algorithm..
bamccaig

I'm in the planning process for a Jigsaw Puzzle game. I'd like the puzzle pieces to be generated at run-time, and I'd like them to be somewhat random/unique; conforming to the general shape of jigsaw puzzle pieces...

Basically I'd like feedback on how to parse pieces from a puzzle image with pretty and smooth shapes.

There is a slight rush on things as development is limited to a week from now...

Thanks.

Steve Terry

I guess what you could do is have some predetermined puzzle piece sides and break your image up into a grid and apply a random side to each side of a pice in the grid. To make your pieces I suppose you would blit the grid peice to a larger individual bitmap then apply your edge mask that places the magic pink color over the piece. For each piece you would have to take the peice next to it and apply the opposite mask to the appropriate side to make the edge on the next piece match with the one you created.

miran

Step 1: Slice the image into a grid of whatever size you want, for example 36x28 for a 1000 piece puzzle. But make the grid lines wavy instead of straight. Use the sine function. The frequency along each axis should be n/2 if n is the number of pieces along this axis (perhaps this isn't necessary, need to try). Use slightly varying random amplitude for extra randomness for each grid line.

Step 2: For the little piece "connectors" use splines or something similar. Maybe a mix of splines and arcs. Each connector could be made of two Bézier splines with random control points within a range dictated by the grid lines:

- The first control point of the first spline would have to be on the side of the piece somewhere inside the first half (or second 6th or something).

- The last point of the second spline would also be on the side but in the 5th sixth.

- The last point of the first spline and the first point of the second spline have to be the same and should be some distance to the left or right (up or down) from the vertical (horizontal) side of the piece. Select the side depending on where the apex of the sinewave grid line is. The spline control point should be on the opposite side of the sine apex.

- The third point of the first spline must be on the "outside" of the line connecting p0 and p3 of the spline. The same goes for p1 of the second spline, it must be on the "outside" of line connecting p0 and p3 of the second spline. What "outside" means depends on when p3 of the first spline (and p0 of the second) is. Also points P2(1), P3(1), P0(2) and P1(2) must all lie on the same line.

- Points p1 of spline1 and p2 of spline2 must lie on the opposite side of p2 and p1 respectively.

When you connect all the control points with splines, you will get the familiar shapes you can see in most jigsaw puzzles. If you select slightly random values (within the bounds), no two pieces will be the same. You can also select how regular or odd looking you want the pieces to be. Narrow the bounds within which you select the spline control points and the pieces will be more regular, widen the bounds and the pieces will look odd.

Here's also a picture of what I mean:

{"name":"589848","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/b\/cb6acf5b9e419e6a70d678bf4acb95f7.png","w":594,"h":583,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/b\/cb6acf5b9e419e6a70d678bf4acb95f7"}

bamccaig

Thanks for the reply. That is definitely useful. I think I see how it can be done now.