For us computer scientists and game developers, Procedural Content Generation is directly connected with computers and algorithms. It seems such a modern thing!

In reality, the exploration of the “combinatorial nature of art and human thoughts” is a much older concept. Probably, the most interesting and early writing on “PCG” is the doctoral dissertation of Gottfried Leibniz, De Arte Combinatoria (On the Combinatorial Art) (1666) in which he exposed the main idea that “all truth are nothing but combinations of a relatively small number of simple concepts.”

Even if that little idea was always in the back of the head of the most daring artists, we have to wait until 1961 to see the first literary work that we can define a PCG opera. That year, Raymond Queneau, a French novelist and poet, published the book Cent mille milliards de poèmes (Hundred Thousand Billion Poems). The book is composed by just ten sonnets of 14 verses, but it was printed such that each verse of the sonnet is on a different paper strip. The reader can, therefore, “generate” a different poem by changing each of the 14 verses with one of the ten variations. In the end, the book contains 1014 different combinations, hundreds thousand billion poems, precisely.

Probably, Marc Saporta, another French writer, thought that 1014 was not enough because in 1962 he published the book “Composition n° 1”, a book composed of 150 not numbered pages that can be shuffled at will by the reader producing 150! (factorial) different books.

This was just the beginning of a literary movement called combinatorial literature, in which authors used math and combinatorial generation as a tool for inspiration. The most emblematic author probably was Georges Perec who creates a complex system referred by himself as “a machine to inspire stories” for the book La Vie mode d’emploi (Life, a User’s Manual). The book tells the story of a big building with 10 floors and 10 rooms per floor (imagine a 10x10 square). The narration starts from a room and continues with L-shaped movements (just like the Knight in Chess) from room to room until covering all the rooms but 1 (the basement).

Moreover, the book contains 42 lists of objects such as, emotions, animals, countries and more arranged according several Graeco-Latin squares (a 10x10 arrangement of pairs of different lists such that every row and every column contains each element of one list exactly once, and that no two cells contain the same ordered pair). These squares are then explored “randomly” by the L-shaped narration producing a list of objects that the author has to include in the current chapter. I know, it is quite confusing right now. Do not worry. We will look at the mathematical structure of this book more in details in the next section.

Another author fascinated by the use of mathematical rules to generate novels was Italo Calvino, an Italian novelist. The influence of the combinatorial authors is evident in books such as Le città invisibili (Invisible Cities) or Il castello dei destini incrociati (The Castle of Crossed Destinies). In the first book, the author (as Marco Polo) describe 45 cities according to 9 thematic groups and in such a way that each part of the description can be exchanged with each other so that “the reader can create its own path in the book.” In the second one, the author uses a deck of 73 tarots arranged in such a way that reading each line (from right to left or left to right, but also from top to bottom or from bottom to top) describe one of the 12 stories narrated in the book.

You probably have noted that all the authors I mentioned are French (except for Calvino), but they have another point in common. They all (except for Saporta) belong to the same literary group: the Oulipo (Ouvroir de littérature potentielle, workshop of potential literature). If you are interested in this sophisticated experimentation with the narrative and the human language, you definitely have to take a look at the Oulipo’s authors. Ah, by the way, the group is still on activity and has a beautiful website (http://oulipo.net/). Check this out.

The algorithm behind “La Vie mode d’emploi”

I think that is worth to look at the algorithm behind Perec’s masterpiece in more details. It is an excellent example of how to build a PCG algorithm using only paper, pen and a bit of patience. The basic structure in “La Vie mode d’emploi” is a 10x10 square grid. The challenge is to create an algorithm that can shuffle a certain amount of lists (objects, locations, characters, and so on) over the grid and to rearrange the order with which we navigate it. Perec solves this problem in a way that is probably unnecessary complex but is part of the mathematical beauty of his work. Let’s start with grid navigation order: the Knight’s Tour.

The Knight’s Tour

As we said before, Perec solves the navigation problem using the Knight’s Tour. The Knight’s Tour is an ancient mathematical problem and consists in finding a path for a knight in a chessboard NxN such that the knight will visit once (and only once) every square of the board. The difficulty comes from the fact that the knight in chess moves in a peculiar L-shaped way.

The Knight’s Tour is a particular instance of a more general problem called Hamiltonian path problem over a graph. Fortunately, even if this problem is NP-complete, the Knight’s Tour is a special case with linear complexity. The way to solve this problem is to follow the Warnsdorf’s rule: “the knight is moved so that it always proceeds to the square from which the knight will have the fewest onward moves.” That is, from the current knight position, compute for each possible move, the number of possible moves in that square and then chose the square with the smallest number. Obviously, using this rule of thumbs you can find only one the many many thousands of possible solution for a grid 10x10, but we don’t care. We only need one solution.

Shuffle all the lists: Graeco-Latin Square

Now that we have a way to navigate the square we need a function that links each square with items we want to include in that chapter. For this purpose, Perec used 21 lists. Each list is composed by two sub-lists with 10 elements each. Then, he built 21 Graeco-Latin squares, one for each list, that, for each chapter specify which pair of elements we need to use from each list (for a total of 42 elements).

Do not worry. This is easiest than it looks. For simplicity, let’s do everything on a smaller scale. Imagine that we have a 4x4 square and just a single list composed by 8 objects divided into 2 columns. For instance:

We want a way to map a pair in this list with a square in the grid. However, we need to maintain some constraints: first, we want that each element appears only once for every row and column and, second, that no square contains a duplicate pair. Such a structure is exactly the definition a Graeco-Latin Square. Therefore, we built our magic square using pairs of integers. For instance, for a 4x4 grid:

Now, suppose we want to see which pairs we need to include in Chapter 5. We look at Chapter 5 on the grid and see that it falls at coordinate (1,3). We take our Graeco-Latin Square and check the pairs at coordinate (1,3). This is the pairs (3,4). Then we look at our list and choose the 3rd element of the first column and the 4th element of the second one. Therefore, Chapter 5 must contain a story about a Cat and a Flamethrower (!!). Repeat this procedure for multiple lists and a bigger board and you will get exactly what Perec did in his book.

As you can see, this is an amazing instrument for shuffling and mixing elements. The problem is that there is no easy way to build a Graeco-Latin square. Note that a solution for a 10x10 grid was only found in 1959! Euler himself conjectured that there was no solution for oddly even squares! (An oddly even number is a number such that n mod 4 is equal to 2, just like 10). Only in 1959 Parker, Bose, and Shrikhande showed that it is possible to build a Graeco-Square number for each grid greater than 2, except a 6x6 square.

Conclusion

I hope this can be a first step for you to explore the combinatorial literature world. Respect to the Seed version, I tried to explain more in details how the “Perec Content Generation” algorithm works. Hope you enjoy!