Thursday, March 15, 2012

Random Dungeons

I scrapped the online algorithm and opted for an offline algorithm instead. I also got rid of the template system, because it is not very flexible. The new algorithm uses a room partitioning strategy to create a bunch of rooms first and then connects them with corridors. The dungeons created in this manner are a lot more interesting and unpredictable.

At first, I tried using a Quadtree to create the rooms. The problem with that was that if you increased the randomness, the algorithm would result in rather elongate rooms (see the example image below). This is due to the fact that when dividing a long rectangle into four, then one ends up with at least two smaller rectangles that are longish. I wanted to have rooms that are almost square, so I tried a different strategy.

Quadtree room partition, leading to elongate rooms
The next thing I tried was a BSP-like approach. Instead of splitting the rooms in four, I only split them in two. The axis was chosen depending on the ratio of the sides which leads to the kinds of rooms I wanted. To connect the rooms, the algorithm starts at the root of the tree and connects from its "splitpoint" (the center of the axis where the room was divided) to the splitpoint of its two children. These children will then connect to theirs and so on. Leaves (which don't have a splitpoint) are connected using their centers. This approach guarantees that every room will be connected. It also makes sure that there are no unwanted intersections between rooms and corridors or corridors and corridors. It didn't quite work for the example image below, but it has been fixed in the final version (see the last image).

Dungeon created using BSP
The BSP-approach worked pretty well, but due to its binary nature, it would only create one corridor per partition. From a gameplay perspective, this would lead to a lot of backtracking which is rather undesirable. To solve this problem, I tried to combine the benefits of both approaches using a hybrid tree. Rooms will usually be split in four, so you'd have many corridors to choose from. If the algorithm encounters an elongate room, it will use only one axis to split it in half. Connecting the rooms works the same as before.

Dungeon created using the Hybridtree

And here is a video of how it looks ingame:

The next step in terms of random dungeon generation would be an algorithm that fills the rooms with life. But before doing that, I might have a look at networking instead. It's always a good idea to incorporate network code at an early stage of development.

No comments:

Post a Comment