Using Hilbert Curves to 100% Zelda
blog.merovius.de
Using Hilbert Curves to 100% Zelda
1–10 of 65 posts
Re: Using Hilbert Curves to 100% Zelda
#2excellent! 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).
Re: Using Hilbert Curves to 100% Zelda
#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-and-bound algorithms can often find optimal solutions even for instances with thousands of points.
Does anyone here know if there is a good open-source solver that we could throw this problem instance at?
Re: Using Hilbert Curves to 100% Zelda
#4> 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 polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation.
Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.
Re: Using Hilbert Curves to 100% Zelda
#52-opt can probably improve on the Hilbert solution (https://en.wikipedia.org/wiki/2-opt)
Is the world planar? There's an epsilon approximation scheme for planar TSP that's linear in the graph size (but exponential in 1/ε)
Re: Using Hilbert Curves to 100% Zelda
#6> 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…
[deleted]
Re: Using Hilbert Curves to 100% Zelda
#7The 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 */)
Re: Using Hilbert Curves to 100% Zelda
#8> 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…
TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points.
With that many points, how do you prove that your solution is optimal?
Re: Using Hilbert Curves to 100% Zelda
#9Why is the Hilbert Curve any better in this situation than say lexicographical order on (x,y)?
Re: Using Hilbert Curves to 100% Zelda
#10> 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…
TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. With that many points, how do you prove that your solution is optimal?
Often in approximations you can prove an upper bound on the optimal solution, even if you don't know the optimal solution itself.
An easy example is by using duality when solving linear programs.
And sometimes your upper bound is close enough to what you already have so you can just say something like "well my solution gets 190 points, I have an upper bound of 190.5 points, and all point rewards are integral so I must have the optimal solution."