I’m frequently inspired to explore a city semi-randomly. By that I mean explore different routes in a neighborhood in a way that I can ultimately synthesize the gathered information and intuitively develop orientation of the city layout. I often combine this with exercise.
Parameters
No consulting the map.
Beyond defeating the purpose of the exercise, the ability to navigate using your internal sensors and intuition is trainable, but atrophies if not sustained.
Initiate and terminate at my start point. That is, cover a cycle.
Distance (or equivalently time) in a certain min/max range.
No repeating paths.
While navigating in a straight line to a certain point and back facilitates the exercise benefit, it severely restricts the learning otherwise achievable in the same time frame. Inner-loops, such as making small circles to complete the overall distance are prohibited.
No repeating points.
I could cover the same reference point multiple times without repeating a path. Imagine a central plaza with many incident routes. I might choose to repeatedly reenter the plaza by means of a different route without repeating my footsteps. While this doesn’t violate the parameters above, it results in a less interesting visual and learning experience.
To clarify the last two parameters above, my goal is to discover such walks (Hamiltonian Cycles in graph theory), but the process may involve multiple iterations. Until that point, I fully expect to retrace my footsteps at a certain point during one day’s walk, although to a minimal extent.
The following presents my intuitive approach in a typical exploration.
Definitions
- current iteration: the current day’s walk
- current path: the path taken in the current iteration.
- nonrepeating current path: the current path minus any incidental loops or repeated segments (such as a dead-end retreat)
- return path: a nonrepeating path leading from your current location to the start point.
- diverging return path: a return path different from the current path reversed.
- new path: a path that hasn’t been covered in any iteration
- walk threshold: the maximally allocated distance or time frame (equivalent) for the current iteration. Or simpler said, how much time/distance you can dedicate to today’s walk.
- cutoff point: the midpoint of the walk threshold.
The algorithm
- Initially, assume zero knowledge of the environment.
- Repeat the following for each iteration:
- Start at initial point
- Pick a previously covered initial trajectory or a random new one that you find appealing
- Repeat the following:
- Proceed straight, mentally accumulating your current path.
- If you stumble upon a point incident to a diverging return path, add the conjunction of the nonrepeating current path + the diverging return path to your list of discovered cycles.
- If you reach the cutoff point:
- Proceed backwards to the start.
- In the return walk, take the first available diverging return path you’ve previously uncovered (if any) that would not compromise the walk threshold.
- Terminate your walk.
- If you encounter a dead end, proceed backwards
- If the scenery becomes unappealing, or you are on a dead-end retreat walk, or a random impulse arises (w/ a minimal viable probability):
- Take the first available turn that diverges from the current path and meets one of the following criteria in decreasing preference:
- Leads to a new path
- Does not strictly lead to a dead end
- Take the first available turn that diverges from the current path and meets one of the following criteria in decreasing preference:
The above high level algorithm may contain some gaps. But generally it should lead to the uncovering of new (Hamiltonian) cycles meeting the established parameters in a modest amount of iterations, assuming the randomness probability meets a minimal threshold. In a follow-up post, I will attempt to carry out a deeper analysis of the above procedure from a graph theory and randomized algorithm perspective.
Questions, comments? Connect.