Programming Challenge 15 Posted
Friday July 4, 2008
Yes this one is definitely a bit early; it doesn't start until August but I wanted to make sure there weren't any gotchas or things I've overlooked. If I've missed any crucial detail please let me know!
The Challenge is to write a program that generates a set of dungeons like you would use in role playing games like Dungeons & Dragons. 30 Years ago I used to run D&D games. Then nearly 20 years ago I actually wrote a dungeon generator as part of a large postal game (called Quest). Mine also had treasures, traps, monsters and non player characters but this challenge is much simpler. Just generate a nine level dungeon with interconnecting rooms and corridors.
- Link to Programming Challenge Fourteen Multiply long numbers together quickly
- Link to Programming Challenge Fifteen Generate a Dungeon
Does the path from level 1 to level 9 have to go through *every* room and corridor in the dungeons?
Does the connection between any two rooms have to be unique, in terms of rooms and corridors it goes through?
Is a solution with the staircases next to each other (*) and the remaining space filled with connected rooms (and 2 (small) corridors), as in the reduced example, acceptable?
**************************
*/\*…………………*
*..*…………………*
*..|…………………*
**-*…….room……….*
*……….space………*
*….with.2.corridors….*
*……………………*
**************************
(*) Of course the staircases would be “/\” on even levels and “\/” on odd levels
The route doesn’t have to go through every room just that you can reach every room (on a level) from any other. No cut off rooms!
Rooms can be reached by different routes from other routes.
Both staircases on a level can’t be in the same room or corridor. The wider they are separated (by # rooms) the better.
I’ve updated the Challenge doc. Thanks!
David
About C, C++ and C#
About.com is owned by the New York Times
I think maps optimized for floor occupancy might look a bit monotonous. Perhaps additional weight for different shapes and sizes of rooms, corridor branches, multi-door rooms, etc?
Do you have a test program that verifies a map. It seems with all the rules/criteria, there might be a few things that are vague or left to interpretation. For instance, the 1st commentor brings up a good point. Can each level be pretty much the same? Swap the staircases for odd levels but put them in different rooms. If we found a level that had a couple corridors and used the maximum possible squares for rooms and had a great distance between each stairway, then why not use that same design for each level?