Bad Apple!!

I made a thing.
Check out the video I linked in the description or it won't make much sense, but long story short:

In Pokemon Ruby and Sapphire there's a species of pokemon called Spinda that's sort of a rabbit with four spots on its face. The locations of the spots are controlled by the octets of a 32-bit integer that's unique to each Spinda. I wrote a program that can generate a matrix of valid Spindas to display an arbitrary image (with some loss of detail, obviously).

The implementation some guy made in Python took around a day and two computers to generate a 10-second clip, while mine generates a 3-minute video in under 15 minutes.
Reminds me of a guy writing a Python program to play piano tiles, but Python was so slow that the tiles moved faster than the program could see then click them.

Video looks good!!
Sounds interesting, but what part of the problem eats all the time? You said spindafy is the bottleneck, but that seems to just be your whole program if I am following correctly. I am guessing its the best fit, and maybe a jpg to pixels to jpg again conversion (can that be avoided?).
Last edited on
Each spot is controlled by an octet, so for each one there's 256 places to put it, and you have to place 4 spots. So that's 1024 Spinda faces you have to compare to the source bitmap to find the one that most closely resembles it. Then in each frame there's space for 360 Spinda faces. With each face being a 35x33 bitmap, that's 426 megapixels to process per frame, or 1.56 GiB. It's just a load of data to get through.
That’s both messed up and very extra cool!

Amazing that today we write computer systems in video games. (Like the guy who made an 8086 in Minecraft or something like that.)
Yeah, there's people who figured out that Magic the Gathering's rules permit encoding a pushdown automaton into the game's state, so you can compute stuff by moving cards around while sticking to the rules (as long as the other player cooperates).
Hmm. I wonder if you could de-res the original image into legal octets, processing less info while matching automatically in one go... we did something like that for OCR in one of our programs... converted it to 2 colors and less resolution so the OCR matcher had a lot less to do and was extremely fast (way back on old school hardware when it was still a challenging problem).
I'm thinking a good strategy is to get a histogram of the selected patterns. If some are selected a lot more often than others it may be possible to reduce the search space.
An easy way to make it four times as fast with some loss of quality is to only check the even coordinates for each spot.
Registered users can post here. Sign in or register to post.