4
$\begingroup$

I'm creating a world that takes place in an infinitly big 3-D maze. This means there can be branches in any direction (not that there's one main place, just from each "room"), even directly upward. The "rooms" are ranging from a normal personal bathroom to a a bedroom. Assume they can easily get through branches in all directions, even up, with equal ease. A branch can be in any direction.

Based on this, how close together can the rooms generally be and still hard to navigate (hard meaning it takes more than 5 years to navigate 1,000 rooms with mostly ease (in a mostly cubic shape))?

$\endgroup$
7
  • 2
    $\begingroup$ First, I think it's more an issue of length than "hard", since you already give the 1000 room complexity. Then, I feel like the simplification of going up and down being the same as right and left implies there's some tool to average the speed. Do people use some kind of elevators to climb as fast as walking, or do they need to crawl when going left-right? Finally, the time to complete a maze is highly dependent on what do you have access to locate yourself : Do people have a map or some paper and pencils to make one, can they mark the locations, either with a thread or something else? $\endgroup$
    – Tortliena
    Sep 16, 2022 at 2:11
  • $\begingroup$ Hard typically depends on the heuristics the person is doing. If you are doing A* with the traditional manhattan distance metric, there are known shapes that are very hard to navigate. However, if a smart human realizes that this is one of those hard-to-navigate-with-A* shapes, its very easy for them to smartly work their way through the maze without issue. $\endgroup$
    – Cort Ammon
    Sep 16, 2022 at 2:46
  • 2
    $\begingroup$ I'm confused! The rooms "...[range] from a normal personal bathroom to a a bedroom..." but it somehow "...takes more than 5 years to navigate 1,000 rooms..."? That's basically just a large hotel... which should only really take a day to explore if you have the keys. Why do you expect the rooms to be so hard/slow to navigate? Are they boobytrapped so that you must be deadly-careful? Or are the rooms not directly connected to other rooms and have long halls connecting them? Or are you saying that everything is tight maze-halls except for small clearings the size of regular rooms? $\endgroup$ Sep 16, 2022 at 6:45
  • $\begingroup$ @LetEpsilonBeLessThanZero they aren't directly connected. Everything is tight maze except the rooms. It is in a random-complex fashion, with no pattern. $\endgroup$
    – 4117
    Sep 16, 2022 at 21:45
  • $\begingroup$ We have a strict one question per post policy. Follow up questions should be asked in separate posts. $\endgroup$
    – sphennings
    Sep 20, 2022 at 5:25

2 Answers 2

8
$\begingroup$

Assuming that people can walk 20 miles in a day there would need to be an average of 36.5 miles traversal between rooms to not fully explore 1000 rooms in 5 years. 20 miles a day with 365 days in a year for 5 years gets you 36500 miles traveled, split between 1000 rooms.

If you factor in backtracking, if your "maze" is a balanced binary tree with 1023 rooms, and you start at the root node, you'd need 2035 room traversals to fully explore every room. (I have no idea if this is the worst case for full graph traversal. Any graph theorists who can provide more insight) Since your explorers will travel 36500 miles in 5 years, the average traversal between rooms must be 17.9 miles.

This is assuming that people are just intending to visit every room. If they're searching for a specific room, 17.9 miles is the maximum distance that guarantees that they will find their goal within 5 years. Assuming that their goal is randomly located, it's likely that they'll find it in 2 and a half years.


Getting a bit nerd sniped by attempting to figure out what the worst graph and starting vertex would be. The shortest worst case minimum traversal is $n-1$ steps from any vertex on a Hamiltonian graph. The longest worst case minimum traversal I've discovered is the star graph, starting from the center vertex. I haven't proved it but I suspect that the star graph may have the longest worst case minimum traversal of any graph.

I haven't determined the formula for the worst case minimum traversal for a binary tree, but the worst starting vertex is the root. The length of the worst case minimum traversal of a binary tree seems to be close to but shorter than that a star graph.

Graph Type Worst Starting Vertex Worst Case Minimum Traversal Distance Between Rooms
Any Hamiltonian graph Any $n-1$ steps 36.53 miles
Path (linear) graph Center $(n-1)+\lfloor \frac{n-1}{2} \rfloor$ steps 24.3 miles
Star graph Center $2(n-2)+1$ steps 18.2 miles
$\endgroup$
3
  • $\begingroup$ The goal isn't to simply go to every room. It's to be able navigate from one room to another in one of the shortest paths most of the time $\endgroup$
    – 4117
    Sep 16, 2022 at 21:52
  • 1
    $\begingroup$ @4117 Visiting every room gives us the worst case travel time between 2 specific rooms, assuming no pre-knowledge of how rooms are connected. This only occurs in the unlikely event that your goal happens to be the last of the 1000 rooms that you visit. On average you will find your target room in about half that distance. Once you know how rooms are connected, the travel time is strictly a function of the shortest path between two rooms. Since this is highly dependent upon the layout of the rooms, something we do not know, the best we can provide is an upper bound. $\endgroup$
    – sphennings
    Sep 16, 2022 at 22:23
  • $\begingroup$ To put it another way: if the average distance traveled between rooms is less than 18.2 miles, it is guaranteed that, an explorer will always be able to locate their goal room, in less 5 years, no matter how the rooms are connected to each other. $\endgroup$
    – sphennings
    Sep 16, 2022 at 22:28
1
$\begingroup$

They are connected randomly.

But they are identical one to the next. They have no orienting features and your explorer does not have a compass. As you move from room to room it is very easy to go in circles. Additonally the connections are not fixed. The spheres rooms are moving and turning. An entrance labelled A will lead to sphere B. But the next time the explorer goes through exit A, B is not above the door on the far side. She is in sphere K. Later she enters a sphere and sees the B over an exit on the far side.

So: 1000 rooms with any one room leading to a random any other room. How long to explore all 1000 rooms with each room happened upon by chance. This is the coupon collectors problem

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Calculating_the_expectation

If each box has a random coupon how many boxes must one buy to collect them all.

Wikipedia gives the approximation n(ln(n) + γn + 1/2 for # of tries to get all n options where each option is random.

I calculated 8484 tries to have good chance of getting all 1000 options.

There are 21900 hours in 5 years. If you never sleep you could try 8484 times with 2.58 hours between each try and finish in 5 years. If you sleep 20% of each day that leaves 17520 hours so 2.06 hours between tries.

If that 2 hours is spent traversing the distance between rooms it depends on how fast you move. I personally move at about 2 miles an hour and so 4 miles apart.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .