53. Revisions Completed

It took a bit longer than I anticipated, but I’ve completed converting all of the puzzles in the game over to the new puzzle panel system I described in the last blog post. I probably could have made this a bit easier on myself if I had more deeply integrated the new system within the old one, but I wanted to keep things as cross-compatible as possible so I more or less have both systems working in parallel.

There’s a couple reasons for doing things this way, one is that I didn’t know how well it was going to work, and so I might want to abort the whole thing partway through. This is much easier if I didn’t break any of the existing stuff in the process. The other reason is that it’s just still easier to design new puzzles using the old system. I can just duplicate a panel and I don’t have to wire it up to anything for it to work. The new system, at minimum, requires wiring up each panel to it’s starting tile.

Going forward, I may choose to more deeply integrate the starting tiles, so that puzzle panels will automatically generate them as needed, and I don’t have to do any particular wiring. But going forward, it shouldn’t ever be as much of a hassle as converting everything was in the first place.

New Art!

I also took this opportunity to heavily revise a couple areas in the game, in order to test out approaches to the art, make something that is a closer approximation of what the game might be like when finished, and encounter issues which I might not encounter otherwise.

Here are a couple screenshots of the “arted up” areas.

Overall, I’d say I’m fairly happy with how the artwork has been coming along. The game seems like it might actually not look terrible, and might have something approaching a unified art style. It is admittedly a bit time-consuming to get this level of fidelity, but I think the results speak for themselves.


The other thing that I’m doing this week, is another round of playtesting. I’m pretty sure the next development steps are going to involve cutting a bunch of puzzles. However, I want to get a more broad base of feedback so I can make more informed decisions about where I should let certain things stay in the game and what areas might feel too tedious or drawn out.

Apologies if you’ve been on the testing waiting list for a long time. Feel free to hit me up in the comments, or on twitter, if you’re interested in testing sometime soon. (Or if you expressed your interest a long time ago and are becoming irate)

The Plateau

I have to admit, I’ve been feeling a bit wore out lately. I haven’t worked full time on a game for many years, and it can be exhausting. No matter how much you love a project, it will always go through ups and downs.

I guess I would say that I’ve reached a new plateau. There’s a certain amount of satisfaction mixed with depression that hits whenever I hit one of these new plateaus. In one sense, the game is clearly better than it’s ever been, but it’s also clear how much I could still improve things. Reaching one plateau means I now have to plan the route to the next plateau.

I’ve already taken some of those first steps though. One of the biggest ones was making this overhaul to the panel interaction method. I had been putting that one off for a long time, as there were still so many easy wins in sight on the puzzle design. Now I have migrated everything over, and the puzzle design challenges seem daunting in comparison. I don’t lack for ideas, but I do lack somewhat for the energy.

(diagram from The Human-Computer Interaction Handbook)

In the diagram of flow state, I’d say I’m more in the frustration section than the fiero section. I feel a bit overwhelmed and stymied. I’m sure I’ll get back into the zone soon enough though.

52. A New(?) Interaction

So, after much deliberation and gnashing of teeth, I have finally begun…

…to write a new devlog post…

I kid I kid.

I’ve finally begun overhauling the way in which the player interacts with panels…to be the way it was when I first started building the game.

The “new panel system for the game

The visuals are a bit WIP, but I do think I want to adopt the look of the walkaround panels for these starting tiles, as they will mostly function the same way. The player has to stand on them to see the puzzle or interact with the starting tile, and clicking the starting tile or pressing the spacebar will depress it. Depressing the tile, in this case, submits the current state of the panel for solution checking.

Way back in 2015 when I first started working on Taiji, in order to create a simpler interface for interaction, I adopted a modal system wherein the player would walk up to a tile in front of each puzzle and press a button in order to be put into “puzzle mode”. In puzzle mode, their normal walking controls would instead move around a cursor on the panel (ala Tetris Attack, Lumines, and many action puzzle games).

The original panel system for the game (apologies for the mouse cursor)
(character art by @martin_cohen)

Obviously I’m joking somewhat about the new system being exactly the same, but it is an interesting case where I believe when I changed the panel interaction to be free cursor based, with a secondary input controlling the cursor. I may have thrown out the baby with the bathwater somewhat. At least part of the baby.

See, the main benefit I can get by moving back to this “starting tile” approach, is that I can fit way more panels in a small world area. Panels that would have otherwise physically overlapped, can now be made to be only visible when the player is standing on their starting tile.

Obviously, this was not present in the first version of the panel system, and was instead sort of a “worst of both worlds” approach where the panels had to take up a large amount of world space, and the player couldn’t interact with them unless they navigated their avatar to the starting tile. (To add additional insult to injury, I had separate buttons for entering and exiting a puzzle, and exiting a puzzle before solving would reset the panel.

A second benefit I get with this change is that I can prevent accidental solutions by requiring the player to manually submit the current state for checking. Previously, the solution was checked each and every time the player toggled a tile. Because the player will most likely only press the “check solution” button when they think they might have solved the panel, the player and game will only ever be out of sync when the player was actually wrong. No more situations where you’re reasoning your way towards something, only to be interrupted partway through by the sound of the panel being solved.

As a final bonus, which I’m sure no one will care about, it makes the player avatar a bit more important in general navigation and puzzle solving. This fact may or may not be utilized later…

51. Snake Puzzles

Since the last blog post, I finished up revisions on the other areas in the game and sent out a test build to a few people. Still not done getting feedback from that, but overall the game seems to at least be improving. So that’s good news.

Needless to say, there’s quite a number of things that I could write about. But since automated puzzle generation/solving seems to be a pet topic of mine lately for the devlog. I thought I might cover a little bit of how I adapted the automated solver to work for the “snake puzzles.”

There are two main types of panels in the game, if categorized based on how you interact with them. Those are the “toggle” panels, which you click on, and the “snake” panels, which you walk around on. I mostly refer to the snake panels as “walking” panels, but the name still sticks around in the code from the early development days when you weren’t walking on them.

An example of how the snake/walking puzzles work.

In any case, because of the nature of the input method for the walking puzzles, the same brute force method of finding all possible solutions doesn’t really work.

Admittedly, there is probably a much smarter way of doing things than what I chose to do, but since I don’t want to spend too much time on the auto solver unless I really have to, I chose to simply take the approach of feeding the output of the current solver into a separate “pruning pass.” This works well enough, because all the solutions which are walk-able are really just a subset of the solutions that are possible using the click-to-toggle mechanics.

I chose to essentially take the output of the brute force solver and feed it through two rejection passes. One is a broad (and hopefully fast) rejection pass, which will never reject valid solutions, but will still leave some impossible solutions un-rejected.

The above grid represents a 3×5 solution state that we might be checking to see if it could be done by walking. I didn’t draw any symbols on the panel because it would be irrelevant as that part of solution validation is already done by this point.

So we take this panel and feed it into our first rejection pass. This broad and hopefully fast pass simply checks to see if all of the walked tiles (those would be the ones in white in the above image) are part of the same area. Since as the player can only step on tiles which are adjacent to ones they have already stepped on, this is a guaranteed property of all valid solutions.

Obviously, we can see that there are several different white regions, so this solution is not valid. But the question you might have in your mind is how I would go about that in code? Well, since I already have a function to find all the tiles in a given area, I simply look across the panel until I find a single white tile, call the function to find all the tiles in that area, and then I compare the count of tiles found to the total number of white tiles in the solution state. If they’re equal, then we pass it on to the next pass.

If not, we reject the solution as invalid.

int whiteTileCount = 0;
bool isValidSolution = false;
foreach(bool b in currentState)
    if(b) whiteTileCount++;

for(int x = 0; x < width; x++)
    for(int y = 0; y < height; y++)
        if(currentState[x+width*y] && !lockedTiles[x+width*y]) //We only want to look at the area of white tiles
            ArrayList checkedTiles = new ArrayList();
            int num_same_tiles = 0;
            FindAllTilesInArea(x, y, ref checkedTiles, ref num_same_tiles, true);
            if(num_same_tiles == whiteTileCount)
                //Could be possible, so we do further testing, we
                //want to OR the values here, because if any spot
                //on the panel allows the solution to be drawn,
                //it's valid
                isValidSolution = isValidSolution | IsSolutionDrawableFrom(x, y, tempState.Clone() as bool[]);
                //We found a disconnected white area, this in and
                //of itself will exclude this solution from being
                //possible on a snake panel
                isValidSolution = false;
                goto EndOfThisSolution;

So, we've rejected the previous state and now we will move on to another potential solution state (pictured above). This one passes the first test, as all of the white tiles are connected into one area. So that means it it will get passed on to the second phase.

In this phase, we walk through the panel, tile by tile, from all available starting points (the example panel starts in the bottom left), and we mark off each tile as we go through it. When we reach a branch, we follow out one of the branches until we have eaten all of the tiles. If we do not eat all the tiles by following a branch, that means there is a dead end in the panel and it is not walk-able.

Below is a visualization of this approach.

The code to do this is somewhat more complex than the first pass, and involves a recursive function:

public bool IsSolutionDrawableFrom(int x, int y, bool[] testState)
    testState[x+width*y] = false;
    bool returnVal = false;
    if(x > 0 && testState[(x-1)+width*y]) returnVal = returnVal | IsSolutionDrawableFrom(x-1, y, testState.Clone() as bool[]);
    if(x  0 && testState[x+width*(y-1)]) returnVal = returnVal | IsSolutionDrawableFrom(x, y-1, testState.Clone() as bool[]);
    if(y < height-1 && testState[x+width*(y+1)]) returnVal = returnVal | IsSolutionDrawableFrom(x, y+1, testState.Clone() as bool[]);

    if(returnVal) return true;

    foreach(bool b in testState)
        //if we reach this point, we've hit a dead end somewhere, this
        //means if find a lit tile that's disconnected from somewhere we
        //could walk to, then this solution must be untenable;
        if(b) return false;
    return true;

That's pretty much it for it this week. Perhaps next week I'll discuss a spoilery meta-puzzle thing I've been working on lately. Although if you'd follow the development live on twitch, you'd already know about that!

50. Dice Area Revisions and Other Fun Stuff

It’s been too long since I wrote a devlog entry. Mostly this has been because I’ve been doing a lot of nitty gritty puzzle design stuff, and I try to keep the blog posts fairly high level so that people can read without getting too spoiled on specific puzzles. I’ve been working through the checklist for the next test build, which involves time-consuming revisions to most of the areas in the game.

The most recent area I’ve finished revising is the “dice” puzzles. Here’s a birds-eye comparison shot between the area “pre-revision” and after. The right version is the new and revised area.

Left: Old   Right: New and Improved!

You’ll notice that the overall structure of the area hasn’t changed too much, but internally there have been a lot of changes. Both some entire sets of puzzles have been added, as well as some of the earlier puzzles have been cut or moved to other areas.

I thought it might be fun to put this image alongside the previous revisions of this area, so you can see four different versions of the same area side-by-side.

Progress? The earliest version is on the left, and latest on the right.

Needless to say, the area has continued to evolve over the years, and will most likely see more changes in the future. The continuing level of flux is the main reason why it’s all still using prototype graphics. Luckily I feel like things are starting to congeal a bit more, so I should be able to start “arting it up” pretty soon.

There are 60 puzzles in the newest version of the area, although it may change to where the player is only required to solve a much smaller subset to “complete” the area.

Area Completion

Speaking of completing areas, I added a fun little effect that happens when you finish an area. This gives the player a bit more satisfaction at that moment and leaves them with little confusion as to whether they need to do more to finish the area.

Puzzle obscured to prevent spoilers.

I may or may not get it in for the next round of testing, but I’d also like to add a warp that allows the player to warp back to the central hub area after finishing a world.

World-Space Cursor

Something else that I spent an inordinate amount of time on over the past month or so is implementing a mouse cursor that exists in world-space instead of screen space.

This means that when the camera moves, the cursor will be fixed relative to the world. For example. if the player was interacting with a puzzle panel, and the camera moved, the mouse cursor would continue to hover over the tile on the panel that the player was originally pointing it at.

You can see a comparison below, screen-space is on the top and world-space is on the bottom. The mouse cursor is represented by a fairy.

This is good because it allows me the flexibility to move the camera without having to worry about negatively impacting the players experience.

However, since I’ve had some people complain about the possibility of this being disorienting or annoying, I’ve decided to maintain the old cursor system in parallel with the new one, until such time as I decide that the world-space cursor (or the old one) is better and I don’t need the other.

49. Slow Speed: Deep Owls

For the past several weeks, besides working a bunch of Saturdays at the day job, and chopping up a bunch of firewood (I rely on wood heat in the winter), I’ve been busy with some logistical behind-the-scenes stuff on the game. Unfortunately, that means not a ton of progress has happened on the game proper.

The project is reaching the stage where the list of planned tasks is ballooning faster than I can keep up with it. Although I have quite a few new ideas and mechanical changes that I’m excited to implement, I need to address the problems that I already know about before I add any new ones to the list.

Therefore, the next step will be to focus on finishing a test build. It’s been over a year(!) since I last sent the game out to testers. I’ve done a tiny bit of spot testing here and there, but the game just hadn’t changed enough to make a full test worthwhile. There are still large sections of the game that I know how to improve but I just haven’t gotten around to yet.


I also started working on some music sketches, and I’m relatively happy with the initial direction there. I’ve attempted music for the game a few times already but never found anything that really clicked. There are also some pretty harsh constraints on the things I am even allowed to do with the music. I don’t want to spoil things too much, but Taiji can be very subtle with the clues to puzzles so it’s quite easy to accidentally create red herrings while just trying to make things look or sound interesting.

Now I have a few pieces in various stages of completion, but it will be a while before I want to share anything publicly yet.

47. The Greatest Puzzle Generation

I promised in the last blog post that I would write a bit about how optimizing the solution-finder paved the way for puzzle generation.

The good news is that I worked on the game a lot in the past week. The bad news is that I still haven’t gotten the offline puzzle generator entirely working. Since it’s a relatively low priority task, and I wanted to ship another quick build to a few people over the weekend, I set the puzzle generator aside in order to make improvements to the starting flow in two of the areas of the game.

Once you have a puzzle solver, making a puzzle generator is actually pretty straightforward. Really all you have to do is plug in random layouts into the solver until you find some that are solvable.

This is already good enough to generate a bunch of solvable puzzles, but it’s a rather blunt tool. It will generate duplicate puzzles, and it doesn’t tell us which puzzles might be worth looking at.

No Dupes

To prevent duplicates, we could generate puzzles in a way that never produces duplicates in the first place. However, this could mean that for any given stretch of time, we could be stuck in a local minima of uninteresting puzzles.

Finding interesting puzzles usually involves a lot of intuition, but generating them could be considered analogous in some ways to a hill-climbing problem. I don’t want to lean much into the analogy, so I’ll just say that since we are hoping to find interesting puzzles that are not very similar to each other, it is good to be as random as possible.

With random puzzles, the only way to prevent duplicates is to keep track of all previously generated layouts. This way, when we want to generate a new layout, we just keep generating layouts until we find one that we have not used already. Since we are already keeping a list of all solvable puzzles, we can easily keep an additional list of all puzzles tested, and check new layouts against the list.

The only real concern here is a trade-off between memory usage and performance. Keeping the list of all tested puzzles in memory will eventually use a lot of memory, but writing the list to disk and parsing that list over and over could be time consuming.

For the time being, I’ve decided to go with the in-memory approach. This simplifies a few things for now, and I can always write things out to disk later.

I chose to use C#’s built-in HashSet collection type to store all the previously generated panels. The benefit of this data structure is that it should be the fastest built-in type for checking if a certain item is on the list (although I have not profiled this).

Currently, puzzles are stored as several arrays. However, for testing the puzzle generator, I’ve just been generating one of these arrays: the symbols array, which stores any symbols that might be on the panel and is just a 1-dimensional integer array of size width*height. (I use a single dimensional array because I’m relying on Unity’s built-in serialization to save the panels and it does not natively support multi-dimensional arrays. I could take the time to write a custom serializer, but I’ve just been accepting the cognitive overhead of doing x+width*y every time I want to do a lookup.)

An annoyance that I immediately encountered when attempting to store generated panels in the HashSet is that when doing the following:

bool done_generating = false;
    //symbols is an int[]
    //previousPanels is a HashSet<int[]>
    symbols = GenerateNewPanel();
        //The panel is unique!
        done_generating = true; 

previousPanels.Contains() would sometimes let duplicate panels through. That is to say, it would declare that a certain panel state was not in the HashSet when it really should have been.

I would have expected to get hash collision problems, and have panels get rejected as duplicates when they were not, but for some reason the opposite problem arose. I’m not sure why this is. Perhaps there is something funny going on with the implicit call to symbols.GetHashCode() since it’s an integer array (You can find the implementation in the reference source code, but I don’t understand it enough to tell what went wrong). Perhaps I don’t understand hash generation well enough in general.

In any case, I averted my eyes from whatever madness was happening there, and just passed a string in instead and moved along.

One other important thing to consider in my specific use case is that puzzles can sometimes be rotated or reflected duplicates. What I mean is that the following three puzzles are identical, as the solution gets rotated and reflected along with the symbols.

Left: A Panel;   Center: Left, Rotated 90° Clockwise;   Right: Left, Mirrored Vertically;

Checking for these duplicates is really just a matter of comparing all possible manipulations of a generated panel to the HashSet before declaring it unique.

The Cream of the Crop

Once you’ve got a list of unique puzzles, the problem then becomes how to sort through the many generated puzzles to find ones that are interesting.

This is the thing that I have mostly not finished. I began by keeping track of how many solutions any given puzzle had, as generally speaking, puzzles with only one solution are more interesting to me (although not always more interesting to put in the game, for various peculiar reasons) than ones that have several solutions.

However, I ran into a strange bug where the number of solutions is being incorrectly reported during puzzle generation. I spent a few hours trying to track down some fault in my generation code, or in the way in which I was serializing the finished puzzles to disk.

My best hypothesis at the moment for the location of the bug is that it has to do with the  solution validation code. When checking if a puzzle is solved or not, I am assuming that the panel has been completely initialized. This is usually a safe assumption because panels don’t have symbols moving around at runtime (yet?) and because if I move them around in the editor, the panel gets reinitialized when I’m done.

However, inside the puzzle generator, I’m not re-initializing the entire panel when the symbols change (primarily as an optimization). This may be causing the solution checking to fail because some state has not been properly set.

More on that later. I won’t guarantee that I will be back in the next post to talk more about puzzle generation, as I am beginning to hack away at the tasklist for the next real test build(!)

The list is only 11 items long, but they’re big items.

46. Optimizations From Underneath a Woolly Mammoth

farcryprimalmammothHeader Image from Far Cry Primal reveal trailer.

I’ve been super productive the past week or so. I worked on some fun relatively non-spoilery things, so I can actually talk about them (yay!). Be forewarned; It’s all very technical. But if you’re intrigued by optimization or procedural puzzle generation, press on.

I sent a quick build out to a few people the past couple weeks. Less for playtesting and more for overall thoughts. I’ve still got the next real test build incoming eventually, so if you’re on the list of testers and have been waiting a while….

Don’t worry, I see you.

Anyway, the next build will still be a while, as I have to essentially revise every area in the game. This will mostly amount to cutting lots of puzzles. But after that we can do some testing, and see if I cut too much.

Optimizing Save/Load

One of the “not-testers” this past couple weeks unfortunately lost their progress due to a VM crash. I had assumed this was probably a failure of my saving code (as no untested code is perfect) resulting in a corrupted file, but it turned out that there was no save file at all. The game was only saving when you exited the program. I had forgotten that I disabled periodic saves because there was a noticable hitch if I saved in the middle of gameplay.

Most of this hitch is just because there are so many puzzles floating around in the game world (about 460, with only 230 or so being accessible to the player, and the rest just in the scene as WIP areas or puzzles which I cut for now but that might find a place eventually), but I figured there had to be some performance gains to be had, since I hadn’t really written it in the first place with an eye to performance.

Even still, I tend to avoid doing unnecessary optimization work if I can, so my first inclination was to take the saving and just spread it out over multiple frames. The main issue there is that there is a lot of state that needs to be kept track of to resume saving in an iterative fashion. In theory, this is what coroutines are for, a simple way to make any function you have into an iterative function, by allowing the function to return an iterator which contains its own stack contents. Thus far, I haven’t found a good use for coroutines, because most of the time it’s easier to just store the state in a variable or two and manually resume on the next frame. But aha! Here was the chance for the coroutine to shine!

Except naturally, when I put the function into a coroutine, initializing the coroutine took longer than the actual saving did. So my hitch got worse instead of better. Another “nice” side affect was that I could no longer handle .NETs I/O exceptions because you’re not allowed to use the yield statement (required for a coroutine) inside of a try{} block.

I tried to make the function use asynchronous file operations as well, but this had a similar overhead hitch. Better than the coroutine, but I wasn’t making gains here.

I could’ve continued on. Maybe used threads. Maybe created a coroutine/thread at the startup of the game and just leave it always running along and waiting for saving tasks, but instead I took all this as a hint that I was wasting time on API nonsense and I should actually instrument my code a little and do some real optimizations.

Since the save system is currently human-readable, writing the save files naturally involves writing a lot of text to the file. So, it wasn’t a surprise to see StreamWriter.Write() eating up the majority of the time spent saving. What was a bit more of a surprise was realizing that most of the time spent in that function was on converting integers to strings.

Now, be warned, the following code may disturb you greatly, but this is what I was actually doing for the inner loop which writes the state of all tiles on all panels in the game:

int currentValue;
for(int x = 0; x < (panel.width*panel.height); x++)
     if(panel.currentState[x] == true) currentValue = 1;
     else currentValue = 0;
     sw.WriteLine(currentValue); //sw is the StreamWriter we're using

Now it should be apparent why I was spending so much time converting integers into strings. For every single tile on every single puzzle in the game, I’m calling the StreamWriter.Write() command and passing it an integer. This means that every time, StreamWriter has to convert it to a string before it can write it to the file.

The reason I was passing an integer into the StreamWriter instead of the booleans directly is because if I simply passed in the booleans, StreamWriter will output them into the file as “True” or “False”, and wanted to write the panel state as “1” and “0”.

So obviously, I made the simple change to the following:

for(int x = 0; x < (panel.width*panel.height); x++)
     if(panel.currentState[x] == true)  sw.WriteLine('1');
     else  sw.WriteLine('0');

Just this one change got me about a 3x speedup, by avoiding the string allocations and the integer to string conversion. But there’s a few more things I decided to do to make it a bit faster. The first should be pretty obvious:

char[] panelValues = new char[(panel.width*panel.height)+(panel.height)];
int ii = 0;
for(int y = 0; y < panel.height; y++)
     for(int x = 0; x < panel.width; x++)
          panelValues[ii++] = (panel.currentState[x+panel.width*y] ? '1':'0');
     panelValues[ii++] = '\n';

The main change here is that I simply pre-allocate a char[] buffer for the entire string that represents the state of the panel, and only access the file in one call to StreamWriter. The reason to switch to char[] instead of string should be obvious: strings produce more garbage. And since we’re in a managed language, the less garbage the better.

There’s a few details that are not completely self-explanatory though. One is that I’m now iterating over both width and height. This is just an aesthetic change in that I wanted the panel state to be written 2 dimensionally in the file for better human readability. This is also why the size of the char[] gets and additional panel.height added onto it at the end. I do this because I need an additional column of characters compared to panel states, in order to add the newline characters at the end of each row.

As a bonus optimization on saving, for the situations in which I have no choice but to write integers to the file, I wrote a function to convert integers to char arrays. The function is not very general purpose (obviously), but is much faster than whatever StreamWriter was using.

Note: This code has been updated from the original version due to some bugs pointed out by “Steve” in the comments. If you’d like to view the original buggy code. I’ve posted it here: https://pastebin.com/HNNp7Zug 

    private static char[] IntToCharArray(int input)
        short len = 0;
        if(input < 10) len = 1;
        else if(input < 100) len = 2;
        else if (input < 1000) len = 3;
        else if (input  0)
            output[len-1] = (char)(48+(input%10));
            if(len>1)input = (int)(input/10);
        return output;

Although the method of determining how many places there are in the number is pretty dumb looking, it’s super fast. If we wanted to support bigger numbers, we could just add some more lines.

I also did a few optimizations to the loading function. I don’t want to get bogged down too much in the technical details, but essentially I did the same type of thing as I did for saving. I buffer up each line of the panel before parsing it, so as to cut down on string generation as well as calls to the StreamReader.

Procedural Puzzle Generation

So, one other thing that I’ve wanted to work on for a while is improving the tools that I use to make the game. Basically all of the puzzles in the game thus far have been hand designed. However, I’ve made use of a brute-force puzzle solver in some cases.

The puzzle solver worked by using a recursive function. This is a bit complicated, but the important thing to know is that it was very slow. So slow in fact that Unity would kill its own process because I froze the UI for so long.

Since this was a case where I didn’t care too much about the overhead cost of firing up a coroutine, the first thing I did was make the meat of the solver work as a coroutine. That way I could return control to the Unity UI and keep Unity from thinking something had crashed.

I was going to inline the code for the recursive function that iterates over all the possible states of the panel, but it’s too big and unwieldy to be properly readable in this blog’s formatting. So you can look at it on pastebin here: https://pastebin.com/deBHmn0h

A Clever Optimization

One of the biggest performance issues that I was having with the puzzle solver code is that it was an extreme memory hog. This would be bad enough if the code was just executing straight through, but because each recursion of the function was encapsulated in a new coroutine, the memory problem gets out of control pretty quickly. I even ran into a situation (possibly to do with script reloading) where the Unity garbage collector failed to clean up and leaked several gigabytes of heap memory.

The natural solution to this is to change the method by which we traverse all possible states of the panel. Ideally, we would like to change this from a recursive function into a loop, but the way in which we should do that is not entirely clear.

Not to pat myself too much on the back, but when thinking about how to speed this up, I think I made a clever connection. Because the panels are essentially series of bits, we can just think about storing the state of the panel in the bits of an integer. In C# a ulong is a 64-bit integer. This gives us enough space to cover the state a panel with 64 fields in it, or an 8×8 panel.

Importantly, we also can know ahead of time how many possible states there are in a panel. The formula is as follows:

c = 2w×h

Where c is the count of all possible states, w is width of the panel, and h is height of the panel.

Funnily enough, if we store c in binary, it will take a (w×h)+1 bits.

For example, if we have a 4×4 panel, there are 16 tiles on the panel (w×h). By plugging that into our formula we get 216 or 65536 states, which in binary is:

0001 0000 0000 0000 0000

This seems useless, but if we take one less than that, or 65535, we get the following in binary:

1111 1111 1111 1111

Which, if we re-project that as a 4×4 panel where means that tile is on and means that tile is off, is the state in which all tiles are toggled on.


If we then take that number and continually subtract one from it over and over again until we reach 0, we will have covered all possible binary states between. This principle means we can create the following iterative function which will visit all possible states of the panel:

ulong possibilities = (ulong)Mathf.Pow(2, width*height);
while (true)
     for(int x = 0; x < currentState.Length; x++)
          currentState[x] = ((possibilities & (ulong)(1<<x)) != 0);
     if(possibilities == 0) break;


The above code was a bit simplified so that it could be inlined. If you’d like to look at the final complete function, you can find that on pastebin here: https://pastebin.com/5xGi7y5V

In addition to being much more lean on memory, it is much faster. It is also easily resumable with or without coroutines because the state is so simple that we only need to store one variable between runs: possibilities.


Wrapping up, we have done some good optimization work on saving and loading. Additionally, because of our puzzle solver optimization, we’ve laid the ground work towards enabling an offline puzzle generator. But I’ll have to cover that in the next devlog post….

I know. I’m cruel… Thanks for reading. 🙂