[leothetechguy]

Step 1 in this situatoon is to try and see if this is a known mathematically unsolved problem, and if it is, giving up.

Isn't this just trying to find a hamiltonian cycle, isn't this NP hard? That's when I would give up, especially because you put so many constraints in it to make it human walkable.

Edit: Of course you don't have to give up, but it's good to know what you get yourself into

[procaryote]

Why would you give up just because something is NP hard if there are good algorithms to approximate a solution, and an approximate but good solution is useful?

[viraptor]

Yeah, there are many problems which are np-hard in theory, but then realistic cases give you way more constraints that make them solvable. So many hard graph problems become way simpler when applied to real maps, because you know that if you start getting away from something, your minimum remaining distance grows. But on an abstract graph there's no real mapping to our dimensions.

[threatofrain]

That just means you didn’t encode the information you wanted into the graph.

[viraptor]

There's no "information you wanted" in the plain np-hard version of traveling salesman for example. There's only cost. My point was that things get easier if you have the extra information and aren't solving the plain version anymore.

[stabbles]

For constant n even exponential complexity reduces to constant time