Programming Challenge 15 - Generate a Simple Dungeon

This challenge is about creating a dungeon as used in games like Dungeons and Dragons. The dungeon you generate will have 9 levels and each level (except the deepest- level 9) will a staircase up to the level above it and one down to the level below. Obviously the up staircase on one level is the same square as the down staircase on the level above)

Each dungeon level occupies a space of 80 x 50 squares (80 across by 50 down). Within this space are rooms and corridors linking the rooms. It's a simple dungeon, so don't worry about monsters, treasures or traps etc just rooms and corridors are all that is needed. Your task is to write a generator that creates all 9 levels with rooms and corridors. All rooms and corridors plus a square for each staircase on one level must fit in the 80 x 50 grid.

A Room can be circular, rectangular or any combination of the two from 12 to 250 squares in size with a minimum of 2 squares width or length. E.g. a 4x3 or 2x6 (or 3x4 or 6x2) room is the smallest. A square is one of * for a wall or space for room/corridor square. Use / for an up staircase and \ for a down and staircases can be in a corridor or room. Rooms must have at least one row or column of * between them. You can have a door in a wall between two rooms. All rooms can have 1-4 doors, double doors (2 side by side) are allowed.

*******************
*******************
*..............****
*....*********-****
*....*********....*
**-***********....*
**.************_***

Basically the whole level starts out as full of *. You then draw rooms, corridors and staircases.

The above shows two rooms connected by a horizontal corridor. Corridors are a single space extending horizontally or vertically. There must be at least 1 * between two corridors or a corridor or a room. Corridors can run into a room without a door but of you put a door in use a dash - for horizontal or a pipe | for vertical doors.

**********
|.........|
**********

Corridor with a door at either end.

Other criteria; all rooms and staircases on a level must interconnect and there must be at least 2 corridors (but can be more). If I enter the dungeon at the up staircase on level 1 there should be a path through rooms corridors etc to level 9.

Summary

• Any room/corridor (on a level) must be reachable from any other.
• Up and down staircases must be in different rooms/corridors.
• The path between the staircases on a level does NOT have to go through every room. Nice if it does of course!
• If there are equal entries, the longer paths between staircases will decide who wins. (Number of rooms apart).

Thanks to Pedro for helping me clarify those.

Winning criteria

There must be a continuous path so it is possible to go from the up staircase on level 1 down through other staircases to the floors below ending up on level 9. The winning entry is the greatest amount of room space occupied on each floor. Please output how many room squares are occupied. A corridor is not a room so don't count corridor spaces.

Output

Please output the 9 level maps into a single text file with a list of the room spaces for all levels after the last map.

Level 1 Map
*************************
...

Level 2 Map.

...

Level 9 Map

L1 Room squares = 1235
L2 Room Squares = 1456
..
L9 Room Squares = 1675

Total Squares in dungeon = 12453

Output

This should be a text file called maps.txt in the same folder as your executable with contents as described above.

The Results

This Challenge was possibly too difficult as there was only one entry from Pedro Graca, As he is the only entry congratulations to Pedro!

1. Pedro Graca C, Portugal

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Challenge 15 email address with the subject line Programming Challenge 15.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition. If it doesn't compile, it can't be run so is automatically disqualified

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is August 31 2008.

The top ten entries will be listed according to how many room squares in total with the highest on top. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

Have fun!

More Programming Challenges

• Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
• Link to Programming Challenge 2 - Count the Islands. (Finished)
• Link to Programming Challenge 3 - Manage Elevators. (Finished)
• Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
• Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
• Link to Programming Challenge 8 - Score Poker Hands - (Finished)
• Link to Programming Challenge 9 - Manage a Data structure - (Finished)
• Link to Programming Challenge 10 - Hide Text (Finished)
• Link to Programming Challenge 11 - Match Sets of Cards (Finished)
• Link to Programming Challenge 12 - Calculate Shortest Path - Completed)
• Link to Programming Challenge 13 - Play Battleships (Finished)
• Link to Programming Challenge 14 - Multiply Large Numbers(Finished)
• Link to Programming Challenge 16 - Solve 1,000 Sliding Puzzles (Deadline September 30)
• Link to Programming Challenge 17 - Implement the Life Cellular Automaton (Deadline October 31)