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

31–40 of 65 posts

Re: Using Hilbert Curves to 100% Zelda

#31

Post by patio11 »

skrebbel wrote: post #30
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?

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.

Re: Using Hilbert Curves to 100% Zelda

#33

Post by decafb »

For reference: The generic name what op does is "spatial indexing". There is an algorithm for efficiently working with such data called Hilbert R-tree (https://en.wikipedia.org/wiki/Hilbert_R-tree). But there are alternatives (see https://en.wikipedia.org/wiki/Spatial_database).

Many databases nowadays contain functions to these operations (e.g. https://dev.mysql.com/doc/refman/5.7/en/spatial-analysis-fun...)

Re: Using Hilbert Curves to 100% Zelda

#35

Post by nullc »

cyphar wrote: post #17
rlanday wrote: post #11

Earlier quoted context omitted.

Concorde is open source and I believe holds the record for largest instance of TSP solved optimally (85,900 cities): http://www.math.uwaterloo.ca/tsp/concorde.html Note that the licensing terms do restrict its free use to "academic research."

> Note that the licensing terms do restrict its free use to "academic research." Then it is not "open source" (violates "No Discrimination Against Fields of Endeavor") nor is it free software (violates the freedom to use for any purpose). It's proprietary -- just because the source code is available doesn't make something "open source" nor does it make it free software.

Unfortunately, such terms are ubiquitous in operations research.

Re: Using Hilbert Curves to 100% Zelda

#36

Post by j05huaNathaniel »

thesmallestcat wrote: post #34

A Zelda game that depends on Google Maps. I'm getting old.

The game doesn't. He references the zeldadungeon.net map which uses google maps javascript api. Nintendo would be full of morons if they ever did something like that. Just read the fine print.

Re: Using Hilbert Curves to 100% Zelda

#38

Post by tgb »

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?

That doesn't seem necessary. Picking a value of p just selects how much you prefer short hope to shorter total distance.

Re: Using Hilbert Curves to 100% Zelda

#39

Post by evincarofautumn »

rileytg wrote: post #2

excellent! i wonder if there are more algorithms that can be used in this game. binary search is an algorithm that can be easily done by a person (doesn't need a ton of iterations to locate result).

Binary search would make a good bar bet. “Pick a number between 1 and 1000. I’ll make guesses, and you just tell me whether they’re too low or too high. I’ll bet you $10 that I can guess the number in only 10 tries or less.”

Re: Using Hilbert Curves to 100% Zelda

#40

Post by Merovius »

j05huaNathaniel wrote: post #37

Except that this doesn't take into account elevation.

As this was only about efficiently enumerating the missing locations, not walking them, that's fine. I.e. I had to find the ~5 needles in the haystack of hundreds that I needed to visit. Given that sparseness, it was most efficient to just jump to the nearest warp point and directly go there.

Elevation and the like would be more interesting to figure out what's the most efficient way to collect all Korok Seeds, for example, when the interesting point cloud isn't as sparse. But then you'd definitely want to view it as a TSP problem anyway.

Post reply on HN