21. Dots, Recursion, Optimization, and More?

This week, I spent some more time designing puzzles for the “dot” mechanic that I mentioned in the previous blog post. I currently have about 60 puzzles sitting around in the world using this mechanic. Definitely take that number with a grain of salt as these are rough draft quality puzzles, and I will probably cut a bunch of them.

Still, it’s been fun designing these puzzles and seeing how much I can wring out of just the baseline, without even including the other mechanics of the game. There is a lot of depth and subtlety, and I really think I probably have just scratched the surface what’s there.

In addition to building out this area, I created a functional prototype of an area that I’d been thinking about before I even started building the game (at least as far back as June 23, 2015, which is the modified date on an old Google Doc where I wrote the idea down). I wasn’t really sure how this area would work at all because the concept was a bit strange, but it actually seems to work well and I am happy with how that is going. Unfortunately, to tell you what the concept behind the area is would be spoilers, so I will just leave you with a mysterious screenshot.

Brute Force Puzzle-Solving, Optimization

So, another thing that I was thinking about for a while, and in particular with regards to designing the dot puzzles, is that it is sometimes difficult for me when designing puzzles to figure out if they have degenerate solutions. By which I mean, I usually am putting a puzzle in the game because I found that it has an interesting and unique solution, but many times I am unaware that there are alternative solutions which may not be nearly as interesting or require as clever thinking on the part of the player.

To that end, I felt that it would be useful to be able to see all the possible solutions for any given panel. This seemed like it would be fairly easy to implement, as it just means using the computer to go through all the possible states that a given panel could be in and checking to see if the panel is solved in each state and keeping a list of all the solved states. Sadly, it was not as simple as I dreamed.

First, even just the basic task of iterating through all possible states for a panel was difficult to figure out how to accomplish. Ultimately, the solution came via mokesmoe, one of the viewers in my twitch chat. It’s a fairly simple algorithm to implement, but it uses recursion and so is a bit hard to wrap ones brain around. But it works and it covers teh whole possibility space once, and only once.

Still, when it came time to test it out, it very quickly became apparent that it was not going to be practical past a very small panel size. Mathematically, this is pretty easy to figure out, as the number of possible states grows exponentially with the increase in panel size, doubling for each new tile that is added. Even a 5×5 panel was enough to lock up Unity completely to the point that after a few minutes, Unity’s built-in crash reporter killed the process and offered for me to report a bug to their developers.

I shouldn’t have been too surprised though. Even though a 5×5 panel seems small, there are 33,554,432 (2^(5*5)) possible configurations that it can be in. If you do anything 33.5 million times then it’s gonna take some time. For example, if each solution validation only took half a millisecond, covering everything would take 4 and a half hours of processing time. (Someone else can double-check my math on that)

So, I set out about trying to optimize the code, both in the coverage code, and in the solution validation code. Sadly, it was a bit difficult to profile what was happening because the Unity profiler and recursion don’t seem to mix very well. Lots of killing Unity.exe from task manager ensued.

Eventually, by pulling some variables out of inner loops and reducing the amount of dynamic memory allocations, I was able to get solution validation down to where it takes less than .05 milliseconds.

Still, although this makes the brute-force solver much more practical, this doesn’t prevent the possibility that some panels will just go into what is basically an infinite loop. So, as an additional precaution, I just added a timeout which will kill the solution search after a certain number of cycles and just consider it “un-brute-forceable.” This basically is just a cheat so that I don’t have to worry about Unity hanging. (Although I still seem to have a problem with some puzzles hanging anyway, so it’s perhaps possible that I’m not doing a thorough enough check (maybe I should just check recursion depth too?)).

Anyway, it was fun to do some optimization work there, but I think mostly I’m still being bitten by both the limits of current technology (we don’t have quantum desktop computers yet), and the limits of high level languages (I don’t really think it should be as slow as 0.05 ms per solution validation on a 5×5 grid, even with the fancy recursive solution validator I have for some of the mechanics)