Cavewalk Algorithm
by trunksbomb
The goal is simple -- map a single, continguous line that follows the contours of the terrain (usually a cave) from one predetermined point until it reaches a second predetermined point. The outline must be able to account for all potential variations in terrain including overhangs, walls and deadends.
The algorithm detailed herein is most similar to the Wall Follower rule for solving mazes, except that we are not trying to exit to a predetermined point as you would in a maze. If you are not familiar with this rule of maze solving, the principle is this: Put one hand on a wall as you enter the maze and keep that same hand on the wall as you maneuver. In many cases, doing so will get you to the exit (or, upon reversing, reliably return you to where you started).
The Cavewalk algorithm takes in a few parameters to get started:
- The World: It must be made aware of the Minecraft world so that it can traverse within it.
- An arbitrary starting position [x, y, z]: The starting position can be anywhere, as we are not trying to solve a maze but rather to trace a contour. Naturally, there would be no contour to follow if you start in middair so it would be wise to find an arbitrary surface on which to begin.
- An arbitrary ending position [x, y, z] and/or a maximum distance: It would be wise to tell the algorithm where and/or when to stop. We must either tell the algorithm where to stop or how many iterations to complete before stopping (or both, depending on your use case).
- The initial facing direction: You must tell the algorithm in which direction it should embark. Once started, it will continue in a straight line on the axis containing its initial facing direction and its walking surface (see below).
- The initial walking surface: Imagining the algorithm as an entity that can defy gravity on a whim, you must define the surface on which it will begin its walk. Imagining it as a regular being affected by gravity, you might tell it that it should begin its walk by sticking to the world's downward direction (ie, the ground as we would walk on it). But you could also tell it to begin its walk stuck upward, or to the north face of a block, etc. Combined with the initial facing direction, this determines the axis on which the algorithm operates.
Once the algorithm has been fed its relevant information, it will begin. The functionality is defined very simply by three possible choices, in order of preference:
- The algorithm will always prefer to stay attached to the block on which its currently walking. For example, if the algorithm is walking with its "feet" facing down (this is our traditional, gravity-based idea of "down") and facing East, its natural inclination will be to try to wrap around the block it's "standing" on by putting its feet on the eastern face of the block, now facing downward.
- If it cannot stay attached to the block that it's currently "standing" on, then it will try to continue walking in a straight line. To do so, the area directly in front of the algorithm's current facing direction must be free to move into, and the area directly in front of the block the algorithm is currently standing on in the algorithm's current facing direction must be a solid block. That's a long-winded way to say "if the next block in its facing direction is empty, and the block 'under' that is solid -- walk straight".
- If that is not possible, the only remaining possibility is that the area directly in the algorithm's facing direction is a solid block; in this case, the algorithm will step onto this block and turn to face the oppposite direction of its previous walking surface (if it was walking with its "feet" down, now it will be facing up).
There is one edge-case to consider, and that's when it could theoretically perform its first, preferred step to wrap around on the same block, but where there is a solid block impeding its path (that is, if it were a physical being unable to phase through matter). This would effectively put it into a new "cave", so to speak, causing unexpected results for the player. To compensate, when this edge case is encountered the algorithm will perform the only remaining logical step of its three possible steps -- the third, where it will step onto the block impeding it from continuing with step one.
The three choices above are, without a doubt, best illustrated by a picture. See figure 1.
Figure 1. The three possible choices
In each of the three choices depicted, the icons are as follows:
- Red arrow: Indicates where the algorithm's walker is positioned currently.
- Red line: Indicates the surface on which the walker is standing currently.
- Blue arrow: Indicates where the walker will be positioned after making this choice.
- Blue line: Indicates the surface on which the walker will stand after making this choice.
By defining these 3 simple choices, or instructions, the Cavewalking algorithm is able to successfully trace the contour of whatever surface it starts on by making a choice, executing it, and then assessing its next choice in the same way.
It should be noted that this algorithm suffers the same pitfalls as related maze-solving algorithms do, in that one single algorithm cannot be relied upon in every case. While this algorithm never truly fails at the simple task it's set out to do, it may not find the "true" contour of a cave if it's started in the "wrong" spot. For example, if you start it on a magically floating surface inside of a bigger cave -- one that has no physical connections to the walls of said bigger cave -- it will only find the contours of the magically floating surface. While this is a success as far as the algorithm is concerned, the player may have expected to find the contour of the bigger surface of the cave instead, in which case a different algorithm should be deployed (or a combination of algorithms).