Most of you here have probably read Tui's mapreading guide
and how mapreading helps dungeons go faster. While that's a great start, knowing map tendencies doesn't explain why
they happen, and they don't help predict early dead ends. Players who have done a lot of dungeoneering (ie, long past 120) can currently predict the map by intuition better than by pure mapreading. This thread is for further map research in an attempt to quantify that intuition.
Right now, this thread is just a rough sketch. Unlike a lot of the other research in this forum, we can't simply collect a lot of data points, plug them into a formula, and reach a conclusion. The questions we ask and the methods we use to answer those questions are constantly changing.
It is my humble opinion that these inner dungeoneering mechanics are the last thing to master. Everything else in the dungeoneering metagame has been explored and perfected already, even if the results have yet to be fully written up (examples: binds, bosses, keying/carrying strategies, optimizing puzzles). Mastering these things is a simple matter of experience and increasing your APM. Map and dungeon loading mechanics are the "final frontier."
Some of the questions we have are (in rough order of importance, and note that these may change):
1. How can current map-reading theory be refined to cover the intuition that experienced players have? How can we predict early dead ends with any accuracy?
2. What makes a dungeon fast, map-wise? What makes it slow? Can we attach numbers to these? Can we create an accurate formula that assigns a numeric score to a layout?
3. Other than layout-wise, is there a limit on active paths, and is the dungeon flow more rigidly controlled on 5:1s, 1:1s, etc? (we can check this by randomly-generated 8x8 mazes)
4. How are the layouts and room shapes stored internally? When are they loaded (and what does that tell us about door lag)?
I've been working on this just as one project, having passed on the google docs for a lot of the other guides to more active floorgazeroverminds. However, this project is really complex, multi-faceted, and requires some technical and theoretical skills I'm not sure I'm capable of (w00ps sentence ending with preposition). At the very least, it'll be good to have a few other people look over my work.
So, here's what progress I've made so far:1. How can we extend map-reading theory to include intuitive map-reading?
This question mainly involves looking at lots of map pictures. Crit path pictures are especially helpful, but unfortunately there were less than 20 usable pictures from the crit path project. Looking at layouts helps you mapread better, but there are no hard rules for when paths dead end early because you can't always tell what's crit and what's not and whether or not there are keys left over that force another room to spawn.
A few players have claimed the ability to tell when paths will dead end early in certain situations. These claims may or may not be credible, or may simply be good mapreading. Note that there are some general situations where you have a pot door and it conflicts in a small area with a path that has to be boss where you can confirm when the bonus path will dead end, but this isn't very useful.
This is the hardest question to answer and will have to be discussed back and forth with many mid-map pictures and situations. It would also really help to have some of the players who claim to predict dead ends with complete accuracy come forward and talk about it.2. What makes a dungeon fast, map-wise? What makes it slow? Can we attach numbers to these? Can we create an accurate formula that assigns a numeric score to a layout?
I've made a bit more progress on this question than on #1. The general idea people seem to have is that 1ways are the slowest and that maps should "fork more," but these are both partial truths. Let me explain my theory of what makes a layout better or worse.
The biggest things that slow you down in a dungeon are GDs and puzzles. Everything else - skill doors, opening key doors, grabbing keys from dead ends - are trivially fast. I define a "required room" to be one that you need to solve or clear in some way to access
every other room in the dungeon. Not all required rooms are GDs or puzzles - some may have all spree doors - but there is a strong correlation between fewer required rooms and faster times. To get an intuition for this, think about what happens when you find a dead end. You don't have to clear it, you don't have to solve it; at worst, you have to grab a key. In any dungeon with N rooms, DE of which are dead ends, the number of required rooms is N-DE-2 (to account for base/boss). I have a spreadsheet of floors going, and the percent of rooms required ranges from 59-71%, which is incredibly when you think about it; significantly more than a third of the rooms in the dungeon don't have to be cleared. Required rooms are a function of a map's total number of rooms and dead ends, so it follows that full maps tend to have a lot more required rooms than short 50-56 room maps.
The other thing that makes a map fast is how quickly you reach these dead ends. Having a lot of dead ends isn't good at all if you have to run a path to get to each of them. Having multiple dead ends off fewer forks takes up a LOT of map space, fast. Therefore, I've defined a forking coefficient as the number of forks divided by the number of dead ends; a lower forking coefficient is ideal.
With all this in mind, I've attempted to create a formula that rates a map purely based on this layout. The formula is currently 1000/((10*FC)+Req)). The 1000 is just to scale maps to a score in the 20-25ish range. FC is the forking coefficient, and 10 is the amount by which it's rated (and is the most interesting part of the formula to figure out. Right now, 10 is just a pretty arbitrary guestimate; having a low forking coefficient is no good if you have barely any forks/dead ends compared to the total number of rooms). Req is the number of required rooms. This formula is fairly accurate for rating a map, but I'd like to refine it.
More than anything with this step, I need to understand the relationship between forks and dead ends. What does it mean to have more forks with less dead ends? How does this look on a map? And how does this affect map speed?3. Other than layout-wise, is there a limit on active paths, and is the dungeon flow more rigidly controlled on 5:1s, etc? (we can check this by randomly-generated 8x8 mazes)
This is an interesting question that may help pathing theory. An active path is any path that can be immediately opened. It may be crit or bonus. Pot doors count as active paths; a path is inactive when it is blocked by a key door. If we can understand how many active paths there can be at any one time (or, if there is a very large limit, how the lengths of those paths are involved), it will help know how and what to path and how to prioritize gates.
Map flow is something we don't get from layout alone. I've noticed that larges designed for 1 person have far
more key doors than 5:5s. Key doors limit map flow, so this is an interesting way to test this question out.4. How are the layouts and room shapes stored internally? When are they loaded (and what does that tell us about door lag)?
Let me present you with two pictures for now:
A current glitch on macs not updated with the latest Java (very hard to get pictures of, only lasts a frame, so need help from someone who can look at videos one frame at a time):
An image from RuneFest 2010, in a dungeoneering development info session:
I'll comment on these later.