Map generation woes

[Omnomnom]

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.

[Krice]

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.

[flend]

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.

[Omnomnom]

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.

[wire_hall_medic]

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.

[requerent]

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 >_<.

[guest509]

  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

[wire_hall_medic]

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.

[requerent]

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.