Author Topic: Dungeon Generation standard elements  (Read 14995 times)

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Dungeon Generation standard elements
« on: September 02, 2014, 07:41:09 AM »
Are there a set of things that all dungeon generation algorithms should support?

I'm thinking of the following so far:
  • Walls
  • Ground
  • Empty Space
  • Door
  • Liquid
  • Stair (or other level exits)
  • Vaults (or other special pre-defined rooms)

--I'm editing this as we go for the things I certainly want in. It's not meant to be exclusionary.
« Last Edit: September 03, 2014, 03:10:48 AM by Eben »

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Dungeon Generation standard elements
« Reply #1 on: September 02, 2014, 08:07:23 AM »
If you're thinking of something generic to put in a library, I think your list hits the main points, but you probably want to make some distinctions between types of walls, ground, and empty space. For example, you may want transparent walls, water or lava flows, and chasms. Each of these fall into one or more of your existing categories, but you may want to handle some of them differently from others.

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: Dungeon Generation standard elements
« Reply #2 on: September 02, 2014, 08:14:33 AM »
If you're thinking of something generic to put in a library, I think your list hits the main points, but you probably want to make some distinctions between types of walls, ground, and empty space. For example, you may want transparent walls, water or lava flows, and chasms. Each of these fall into one or more of your existing categories, but you may want to handle some of them differently from others.

Putting them in a library is indeed exactly what I'm thinking.

I'm not sure yet if having a really basic set of things and post-processing to more complex ones (like wall types) or starting with complex ones and post-processing to minimized types (if desired) would be better.

Currently I have generators ranging from ones that turn out simple booleans to ones that put in every real-life type of stone and gem, along with simulated ground faulting and metamorphism. I'd like to have a more unified interface for them (where possible), so I'm looking for help in deciding what needs to be in that interface.

One more for the list for sure:
  • Liquid

tuturto

  • Rogueliker
  • ***
  • Posts: 259
  • Karma: +0/-0
    • View Profile
    • pyherc
Re: Dungeon Generation standard elements
« Reply #3 on: September 02, 2014, 08:45:13 AM »
It would be nice, if there were a clear way of querying levels for locations of specific type. For example, finding out all the locations that are next to walls, so you can place bookshelves there. Or very middle spots inside of rooms for placing altars. Or locations that are next to doorways in cardinal direction, so I can put braziers there.
Everyone you will ever meet knows something you don't.
 - Bill Nye

CaptainKraft

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 60
  • Karma: +0/-0
    • View Profile
Re: Dungeon Generation standard elements
« Reply #4 on: September 02, 2014, 04:17:14 PM »
Would you consider a hallway a discrete element or just walls and floor?
Build a man a fire, and he'll be warm for a day.
Set a man on fire, and he'll be warm for the rest of his life.

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: Dungeon Generation standard elements
« Reply #5 on: September 02, 2014, 04:39:20 PM »
It would be nice, if there were a clear way of querying levels for locations of specific type. For example, finding out all the locations that are next to walls, so you can place bookshelves there. Or very middle spots inside of rooms for placing altars. Or locations that are next to doorways in cardinal direction, so I can put braziers there.

That is a good suggestion. If the generator was simple with post-processed complexity, then something like this would need to be implemented in any case, although you've suggested a couple detections I hadn't considered.

Would you consider a hallway a discrete element or just walls and floor?

Excellent question. In some of the generators they are and some they're not. This (and rooms) might be something best labeled by the actual generation process since if odd shapes are allowed it might be really hard to determine them post-process.

Paul Jeffries

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 257
  • Karma: +1/-0
    • View Profile
    • Vitruality.com
Re: Dungeon Generation standard elements
« Reply #6 on: September 02, 2014, 06:35:09 PM »
How about Up/Down Stairs (or some other more generic entry/exit tile)?

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: Dungeon Generation standard elements
« Reply #7 on: September 02, 2014, 07:14:16 PM »
How about Up/Down Stairs (or some other more generic entry/exit tile)?

Currently they're in the post-process, adding them to the generation proper would allow for stair-specific rooms or entryways without having to disrupt the generated map awkwardly. I'll add them to the list.

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 805
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Dungeon Generation standard elements
« Reply #8 on: September 02, 2014, 10:21:34 PM »
It would be nice, if there were a clear way of querying levels for locations of specific type.
My old game Squirm did what you're describing. The generator would dig one room/corridorsegment at a time, keeping track of where are the walls, doors, spaces next to walls/doors, and open spaces. I used it mostly to generate room templates that would put critters and furniture appropriately, but the list/graph of rooms, their locations and connections was also nice to have for stuff like exploration AI. Eg. a monster exploring to find the player would use visited/unvisited rooms as waypoints and just pathfind from door to door with A*. (Simple solutions fit stupid programmers like me ;))

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

quixotic

  • Newcomer
  • Posts: 8
  • Karma: +0/-0
    • View Profile
Re: Dungeon Generation standard elements
« Reply #9 on: September 03, 2014, 02:15:11 AM »
Vaults as well. Or other similar "premade rooms" as addressed with the hallway question.

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: Dungeon Generation standard elements
« Reply #10 on: September 03, 2014, 03:11:26 AM »
Vaults as well. Or other similar "premade rooms" as addressed with the hallway question.

Good one, I added it to the list.

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Dungeon Generation standard elements
« Reply #11 on: September 03, 2014, 06:46:32 PM »
I'm about to start hacking map generation code myself. 

I have several different map generators, and I want to make one now that can use a different generator to do different parts of the same map. 

The immediate task is, I have a "caverns" generator that uses cellular automata and makes fairly nice caverns.  I also have an "ant nest" generator that makes a characteristic radial pattern of egg chambers, food storage chambers, defense/connection areas, etc around a central chamber.  Now I want to make maps that are mostly caverns, but with an antnest at some location inside.

That would be easy enough to just code, but I want a more general answer.  The answer I come up with also needs to serve other purposes too, like rooms-and-corridors generation with optional vaults. 

So what I'm thinking now is I want to have the map generators take the area they're responsible for filling as a parameter.  And some dungeon generators call others to fill in some sub-areas. 

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Dungeon Generation standard elements
« Reply #12 on: September 03, 2014, 06:59:07 PM »
I will stick with (and highly recommend) a standard way to communicate maps from map generator to the rest of the game. 

The map generator returns an "intmap" - that is, a 2-dimensional array of integers, where each type of terrain is indicated by a different number.  (0 is open floor, 1 is wall, 2 is standard door, etc)

The game, in turn, is responsible for taking an intmap and doing whatever it does to convert it to  whatever map representation the game uses internally.

Decoupling map generation from map representation is useful, IMO, because the specifics of map representation are very likely to change during development (f'rexample I hacked in flags for directional lighting this week), and you don't want to have to revise every map generator every time that happens.  Just the appropriate changes to the conversion function and all the existing map generators are applicable. 


reaver

  • Rogueliker
  • ***
  • Posts: 207
  • Karma: +0/-0
    • View Profile
Re: Dungeon Generation standard elements
« Reply #13 on: September 03, 2014, 07:02:00 PM »
* Bottomless pits. Can't mine them away, they don't block your view, push someone there for instadeath.

Trystan

  • Rogueliker
  • ***
  • Posts: 164
  • Karma: +0/-0
    • View Profile
    • my blog
Re: Dungeon Generation standard elements
« Reply #14 on: September 04, 2014, 12:23:38 AM »
So what I'm thinking now is I want to have the map generators take the area they're responsible for filling as a parameter.  And some dungeon generators call others to fill in some sub-areas.

Composable map generators are really really cool. I've played around with them on some of my little projects and with a few simple generators, you can make some really wild and interesting things. Especially when you start randomly combining them. I'd be interested in anything you come up with involving this.