Binding of Isaac and its remake Binding Of Isaac: Rebirth are some of my favorite games. They belong to the roguelite twin stick shooter genre and are very similar to Enter the Gungeon .
The dungeons generated by these games are especially famous. I have seen countless tutorials on the Internet on how to create Isaac-style generation, but I wondered how it was implemented in the original. To my surprise, most of the tutorials describe the process incorrectly. In this article I will talk about how generation works and show an example of it in a Javascript demo.
Although I had to decompile and refresh my dusty Flash knowledge (I once wrote my own Actionscript decompiler), I was also very lucky: developer IsaacFlorian Himsl and one of the core developers of Rebirth, Simon Parser , happily answered my questions. In fact, Florian even recently recorded a video describing the algorithm. On his channel, you can also find out the details of the development of his new game Squid Invaders.
Given the presence of his story, my article can be considered redundant, but if you want bloody details, then continue reading.
Basic algorithm
Isaac's developers were heavily inspired by the 2D games in the Zelda series and generated maps similar to their dungeons.
It is a set of square rooms connected by edges to each other. Some rooms are special - there is always a shop
, a treasure room 
and a boss on each floor 
; in addition, several other special rooms are randomly selected. Except for the secret room 
, there are no loops in the dungeon.
The game itself consists in a linear passage of such levels, usually there are two of them per "chapter". In the process of passing, the maps become a little larger, and the contents of the rooms change, but the algorithm for creating their structure, in fact, remains the same every time.
The first version of Isaac was developed in less than 3 months, so Himslu had to use his time incredibly efficiently. The fundamental design of the game is sleek and simple. First, a floor plan (level) is generated. Then some rooms are selected as special. Then the interior of each room is selected from the corresponding pool.
Floor plan
Isaac is generated on a 9x8 grid. For convenience, the cells are denoted by numbers - ones indicate the X position, tens - the Y position. This means that you can move up, down, left and right, simply adding +10, -10, +1 and -1. Cells with an X position of 0 are not used (always empty), which means that most of the code does not need to worry about map boundaries. That is, the top-left cell on the map is 01, and the bottom-right cell is 79.
The floor plan only defines which cells will contain rooms - the contents of the room are selected later.
First, the formula
random(2) + 5 + level * 2.6determines the number of rooms. Those. levels start at 7 or 8 rooms and increase by 2 or 3 rooms each time.
The game then places the starting room (cell 35) in the queue. Then it cycles through the queue. For each cell in the queue, it cycles through the 4 main directions and does the following:
- Determines the adjacent cell by adding + 10 / -10 / + 1 / -1 to the current cell.
- If the adjacent cell is already occupied, then the game does nothing.
- If the neighboring cell itself has more than one filled neighbor, then the game does nothing.
- If there are already enough rooms on the level, the game does nothing.
- The game does nothing with a 50% probability.
- Otherwise, the game marks the adjacent cell as containing the room and adds it to the queue.
If a cell does not add a room to any of the adjacent cells, then it is a dead end and it can be added to the list of destination rooms for further use.
In case maps require more than 16 rooms, the starting room is periodically queued again to stimulate growth.
Since the algorithm described above starts with a single room and expands outward many times, it is, in fact, a breadth first exploration. The restriction not allowing a room to be added if there are already two neighbors divides rooms into separate corridors that never come together in loops.
The floor plan is then checked for consistency. It should contain the required number of rooms, and the boss room should not be located next to the starting room. Otherwise, generation starts over.
Special rooms
Boss rooms are placed by reading the last item from the end room list. Due to the fact that the generation is performed as an outward growth, it will always be one of the rooms located at the farthest distance from the starting room.
Then the position of the secret room is indicated. These rooms are added to the floor plan; they are one of the few exceptions to the rule that prohibits placing rooms next to several existing ones. In fact, the algorithm, on the contrary, prefers to place them like this. The generator randomly searches for an empty cell next to at least three rooms and not near any of the end rooms. If he does not find it after 300 attempts, then it weakens the search criterion slightly, and after 600 attempts it weakens it even more. This procedure ensures that the secret room is always placed on the level, but usually they are squeezed near intersections, meaning there are always many rooms near them.
Almost all other special rooms are located in random end rooms. Some rooms are guaranteed, others have a small chance or criterion. For example, sacrifice rooms appear one of seven times; if the player is at full health, then they occur about one in three times.
Regular rooms
Adjacent rooms always have a door (or breakable wall) exactly in the center, and each room is designed to be accessible from all four directions. Therefore, no special considerations are required when choosing rooms - any combination will do.
Rooms are randomly selected from the pool. Information about rooms contains both structure (pits, fire, stones, etc.) and monsters. Both are subject to random variations, such as the appearance of champion monsters and red fireplaces.
There are three pools for regular rooms: easy, medium, and hard. The first stage of the chapter chooses from simple and medium rooms, and the second from medium and difficult. The first chapter (Basement) contains 174 ordinary rooms in pools. "Alternate Chapters" like Cellar, which randomly replaces Basement, have a slightly different set of rooms.
Curse of the labyrinth
One of the most interesting additional features of the code is the double-sized maps. They are created randomly and only for some challenge modes. In addition to the obvious doubling of the number of special rooms and two adjacent boss rooms, they also have many small details:
- 80% more normal rooms (max 45)
- For special rooms, only the 6 far end rooms are used
- Levels select rooms from pools of simple, medium, and complex rooms.
- Additional normal rooms are randomly added to the floor plan with placement logic similar to secret rooms.
Demo
I created a simplified example of a generator in Javascript so you can experiment with it. The complete code can be found here , and a working example can be found in the original article.
Rebirth
Binding of Isaac: Rebirth is a remake of the original Binding of Isaac created by Nicalis , which at the time was famous for their VVVVV and Cave Story ports . The game was ported to C ++ and all sounds and graphics were redone. Over the years, the game has received many DLCs, adding new items and enemies to the already impressive list of the original.
While Rebirth has a bunch of interesting innovations, the main contribution to level generation was the addition of larger, irregular rooms.
With a full set of DLCs (at the time of this writing, this is Afterbirth +), the game has 11 large rooms: 2 × 2, 2 × 1, L-shaped and narrow corridors in different rotation options.
Typical L-shaped room, three times the size of a normal room. It was implemented by Simon Parser through careful modification of the Himsla source code.
Instead of looping through all directions, the algorithm bypasses all exits from the room. In a 2x2 room, there can be up to eight of them.
When it comes to inserting a room, he randomly tries to insert a large room instead. Neighbor checks are still applied, but only to the first cell next to the door; however, the algorithm checks to see if there is enough room for the rest of the room. This means that large rooms can create level loops. Usually, two large rooms are generated next to each other and are complemented by a pair of doors connecting them.
If there is not enough space for a room, then the algorithm tries to insert another candidate. If large rooms are inserted successfully, there is a 95% chance that they will be removed from the pool.
Even more code is needed to handle the large boss rooms. Remember that boss rooms are always located as far away from the starting room as possible. If a larger room is desired, the generator replaces the intended single room. Since boss rooms are always dead ends, when replacing, the algorithm checks to see if they are adjacent to some additional rooms. Sometimes replacement is still impossible, so all endpoints are checked at the maximum distance from the starting room, and if they do not fit, then the algorithm gives up.
For secret rooms, adjoining rooms on the floor plan are considered for placement, and rooms are selected only when the algorithm determines that doors are not needed.
In Isaac, chasms are usually impossible to cross
Output
The Isaac Level Generator is not the most complex one I've seen, but despite such a small amount of code, it works incredibly well. This is probably why they try to recreate it so often. Its simplicity allows for changes and extensions, as we can see in the example of Rebirth. An incredible result.
You can also notice that this game continues the trend of generating floor plans separately from room details. In my articles about Diablo 1 [ translation into Habré] and Enter the Gungeon [ translation into Habré], I said why this approach can be very powerful.
When decompiling the code, I did not find any particularly interesting details. The most interesting thing I can say is that the location of the treasure room is stored in a variable named "boner" - probably short for Bonus Room. There are also subtleties in the code regarding minor side effects of various items, but I'll leave this topic to the analyzers .
Then you can watch Himsla's series of videos on the internals of the game, or even play Isaac and see all the levels live. I heard that the new Repentance DLC is coming out this year. I also recommend playing other games by Chief Designer Edmund McMillen (especially Super Meat Boy).