Dungeon Generation
Jul. 6th, 2010 07:22 pmOne of the most interesting aspects of the old "Roguelike" games are their dungeon building algorithms. Every time you descend into the depths of the dark cave or the gloomy catacombs, you're faced with a new, automatically generated setting. There are rooms of treasure, long corridors filled with traps, hidden rooms, and so forth.
Dungeon generation, I would hazard to say, is one of the most fascinating problems in computer science, not only because of how common it is in game development, but because of the sheer scope of the problem. It is, at its heart, a purely decision-based situation. Should this tile be a wall or a floor? Are all the rooms connected? No? How do I connect them? Where should I put the door? Where do I put the traps?
There are many different algorithms out there that focus on this problem. Some are rooted in cellular biology and artificial life that create some very cool looking cave-like structures with irregularly shaped rooms. Others produce honest-to-god mazes and labyrinths of winding corridors and few open spaces.
Today we are going to focus on a very simple dungeon generation program that will build the dungeon itself, but not place anything in it. Doors, traps, stairs, monsters, and treasures will not fall within the scope of this program. Even the dungeon itself will be rather simplistic: it will consist of square or rectangular rooms, and corridors.
( Dungeon generation )
Dungeon generation, I would hazard to say, is one of the most fascinating problems in computer science, not only because of how common it is in game development, but because of the sheer scope of the problem. It is, at its heart, a purely decision-based situation. Should this tile be a wall or a floor? Are all the rooms connected? No? How do I connect them? Where should I put the door? Where do I put the traps?
There are many different algorithms out there that focus on this problem. Some are rooted in cellular biology and artificial life that create some very cool looking cave-like structures with irregularly shaped rooms. Others produce honest-to-god mazes and labyrinths of winding corridors and few open spaces.
Today we are going to focus on a very simple dungeon generation program that will build the dungeon itself, but not place anything in it. Doors, traps, stairs, monsters, and treasures will not fall within the scope of this program. Even the dungeon itself will be rather simplistic: it will consist of square or rectangular rooms, and corridors.
( Dungeon generation )
