Generate unique custom jigsaw puzzle layouts of any size with irregularly shaped pieces.
Regular puzzles with many pieces can be very difficult to solve, especially if they have high piece counts and large areas of flat colors. Irregular pieces can help in these situations and provide a new challenge for experienced puzzlers as some established techniques may not work as well.
- choose approximate height and width of the puzzle (in pieces)
- generate grid with these dimensions
- in each grid cell, choose a random point
- scale grid to desired puzzle size
- calculate the voronoi diagram from these points
- (optional) For even more irregularly shaped pieces, generate a random number of random points within each voronoi cell. Calculate the new voronoi diagram from these points. Join any new cells where the new points are within the same old voronoi cell. Repeat this step as often as desired.
- for all voronoi edges (between pieces), replace the edge with a randomized connection scaled to the proper size.
- (optional) user may provide a target piece count. Choose a grid with slightly more pieces than that, then merge random pieces or the smallest ones until the target count is reached.
- (optional) user may provide a minimum surface area for each piece. If a piece is too small, it is merged with a neighboring piece. Additionally, ensure the bounding box of each piece has an aspect ratio not too far from 1 (e.g. <3:1)
Currently, step 6 only generates one new point per cell. This doesn't do much to change the piece shapes, but makes the initial grid less recognizable. Steps 8 and 9 also help a lot to mask the grid structure as already irregular pieces are merged.
Steps 8 and 9 are currently the only way to get non-convex shapes.
Step 7 is not implemented yet.
- from the voronoi diagram, calculate verlet lists, listing the neighbours of each cell. Then use these lists when merging with the smallest neighbouring pieces, updating the neighbours lists accordingly.
- Implement basic algorithm
- Implement step 7: place connectors on edges.
Currently, connectors may overlap, creating loose pieces. - in steps 8 and 9, merge the adjacent piece with the longest shared edge, not to the one with the smallest area (current implementation)
This modification requires finding the maximum length of shared edges between two polygons. Due to steps 6 (with multiple points) and 8 & 9, polygons are not necessarily convex, so adjacent polygons can share multiple edges. - split code into multiple files
- avoid pieces with too thin sections:
For each piece calculate the minimum distance between points on the boundary that are at least 2 points apart (i.e. polygon needs at least 6 vertices). If this distance is below a threshold, merge the piece with the neighbour sharing an edge connected to one of the problematic points.