Dungeon Generation in Binding of Isaac

BorisTheBrave.Com

 https://www.boristhebrave.com/2020/09/12/dungeon-generation-in-binding-of-isaac/

The Binding of Isaac, and its remake, Binding Of Isaac: Rebirth are one of my favourite games of all time. It’s a roguelite twin stick shooter, much like Enter the Gungeon.

The dungeons it generates are particularly iconic. I’ve seen countless tutorials online offering how to do Isaac-like generation, but I was interested in how the original did it. To my suprise, most tutorials get it wrong. In this article I go over how the generation works, including a Javascript demo.

Though I did work through a decompilation, and brush up on my rusty knowledge of Flash (I wrote my own actionscript decompiler back in the day), I was also very fortunate that Florian Himsl, the developer of Isaac, and Simon Parzer, one of the key developers of Rebirth, were both happy to answer my questions. In fact, Florian has recently made a video describing the algorithm. Check out his whole channel for development details on his latest game, Squid Invaders.

Given his write up, this article is somewhat redundant, but if you want the gory details, press on.

本文中，我將介紹生成的工作原理，包括一個Javascript演示。

以撒的作者Florian最近做了一個視頻來描述這個算法。

 

The Core Algorithm

Isaac is heavily inspired by the 2d zelda games, and generates maps similar to their dungeons.

It’s a bunch of square rooms that connect adjacently to each other. Several rooms are special – there’s always a shop , reward room  and boss on each floor, and a few other special rooms are randomly picked too. With the exception of the secret room , there are no loops in the dungeon.

The game itself is a linear progression of such levels, typically two per “chapter”. The maps get slightly larger for later levels, and the contents of rooms change, but the layout algorithm is essentially the same every time.

The first version of Isaac was developed in under 3 months, so Himsl had to be incredibly efficient with his time. The key design is elegantly simple. First, a floorplan is generated. Then some rooms are designated as special rooms. Then the interior of each room is picked from an appropriate pool.

 

1.房間都是以方塊為單位相連的

2.有幾類特殊房間是必定有的， 有幾個特殊房間是隨機選的

3.隱藏房間比較特殊，沒有走主loop生成，是特殊處理的

4.設計上 有效、直觀、簡單。

5.首先生成一個布局圖floorplan；然后一些房間被指定為特殊房，然后有個合適的“房間池”去選擇普通戰斗房。

 

Floorplan 布局圖

Isaac is generated on a 9×8 grid. For convenience, the cells are numbered numerically, with the units digit indicating the x position and the tens digit indicating the y postion. This means you can move up, down, left, and right just by adding +10, -10, +1 and -1. The cells with an x position of 0 are unused (always empty), which means that most of the code doesn’t need worry about the boundaries of the map. So the top left cell of the map is 01 and the bottom right cell is 79.

1.9*8的格子，  up:+10  down-10  左+1 右-1

2.個位數為x ，十位為y， 左上角為01  右下角為79  【這里翻譯后我對細節保持懷疑。不過不是重點】

 

First, the number of rooms is determined by formula random(2) + 5 + level * 2.6. I.e. levels start with 7 or 8 rooms, and increase by 2 or 3 each time.

首先，房間個數公式為：   random(2) + 5 + level * 2.6 。 例如關卡開始為7或8個房間，然后每次增長2或3個房間。

The game then places the starting room, cell 35, on a queue. It then loops over the queue.

游戲將開始房間(單元35)放置在一個隊列中。然后循環遍歷隊列。

For each cell in the queue, it loops over the 4 cardinal directions and does the following:

對于每個格子，在4個方向上進行循環以下操作：

• Determine the neighbour cell by adding +10/-10/+1/-1 to the currency cell. （上下左右找相鄰cell）
• If the neighbour cell is already occupied, give up  （如果相鄰cell已有實體，放棄）
• If the neighbour cell itself has more than one filled neighbour, give up.（如果相鄰cell的鄰居有2個以及2個以上的實體，放棄）
• If we already have enough rooms, give up（如果我們房間數量夠了，放棄）
• Random 50% chance, give up  （50%的概率，放棄）
• Otherwise, mark the neighbour cell as having a room in it, and add it to the queue.  （否則，標記這個cell為實體房，并放入隊列中去）

 

If a cell doesn’t add a room to any of its neighbours, it’s a dead end, and it can be added to a list of end rooms for use later.

如果一個cell不能將一個房間添加給它的任何鄰居（沒看懂 馬上再說   -> 解釋：文章內一個cell就是一個room），那么它就是一個死胡同，可以將它添加到一個終端房間列表中以供以后使用。

In the case of maps needing more than 16 rooms, the starting room is reseeded into the queue periodically to encourage more growth.

如果需要超過16個房間，起始房間會周期性重新生成，用于達到多房間的目的。

As the above starts with a single room, and repeatedly expands outwards, it’s essentially a breadth first exploration. The restriction that it won’t add a room which already has 2 neighbours keeps the rooms in separate corridors that never loop around.

本質上是個廣度優先搜索，不能有2個實體鄰居的限制，確保不會出現回形房間。

The floorplan is then checked for consistency. It must have the right number of rooms, and the boss room cannot be adjacent to starting room. Otherwise, we retry from the start.

然后進行一致性檢查：正確的房間數量，boss房不能和起始房間相鄰。否則重新生成。

Special Rooms

Boss rooms are placed by reading the last item from the end rooms list. Because of the outward growth, this is always one of the rooms furthest from the start area.

Boss放從endRoom隊列中選取最后一個。這是離起始房間最遠的房間之一。

Then, the Secret Room is placed. These are added to the floorplan, and one one of the few exceptions to rooms not being placed adjacent to multiple existing rooms.

In fact, it prefers it. The generator randomly searches for an empty cell that is next to at least three rooms, and not next to any end rooms

If doesn’t find one after 300 attempts, it loosens the criteria a bit, and after 600 attempts it loosens it even futher. This procedure ensures that the secret room will always be placed, but generally they are wedged near intersections so they are next to a lot of rooms.

隱藏房：最大限度保證：楔在十字路口附近，靠近許多房間。

首先隨機找出鄰接3個實體的空cell，并且不和endRoom相鄰。如果300次嘗試沒有找到 則放寬條件（猜測放寬條件的意思是相鄰2個實體）。600次找不到則再放寬條件。

Nearly all other special rooms are placed at a random end room. Some rooms are guaranteed to spawn, while others have a small chance or criteria. For example, Sacrifice rooms appear 1 in 7 times, unless you are at full health, in which case they appear about 1 in 3 times.

其他特殊房間也是隨機到endRoom內。一些房間確保生成，但是有些只有很小概率。比如獻祭房只有1/7的概率創建，但是如果你HP是滿的，則有1/3概率創建。（這么說有些特殊房間還是runtime決定的 ？存疑）

 

Normal Rooms 標準戰斗房間

Adjacent rooms always have a door (or destructible wall) in the exact center and every room is designed to always be accessible from a four directions. Thus, there’s no special considerations required when choosing rooms – they will always work.

相鄰房間總是聯通的（有門或者可破壞的墻）。這樣的話在選擇NormalRoom時候不需要特殊考慮

Rooms are randomly picked from a pool. Rooms include both the layout (pits, fires, boulders etc) and the monsters. Both are subject to random variations like champion monsters, tinted rocks, and red fireplaces.

房間是從隨機池拿出并創建的。房間內的怪物、障礙物等也都是隨機創建的。

For normal rooms, there are 3 pools of rooms – easy, medium and hard. The first stage in a given chapter draws easy and medium rooms, and the second stage from medium and hard. The first chapter, the Basement, has 174 normals rooms in the pools. The “alternative chapters” such as the Cellar which can replace the Basement randomly, have a slightly different set of rooms.

針對標準房，有三種大類型的pool：簡單中等和困難。章節剛開始的階段是簡單和中等房間，第二階段是中等和困難房間。第一章地下室有174的房間在pool里（174個房間什么意思？一共就不超過20個類型的房間啊？存疑，大概率是同種形狀的房間  enemy模版等不一樣。）

 

Curse of the Labyrinth  迷宮的詛咒

One of the most interesting extras in the code is double sized maps. These occur randomly, and also for several of the games challenge modes. Aside from the obvious duplication of special rooms and two adjacent boss rooms, it has lots of small details too:

雙倍大小地圖。隨機觸發的，有些挑戰模式也是隨機觸發的。除了明顯的 重復特殊房和2個相鄰的boss房外，還有以下細節：

• 80% more normal rooms (max 45)   多了80%的標準房間（上限45）
• Only use the 6 furthest away end rooms for special rooms  特殊房間指定為最遠端的6個房間
• It pulls from easy, medium, and hard room pools.  不分階段，直接從3種房間池中提取。 
• Randomly adds extra normal rooms to the floorplan with similar placement logic to Secret rooms.  隨機添加額外的普通房間，布局邏輯與秘密房間相似。

 

Demo

I’ve put together a simplified example of the generator in javascript for you to play with. The full code can be found here.

 

Rebirth   以撒 重生

Though Rebirth has a lot of fun new features, the main contribution to the level generation is adding larger, irregularly shaped rooms.

重置版內有：更大且形狀不規則的房間。

This was implemented by Simon Parzer as a careful modification of Himsl’s original code.

作者重改了源碼實現的

Instead of looping over the cardinal directions, it loops over all exits of a room instead. There can be up to 8, on a 2×2 room.

不再使用可選方向進行循環。使用所有可能存在的Room方向進行循環。比如2X2的大方形房間，有8種類型的可能。

When it comes to inserting a room, it randomly tries to use a big room instead. The neighbour check still only applies to the first cell, the one by the door, but it does check that there is empty space for the rest of the room.

That means that big rooms can cause some loops in the level. Commonly two large rooms are generated side by side, complete with a pair of doors leading between them.

沒看懂

If there’s no space for the room, another candidate is tried. When large rooms are successfully inserted, there’s a 95% they are removed from the pool.

Even more code was needed to handle large boss rooms. Recall that boss rooms are always placed as far as possible from the starting room. If a large room is desired, the generator replaces the designated single room. As boss rooms are always dead ends, the replacement is checked that it not adjacent to any extra rooms. Sometimes the replacement is still not possible, so all the endpoints at max distance from the start room are tried before giving up entirely.

When it comes to selection rooms, the adjacent rooms on the floorplan are now considered, and some rooms are only picked if it determines that no doors are needed.

沒看懂

 

本文詳細說明了以撒原版的實現規則。不過以撒重生（多種形狀的Room）的實現規則比較模糊，待我再找找。

文章作者的js代碼：

https://www.boristhebrave.com/permanent/20/09/isaac_gen/gen.js

參考上文鏈接實現了一個unity版本的實現：

https://github.com/fechen2/TestRoomGenerator.git

基本ok。 多形狀Room的isaac實現我沒找到，不過我想到了一種方式，實現并測試。

下圖是實現的ShapeRoom的隨機生成: