View unanswered posts | View active topics It is currently Sat Jul 22, 2017 1:43 am



Welcome
Welcome to XP-Waste!

You are currently viewing our boards as a guest, which gives you limited access to view most discussions and access our other features. By joining our free community, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content, and access many other special features. In addition, registered members also see less advertisements. Registration is fast, simple, and absolutely free, so please, join our community today!


Reply to topic  [ 7 posts ] 
 Map Research 
Author Message
DGS Admin
DGS Admin
User avatar

Joined: Mon Apr 18, 2011 6:31 pm
Posts: 402
Highscores: 2
RSN: Jettrider
Post Map Research
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):
Image

An image from RuneFest 2010, in a dungeoneering development info session:
Image

I'll comment on these later.

_________________
-----------Completionist @2496-----------
ImageImage


Fri Oct 28, 2011 8:00 pm
Profile
User avatar

Joined: Fri Apr 15, 2011 8:07 am
Posts: 46
RSN: Capt_Davy
Post Re: Map Research
http://youtu.be/WsCLcCTXuwI?t=1m9s

If you can rip it off of yt, download it, and play it back slower, you could gain some pictures from it (mostly around 1:10 or so in the vid).
I do not have the original file on my computer any more, and I can't download the yt vid (blocked my filters on uni net fml). Atm, I'm trying to obtain some more HQ images for you, but we'll see how that goes. [edit: ok no worries about that, i can easily gain large amounts of data. it looks like this happens every single time I open a door. Most of the time it happens to quickly to see, but frame-by-frame playback shows the map image on the left hand side appearing every time i open a door].

Just FYI about the map image on the left hand side of the screen, I also see this for the area I'm logging in to (ex, daemonheim, I'd see an image similar to the minimap image but more detailed and larger, and on the left hand of the screen).

Edit: obtained some more.
Spoiler:
sorry for the messy background, that's the graphical mess that happens in Open GL in dg (except on warped floors, wierdly). In order they appeared, frame-by-frame (note: the 2nd and 3rd image each lasted for 2-3 frames, while the first image only lasted for 1 frame).
Image
Image
Image
and if it's relevant, the map just after the door was opened:Image

I'm sorry if I've posted some irrelevant information, but it's 1 AM and my brain's just a mess and I'd rather you not miss out on whatever data I've gathered.

edit2: Gathered quite a lot more. I'll post it once I've sifted through it and taken pictures of the relevant frames. Are you interested in partial-room pictures, or do you prefer ones with multiple full rooms shown? Do you want images of the map layout (not the dg map) to compare to the left-hand mini-map?


Sat Oct 29, 2011 12:02 am
Profile
User avatar

Joined: Thu Jul 28, 2011 12:09 am
Posts: 23
Location: california
RSN: king omador
Post Re: Map Research
i would like to do research on this, the best way i can think of to do this is to do some solo large floors and screen shot the map every time i open a door, then see if i can take the pictures and put together into some sort of slide show so that you can visually see how the map is opening up all at once, doing it this way may allow us to figure out if there is some sort of notable equation to how the floor is opened by noting similarities between floors. in the mean time, i believe i have some screenshots of finished maps in case the actual layout could be useful

_________________
look up lessirkilion on youtube to see my skydiving vids
https://docs.google.com/spreadsheet/ccc ... BaEE#gid=6


Sat Oct 29, 2011 12:17 am
Profile

Joined: Mon Feb 25, 2013 4:22 pm
Posts: 1
RSN: [empty]
Post Re: Map Research
The Dungeoneering Development Info Session Picture...

map_generate (a,b,c,d) suggests fairly unsubstantial or random variables.

Square count:
1x dark green
31x medium green
4x light green
23x purple
5x blue

Dark green appears to be the base, blue appears to be nonexistant rooms.

Medium green would appear to be the critical path, but at 31 rooms, this is impossible. Same problem with the purple "bonus" squares. The 4 light green squares in the middle are strange, suggesting some sort of giant room. First thought would be a boss room, but it's 2x2 and not 1x1.

There are 15 corridors connecting rooms, with writing inside them, and 15 different squares containing some sort of writing about 1/4 down from the top of the square. I would guess this refers to key doors and keys.

There must be something going on with the green and purple, I'm not sure what it is. 31 Light Green doors plus the dark green base cannot be a coincidence.


Mon Feb 25, 2013 4:34 pm
Profile
DGS Reviewer
DGS Reviewer
User avatar

Joined: Wed Jul 27, 2011 10:29 pm
Posts: 948
Location: The Netherlands
RSN: Newbcake
Post Re: Map Research
The colors are probably exactly as you just described, I have little doubt.

This is DG in development, it isn't unlikely that they had bigger bosses in mind that required a larger room etc.

_________________

^ Click. ^


Tue Feb 26, 2013 10:01 pm
Profile
User avatar

Joined: Sat Feb 04, 2012 7:06 pm
Posts: 348
RSN: Caaizoj
Post Re: Map Research
Agree with Neal, crit path might also have been longer at this point in development.

_________________
Image


Wed Feb 27, 2013 4:17 am
Profile

Joined: Wed May 16, 2012 4:55 pm
Posts: 79
RSN: [empty]
Post Re: Map Research
Sizes:
Small: 10-16 rooms = avg 13
Medium: 23-32 rooms = avg 27.5
Large: 50-64 rooms = avg 57


Crit path:
Small: 6-8 rooms = avg 7
Medium: 10-14 rooms = avg 12
Large: 19-23 rooms = avg 21
Original large example: 33, counting 4 rooms as 1 boss and incl ht

Crit avg / Size avg:
Small: 54%
Med: 44%
Large: 37%
Original large ex: 56% (example is 59 rooms 33 crit - I don't know the range obviously.)

So, perhaps they intended crit/size to be same ratio regardless of size originally. Why change it? Maybe they intended people to gain xp through guide mode skipping bonus more and wanted to balance xp for bigger sizes compared to smaller. Or maybe they decided crit was too big with multiple people: with uneven skill levels the higher-leveled people would have a lot of trouble running around the bigger it is. Keep in mind the GGS didn't exist originally. (Think it came out around 5 months in.) This is assuming they had crit level requirements in mind at this point. They could've partially solved that by say, changing x-9 to x-20 for crit level requirements.
This speculation doesn't really matter.


Comparing the map to some of the info in this thread:
new-dungeoneering-discovery-t3585.html

"The critical path of a small dungeon has 2-3 key doors.
The critical path of a medium dungeon has 3-5 key doors.
The critical path of a large dungeon has 5-8 key doors."
Original large example has 10 crit key doors, which makes sense with a larger crit path.

Also means each size has about 33% key doors on the crit path..

_________________
Image


Thu Nov 14, 2013 1:44 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 7 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
suspicion-preferred