Problem Analysis: What are our goals? How will our algorithm meet them?

• Fast: The algorithm needs to generate a puzzle in a reasonable amount of time. A load screen is fine but no one wants to wait five minutes to play. Keeping in mind lower end devices is essential.

• Scalable: Supporting a variety of puzzle sizes means that our algorithm needs to work whether our puzzle is 8 pieces or 8,000.

• Variety: Pieces need to look unique, otherwise there isn’t much benefit in using a procedural generation system. Supporting designer influence will ensure that pieces are visibly varied and aesthetically pleasing.

• Deterministic: While not essential, ensuring a unique puzzle can be repeatedly generated from a given seed is helpful. This allows players to communicate easily while playing online together, as everyone would be looking at an identical puzzle.

Representing a piece: As a puzzle is just a collection of pieces, it makes sense to start with piece generation. We can break a piece down further. A piece has four sides (usually), as well as a connecting segment that acts as an anchor between it and its neighbouring pieces. In essence, each of these sides are just a curve or series of curves strung together. 

Representing a curve is something that can be implemented with the use of a Bezier curve. Given an ordered set of two or more points, a Bezier curve represents any point across its length. It can do this by interpolating between each point it's composed of, weighing the influence of each point differently based on how far along the curve the point we’re trying to sample is. So, given a value between zero and one representing our desired “distance” along the curve, we can generate a point anywhere across it. Combining a series of these points together, we now have a representation of the curve!

For more complicated shapes, we can combine Bezier curves into a composite curve, or Bezier spline, by starting a new curve where our previous one ended. This technique can be used to represent more abstract parts of a puzzle piece. In our case, we modelled each side as a three-piece composite Bezier, giving us the building blocks to create entire puzzles.

Representing a puzzle: While building a single piece is useful, they exist within the context of an entire puzzle. Each piece will share its side shape with its neighbours, mirroring the design of each curve. Luckily, this works in our favour, pieces sharing sides allows us to double dip on data usage, using the curve of a piece’s right side to represent its neighbour’s left for example.

In our model of a puzzle, we represented each “line” of curves that would separate pieces from each other. Each line consisted of segments that modelled a single side of an individual piece and could be used to sample the curve. With these models in place we could represent a puzzle of any dimensions. By simply sampling specific segments of each line, any piece of the puzzle could be built.

Representing Pieces In Game: All this data is well and good in memory but it’s of no use to us if we can’t visualize it in game. While a variety of methods were viable, two methods were explored with one ultimately winning out over the other after multiple iterations.

Cutout Textures: The first method explored was the use of a cutout texture on a simple plane. When provided to a material, a cutout texture would tell the renderer what parts of the plane to make transparent, according to the alpha value. To create these cutout textures, a master texture was used. Each line would need to be drawn pixel by pixel, for each line of the puzzle. The cutout texture would then be created by flood-filling the piece at the desired location before being translated onto a new texture of the correct size.

Ultimately this proved to have a variety of downsides. The quality of the textures suffered due to their limited size, resulting in jagged edges. Higher quality, aesthetically pleasing pieces needed larger textures. These ate more memory and were slower to build. This was especially apparent when larger puzzles were being built, as load times hit multiple minutes for multi-thousand piece, high quality puzzles. Thus we turned to another approach.

Mesh Generation: With our same building blocks in place, another way of representing our pieces was through the use of meshes. Much of the time spent generating textures was used flood-filling pieces, a process that meshes don’t require. By simply generating the outline of our mesh, then triangulating the vertices, we can build faces that can easily be textured with UVs. Instead of creating a larger texture for higher quality pieces, we can instead sample more vertices from our data structures.

This method proved to be much more performant and generated better looking pieces in a fraction of the time. Meshes were both smaller in memory size as well as faster to make. Puzzles of around 8,000 pieces would require no more than a minute load time for lower end devices.

Getting Funky:  At this point, we considered three of our four goals to be completed. Our generation was fast and scaled well to larger sizes, and providing the generator a seed would produce the same puzzle every time. The only issue was our pieces looked boring. Minor variations were being made on a single shape that resulted in every piece looking too similar. We needed a human touch. If only we could design our own side shapes with the use of some in editor tools…

With a little bit of tweaking I found this could easily be accomplished as well. Defining a data structure out of a composite Bezier curve, we could feed the algorithm a variety of shapes that it could randomly pick from when generating. Creating a tool that allowed a designer to build out curves and edit them easily aided in the process. Without touching a piece of code, anyone could build a curve out of any number of points or internal curves, receiving feedback as to what the shape would look like with each movement on the internal Bezier points. The editor of course had the essential feature of loading and saving shapes into our assets as a scriptable object as well.

Conclusions: Looking back at our original goals, the algorithm and tool suite now meets each of them. The algorithm is fast and scalable, allowing us to generate multi-thousand piece puzzles quickly. The use of seeded randomization keeps the process deterministic, ensuring our players will be looking at identical puzzles. With our piece shape tool, the creation of varied pieces is also seamless. From within the Unity editor, new piece shapes can be made, edited and saved before being added to the algorithm to appear in game. This ensures our pieces look interesting and varied, achieving our last goal!