An algorithm for exhaustively, efficiently dungeon crawling

[Alodar]

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.

[MrFlibble]

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.

[Alodar]

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.

[MrFlibble]

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.

[AFigureInBlack]

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.

[Rickel]

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.