Imbroglio (Dungeon Generation)

[The Great Hippo]

Hello!

I've been plugging away at this for a little while, largely because I find the inherent problem (dungeon generation) to be a very intriguing one. So, after about two months' of work, I've come up with an algorithm which produces the following (map legend will be beneath the image!):


White -- Walls, obviously!
Light Grey -- Caverns! (Produced via cellular automata)
Dark Grey -- Chasms (also produced via cellular automata)! With light grey 'pathways' connecting their edges.
Any Other Color -- A particular 'Dungeon Zone' (I haven't gotten around to distinguishing dungeon zones yet).

The thing is, after doing nothing but dungeon generation for two months, I have realized two things: I am sick and tired of dungeon generation (but willing to work on it a bit more later down the road!), and I also have absolutely no idea if the maps I'm producing will be suitable for roguelikes in general.

I really love roguelikes--I'm trying to build my own (it's my first stab at programming!)--and I figure that now is a good of a time as any to start asking for advice and feedback and trying to acquire the collective wisdom of others who *have* built roguelikes, and *do* know quite a little something about the problems I'm trying to tackle.

So, some of the questions I wanted to ask here about the above map:

* Is this too big for a roguelike? It's 200x200; I can shrink or expand it to any arbitrary size (though obviously it starts looking a little weird when you get as small as 20x20!). I'm trying to find other roguelikes to compare my map size to (such as Incursion) but I'm finding it hard to get any hard data on what the standard map-size tends to be.
* Are the 'double walls' something you usually don't see in roguelikes? I'm worried they're a bit aesthetically off-putting--part of the problem is that because of the way my zoning/structure/room procedures work, ensuring no double walls is actually a bit tricky (but not impossible!). It is way easier to just allow for them in an orderly way.
* One of the ideas I had as far as dungeon generation goes: Why not put the stairs leading up/down in the same 'zone' (area)? Have them always occur in the same area--because really, I see no reason to make the player search around for a set of stairs to proceed! This has the benefit of making stairs easy to code, but also gives the player an interesting initial choice: Go down a level for greater risks/rewards? Or wait until they've finished exploring this level? -- is this a good idea? Are there any reasons why it might be a bad idea?

Some of the things I'd like to put in this algorithm after I take a little break (I'm going to work on monster AI for a while, I think--meanwhile, I just want to talk about dungeon generation without actually *doing* dungeon generation):
* More distinguished dungeon zones--I'd like to make some of them have a very structured 'built-for-a-purpose' look, others to appear quite chaotic and organic, and perhaps even a rare labyrinth or two.
* 'Massive Room' zones--in cases where a zone ends up only being one region, I'd like to turn the zone into a single room rather than multiple rooms--just a really big one!
* Chasms, lakes, magma, and other 'obstacle' structures within Caverns themselves--the caverns I'm building look extraordinarily boring (to me! But then again I've been staring at them for over two months). I'd like to put in interesting features that don't block access to all points.
* Puzzle trees! Brogue is one of my favorite roguelikes ever, and one of the things I'm enamored of about it is the puzzle system--I'd like to do something similar (and thanks to the dungeon generation algorithm, I already have the basic architecture necessary for such a system in place!). Mostly, I'm thinking of doors that lead to 'dead end' zones that need a special key (found in another zone), or obstacles that require some item that must be found in the rest of the zone.
* Also, I'm welcome (and very interested) in suggestions about ways to make the shape of these zones more interesting! Or different types of zones for me to define!

 

[Krice]

I see no reason to make the player search around for a set of stairs to proceed!

It's a good idea I think, when you have to travel between levels. However for some level types it might be a bad idea, in a labyrinth for example. It's not cool if you don't have to go through the labyrinth.

This map looks like it has roguelikeis dungeonitis which means just lots of rooms and stuff. My idea for generating levels is to approach it from practical point of view: what the level would be like in reality, what happens in there, why it has those rooms etc. That way it makes a lot more sense.

[The Great Hippo]

It's a good idea I think, when you have to travel between levels. However for some level types it might be a bad idea, in a labyrinth for example. It's not cool if you don't have to go through the labyrinth.

True enough! One of my ideas, though, is that exploration/curiosity should be the primary driving factor behind the player's decisions--put rewards at every dead end (by rewards, I just mean 'interesting things') and encourage the player to *want* to explore the entire dungeon (rather than requiring exploration to proceed). I'm hoping (perhaps quite incorrectly!) that a desire to explore will overcome a desire to just get to the end.

This map looks like it has roguelikeis dungeonitis which means just lots of rooms and stuff. My idea for generating levels is to approach it from practical point of view: what the level would be like in reality, what happens in there, why it has those rooms etc. That way it makes a lot more sense.

Very fair, and I'm worried about that, and--to be honest--I'm not very satisfied with the above map (I think part of me posting it here was just an attempt to get some validation--largely in the direction you're taking it ('your map looks *way* too random').

I *really* want dungeon areas that look structured for an explicit purpose--IE, to build things from the 'top down'. The problem is that doing this while guaranteeing an interesting 'random' look is quite tricky. Now that I've guaranteed connectivity between all the zones, though, I'm *hoping* I can make each dungeon zone look far more specific and less random.

Part of the problem is that I have to *think* of explicit purposes for dungeon zones before I can structure them to that purpose. 'Laboratory', or 'Library', or 'Barracks'--but I want to stay vague, because when I'm finished, I want to make this available to anyone else who wants to use it (assuming it turns out to be good enough to use!).

EDIT: Also, I just realized--this is the wrong subforum to post this in, isn't it? If that's the case, I beg pardon, and would request that this be moved to the 'Development' subforum.

[The Great Hippo]

Also (pardon the double post! On my way off to work, and have little else to do but tweak my code before I'm out the door), taking to heart what you said about the 'dungeonitis' thing, I reduced the starting size and got this:

--which still has problems, but I find myself liking it a lot more (and it feels more like something I could work with and figure out some ways to make it less 'chaotic'--find a purpose for every room in there, etc).

Caverns and chasms become much more of a rarity (they occur only in cases where a zone has three or more connections to other zones), but I think that's fine, as I expected them to be rare (and frankly, caverns are probably kind of boring to explore anyway).

[Joonas]

As a map image the bigger one might look better but in actual play the smaller one is probably better. The bigger one might be tedious to navigate. Probably just more empty areas whereas the smaller one can be packed more tightly with interesting content.

Add passages or doorways between the various colored zones to minimize backtracking when navigating through the map.

You could spice it up more by adding vaults or specially shaped rooms. Rotate and mirror them for more variation. I made a simple drawing tool to draw special rooms but many roguelikes use just plain text to describe these.

Example, 96x96 map:



I'd say don't focus too long on one area (whether it's dungeon generation, line of sight or whatever) of the game or you might get burned out.

[The Great Hippo]

I appreciate the advice (and the example map)! Both gave me something to think about; the example map in particular.

[IBOL]

i personally love the output of your algorithms. i actually bothered to sign in to say so.
anyway, for a roguelike , i am personally moving toward "smaller is better" as far as level design. i used to do 60x60 (3600 tiles) , but am now working in 40x40 (or 45x45) can't decide.

basically, as they've said above, less space that is made interesting is better than more space that is tedious. but the output maps look wonderful.

i especailly like how the caverns/tunnels/etc. are mixed in with zones of rooms and corridors.
that is a stroke of brilliance.

about the stairs, do it however you want. but don't worry about the coding.
stairs are stairs no matter where you put them, and your program will know that.

[The Great Hippo]

Thanks! I really appreciate you saying so!

It was a hard trick to pull off while simultaneously keeping everything connected without resorting to 'try-to-connect-everything' loops--it works by defining a big 2D block, splitting the block (and each of the resulting blocks) in two a number of times (generating a BSP tree), building an adjacency map out of the resulting blocks, using it to allow 'zones' to spread a random number of steps and claim each block as they spread (only along edges that are 'perfect' -- ie, one side is *completely* adjacent -- or 'mutually perfect' -- ie, both sides are *completely* adjacent), building a 'connected zone map' out of the zones (figure out which zones are connected to which!), then defining some of the resulting irregularly shaped zones as 'caverns' and just letting the cellular automata algorithm go nuts inside of their space (followed by a few moore neighbor searches on each block or 'region' in the cavern zone is 'symmetrical'--IE, all the points in the block can be reached by any other point in the block). I'm really fond of the resulting look of the caverns--even if they're a bit big!

That being said, I've now got a random map generator that produces a completely connected map each and every time--it includes rooms, caverns, and chasms. I want to do a lot more work on making those things more structured, compact, and interesting--but I think I'm going to take Joonas' advice as far as moving on goes. Because I *am* worried about burning myself out on the dungeon generation stuff, and I suspect if I come back to it later, I'll have a lot more interesting ideas.

I'm going to work on basic monster AI next, I think. Either that, or my lighting system. One of the things I want to do is have a really, really, *really* cheap sort of 'specularity'--something really simple where light bounces off of walls once. I've managed to get a basic version working:


...but there are a few 'interesting' glitches (like walls illuminating space behind them--since I treat lit walls like a new light-source). Interestingly, the 'double-wall' phenomenon fixes that problem, but I think I want to have a more robust solution that doesn't rely on what was initially a glitch anyway. But I'm a little worried my obsession with lighting systems is distracting me from more important tasks, like making sure monsters attack the player instead of each other (right now, they just move about randomly!)

(I also need to work on cleaning up the GUI--it all currently works, but the GUI event system is pretty much piped directly into the game's event system--in other words, GUI events like 'Click' and 'Drag' and 'CloseWindow' are treated alongside things like 'EntityTakeTurn' or 'EntityMove'--and I think that's going to cause me some serious headaches later if I don't fix it now).

[Valmond]

Nice work!

Just by curiosity, why "Imbroglio"?

[The Great Hippo]

Thanks--and because it's one of my favorite words.

[Valmond]

Thanks--and because it's one of my favorite words.

One of my favorites too ^^

[The Great Hippo]

Oh, hey! I beg pardon; I actually did a couple of searches way back to make sure no one else was using this name (but I didn't search particularly hard!). I don't think 'Imbroglio' will be the final name, though--it's mostly just a placeholder. That, and I sincerely doubt much will ever come from my code--I'm doing it because I really enjoy the challenges.

I'm enjoying reading through your blog, though, and some of your posts are giving me ideas for solving various problems I'm going to encounter later down the road!

EDIT: It also reminds me that one of the things I wanted to investigate was the possibility of building the roguelike in HTML 5/Java rather than Python--because I deeply value portability; that being said, I really want a turn-based game, which means I really (probably) don't want a multiplayer game (since turn-based roguelikes are a horrible fit for multiplayer--for a variety of reasons), so HTML 5 might not be the best choice.

[Valmond]

Hey no problem if you want to use 'Imbroglio' in your game name, I just thought that it was a funny coincident
Nice to hear that you liked the blog, even if the development is a bit down at the moment (both game and blog), I got too many other things to do (changing work and maybe country) so I'm making a smaller game, a Windows Rogue like, working name "Seven Rogues", hope you don't especially fancy the word "seven" eh

BTW, you can use HTML5 for singleplayer games too, I actually started out with it to check if it works well with tablets (and it does) and I guess it works well on Linux/Mac too (I'm on Windows).

[The Great Hippo]

Thanks--and I might end up going with HTML 5 in the long run anyway (like I said, I deeply value portability); if it's well-suited for a roguelike, and it can handle classes in a similar way to Python (one of the reasons I love Python is because of just how well it can handle classes!), I might end up porting my code over to it.

(I actually don't have a tremendous amount of code, so it might not be that hard, depending! I'd have to learn HTML 5, of course, but I'm always willing to learn something new).

[Valmond]

If you need classes (and strong typing) maybe Haxe would be something for you, it compiles to javascript (which is a horror coming to classes but is also what is used in HTML5).
Have never used it though...