An algorithm for exhaustively, efficiently dungeon crawling
Posted: Sun Nov 17, 2013 2:06 pm
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.
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.