UESP Forums

Discuss the uesp.net site and Elder Scrolls topics.
* FAQ    * Search
* Register    * Login
It is currently Thu Jan 17, 2019 3:47 pm

Loading

All times are UTC

Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: An algorithm for exhaustively, efficiently dungeon crawling
PostPosted: Sun Nov 17, 2013 2:06 pm 
Offline
Associate
Associate

Joined: Mon Nov 11, 2013 9:27 pm
Posts: 19
ES Games: all 5 elder scrolls games
Platform: PC
Other Profiles: alodar
UESPoints: 0
A major challenge in Daggerfall is finding something in a dungeon. It seems to me the following procedure should work in a dungeon with only 3-way junctions. (I am uncertain about the obvious extension to dungeons with 4-way junctions.) I have not yet tried it, so this is a proposal and I would be very interested in people's reactions. The object of the procedure is to guarantee that every node (junction) and path is visited; it is efficient if every path is traversed a minimum number of times.

Assume that the "Create Item" spell is available and is used to create two kinds of distinctive object, call them "A" and "B." These will be used to label paths (not just nodes) placing them inside but near the terminus of path segments. It is assumed that the resulting "treasure piles" remain for the entire time one is in the dungeon and can be verified when they are re-encountered. Basically, "A" means "left-path not taken" and "B" means "dont take this path."

The procedure follows:

Mark the left branch at the dungeon-start A, follow a right-hand path marking each left branch at a junction A
(The mark is placed in the branch, not just at the junction)
Eventually the path comes to a dead-end or is re-encountered, coming back in on a path segment marked A(*)
At a dead-end, reverse direction and mark the path you come in on B at the next junction
REPEAT
The next junction encountered has
1) an A on the branch you came in on,
or 2) an A on the branch to your right that you will go out on (*)
or 3) a B (on one of the other branches)
or 4) no marked branch
If 1, replace A with B and reverse direction (right wall is now what was formerly the left wall)
if 2, put a B mark on the path you came out of, remove the A mark on the path you follow out of the node
if 3 , put a B mark on the path you just came in on and continue following the right wall
If 4, mark the left path A and continue following the right wall
END REPEAT
(*) If the A is to your left, then you must have previously rejoined the "right hand path" which means that you missed
a previous junction where you FIRST re-encounted that path; in other words, you made a mistake at a previous
junction.


Top
 Profile  
 
 Post subject: Re: An algorithm for exhaustively, efficiently dungeon crawl
PostPosted: Sun Nov 17, 2013 9:37 pm 
Offline
Apprentice
Apprentice

Joined: Sun Sep 15, 2013 4:38 pm
Posts: 141
UESPoints: 1
Interesting idea! :) I've always resorted to just wandering around until I find something (it also helps to have the teleport spell, and/or to save your game at the entrance, so that you can backtrack more or less easily if you get stuck). The quasi-advantage of random dungeons in Daggerfall is that they are made of typical blocks that soon get quite familiar, and it only becomes problematic if a dungeon happens to have two or more adjacent blocks that have the same architecture. Also, each dungeon has only a limited number of locations where quest items may be placed, so with some experience you can just get straight to the quest item location in each of the familiar segments.

Oh yes, another complication in this respect are those "teleporters" that are disguised as brick walls.

_________________
Daggerfall graphics fix


Top
 Profile  
 
 Post subject: Re: An algorithm for exhaustively, efficiently dungeon crawl
PostPosted: Mon Nov 18, 2013 1:44 pm 
Offline
Associate
Associate

Joined: Mon Nov 11, 2013 9:27 pm
Posts: 19
ES Games: all 5 elder scrolls games
Platform: PC
Other Profiles: alodar
UESPoints: 0
I've been trying the algorthm out in Vladimyth (which is a brute!) and some problems and possible fixes have emerged. The obvious fix for 4 way junctions seems to work : mark all untaken branches A, and option 2 (on returning to the junction) is modified in that the remaining available A-branches are not necessarily on your right. Not a problem!

Descending a shaft may lead to a room with multiple doors and no obvious "right" path. Mark them all A; pick one at random, remove the mark and proceed as usual. You may encounter switches that may ultimately control doors in a different part of the dungeon. You need a third mark, call it C, that says "this is a dead end branch that leads to a switch." Finally, a portion of the maze may only be reached by levitating up in a large area where the existence of something above is not obvious. I guess you just have to go up and check whenever that might be the case.

Overall, the procedure seems to work but is pretty tedious. It would probably only be worthwhile if a quick romp thru the maze didn't locate what you're after.


Top
 Profile  
 
 Post subject: Re: An algorithm for exhaustively, efficiently dungeon crawl
PostPosted: Mon Nov 18, 2013 2:39 pm 
Offline
Apprentice
Apprentice

Joined: Sun Sep 15, 2013 4:38 pm
Posts: 141
UESPoints: 1
Actually, IIRC there should be some way to mark sectors on the automap, but maybe I'm confusing this with Arena. You can certainly make sectors invisible by clicking on them (RMB IIRC), and make them blink, thus marking a sector. Not sure if you can add messages, maybe this was only in the early demo v0.1, if at all.

_________________
Daggerfall graphics fix


Top
 Profile  
 
 Post subject: Re: An algorithm for exhaustively, efficiently dungeon crawl
PostPosted: Thu Jan 09, 2014 12:57 am 
Offline
Layman
Layman

Joined: Sun Apr 12, 2009 8:37 pm
Posts: 8
ES Games: Arena, Daggerfall
Platform: PC
UESPoints: 0
I always draw a map when I explore a dungeon. I take the right hand path and when I reach a dead-end or a visited junction I turn back and take the next unexplored passage. I have thoroughly searched more than 100 dungeons that way, always sneaking to improve the skill.


Top
 Profile  
 
 Post subject: Re: An algorithm for exhaustively, efficiently dungeon crawl
PostPosted: Tue Apr 07, 2015 11:49 pm 
Offline
Initiate
Initiate

Joined: Thu Apr 02, 2015 5:43 pm
Posts: 27
ES Games: Arena, Daggerfall, Morrowind, Oblivion
Platform: PC, Xbox
UESPoints: 0
I generally just keep my right hand on the wall, and drop useless loot when I come to an intersection(depending on the size of the dungeon). This works pretty well for most dungeons. Don't over complicate it.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC


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:  

Sponsored Links

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group