How far apart would "rooms" need to be in a 3-D maze and still be hard to navigate

Question

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))?

Answer 1

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

Answer 2

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.