Using Hilbert Curves to 100% Zelda • Hacker News Board

Re: Using Hilbert Curves to 100% Zelda

#21

Post by Spivak » Sun, Jul 23, 2017, 4:27 AM UTC

modalduality wrote: post #20

Retric wrote: post #19

Earlier quoted context omitted.

If you want to minimize the long distance walks add an exponential weight for distance then solve. There are many ways to go about this stuff, but the goal is to map your preferences to the weight function.

Right, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?

So say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred.

You might make your weight function as w(d, p) = d * (2 ^ p)

Re: Using Hilbert Curves to 100% Zelda

#22

Post by twotwotwo » Sun, Jul 23, 2017, 4:51 AM UTC

> So I started on the onerous task of finding the last 17 locations.

A French guy (Xalikah) who did the first, manually planned 100% speedrun of the game had a similar problem; he spent a few hours with a couple folks helping him check his map for obscure place names he was missing, and when he was at the last one, someone joked "99.81% speedrun," and people were suggesting he do a slow systematic scroll over the map so they could look for missing placenames. He wound up sleeping five hours or so and in the morning remembered that he'd skipped using some bridge somewhere. 49 hours!

It's kinda wild that game worlds are now large enough that you can reasonably use algorithms not only to write games but to get 100% completion playing them as well.

Re: Using Hilbert Curves to 100% Zelda

#23

Post by modalduality » Sun, Jul 23, 2017, 5:52 AM UTC

Spivak wrote: post #21

modalduality wrote: post #20

Earlier quoted context omitted.

Right, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?

So say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred. You might make your weight function as w(d, p) = d * (2 ^ p)

That's fine, but `p` is a variable, not a constant, in the original post's case, right?

Re: Using Hilbert Curves to 100% Zelda

#24

Post by srean » Sun, Jul 23, 2017, 5:56 AM UTC

ufo wrote: post #3

> There might also be better approaches than Hilbert Curves. For example, we could view it as an instance of the Traveling Salesman Problem with a couple of hundred points; it should be possible to have a good heuristic solution for that. On the other hand, a TSP solution doesn't necessarily only have short jumps, so it might not be that good? TSP is actually very amenable to heuristics and state of the art branch-an…

You might get a laugh out of the fact that Hilbert curves are used to approximate Euclidean TSP. If I remember correctly it yields a log n approximation where n is the number of cities.

Re: Using Hilbert Curves to 100% Zelda

#25

Post by Merovius » Sun, Jul 23, 2017, 6:08 AM UTC

cbhl wrote: post #16

xxbondsxx wrote: post #12

Earlier quoted context omitted.

Yes this is just a standard JSONP response as served through jQuery; not sure why this wasn't clarified.

My guess is author has never heard of JSONP before. Obligatory: https://xkcd.com/1053/

I have seen JSONP. But I'm not a frontend dev and in my experience the web suffers from a persistent overspecialization of terms. I didn't mention the term JSONP, because I didn't want to end up calling something JSONP just to have someone point out, that this isn't really JSONP, but floobleworp, which is when you use jQuery and add the comment-symbols to make it safe against XSS or something in that regard.

Also, I still consider JSONP an incredibly gross idea :)

Re: Using Hilbert Curves to 100% Zelda

#26

Post by Merovius » Sun, Jul 23, 2017, 6:11 AM UTC

nwjtkjn wrote: post #9

Why is the Hilbert Curve any better in this situation than say lexicographical order on (x,y)?

Basically, what others have replied is true. But, in essence, yes, I now believe that this would've worked too, if you choose an appropriate discretization of the grid. Hilbert Curves probably were simply the Hammer I had lying around. In the end, it didn't really matter, given that the actual Hilbert Curve part was mostly copy-pasted, but at least it gave me the opportunity to actually use them (and learn from it).

Re: Using Hilbert Curves to 100% Zelda

#27

Post by Merovius » Sun, Jul 23, 2017, 6:23 AM UTC

cbhl wrote: post #18

ufo wrote: post #3

> There might also be better approaches than Hilbert Curves. For example, we could view it as an instance of the Traveling Salesman Problem with a couple of hundred points; it should be possible to have a good heuristic solution for that. On the other hand, a TSP solution doesn't necessarily only have short jumps, so it might not be that good? TSP is actually very amenable to heuristics and state of the art branch-an…

If you wanted to guarantee you "only have short jumps", it would probably be good to consider that you can teleport to the top of the towers and hang-glide down from them (at the cost of some loading time) much more easily than climbing up a cliff.

Given that this wasn't about actually walking the map, but about just finding the locations still missing (and those locations where few and sparse), this really isn't necessary.

It would be, if you'd want to do a speedrun, though.

Re: Using Hilbert Curves to 100% Zelda

#28

Post by sdenton4 » Sun, Jul 23, 2017, 6:27 AM UTC

(I experimented with using space filling curves in City Skylines (a sim city clone) a while ago; here's awriteup for any who might be interested: https://inventingsituations.net/2015/11/28/space-filling-cur... )

Re: Using Hilbert Curves to 100% Zelda

#29

Post by Evelin789 » Sun, Jul 23, 2017, 7:08 AM UTC

modalduality wrote: post #23

Spivak wrote: post #21

Earlier quoted context omitted.

So say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred. You might make your weight function as w(d, p) = d * (2 ^ p)

That's fine, but `p` is a variable, not a constant, in the original post's case, right?

what Ralph answered I didnt know that anybody can get paid $6830 in 1 month on the > computer . i was reading this>>>>>>>>>>>http://ow.ly/iBXm30dNtIZ

Re: Using Hilbert Curves to 100% Zelda

#30

Post by skrebbel » Sun, Jul 23, 2017, 7:22 AM UTC

twotwotwo wrote: post #22

> So I started on the onerous task of finding the last 17 locations. A French guy (Xalikah) who did the first, manually planned 100% speedrun of the game had a similar problem; he spent a few hours with a couple folks helping him check his map for obscure place names he was missing, and when he was at the last one, someone joked "99.81% speedrun," and people were suggesting he do a slow systematic scroll over the map…

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