I'm confused by the grammar - is "100%" being used as a verb? Is that correct in English?
Using Hilbert Curves to 100% Zelda
41–50 of 65 posts
Re: Using Hilbert Curves to 100% Zelda
#42> 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?
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.
Re: Using Hilbert Curves to 100% Zelda
#43I'm confused by the grammar - is "100%" being used as a verb? Is that correct in English?
Yes it is being used as a verb. It's at least common terminology among speedrunners.
Many games, including the one in question, have an in-game progress tracker. To "100%" the game is to complete everything necessary to make it reach 100%.
For games without such a tracker, the community usually reaches a consensus on what is considered to be 100%.
Re: Using Hilbert Curves to 100% Zelda
#44I'm confused by the grammar - is "100%" being used as a verb? Is that correct in English?
Strictly speaking you can use any noun as a verb in English. The grammar allows for it, though most nouns will not have a meaningful verb counterpart, semantically, or it will not have a usage that most people will understand (i.e. it won't be colloquial)
So in a speed running context, I would definitely say it is acceptable, but it might not be in the greater population. But the grammar nazi have nothing on this one.
Re: Using Hilbert Curves to 100% Zelda
#45(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... )
This is really interesting, thanks for linking :)
Re: Using Hilbert Curves to 100% Zelda
#46I'm confused by the grammar - is "100%" being used as a verb? Is that correct in English?
If it isn't, I'm invoking my right to English incorrectly, given that it's not my native language ;)
(yes, I'm being toung-in-cheek by using "English" as a verb here :) )
Re: Using Hilbert Curves to 100% Zelda
#47> 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…
OptaPlanner is an open source constraint satisfaction solver (https://www.optaplanner.org/). Here is an explanation of how it can be used to solve the Vehicle Routing Problem, closely related to TSP: https://www.optaplanner.org/learn/useCases/vehicleRoutingPro...
Re: Using Hilbert Curves to 100% Zelda
#48> 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.
In own research (inverse problems related to signal recovery), I've noticed that a lot of NP-hard problems are actually easily solvable given that the data has some kind of structure to it. I know very little about computational complexity theory, but I've read some papers describing how there is often a phase transition where a high SNR puts the problem in P territory, but a sufficiently low SNR moves the problem moves to NP territory (but it's still solvable). Beyond the phase transition, a solution is information theoretically impossible. I wonder if most of these real world TSP problems actually lie in P, but I don't know how one would go about showing that. (I haven't performed a literature search, but I wouldn't be surprised if someone has already demonstrated this.)
Re: Using Hilbert Curves to 100% Zelda
#49Why 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.
Yeah, sorry I meant like lexicographic on x, then swapping between lexi and reverse-lexi on y. Basically snaking back and forth.