designing picture puzzle.

Question

I am planning to develop a jigsaw puzzle game. Now I already have images and image pieces, so we don't need algorithm to cut the image in pieces.

On the UI side there would be two sections

1. First section contains the broken images in random order.
2. Second section contains the outline of the full image. User need to drag and drop the the cut images onto the outline image.

I am not sure how can the pieces be matched on the the outline image? Any idea about the algorithm or the starting pointers?

Answer 1

the data structure is simple I guess- each peace will point to it's neighbors and will hold the actual shape to display.

on the MMI (UI) of the app - what is your developing environment ? If it's windows - I would go with c# and winforms or even better wpf. if it's unix, you'll have to get someone else's advise, as I'm not an expert there.

Answer 2

For a regular shapes you can go with a matrix. I recommend this as the first approach. Dividing the puzzle is as simple as defining X,Y dimensions of the matrix. For each piece you have a series of four values then, one for each side, saying whether it is flat, pointing out, or pointing in. This will give you a very classic jigsaw puzzle setup.

How the pieces actually look becomes a strict GUI thing. Now, for the first draft I recommend getting it working with perfectly square pieces. Taking rectangular bits of an image should be easy to do in any GUI framework.

To go to shaped pieces you'll need a series of templates. These will become masks that you apply to the image. Each mask clips out a tiny portion of the image to produce your piece. You'll probably need to dynamically create the masks in order to fit them to the puzzle. At first start with simply triangular connections. Once you have that working you can do the math to get nice bulbous connector shapes. Look up "clip" and "mask" in your GUI framework.

If you wish to do irregular polygon shapes that don't follow a general matrix layout, then you need to do a lot more work. This is why I recommend getting the square first working as a good example. Now you'll need to delve into graph theory and partitioning. Pick up some books on 3D programming -- focusing on algorithms, as they do partitioning all the time. Though I wouldn't doubt if there is a book with this exact topic in it.

Have fun.