Temple of The Roguelike Forums
Development => Programming => Topic started by: Omnomnom on November 07, 2012, 11:37:31 PM
-
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.
(http://img248.imageshack.us/img248/6951/map1sc.png)
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.
-
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.
-
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.
-
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.
-
(http://i48.tinypic.com/23ldthd.png)
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.
-
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.
-
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.
-
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.
-
Map with loops
(http://imageshack.us/a/img69/7423/loops1.png)
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):
(http://imageshack.us/a/img843/8427/loops2.png)
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.
-
I'd play that dungeon.
-
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.
-
That is one epic dungeon! :o
-
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
-
Your generator somewhat inspired me to write this:
http://www.gruesomegames.com/blog/?p=236
-
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 (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:
(http://img19.imageshack.us/img19/9664/room9n.png)
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.
-
Your generator somewhat inspired me to write this:
http://www.gruesomegames.com/blog/?p=236
That's the holy grail to be able to make maps like that. I can't figure out how to make a computer think like that though. For example my generator doesn't have any thinking in it, it isn't procedural and it's very random. The room positioning for example is haphazzard (the rooms themselves are hand designed so don't count). A human would be able to think ahead and make the rooms align better, use symmetry and have a plan for the available space and what the rooms should be, both in terms of how they would play in combat, eg could be used defensively, but also what the room is (eg an armory). A human would probably think a medical room should be tucked away near the safe part of a fortress. A computer might put the medical room outside the fortress. Maybe something like a computer controlled dwarf fortress could learn to produce dungeons that serve a purpose.
-
That's the holy grail to be able to make maps like that. I can't figure out how to make a computer think like that though. For example my generator doesn't have any thinking in it, it isn't procedural and it's very random.
Room types can help, because you can detemine which room types are connected. I'm planning something like that for Kaduria, where I have an idea to construct houses (or any collection of rooms) from room units.
-
I'm going to assume we want to assign a type of room to the rooms in an already built map. (Optionally we could do this on a semi-built map, e.g. a BSP type before doing final room generation, to give us more scope in customising the room).
With the graph of room connectivity you could do something simple like the following:
1: Place room of type 'medical' at random location
2: Find list of all free rooms up to distance 3 connections away
3: Place (n < / << m) rooms of same type at random rooms in list
A more complex algorithm might be:
Or you could have a [symmetric] matrix of room simularities
medical housing armory
med 10 8 6
hous 8 10 2
arm 6 2 10
And you could have a matrix of the distance from each free room to each other free room.
You could then seed a couple of rooms of different types at random location then try to assign types to rooms that that optimise a combined error score of similarity and distance (have to think how exactly to do the optimisation...). A few optimisation passes might give an interestingly semi-optimised map.
Just some random unstructured thoughts for you.
-
That's a good idea to have a table of room type compatibility and then bias the room placement so that rooms with higher compatibility are placed nearer each other. I was thinking about something similar with room shapes to get different zones of architecture. Haven't been able to try it yet as all my rooms are pretty similar (gray walls and floors) although I might try compatibility for circle rooms vs square corner rooms.
I haven't really thought about room purpose much. I guess medical rooms would be more likely to have medical items and monsters, eg undead "surgeons" who want to cut you to pieces so they can put you back together again. Houses could typically have locked doors that need bashing down and can have small amounts of random loot (or sometimes an angry occupant) and armories are more obvious.
Another idea with choosing room purpose is to place guarded items at dead ends. Darren mentioned this example in his blog in point #8:
8. Hmm, there’s a dead-end room in the west. Any chance of a special item for here? Sure, a special potion. In a trapped chest. Guarded by… mages. Path to the dungeon entrance from here is to the north, so I’ll position them in a defensive formation near the door there, with a healer behind them.
Dead ends can be made the most secure rooms as they only have only one way in. Also they can be optional so the player could decide not to bother risking it and just continue to the stairs. I guess guardian rooms can't just be any old room, eg a special item in a house doesn't feel like it makes much sense. It would probably have to be things like a tomb or vault. In which case that has to be decided first. Then your compatibility table applies afterwards. If the guardian room is a tomb you wouldn't have something like an armory next door (I don't think) you'd probably have a kind of buffer area of more compatible rooms like lesser tombs or storage rooms or temples nearby and only after that do the rooms start getting "normal" again.
-
You could use Markov Chains. Design a hundred maps, break them down into relational placement data, and use that to seed the generator.
Or have a Markov generator that uses a small amount of random (ie non-Markov) data. Generate map, then decide whether or not to add it to the library. Repeat many, many times. You'd theoretically wind up with a dungeon generator that literally evolved to suit your tastes.
-
You could use Markov Chains. Design a hundred maps, break them down into relational placement data, and use that to seed the generator.
Or have a Markov generator that uses a small amount of random (ie non-Markov) data. Generate map, then decide whether or not to add it to the library. Repeat many, many times. You'd theoretically wind up with a dungeon generator that literally evolved to suit your tastes.
Umm... I'm confused. The more you repeat the more you will converge toward a stationary distribution- correct? Or are you describing a hidden markov chain?
I'm more of a fuzzy-logic kind of guy >_<.
-
When building card games I've worked on a system that generates levels based on...
Difficulty: Generally just depth. I've failed at this so far.
Environment: Just a tile set really, lava instead of water. Trees instead of walls. Affects 'wandering monster' list and some enviro hazards.
Architecture: Cave, Dungeon, Castle, etc...tends to control which traps and some hazards. So far environment and architecture are linked, hard to separate with cards.
Boss: Boss of that section of the game controls which minions your find.
Loot: You want the loot to be boss and minion specific, and the treasure chests to be enviro/architecture specific. Like the "Skeleton Key" only pops up in the dungeon architecture and only from a high level minion serving The Bone Lord...for example.
Achieving linkage like this is vastly different for card games, but I did it through various small decks.
1. Dungeon Decks: 18 rooms per environment. Ice level, fire level, dungeon, cave, castle. Rooms can have 1 to 4 entrances. Some doors are locked. Sometimes there's a big treasure chest or a 'wandering monster' that you only get one shot at before he wanders away. 1 boss room, enter at your own risk. Some 'hazard rooms' like pits, lava and such (agility challenges, roll to jump/dodge/duck etc...)
2. Boss Deck: 5 Different bosses so far. Draw this at the beginning of the level so everyone knows which boss they'll face. Find the boss room to fight him. Beat him, beat the level, and take his treasure (artifact!).
3. Artifacts (boss loot): About 20, tried to somehow link these to the bosses, but haven't figured it out yet. If you beat a boss you draw an artifact. Yay! Maybe I'll have small decks of 5 artifacts that go with each boss...hmmm....
4. Monster Decks: 5 different decks of about 20 monsters. Each linked to a boss thematically (Balrog boss has demons, The Necromancer has zombies, etc...) Enough for one monster per room and then some. Players draw a monster per room, this card stays on the room until you beat him. He has treasure with him depending on his strength. Beat him, win the treasures AND passage through the room. Fights are simple Roll and Add Bonuses, miss too badly and you die (Knocked out really, go back to the beginning and restart, lose a treasure. Or play hardcore...death is final).
5. Treasure Deck: 100 treasures. You basic armor, weapons, magic items, consumables, etc...
6. Character Races and Classes: Still working on how these will work...original characters were based on porn stars. Ron Jeremy the Dwarf, Belladona the Sorceress, Peter the Northman, Penny the Flame Witch...and Jeff Stryker the Pirate (he's a gay porn star...hilarious...pirate...chuckle)
Ramping up of difficulty is virtually nonexistent, but the challenge is in beating the other players.
I outline this here as food for thought on how to build dungeons, I think it's strong in linking minions to bosses and hazards to the environment. I'd like to be able to link bosses to the environments and vary the architectures, as well as linking treasure to the different minions...but there's only so much you can do with a tabletop game before it starts to get incredibly wonky.
-Jo
-
Perhaps I'm using the wrong term. I'm not suggesting a person compile a list of the probability of particular layout fragments, but a list of possible layout fragments. The (very) rough engine above would need some sort of tuning mechanic.
-
Perhaps I'm using the wrong term. I'm not suggesting a person compile a list of the probability of particular layout fragments, but a list of possible layout fragments. The (very) rough engine above would need some sort of tuning mechanic.
Ah-- Okay. So you'd basically have X amount of pre-made layouts and apply weighted interpolations between them to create new layouts? That's a similar technique for generating coherent isomorphic meshes in 3d space.
You can then add a highly desirable resultant layout to the list (though that would eventually result in convergence, which, in this case, you would want to avoid at all costs).
Thinking on it a bit more- I wonder what you could get mixing a purely random map, a map based on that sea-shell algorithm, and a purely room structured map... I think you'd apply weights at random points within the layouts and generate logical transitions between two different weights of different types- just need to ensure connectivity.