Log in

No account? Create an account
'Twas brillig, and the slithy toves did gyre and gimble in the wabe [entries|archive|friends|userinfo]

[ website | Beware the Jabberwock... ]
[ deviantArt | the-boggyb ]
[ FanFiction | Torkell ]
[ Tumblr | torkellr ]

[Random links| BBC news | Vulture Central | Slashdot | Dangerous Prototypes | LWN | Raspberry Pi]
[Fellow blogs| a Half Empty Glass | the Broken Cube | The Music Jungle | Please remove your feet | A letter from home]
[Other haunts| Un4seen Developments | Jazz 2 Online | EmuTalk.net | Feng's shui]

Using Hilbert Curves to 100% Zelda [Sunday 23rd July 2017 at 2:13 pm]

[Tags|, , ]
[Feeling |curiouscurious]

Today's random link for the Zelda geeks on my flist: Using Hilbert Curves to 100% Zelda.

I had been wondering how to handle tracking down the last few collectibles. My normal approach is to either keep a log of where I find items or to take a printout from a FAQ/walkthrough and tick off items as and when I find them - either way I can easily work out what I'm missing by comparing against my found list - but I hadn't done that for Breath of the Wild. Not that I think it would have helped as there's a ludicrous [Spoiler (click to open)]900 Korok Seeds to track down and those are absolutely everywhere. Shrines are a bit easier, though every time I think I've found the last shrine (based on hitting a round number or a given set of heart containers) I discover another one somewhere - I think the total is [Spoiler (click to open)]120. And what I hadn't realised until I read the linked post is that discovering landmarks also counts to that 100% and there's a fair number of those as well.
Link | Previous Entry | Share | Next Entry[ 4 pennies | Penny for your thoughts? ]

[User Picture]From: nendil
Monday 24th July 2017 at 5:42 am (UTC)
So am I understanding right that his approach still just results in "manually check every inch of the map in a systematic manner"?

I appreciate having this problem presented from a programmer-problem-solving point of view, though :) If you want to create an as-automated-as-possible solution to this, I imagine you'd need some way to grab data of your game state. And since I don't want to spend time to learn how to hack WiiU and/or Switch save data, the next-best solution that comes to mind is:

1) Take screenshots of each section of your in-game map at max zoom
2) Do the same for the online map, with appropriate icons turned on/off (or hack & recreate the image data???)
3) Using Photoshop or another tool, examine the diffs between the two maps

It's a pretty darn big map at max zoom so even just grabbing & setting up these screenshots is easier said than done. But, it depends on if you have more fun playing in-game or being a hacker programmer ;)
(Reply) (Thread)
[User Picture]From: boggyb
Tuesday 25th July 2017 at 11:11 pm (UTC)
That's pretty much it - a Hilbert Curve orders your list such that sequential items are geographically nearby. So when checking against the map you're not constantly scrolling vast distances to find the next item. It's still a manual process to compare against the list.

I was mulling over your automated-as-possible proposal and wondered if it could be made more automated. As you said it's a massive map and screenshotting it by hand would take ages at max zoom (and I think you need max zoom for the Korok Seeds). But it ought to be possible to take a video of scrolling back and forth across the map and then process that to stitch the frames from the video together into a complete map - the movement is strictly 2D and everything is moving in the same direction. That automates step 1, and then steps 2/3 are much the same as you've described (though again one could automate comparing the two: subtract the online map from the captured one, then for each item check that the expected icon is present).

Hmm... I think I'll add this to my pile of semi-bonkers programming project ideas...
(Reply) (Parent) (Thread)
[User Picture]From: nendil
Wednesday 26th July 2017 at 4:29 am (UTC)
The video idea is not bad, but I feel like it'd be a similar amount of work to get & stitch the frames together anyway. Plus with the screencaps, at least the Switch has a pretty convenient button to grab those natively.

Also to note: It would be a lot easier to scan this diff-ed map visually than programmatically because you'd have to account for things like (if I recall correctly) in-game textures/filters over the map, differences in text display (size/font/alignment), etc. It might be faster in the end to hack the WiiU save data after all... but if you're on the Switch (as I am), then welp.
(Reply) (Parent) (Thread)
[User Picture]From: boggyb
Sunday 5th November 2017 at 11:34 pm (UTC)
I hadn't taken this any further as while I have found a potential tool for stitching together panoramas, I don't have a HDMI capture card and so couldn't capture video from the Switch. Except Nintendo have now added built-in video recording so actually videoing the map becomes very easy. I might have another look at this...
(Reply) (Parent) (Thread)