Map generation woes

[Omnomnom]

Well woes is too harsh a word, it's fun but having some trouble. This is the kind of map my map generator is currently spitting out.



The red dot is the player. There's a few things to excuse here. Firstly the graphics are just for testing, I am not seriously thinking of solid-color tiles and a red dot for the player. There are also two bugs on the map where corridors wrongly overlap, just ignore those. The rooms are also repetitive I know, they are working off a handful of templates I made for testing. What I want to ask is about the general map layout, ie how rooms connect.

Something seems wrong about it. Maybe it's the graphics but are there too many rooms? Perhaps rooms are too small? I know there is a loop problem I am having a problem with generating loops. Is that a big deal? How important are loops in a roguelike in general?

I am also thinking about the game element of the map, such as adding things like locked doors or raised drawbridges. I know a major problem with those is if the stairs and key get spawned behind a locked door it can mean game over....also along similar lines stair placement. If the stairs are placed away from any loop and you immediately encounter a badass monster and have nowhere to run, that is gameover too. How can I avoid stuff like that? Do I just flood the map with loops? Can there be too many loops?

I have maintained a connection graph of the rooms as I suspect that might be useful, but on the otherhand this is also why I am having trouble with creating loops. The generator uses a strict method of joining rooms to guarantee no rogue connections are made. I suspect to guarantee loops though I will need to just drill through a wall now and again but that means my room connection graph might end up faulty...so it's like one of those vicious circles of chickens and eggs.

[WraithGlade]

I'm new here so maybe I don't know what I'm talking about, but:

I'm not sure exactly what you think is wrong with your map. You said to ignore the "wrongly overlapping" corridors. Are you talking about the walls that break connectivity?

Also, I don't know what your various tile types actually are, so my interpretation is just based on assumptions. It could be that light blue areas in your system are closed walls and dark areas are open floors. I doubt it, but since we don't know your system we can't technically know what each color means. (I'm guessing light blue is open though)

As for loops and gameplay, it's really an arbitrary design decision. It would probably be more helpful if you stated what kind of features you want more specifically.

Do you want a way to generate more loops? Do you want a way to fix the connectivity? I really just don't quite understand what is being asked.

In any case though, the map looks pretty cool to me, connectivity and other visual artifacts aside. It's got a pretty interesting structure to it.

I wouldn't say that there's "too many rooms". In fact, what that even means really depends totally on what kind of game you want to design.

[guest509]

  I dunno man, looks good. You tried with with less rooms? Is that easy for you to do, fix a variable and get more or less rooms?

  As far as loops go, it's just not loops for running. If a player runs into a lot of dead ends and has to backtrack too much that can start to be a chore. I can see quite a few dead ends. Looks good anyway though, i'd play that level.

  I am thinking that the golden areas are lava? The corridors over lava are actually bridges, right, that's why they don't have any walls?

  I dunno what the guy above is talking about with blue. I see grey, greyer, green/grey and golden.

  I wish I had more answers for you. I think you need to playtest it and see how to flows.

[Krice]

Do I just flood the map with loops? Can there be too many loops?

In "cavern-style" level if there are rooms/corridors nearby it's possibly better just loop them, because that's what would happen in a cave. It's not practical to dig areas that are close to each another but not connected. Some dead ends are fine, no need to connect everything.

[guest509]

Okay, so here's what it looks like if you attach the adjacent rooms.

You lose most of your dead ends and connect formerly unreachable areas. Note some areas require a room or 2 to find the dead end, which could be boring because you have to back track.

Legend:
  Red Line = Adjacent room connections.
  Red X = Dead ends eliminated.
  Green X = Existing dead ends.
  Green Dots = Have to backtrack, long walk into a dead end.
  Green Circle = Areas you can reach now due to adjacent room connections.

[Darren Grey]

Loops are very important for the gameplay because without them you end up spending half your time backtracking through empty space, which isn't fun.  I think you should maybe start your map with a loop and build off it.

Another way to force loops is with floodfill.  Do a floodfill heightmap from each set of stairs, with distance from the stairs being a high number.  Then try to connect up local maxima.

The generator itself seems fine.  A very important test is to try actually exploring it with FOV.  Seeing this sort of overview doesn't really tell you anything about how exploration feels on the map.

For key/door generation use floodfill again to check the key is generated on the accessible side of the stairs.

You may want to try using less rooms but larger rooms.  Your 3x3 rooms seem too common - maybe force a minimum of 4x4, or make 3x3 far less common.

[Omnomnom]

Thanks for the map edit Jo that's clarified the difference between dead ends and loops to me and how to eliminate many of the dead ends.

I hadn't thought about loops being important to reduce backtracking. Maybe it was you Darren who mentioned the importance of loops in one of the roguelike radio episodes or perhaps at the irdc. Someone at least planted the importance of loops in my mind for me to get worried about it, but along the way I forgot the reason why. I was only thinking about loops being useful for running from monsters (which is dumb really as you are just as likely to run into a monster coming the other way). Avoiding backtracking is a better reason for loops.

I'll try bigger rooms. The reason why the 3x3 rooms dominate so much is that as the map fills up a lot of the remaining spaces can only fit small rooms, so that's what happens. I will trying putting some sort of cap on them.

[Darren Grey]

Include the option for the generator to make single square rooms - these will act as connectors and branch makers that spread the space out a bit. Just make sure not to have a dead end on one.

[Omnomnom]

Map with loops


The map is generated without loops first and then nearby rooms are connected like in Jo's image. To prevent short loops the generator doesn't connect rooms if there is already a short enough path between them. Backtracking is reduced but it's still there. I guess it can't be totally eradicated.

That big circular flower-like room isn't a generated loop, it's a room template that has a hole in the middle where other rooms usually end up built. I tried out a single square room template darren and it works great, except I have had to disable it for now until I've added the trimming of dead ends.

Crossing the bridge over lava in FOV (clearly inspired by brogue):


40% of the map is lava. It's meant to be an atmospheric feature of the map, but most of it is wasted as from the above image you can see only a small part of the lava is ever seen. Most of the lava is wasted space. I will try adding windows to walls overlooking the lava.

[guest509]

  I'd play that dungeon.

[wire_hall_medic]

I don't know about "wasted space," but it makes the two rooms across the bridge look important; crossing the bridge is a tension-building moment.  If your generator makes these types of map with any regularity, you might capitalize on that.  Make them more dangerous and more swag-filled.

[XLambda]

That is one epic dungeon! 

[flend]

Omnomnom,

Could you share some details on your map generator algorithm? Those areas look fantastic.

I'm interested to hear that you are keeping a connection graph of rooms. I'm also planning to do this in my next project. For one map generator I was going to do a BSP (giving me a tree), then adding connections between adjacent rooms on the map, as suggested above, and also making sure these extra connections were added to the tree, giving me a cyclic graph. I think having a correct connectivity graph could be useful for placing monsters etc. - e.g. place a difficult monster close to a loop to give the player some wiggle-room.

-flend

[Darren Grey]

Your generator somewhat inspired me to write this:

http://www.gruesomegames.com/blog/?p=236

[Omnomnom]

Omnomnom,

Could you share some details on your map generator algorithm?

the natural environment is created first - rock and lava (perlin noise). Then the output of that gets fed into the room generator. The room generator is very similar to this:
http://roguebasin.roguelikedevelopment.org/index.php?title=Dungeon-Building_Algorithm

The room are picked from a fixed set of handmade templates. It would be better if rooms were generated procedurally rather than from a small list of templates, but I have no idea how to do that. Here is an example 7x7 template for a roundish room. Each template is a bitmap file, I decided to use that so I could make them with paint rather than needing to make some kind of template editor. Each pixel of the template is a tile:


The orange pixels are walls but also indicate the best places to put entrances. The generator gives them priority when creating entrances. The white pixels are empty. When placing the template over the map empty areas are not hit tested against existing structures or lava which means even though the templates are always square or cuboid the circular templates are really treated at circular, but there's just overhead of the unused empty tiles.

Everything on the map is from templates linking together at entrance positions. Even the corridors and bridges are templates (although they are dynamically created because they have varying lengths).

One thing I am doing differently from the above link is that the generator doesn't modify the map when a template is placed. Instead the template is placed "over" the map in its own layer. Basically each template has it's own X and Y position on the map and coupled with it's width and height (7x7 in the above example) it's possible to query whether the template has a tile at certain map coordinate and ask what that tile is. This wasn't intentional it just happened because i had to mess about with loading them from a bitmap so they had their own grid anyway and then realized it was easier to just pretend they were hovering over the map rather than building them directly into it and throwing them away. It turns out it makes some things much easier though. It makes it simple to move or remove templates after they are placed without having to revert tiles on the map.

It also separates the building process from the design process.

Also because each template represents a room and has a list of live entrances, they can be used as a connection graph. If a template is at position 20,30 on the map and has an in-use entrance at local coordinates (3,3) then you can find out where that leads by finding which template has an in-use entrance on map tile 23,33. It's messy as a connection graph but it does work (eventually).

Additionally with layers it should be possible to more easily copy-and-paste parts of the map a lot easier. Eg copy 3 connected templates and paste them somewhere else. Whereas doing that with a built map is a lot harder because you have to cut around all the other stuff.

the template placement process:

1. Pick a template at random from the handmade templates. Place the template at a random place over the map. This is the initial room. If the placement is invalid then retry until a valid placement is found. Templates can only overlap each other in some ways (eg share walls and entrances). Templates also can't overlap map tiles that contain lava (although I allow exterior walls to overlap with lava to encourage rooms to fit perch at the edge of lava)

2. Add all possible entrance tiles of the placed template to a global list of candidate entrances. Assign each one a priority. If the template has ideal entrance positions (marked in orange on the template above) give those a higher priority.

3. Choose an entrance candidate X from the global list. Higher priority entrances are picked first. This chosen entrance X will be used to expand a new room off of.

4. Create another template. This template is the new room that will be positioned so it joins to the entrance X of the existing room.

5. Choose a random entrance Y from the new template.

6. Join X to Y by positioning/rotating the new template over the map so that its entrance Y lines up with the entrance X of the existing template. Two options are used (50/50): Either a) join them directly (they will share walls this way) or b) place the new room some distance away and connect X and Y with a corridor.

7. Validate the new template placement (and the corridor if one was placed). If either do not validate (eg they overlap an existing template invalidly or overlap lava) then "give up". Remove the new template (and the corridor if one was placed) and go back to step 3. Before going back to step 3 reduce the priority of entrance X. Doing this suppresses entrances that repeatedly fail to work (perhaps there is insufficient space available) and other entrances are given a chance instead.

8. If the new template was successfully placed then set entrance tile X and Y priorities to zero. They they can't be used again. Go to step 3 to continue building.

For bridges everytime a template is placed a check is made to see if any potential entrances border lava on the map. If any do then a line is traced from that entrance across the lava to the other side. A bridge can only be created between two entrances. So first a room has to be created on the otherside of the lava. If one can't be created then the bridge project is abandoned.

The above process leads to a map without loops. Loops are added at the end as mentioned earlier in the thread.