Re: [pygame] Re: manually cutting a picture

[Casey Duncan <casey@xxxxxxxxxxx>]

On Nov 6, 2007, at 9:29 AM, Joseph king wrote:

> I have a kinda hard question.... i am trying to build a jigsaw game  
> with python, i would like to give the option for people to create  
> there own puzzle piece.... does anyone know how to accomplish this  
> it is becoming increasingly difficult for me

Note that you don't just create one piece, you need a template in  
which to cut out the entire puzzle. From there you would need to  
create "die" surfaces you can use to stamp out the piece shapes from  
the original image. The dies could use alpha blending and even make  
nice looking chamfered edges if you wanted.

I think making the dies is the hard part. Are you looking to do that  
at run-time or have a set of pregenerated templates?

The dies would consist of surfaces slightly larger than the pieces  
they cut out. Around the outside of the die, the surface would be an  
opaque black (0,0,0,255). On the inside of the die, where the piece  
is, the die would be completely transparent (0,0,0,0). Along the  
border of the piece you could transition from slightly translucent to  
transparent for a few pixels to make it look die-cut.

To create a piece, you would blit the puzzle image into a new surface  
that is the size of the die (cutting out a rectangular piece of the  
puzzle). Then you would blit the die on top. This would "cut" out the  
piece in the desired irregular shape.

To make the dies, you would need to come up with an algorithm that  
creates irregular curved lines across and down your puzzle rectangle.  
The lines should be regularly spaced so you can know the approximate  
size of each piece ahead of time. This could be a parameter the user  
inputs, for instance. You need to make sure the curved parts of the  
line aren't too large or happen to close to the intersections, or  
you'll wind up with lots of little shards of pieces. I'm sure there  
are well studied algorithms for this out there, I'll leave finding  
one as an exercise for the reader.

Once you have the lines, you need to figure out where the  
intersections are. If you are clever enough they can probably be  
completely fixed positions depending on the piece size. Once you know  
that you can derive the desired rect of each die (note they will  
overlap each other if laid out together on the puzzle image). Then  
creating the die becomes a matter of "filling" (using a seed fill or  
somesuch) the area of each die outside the piece. You need to make  
sure the die is big enough that the fill can "flow" around the edges  
properly. Basically the die rect must be slightly larger than the  
irregular border of the piece.

Writing a seed fill in python is probably too slow, so you'll want to  
find an alternative. One way would be to approximate each die edge as  
a filled polygon, then let the filling happen in the library code.  
You could also make each piece a polygon and make a die for each  
piece but cutting it out and filling the pieces around it. To  
accomplish that I would suggest starting with a grid to mark each  
piece corner and creating the lines between the pieces as lists of  
points approximating a curve. The poly for each piece then becomes  
the concatenation of the four point lists for the corners of that  
piece. Edges are just a straight line between the corners.

To further simplify things, you could come up with a fixed number of  
edge shapes (represented as a list of points relative to a corner).  
By combining them in different ways for each piece, the puzzle would  
still always be different, but you wouldn't have to worry about  
random edge generation cutting things incorrectly.

Anyhow, those are some suggestions off the top of my head. Seems like  
a fun problem to solve. Good luck!

-Casey