Total Library

The Library of Babel is a phenomenal short story by Jorge Luis Borges. It's a crystalized version of the kind of mathy alternate universe story I am obsessed with¹. The story takes place inside an apparently endless library, the walls are lined with books with nonsense contents composed of apparently random sequences of letters. The narrator posits that the library contains exactly one copy of every possible book. I've wanted to recreate this world myself for a while and spent about a year on and off building it into a game.

Source on Github

I built the game in Godot 3.5, and used C++ with gdnative for the heavy computation.

Representing Far Too Many Books🔗

It may feel natural to represent the books' contents as normal strings, however we can be more efficient. Most characters aren't really necessary to get the vibe of the story across, so we can pick a subset and roll our own tightly-packed character encoding. And then for math reasons in the next few sections, we want to be able to pack and unpack our book contents to an integer.

To get there, first we need to pick a character encoding. For this we can pick $C$ characters and assign them a number from $0$ to $C-1$. In the story Borges states there are 25 symbols: the period, comma, space, and 22 letters of the alphabet. From this source Borges explains that his count of 22 letters comes from throwing out several letters he considers redundant. I plan to use all 26 letters of the English alphabet along with the period, comma, apostrophe, space, exclamation mark, and question mark for 32 total characters.

Packing and unpacking the contents between integers and strings is straightforward, it's the same as converting a base $C$ number to or from a string. I'm sure almost everyone learning to code has done that exercise converting numbers to strings as decimal or hexadecimal. Using a power of two for the size of the character set gives us a solid performance boost because it lets us use bit shifts and bitwise ands to extract characters rather than division and remainder.

For the length of the books, Borges states there are 410 pages to each book, each page with 40 lines, and each line with 80 characters. I ended up reducing this to 100 pages for the sake of runtime and 18 lines of 25 characters for legibility. That gives a total of $100 \cdot 18 \cdot 25 = 45,000$ characters per book. I also count the title as part of the contents, so that's an extra 10 characters. That leaves us with a total of $32^{45,010}$ unique books and about 28KB of data to represent one book. And because of that we need to use arbitrary-precision integers, or BigInts as they're called in several languages.

Arranging the Books🔗

Now we need to physically place all the books in the library. The story describes hexagonal gallery rooms with shelves and 'vestibules' separating the rooms. It also describes endless spiral staircases in the vestibules and ventilation shafts in the gallery rooms. However, the story is rather ambiguous with the exact layout of these rooms so that took some imagination to come up with something reasonable. I went with a hexagonal grid² layout of gallery rooms and vestibules, with each taking up a full cell.

Then the rooms are stacked with every other layer rotated by $60\degree$ so that you can switch between traveling along the x and y axes by going up or down a level.

While this layout does let you travel in any direction, it has the side effect that that the rooms you can see directly above and below you through the ventilation shaft are unreachable.

With the layout defined, we can place the books in a fairly simple row-major order. Each book has a unique index from how we defined the mapping between the text of the book and integers. So we place books within a room sequentially by index, then move to the next room along the x axis, then at some point we wrap back to the next row along the y-axis, and finally wrap to the next layer along the z axis. This requires us to pick a length for the x and y axes, I went with something close to the cube root of the total number of books. With this we can write some fairly simple C++ code to map from a grid coordinate to a flat index:

big_int book_index(
    int room_x, 
    int room_y, 
    int room_z,
    int shelf, 
    int book) {
  // Cancel out the vestibule rooms, they don't have books
  int gallery_room_x = (room_x + 1) / 2;

  return (BOOKS_PER_ROOM * gallery_room_x
           + X_LENGTH * room_y 
           + (X_LENGTH * Y_LENGTH) * room_z) 
         + (shelf * (BOOKS_PER_ROOM / NUM_SHELVES)) + book;
}

Random Permutation of Borges' Number🔗

Having the books in alphabetical order would be boring. Part of the mystery of the story involves people only occasionally finding books with recognizable patterns.

So let's lay out some requirements:

1. Every book needs to appear exactly once in the sequence. That is, it needs to be a permutation and therefore a bijection from the set of books onto itself.
2. We need fast random access to any point in the sequence.
3. Neighboring books and rooms can't look similar, in particular the titles. I won't require them to pass any kind of randomness test, all I need is to avoid any obvious patterns.

This stackoverflow post suggests a way to generate a random permutation of a large $N$ using modular exponentiation. However, that requires $N$ to be a prime number, which doesn't work because our $N$ is always a power of something, or it requires you to pick a prime larger than $N$ and skip any numbers you generate larger than $N$. That would mean the numbers could only be generated in sequence as there is no efficient way to know how many numbers have been skipped at any point in the sequence. Also, The number picked may produce a much smaller cycle than the full set of books, in particular the order of the subgroups is always a divisor of $p-1$ and finding a subgroup with order $p-1$ is non trivial. You essentially have to check the full cycle, or check at divisors of $p-1$ that it hasn't looped back to $1$.

The author of libraryofbabel.info shares one of their methods which involves a modular multiplication and some bit shuffling inspired by Mersenne Twister: https://github.com/librarianofbabel/libraryofbabel.info-algo

This method works well and is essentially what I went with. The multiplier can be picked at random, and that alone does a good job hiding patterns between consecutive books. However, when moving between rooms on the y axis it can leave the lower third of the books identical because of the larger shift. To account for that we can do a x ^= x >> n to mix up the lower bits using the higher bits. The only thing we need to do to guarantee that this is a permutation is show how to invert each of these steps. This is true when the multiplier is coprime with the number of books, and the bit shift n is greater than half the number of bits in the number of books. The first point comes from abstract algebra, treating the books as a cyclic group. The second is relatively easy to show, let:

Then as long as $n$ is greater than half the length of the number:

And since xor is its own inverse:

So this is invertible by applying the same operation to the output. It's also quick for random access and looks good in practice so meets all the requirements and I'm happy with it.

The actual code is very simple and looks something like:

val *= multiplier;
val ^= val >> shift;

However in practice I'm generating a bunch of books in sequence, so instead I do the multiplication once for the first book, save it, and increment by the multiplier for each subsequent book. That ends up being significantly faster than doing a bunch of multiplications of 28KB numbers.

big_int multiplied = val * multiplier;
for (int i = 0; i < num_books; i++) {
    big_int book = multiplied ^ (multiplied >> shift);
    
    // Do something with book...

    multiplied += multiplier;
}

Rendering the books🔗

There are a lot of books in view at any given time so optimizing their render cost is important. They're also the focus of the game so they need to look nice.

There are two modes I've settled on for rendering the books:

1. A book on a shelf or on the ground. Always closed, only need to render the title, cover, and sides of the pages.
2. A book in-hand, potentially open. Needs to be rigged and animated, needs to render large amounts of text inside. Only one at a time.

Shelf/Floor books🔗

There could be thousands of books in view at any given time. I also want to display the book's title on its spine, meaning there needs to be some kind of text rendering for all of them.

I've chosen to render the shelf books as multimeshes which I believe uses GPU instancing. I provide the book mesh and the transforms for each book it should render. I can also pass a color and "custom data" (also formatted as a color) to each instance. Each color gives me four floats to pack some data for the title text into. Unfortunately though, I couldn't use all of the bits for each float. Somewhere in the pipeline the floats must get reinterpreted and my title data wasn't getting through. I was able to use the 23 bits in the mantissa to store an int value which I could cast back and forth losslessly. That gives me 92 bits in just the color data which is more than enough.

Packing to the gdnative buffer looks something like this:

const uint32_t MANTISSA_BITS = 23
const uint32_t MANTISSA_MASK = (1 << MANTISSA_BITS) - 1;

void pack_num_to_floats(const big_int &num,
                        godot::PoolRealArray &buff) {
  big_int val = num;
  int packed_val = 0;
  int packed_bits = 0;
  while (val > 0) {
    packed_val |= (val % NUM_CHARS).convert_to<uint32_t>() << packed_bits;
    packed_bits += BITS_PER_CHAR;
    if (packed_bits >= MANTISSA_BITS) {
      buff.append((float)(packed_val & MANTISSA_MASK));
      packed_val >>= MANTISSA_BITS;
      packed_bits -= MANTISSA_BITS;
    }
    val /= NUM_CHARS;
  }
  if (packed_val > 0) {
    buff.push_back((float)packed_val);
  }
}

Unpacking a character in the shader requires dealing with bits being spread across multiple components of the color, that looks like this:

uint bit_offset = char_index * TITLE_BITS_PER_CHAR;
int channel_ind = int(bit_offset/MANTISSA_BITS)
uint shift = bit_offset % MANTISSA_BITS;

uint target_char;
switch(channel_ind) {
    case 0:
        target_char = (title_bits.r >> shift) | (title_bits.g << (MANTISSA_BITS - shift));
        break;
    case 1:
        target_char = (title_bits.g >> shift) | (title_bits.b << (MANTISSA_BITS - shift));
        break;
    case 2:
        target_char = (title_bits.b >> shift) | (title_bits.a << (MANTISSA_BITS - shift));
        break;
    case 3:
        target_char = (title_bits.a >> shift);
        break;
    default:
        target_char = uint(0);
        break;
}

target_char &= ((uint(1) << title_bits_per_char) - uint(1));

The title is then rendered using a font atlas texture and a bunch of UV transform fuckery. Using a normal sprite font texture would make the text look pixelated close-up unless it was rendered at a very high resolution. Instead I'm using a technique from this paper from Valve which describes how to use Signed Distance Fields (SDFs) to render vector graphics using raster textures. In summary the process is:

1. Render your desired vector image at a high resolution
2. Resample at a lower resolution, storing the distance to the closest pixel of the opposite transparency in the high-resolution image
3. When rendering, make sure the texture is using bilinear sampling and put a threshold on the alpha channel

I got good results with a 1024 "size" source font (not sure if pt size or pixel height) and a 64 pixel height SDF texture output.

Check out my conversion script:

• SDFConverter.tscn
• SDFConverter.gd
• SDFConverter.gdshader

The technique only requires one line of code in the shader, but does require a somewhat slow preprocessing step. Here's a comparison of a regular font and an SDF-ified version with the same resolution:

The SDF font can draw straight lines with a large range of slopes, with the slope changing at most once per pixel in the raster texture. It also tends to round off sharp corners. Overall though it is higher quality than even a much higher resolution raster version.

Here's final the shader: book_shader.gdshader

Fortunately, Godot 4 has an improved version of this called MSDF built-in. So now this should be almost effortless, but might still require some custom shader work to layer it with other effects.

Held book🔗

The held book is rigged and animated in Blender, then exported to Godot. Whenever the player picks up one of the other books, we can swap it out for the held book model and animate it.

There can be 4 full pages in view as a page is turned, so there isn't any easy way to pass all that as text to the shader like we did for the titles. Instead, the best route for this is to prerender the visible pages to viewport textures and apply them to the book pages. The impact for this should be minimal as long as we guarantee that there is only one open book at a time, which only requires closing the book as it's put down.

The held book requires managing a bunch of transitions, so I modeled it as a state machine and set up some tweening code to transition between different states:

• Held
• Starting on the shelf or on the floor and moving to the held position
• Starting held and moving to a slot on the shelf
• Starting held and dropping to the floor
• Turning pages

HeldBook.gd

Endless Hallway Effect🔗

This works using what is essentially half a portal and a tilable hallway segment.

Check out the code:

• PortalPlane.tscn
• PortalPlane.gd

Take a camera rendering to a viewport, place it one segment back from the end of the hallway, then render its view to a flat plane covering the end of the hallway. Since the plane is included in the view of the camera, each frame the camera will add another copy of the hallway segment to the image drawn on the plane. At a high enough framerate, and from far enough away, the image on the plane looks like an infinite hallway with the correct perspective.

The core of it is setting the viewport's camera to the right position:

func _process(_delta):
    var local_pos = to_local(get_viewport().get_camera().global_transform.origin)
    self.camera_node.frustum_offset = Vector2(-local_pos.x, -local_pos.y)
    self.camera_node.near = local_pos.z
    self.camera_node.size = portal_size.y
    # Because camera is a child of the viewport, it doesn't inherit the transform from this node
    self.camera_node.transform = self.transform.translated(local_pos + render_offset)

However there are a few caveats to get it to look right:

At lower framerates the hallway can appear to bend as the player moves, because the further iterations of the rendering aren't refreshed fast enough to account for the movement.

If the plane is too close to the main camera, the difference in perspective between the first and second iteration is too big and the hallway appears stretched. To fix this put a few more real hallway segments between the main camera and the plane.

The game uses three "real" copies of the hallway segment, then uses this effect to render the rest. It should have the same performance as rendering one extra iteration of the hallway.

The viewport camera also needs to be set up to follow the main camera and use the right view frustum. The viewport camera should:

• have it's position match the main camera's position but displaced back by the length of a hallway segment.
• be pointed parallel to the normal of the plane that's displaying the viewport texture. Importantly not pointed at the plane or the view will be weird and skewed.
• use the right custom frustum projection. In Godot this is the "Frustum" projection mode, with the "Frustum Offset" set to the main camera's position projected onto the display plane, the far plane set just past the display plane, and the near plane set one segment's length behind the display plane.

And to get the viewport texture to look right:

• make sure the plane's material has "unshaded" enabled so that it doesn't catch shadows or light
• flip the texture vertically by checking "V Flip" in the viewport because of the coordinate system mismatch between "textures" and "images". "Textures" tend to put the origin in the bottom left, "images" put it in the top left with y pointing down.
• enable "Albedo Tex Force sRGB" in the material settings to stop the texture from fading to white with each iteration. Not entirely sure why this is necessary, but there is apparently some mismatch in between the color space of the texture and the color space Godot using to interpret it.
• set the shadow atlas size on the viewport to something non-zero. It defaults to 0 which disables shadows in the viewport texture and makes things brighter than they should be.