After finding 98.59 per cent of everything Breath of the Wild had to offer, programmer and mathematician Axel Wagner was stumped. He had to find that last 1.41 per cent. Manually trying to identify the last few locations using an online map got him to 99.58 per cent, but turned out to be too error-prone, leaving Wagner with one option — a Hilbert curve.
Wagner’s problem was efficiently figuring out where he still had to go and doing it the old-fashioned way (relatively speaking) wasn’t working:
Alphabetical just wasn’t a great way to organise [the locations]; I wanted a list that I could systematically check. But I didn’t want it alphabetically but geographically. I didn’t want to have to jump around the map to try and find the next one. Which is when I realised that this would be the perfect application for a Hilbert curve.
No, a Hilbert curve is not a special power or move from the game — it’s a “continuous fractal space-filling curve”, according to Wikipedia.
My command of maths is nowhere near good enough to explain what this means or how to would help Wagner, so I’ll let him do it instead:
One of the most interesting properties of the curve and its finite approximations is that points that are close on the real number line get mapped to points that are close in the plane. So if we could extract all locations from the online map, figure out for each what real number gets mapped to that point and order the locations by those numbers, we’d get a list of locations where neighbours in the list are close to each other on the map.
And that helps him how? That’s the easier part:
Presumably, that would make for easy checking of the list: The next location should be pretty much neighbouring the previous one and if I can’t find a location nearby, chances are that I didn’t visit it yet (and I can then look it up specifically).
From there, Wagner was able to visit the missing locations and get his 100 per cent. Whether he earned it fairly is up for debate, but as a programmer myself, it gets a thumbs-up from me.
Using Hilbert Curves to 100% Zelda [Between a rock and a crazy place]
Comments
5 responses to “How A Mathematician Used ‘Fractal Curves’ To 100% Zelda: Breath Of The Wild”
At the end of the day, he is following a check list of collectables in order to hit 100%. Using a Hilbert Curve to decide which order to check off items on the list is novel idea and probably saved some time, but ultimately he’s using the same help many others would to hit 100%.
I’m pretty sure a Hilbert Curve would be an inefficient solution for hitting known locations anyway. He mentions the Travelling Salesman problem in his original post, and I’m confident it would give the most efficient traversal of a set of known locations. There are some pretty good TSP solutions that aren’t computationally expensive.
I have only had the game for a week and cannot even begin to imagine going for 100%.
I’ve had it for 3 weeks and only now am I beginning to feel comfortable traipsing around this version of Hyrule.
I have only just hit the stable after duelling peaks and feel like I need to go back to the Great Plateau. My only problem is that I think I need to progress the story a bit to get some better gear and stuff.