Algorithm Notes about Endless Library

Endless Library is a procedurally generated library which was originally created for PROCJAM. It contains rooms, and the rooms contain books and furniture. There's no objective for the player, other than to wander around the library.

I had some design goals entering into this project:

• The same seed should deterministically produce the same library, so that people on different computers can share places or vignettes they discovered inside the library just by sharing a seed.
• No part of the contents of the library should be predetermined in the code; everything inside needs to be generated.
• A given library should be infinitely large.
• The player should be able navigate within the library however they want, with the ability to move backward and forward between rooms, and revisit places they've seen before.
• Objects in the room should be placed the way a human might actually arrange them.
• It should achieve a wintery, solitary mood.

Creating the map of the library

I didn't use a particularly fancy algorithm to create anything in here, but there were a couple interesting constraints that came up when trying to achieve the design goals.

• Since the library needs to be infinitely large, I can't generate the whole thing in advance when I get a seed. Instead, I need to generate each room as you enter it.
• Since I don't persist the contents of the library, I need a way of rebuilding a room when you reenter it. That means the random number generator should deterministically return to the same state every time you reenter a particular room.
• Doors between rooms need to be reciprocal; if you take a door from room A to room B, and then turn around and go back through the door, you should return to room A and not some other room.

The code which takes care of these constraints is in the source code in map.lua:

https://github.com/terribleben/endless-library/blob/master/map.lua

Each room is identified by its seed, and seeds are deterministically generated based on the accumulation of all previous seeds between the root and here. Right now you can only exit rooms through the left or right, which means that at the moment this data structure is a 1-dimensional linked list.

Originally, I planned to add other doors elsewhere within a room, but I ran out of time. If I did that, this data structure would generalize to be a tree. In order to deterministically recreate the same room (given only the root seed of the whole library), the id of the room needs to uniquely express the path taken from the root to that room. I'm not sure how I would do this if the map of the library allowed cycles (becoming an arbitrary graph rather than a tree), and was still required to be infinitely large.

Arranging objects in the library

Probably the other interesting thing I played with when creating the library was attempting to make objects look like people had actually put them there. There are a number of scattered places where this matters:

• Most books come in a couple standard sizes, "paperback" and "pulp", but then there are a minority of books that have random non-standard sizes. There are also a scant few big oversize books.
• If a book on a shelf is leaning over, the books around it are more likely to be leaning at the same angle.
• Some bookcases have uniform shelves within the bookcase. Others have a variety of tall and short shelves. This is just how I observed bookcases in my own house seem to work.
• Some rooms have a grand set of matching bookcases. Others have the bookcases piled up as though they accumulated there; this is achieved by placing one bookcase randomly in the room, then recursively doing the same thing on the left and right side of the bookcase.
• Some rooms are reading rooms, with a desk, and even with a lamp.

You can see the code for the above scattered through a few files in the code; in particular,

https://github.com/terribleben/endless-library/blob/master/shelf.lua

https://github.com/terribleben/endless-library/blob/master/zone.lua

Tools I used

Endless Library is written in lua and Love2d. I used an environment called Castle which took care of loading my code over the air and running/rendering it, so I didn't need to worry about packaging Endless Library in its own binary.

Next steps

There are a number of ideas I wanted to build this week but didn't have time for.

• Library-wide supertraits which vary with the root seed but are consistent between rooms of the same library.
• Much larger rooms which scale vertically, with stairs and ladders.
• Rooms with independent "zones" which are just decorated as sub-rooms.
• Placing lamps and books randomly on furniture in a more generalized way; right now a lamp can only appear on a desk.
• Varying the style of furniture and introducing ornate, antique woodwork.
• Doors in the walls of rooms rather than just left and right exits. This is mentioned above in the map section of this post.
• Things outside, visible through the windows.
• More interesting arrangements of "reading rooms" with many desks, the way you would find in a grand library.
• Ambient sound.
• Names of rooms, maybe named after sections of libraries.
• The ability to share a deep link with a URL to a particular library seed.