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

11–20 of 65 posts

Re: Using Hilbert Curves to 100% Zelda

#11

Post by rlanday »

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…

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."

Re: Using Hilbert Curves to 100% Zelda

#12

Post by xxbondsxx »

nitrogen wrote: post #7

The returned file turns out to not actually be JSON (that'd be too easy, I guess) but some kind of javascript-code which is then probably eventually eval'd to get the data: /**/jQuery3110644358575 2152035_1500757689075( /* json-data */) Is that just JSONP?

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

Re: Using Hilbert Curves to 100% Zelda

#13

Post by xxbondsxx »

nwjtkjn wrote: post #9

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

Given the precision of the points, lexicographical order on (x,y) would essentially be lexicographical order on just x, which then induces a lot of jumping around the map.

Re: Using Hilbert Curves to 100% Zelda

#15

Post by cbhl »

nwjtkjn wrote: post #9

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

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

Re: Using Hilbert Curves to 100% Zelda

#16

Post by cbhl »

xxbondsxx wrote: post #12
nitrogen wrote: post #7

The returned file turns out to not actually be JSON (that'd be too easy, I guess) but some kind of javascript-code which is then probably eventually eval'd to get the data: /**/jQuery3110644358575 2152035_1500757689075( /* json-data */) Is that just JSONP?

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/

Re: Using Hilbert Curves to 100% Zelda

#17

Post by cyphar »

rlanday wrote: post #11
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…

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.

Re: Using Hilbert Curves to 100% Zelda

#18

Post by cbhl »

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.

Re: Using Hilbert Curves to 100% Zelda

#19

Post by Retric »

modalduality wrote: post #4
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…

The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length. I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too). Incidentally, achieving a polynomia…

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.

Re: Using Hilbert Curves to 100% Zelda

#20

Post by modalduality »

Retric wrote: post #19
modalduality wrote: post #4

Earlier quoted context omitted.

The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length. I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too). Incidentally, achieving a polynomia…

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?
Post reply on HN