Temple of The Roguelike Forums
Development => Programming => Topic started by: Eben 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.
-
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.
-
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:
-
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.
-
Would you consider a hallway a discrete element or just walls and floor?
-
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.
-
How about Up/Down Stairs (or some other more generic entry/exit tile)?
-
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.
-
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
-
Vaults as well. Or other similar "premade rooms" as addressed with the hallway question.
-
Vaults as well. Or other similar "premade rooms" as addressed with the hallway question.
Good one, I added it to the list.
-
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.
-
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.
-
* Bottomless pits. Can't mine them away, they don't block your view, push someone there for instadeath.
-
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.
-
* Bottomless pits. Can't mine them away, they don't block your view, push someone there for instadeath.
Yes indeed! I've mentally added this to "empty space" on the list.
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.
Composability is my primary goal here. Clearly allowing for a "this is a central cavern", "this is a side tunnel", etc is important. I like the idea of the int map, but I'm not sure it's expressive enough. OTOH I don't want to go full OOP interface on the 2d array for the mapping since theoretically there'll be a lot of processing on them.
Leaning heavily towards the int[][] solution right now, probably with some predefined generator-specific constants indicating the common usage for the results.
-
Wow, can't wait to see the dungeon generation library in use! Will it have a front-end of some kind, like the Tiled editor, and what language is it gonna be coded in?
-
What are the languages this hypotetical library will be useable with?
Just C/C++ (judging from int[][]) or more?(i've made a fool out of myself)
About the list of tile types, I think it might be a better idea to leave such list mostly unspecified. If there will be multiple generators, most likely some of them will introduce totally new or adjust previously used tile types. Leaving the precise list of types to the concrete generator documentation should be more flexible. If there is a need for post-processing, such list may be converted to the one more convenient to the application by a simple lookup table (optionally grouping types specified too precisely for application to handle).
Also, depending on intended complexity of generation, it may be useful to allow querying tile 'properties' like water depth, glass opacity or portal ids (for entrance-exit pairing). Simpler applications may just stop on tile types (if applicable) while more sophisticated ones will take advantage of more detailed description.
-
What are the languages this hypotetical library will be useable with? Just C/C++ (judging from int[][]) or more?
Wow, can't wait to see the dungeon generation library in use! Will it have a front-end of some kind, like the Tiled editor, and what language is it gonna be coded in?
Nothing hypothetical about this library, it's going into my Java library that's been around for years: https://github.com/SquidPony/SquidLib (https://github.com/SquidPony/SquidLib)
I've considered the idea of having a front-end before, and I might still do it. I think it would be nice to have a hand-tunable dungeon generator, or at the very least good front end for seeing what different parameter tweaks do. In any case, it would output some sort of JSON for the built dungeon. While the front end would be in Java, it would just run as a desktop app. You could then use the JSON dungeon file wherever you wanted.
About the list of tile types, I think it might be a better idea to leave such list mostly unspecified. If there will be multiple generators, most likely some of them will introduce totally new or adjust previously used tile types. Leaving the precise list of types to the concrete generator module documentation should be more flexible. If there is a need for post-processing, such list may be converted to the one more convenient to the application by a simple lookup table (optionally grouping types, specified too precisely for application to handle).
Also, depending on intended complexity of generation, it may be useful to allow querying tile 'properties' like water depth, glass opacity or portal ids (for entrance-exit pairing). Simpler applications may just stop on tile types (if applicable) while more sophisticated ones will take advantage of more detailed description.
You're right about translating being a potential difficulty with too-strictly defined starting points. That's an area where a language like JavaScript would be useful for just shoving things in as you go and sorting it all out later. The way you stated the problem though makes me think of some new approaches I could take in handling it :)