Friday, October 4, 2013

Worldgen and dungeon variations in Pugnacious Wizards 2

I want to share the basic world generation algorithm used in Pugnacious Wizards 2 and some things I did to add as much replayability, variety, and interest to the world generation. Hopefully you can try some of these ideas in your roguelikes.

In case you haven't seen it yet, the game takes place in a densely packed single level castle that's made of a 9 by 9 grid of 7 by 7 rooms. Here's an example of what the entire game looks like on the first turn without FOV applied:

Here's the basic algorithm that Pugnacious Wizards 2 uses to create a level. It can be adapted to other roguelikes too:

  1. Start with a perfect maze. A perfect maze is a maze with no loops - there's one and only one way from each room to each room. This means there's lots of choices since most rooms will have two or three doors that you can go through. This also means there's lots of dead ends. There's a ton of great resources on the internet about maze types, maze making algorithms, and maze solving algorithms. I don't think dead ends are fun so that's what the next step solves.
  2. Add extra connections. Decide how many dead ends you want to have and as long as there are more dead ends than that, connect a dead end to a random neighboring room. I choose to make each dungeon have up to 12 dead ends - each with it's own treasure. Three dead ends have amulets that you collect to win, six dead ends have a spell that you can pick up, and the remaining few dead ends have heart containers that will heal you.
  3. Place themed rooms. Now that all the rooms are connected, assign a random theme to each one and place them on the actual map. There's about a dozen themes: empty rooms, wall traps, floor traps, courtyard, treasure room, portal room, etc. Most rooms also have extra walls that follow a preset pattern and maybe a few randomly placed wall tiles. Trees are also added. This adds a bit more variability and tactical options. You can hide behind walls to avoid traps and burn trees to damage others or yourself. Room themes that include treasures, traps, guards, archers, or wizards will also place those at this time. Finally, each room has a very small percent of being a special version: a courtyard will be completely filled with trees, an empty room will be filled with skeletons, a trap room will have far more traps, etc.
  4. Place regional themes. Each treasure room with an amulet is guarded by a fire wizard, a poison wizard, or an ice wizard. That room and three rooms joined to it are rethemed with the appropriate element: all the traps are changed to that element and visible floor traps are placed in the corners of each room. Also the element is applied to each tile; water gets frozen or poisoned, grass and trees get burnt or poisoned, etc. This means you can tell when you're close to the amulets and is sort of like a mini-level in the dungeon. Most games have ice levels or fire levels and this is one way to get that same feeling in a single dungeon. In the above example picture, you can see how the poison region near the center of the castle has greenish poisoned water in one room and the fire region in the upper right of the castle has grass that's on fire. If there were any towers or traps then they would also be themed.
  5. Place extra stuff. Additional gold, blood, bone piles, and see-through wall tiles are added at random.

So that's the basic algorithm. A perfect maze with extra connections, treasures in the dead ends, themed rooms, themed areas, and extra loot.

But that's not all that happens. The real variety comes from tweaking the worldgen algorithm itself.

Tweak the variables. These variables include what percent of grass tiles are trees, what percent of walls that have see-through tiles added, what percent of doors are unburnable stone doors, how many extra room connections are added, how much total gold there is, and a few other things. In the above example picture, you can see how trees are common in the courtyards and as decorations in other rooms.

Tweak the lists. It starts with a list of every room theme: 12 or so in total. Then a few are removed at random - they won't show up in this game. Then a few are chosen from the remaining at random and added to the list again - these themes will show up more often than others. This small difference means you can play a few games before seeing each theme. It can also change the feel quite a bit. A dungeon with lots of portals plays differently than one with no portals and a dungeon with lots of anti-magic rooms plays differently than one with lots of trap rooms or lots of creature rooms. In the above example picture, you can see how there are plenty of archer barracks but no guard barracks: they must have been removed from the list of room themes.

Apply explicit variations. There's a list of 30 or so variations. Two, three, or four are picked at random and applied to the map and added to the subtitle. Some variations just make one room theme far more common by adding it to the list of themes 9 times, some will change the stats of archers or guards, some change how much damage is done by fire, ice, poison, arrows, or melee, and some have other small effects like changing the prices of spells, how large explosions are, etc. A game where skeletons regenerate in only a few turns is very different than a game where fire traps are far more common and do double damage. In the above example picture, you can see how archer barracks, which have an "a" pattern on the floor, and portal rooms, which have a glowing block in the center, are far more common than other rooms. These variations also affect the subtitle.