Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Hilbert Curves to 100% Zelda

blog.merovius.de

Post reply on HN
Print view View original

61–65 of 65 posts

Re: Using Hilbert Curves to 100% Zelda

#61

Post by Merovius »

CamperBob2 wrote: post #60
amalcon wrote: post #42

Earlier quoted context omitted.

TSP (in the traditional sense of finding an optimal solution) is NP-complete, so (by definition of NP-complete) it's much easier to check a proposed correct answer than to find that answer.

Hmm. So there's a polynomial-time method for verifying that you've found the shortest path in TSP, but not for finding it in the first place?

Yes. Crash-course complexity theory:

This is easy to understand with integer factorization: It is very hard to factor large integers. Yet, if I where to give you two numbers, it is very easy to verify that their product is the integer you where looking at. So factorization is easy to verify, but hard to do (side-note: This is an intentional illustrative simplification. Integer factorization is not known to actually be "hard" and it is not known whether "hard" is even a thing. See below).

And that's the definition of an NP problem: It has a polynomial time deterministic algorithm to verify a solution.

An NP-complete problem is a problem that is at least as hard as any NP problem. That is, if you have an algorithm for an NP-complete problem, you can take any NP problem, transform it efficiently into that problem, use your algorithm and transform the solution efficiently back. Thus, if you've solved an NP-complete problem efficiently, you can solve all NP problems efficiently. TSP is NP-complete. Whether or not Integer Factorization is NP-complete is unknown.

Lastly, there is the question of whether there are problems that are in NP (that is, have a polynomial algorithm to verify a solution) but not in P (that is, have a polynomial algorithm to find a solution). That's the famous P vs. NP question, which is currently undecided.

Re: Using Hilbert Curves to 100% Zelda

#62

Post by twotwotwo »

patio11 wrote: post #31
skrebbel wrote: post #30

Earlier quoted context omitted.

> It's kinda wild that game worlds are now large enough that I haven't played Breath of the Wild yet, but eg Chrono Trigger has an enormous game world as well. Did they really get much bigger since?

It is hard to make an apples to apples comparison against Chrono Trigger, but you'd not be grossly wrong if you described BoW as having a 100X bigger map. It is also much, much more populated with things to do, enemies to beat, mushrooms to pick, etc.

> mushrooms to pick

And durian. Delicious, delicious durian.

Re: Using Hilbert Curves to 100% Zelda

#63

Post by Merovius »

nwjtkjn wrote: post #51
cbhl wrote: post #15

Earlier quoted context omitted.

It's pretty easy to imagine a counter-example that would have you traverse the length of the map, when the best route would be to detour on an existing traversal. Consider: 1...2...3...4...5 7...............6 8.......9........ 13..12.....11..10 versus 1...2...3...4...5 13..............6 12......9........ 11..10......8...7

Good point, though I'm not convinced Hilbert really avoids this. For example, look at n=3 here: http://www.texample.net/media/tikz/examples/PNG/hilbert-curv... This might lead to say . . . . . . . . 1 . . . . . . 2 4 . . . . . . 3 . . . . . . . . when . . . . . . . . 1 . . . . . . 4 2 . . . . . . 3 . . . . . . . . is more efficient. Generally speaking, it seems this is basically TSP.

I tried describing here https://www.reddit.com/r/programming/comments/6oxra8/using_h... why I think that this is theoretically a TSP problem, I don't consider that necessarily the best way to treat it. tl;dr is, that at least to me, at the time, for this problem, the speedup of an optimal solution wouldn't have outweighed the additional thinking time to get to that optimal solution (and, most importantly, to actually make it useful; after all, I wasn't actually drawing a path, I was outputting a list of names).

You can even see that in the argument I added to the post; while a zig-zag line might've been, in theory, a stupider, easier way to solve the problem, in practice it would've meant spending some time thinking about the right discretization. With a Hilbert-curve, I could just choose some n that is definitely large enough and be done with it and the additional cost of the more complicated curve doesn't really factor in, as I could just copy-paste it anyway.

But yes. The theoretical problem is a TSP and with the right set of tools, I could've added some efficiency to the search by viewing it as such.

Re: Using Hilbert Curves to 100% Zelda

#64

Post by Merovius »

tedunangst wrote: post #53
nwjtkjn wrote: post #50

Earlier quoted context omitted.

Yeah sorry I meant like snaking back and forth, which you're right is not the same as pure lexicographic.

Yeah, the length of such a snake is equal to the Hilbert curve.

Yes, but we wouldn't actually walking the whole snake, just as we are not walking the whole Hilbert curve. We are walking the point cloud in the order dictated by either, and those will, in general, differ.
Post reply on HN