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;
while(!done_generating)
{
    //symbols is an int[]
    //previousPanels is a HashSet<int[]>
    symbols = GenerateNewPanel();
    if(!previousPanels.Contains(symbols)) 
    {
        //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.

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.

Header 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';
}
sw.Write(panelValues);

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);
            len--;
        }
        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 = 2^w×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 2¹⁶ 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 1 means that tile is on and 0 means that tile is off, is the state in which all tiles are toggled on.

1111
1111
1111
1111

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)
{
     possibilities--;
     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.

TTFN

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. 🙂

 

Still can’t talk about this.

Can’t say too much about what I worked on this week, but it’s pretty cool I think.

These past few days have been relatively productive, but in a way that hasn’t really changed anything about the actual game if you sat down to play it. Recently it’s felt like every time I go to add something, I’m needing to clean up a lot of cruft first. I suppose this is normal for this stage of development, but it does feel a bit like wading through mud from time to time and has been slowing down development progress. Furthermore, although it might be appreciably nicer to work with the code after a good long day of refactoring. It’s boring as crap to talk about what I did.

I finished up the meta-tiles in the manner I mentioned in the previous post. Getting them to work alongside the dice face mechanic and the walk-able puzzles was fairly straightforward. Mostly because of the choice I made to use meta-tile numbers for all of the run-time puzzle calculations. The current implementation of the area search feels like it’s a bit inefficient, but it works so I’m happy enough.

Part of how I managed to get everything working relatively quickly is that I created a nice little helper function that looks up the meta-tile for any given (x,y) position and sets it to a certain state. This means most of my old algorithms work just the same; I can just drop in this setMetatile() function in place of my old calls to set individual tiles, and I’m good to go.

I’m still using the connections-based approach for the puzzle editor, but I may end up changing that as well. As I mentioned before, although switching to editing the meta-tile numbers directly might make building puzzles a bit more time consuming, it would also give me higher precision and allow me to implement some puzzle types that I don’t currently have. So, it’s probably worth it.

There are some other interesting details that came alongside the implementation for the walk-able puzzles, but I don’t want to spoil everything!

As I’ve said previously, I mostly implemented these metatiles because it felt like something obvious that was missing. This is a bit strange feeling, because I don’t have any immediate plans for puzzles involving them. I do hope to find some, but usually I don’t do this much work before I even know if the idea is going to bear fruit.

Normally, I use a process for prototyping new puzzle ideas that is intended to reduce the amount of wasted implementation work as much as possible. I start with prototyping ideas on paper. Just drawing stuff out in a notebook of graph paper. Then, if I see some potential there, I will usually implement a bare bones version of the mechanic into the game, without much thought for what it looks like. In this case, I think the mechanic itself ended up being just complex enough that it was pretty hard for me to paper prototype it, and just visual enough that it was difficult for me to digitally prototype it without doing a fair amount of implementation work.

I think there’s a similar situation in my mind with any puzzles that have to do details in the visual element of the game.  Those kinds of visual puzzles tend to be rather subtle, and as long as the game has programmer art, there are only so many ideas that are going to come to my mind. Simply enough, the elements necessary to build the puzzles just aren’t there yet.

In any case, I hope to find some good puzzles.

P.S. I still have yet to upload the higher-quality archives for the past 4 development streams, including two I did in the past week. So look forward to that before too long.

This week, I’ve been working on implementing a feature that I have wanted to have for a long time: puzzles which feature tiles of non-uniform size.

Thus far, all of the puzzles in the game have been built around fixed-size tiles. It’s a bit hard to explain the difference in words, so here’s a visual example:

The left image is how all the puzzles in the game currently operate, as a grid of uniform tiles of all the same size. The panel on the right is a mock-up of what I want to do. Essentially, I want the capability to make puzzles where tiles can be “connected” together into larger groups, or meta-tiles. Doing this requires a bit of ingenuity, both within the tech and from a graphic design perspective.

Since I’m still keeping the grid-based setup, the problem is much simpler than it could be. 

As far as the artwork is concerned, we can cover all of the shapes we might want by subdividing each panel tile into 4 smaller sub-tiles, each of which can be one of three different graphics:

This is the most economical choice from an asset design perspective, because although there are more variations required than the 3 sub-tiles, they can all be expressed simply by rotating the tile images.

As simple as the art is, the code is kind of complex, both in determining how to rotate the sub-tiles, and because there is an additional “corner” case (Get it?). 

For example, with the basic approach, in which you just check the neighboring tile and see which ones are connected, if you were to have a large connected block of four tiles, you’d end up with something like the left-hand image below:

Notice that each tile is drawn as a single-width corner, and so we end up with a hole in the middle of the area. This might be desirable in some cases, but here it’s really just an accident. 

Luckily, this isn’t too difficult to resolve. You simply check, for each tile, if it is connected so as to form a corner, and then you additionally check if the tile diagonally opposite that corner is also connected to form a corner, and if it is, you just change the inner corner graphic. This technically requires a fourth sub-tile for the inner corner, which is just a solid color.

Data Structure

One of the other challenges was deciding upon a data format to express these meta-tiles, and additionally, how I would interface with that format in the code.

There are two approaches that initially came to mind, both of which have their costs and benefits.

1. Add four booleans (true/false values) to each tile, for each of the four cardinal directions, to indicate whether or not the tile is connected to its neighbor along that direction. The benefit here is that checking for connections is simply a matter of checking a value stored alongside the tile. However, it is rather wasteful of memory, with four additional entries per tile. And furthermore, for each connection, there are two values, leaving the possibility that the connection values could end up out of sync. (This can be resolved with reference types though, as I’ll explain later)
2. Create an array which stores the connections between tiles as booleans. This is memory efficient, as there is no data duplication. However, it is somewhat cumbersome to work with in the code, without doing some additional engineering. (The panel is made up of one 2D array, and the connections are an additional 2D array, but it is somewhat hard to make direct comparisons between the two arrays.)

I decided to go with the second option to begin with. Both options have their upsides and downsides, but the memory efficiency of the second option seemed most appealing to me for whatever reason.

Notice that both approaches are thinking about properties of the individual tiles which make up the meta-tile. Each tile has connections to its neighbors. This approach has some flaws which will come back to bite me in a bit, but this is what I chose to go with first, and I think it’s important to document my process as it happens.

My general strategy when doing any engineering work (and sometimes design as well), is to do the simplest dumbest thing that seems like it will work, and clean it up later. This means I may just implement the first solution that comes to my head. This is a good approach because, most of the time, unless a problem is utterly trivial (or you have implemented a similar solution many times before), you don’t really understand the problem well enough before you begin. The likelihood of anything you think of before you start coding being the right solution is pretty close to zero.

So get your ego out of the way and just start coding!

(Relevant:)

It’s a bit difficult to explain the way that I structured the data, but since I went through the trouble of creating an editor interface for the connections, I’ll simply show you what that looks like, as it’s a useful way to visualize the data structure of the panel in terms of how it relates to the connections.

In the editor interface shown above, the actual tiles of the panel are represented by the ☐’s. The connections between the tiles are represented by the checkbox buttons.

In terms of the data layout, the panel state is stored as a 3×3 array of booleans, and the connections are stored as a 3×5 array. I need the additional rows. as each tile has vertical as well as horizontal connections.

…

Fun fact: For any particular panel of dimensions W¹×H¹, the formula to determine the size of the array necessary for storing the connections between tiles is

W²=W¹; H²=(H¹*2)-1.

Second Fun Fact: Every other row, I don’t use the last horizontal entry in the row, so I technically do waste a bit of memory.

…

As I mentioned earlier, because of the unusual data layout, it is not exactly obvious, for any given tile (x, y) on the panel, which (x, y) to look at in the connections array. This is one of the flaws of the tile-centric approach.

Ultimately I ended up writing a helper function:

bool isConnected(int x, int y, Direction dir)
 {
     if(dir == Direction.E) return (x < (width-1) && connections[x+width*(y*2)]);  
     if(dir == Direction.W) return (x > 0 && connections[(x-1)+width*(y*2)]);

     if(dir == Direction.N) return (y < (height-1) && connections[x+width*((y*2)+1)]);  
     if(dir == Direction.S) return (y > 0 && connections[x+width*((y*2)-1)]);

     return false;
 }

This function gets called a lot, and is pretty computationally inefficient. One solution would be to cache the results of these calculations and store the results alongside each tile. This is equivalent to option #1 from earlier, however if the stored values were only references to the values in the connections array, this would avoid the problem of the data getting out of sync.

Highlighting Inefficiency

The next thing we have to resolve is toggling the whole connected piece when the player clicks on it, and handling the highlights when the player hovers over the piece.

Since the code that deals with the player clicking on tiles still works with individual tiles, rather than the whole connected group, when the player clicks on any given tile, we have to do a search to determine all the tiles connected to that tile. From a technical standpoint this is somewhat non-trivial, but it is analogous enough to the issue of finding all the tiles within a colored area, that it was a problem which I’d already solved. The only difference here is the criteria by which the tiles are considered “connected.”

So, we do the exhaustive search for all connected tiles when the player clicks to toggle. Although this works well enough when we’re toggling, we also need to highlight the tile when the player mouses over it. (Notice in the above GIF that the tile highlight is still isolated to the individual tiles, and doesn’t cover the whole connected group)

We could do the same search that we were doing when toggling a tile, it would technically work, but doing it every frame seems a bit wasteful. Of course, we could do some basic optimization and only do the search when we really need to, when the player has moused over a new tile.

This is all fine, but something started to smell funny to me. I didn’t like how wasteful things were getting computationally. After thinking about it for a bit, I came to a more optimal solution.

Until I got fairly deep into the implementation, I had been thinking about this whole problem from the bottom up. I was thinking only about the same uniform tiles I always had, rather than the meta-tiles. A meta-tile, as far as I was concerned was just an emergent result of a system which allowed tiles to be connected to each other.

But what if we think of a meta-tile as it’s own entity? If we do, then our problem of finding all the tiles that make up a meta-tile suddenly becomes trivial.

Additionally, because the layout of the panels in the game never changes in real-time (thus far), I have the luxury of baking down any complex calculations that have to do with the panel layout. In this case, I can just bake-down the meta tile groups at startup.

In the baking process, I iterate across all the tiles on the panel and store an integer for each tile, denoting which meta-tile group it is part of. For example, if the first tile I check is connected to form a meta-tile, I will mark all of those tiles with a meta-tile number of 1. The next meta-tile I find, will have a meta-tile number of 2. And so on. 

The numbers don’t really matter as long as they are the same for all tiles within the same meta-tile group. 

This means I only have to do the exhaustive search at startup, and from then on, whenever I need to find all tiles that are connected to a current tile, I can simply compare the current tile’s meta-tile number to all the other tiles on the panel, and if the numbers match, the tiles are connected.

(This is actually a simple enough way to handle connected tiles that I may choose to do away with the connections array. Additionally, opening up the ability for overriding the meta-tile group manually would allow for some additional things, such as having tiles that are not physically connected, but can only be toggled in unison.)

Fixing the Mechanics

Getting the gameplay mechanics working again is somewhat more complicated, as I have to combine the idea of areas connected by color with the idea of multiple “tiles” being connected together into one big tile. This shouldn’t be too difficult though, as we just have to add meta-tile awareness to our normal area search. Still, I didn’t get to it this week.

So…to be continued.

Optimizations

In the process of doing all of this, I ran into some performance problems. This is somewhat to be expected. Previously, each puzzle panel tile required 3 sprites, but under the new system, there are 9 sprites per tile. (I have the four corner sprites both for the fill part of the tile and the outline part, as they can be colored/enabled separately. Additionally, there is a background color sprite for each tile.)

One of the obvious issues was a huge uptick in the time spent on start-up. This has been a bit of an issue for some time already, but it really just skyrocketed. I try to keep the startup time down to less than 5 seconds (Ideally it would be much faster than that, but there seems to be a certain amount of overhead in Unity that is simply unavoidable), but after making the changes to allow for the increased graphical flexibility, the start-up time ballooned past 10 seconds. 

This may not seem like a lot, but I like to keep my iteration times as fast as I can. This desire for instant feedback (or as close to it as possible) is why I took the time to get a live updating feature for the puzzle panels.

The overhead came because I was initializing every single puzzle panel in the game at startup. This involves not just spawning objects for each panel, but for every single tile on every single panel. As many of you who are familiar with Unity may know, spawning new GameObjects is one of the more expensive things you can do. Unfortunately, with all the additional GameObjects involved in the new sub-tiles, there were just too many objects being created at start-up for it to happen in a reasonable timeframe.

So in order to reduce the start-up time significantly, the thing that made the most sense was to avoid initializing anything that wasn’t completely necessary. I could have chosen to go right to an object pool system, where I reuse tiles from panels as needed and only spawn a few at a time. But instead, I just chose to go for the simpler method, which is just to check which panels are visible to the player when the game starts, and only initialize those.

Apart from the startup time, there were some other issues with how I was handling control of the colors and images on the sprites. I made the initial mistake of delegating all of that work down to the individual 8x8px corner tiles, but it really made more sense to cluster the work up at a higher abstraction level in the 16x16px tiles. There is a decent overhead to each individual MonoBehaviour component in Unity, so the less you can have of them, the better.

As time goes on, it may make more sense to bring that tile management work all the way up to the level the entire panel itself, but for now this is a good balance between locus-of-control and performance.

There were some additional minor performance issues unrelated to the new panel changes that I nevertheless took the time to clear up. I won’t really go into those here, but it always feels nice when you get things running better.

I’ll be back next week to talk about getting the puzzle mechanics working again. I also need to repair the walking puzzles, cause I seem to have broken the graphics for them.

This week I didn’t spend a ton of time on the game, nor did I add anything flashy. However, I did take some of the things that I learned last week while improving the puzzle panel editor GUI and used them to redesign the editor for my custom animation system.

This was the previous system, which involved using several separate components. Both a master Sprite Animation component, and an additional Sprite Animation Strip component for each individual animation:

Although this certainly worked. It was pretty cumbersome to add new animations or tell what you’re looking at. As you can see, the first Sprite Animation component simply has a flat array references to the other Sprite Animation Strip components. Unfortunately, it is impossible to tell the difference between each animation in the list, because all the duplicate components have the same name. Not to mention, having a bunch of separate components wastes vertical space on irrelevant information, and overall… it’s just a mess.

Here’s the redesigned interface:

Although it is almost functionally identical to the previous system (in fact, this is the same set of animations), you can see that there are a number of usability improvements here. For one thing, each animation gets its own name, this makes things way more readable.

Now, you might ask, why even go through the trouble of writing your own animation system when you could just use the built-in Unity animation system, which surely supports way more that this.

I prefer as much as possible for the code to be doing the heavy lifting on things like this, so the Unity GUI editor and data-driven approach just doesn’t appeal to me. Additionally, although the Unity system is fully featured; for a 2D sprite-based game, it’s just overkill. I’m not doing animation blending, so thinking about the animation as a tree is a strange way to think about it. Essentially, a 2D animation is just a flipbook of frames. That can be represented as a 1D array both in the code and in the interface. If I give each of these arrays an index, this makes it super easy to change an animation from within the code. There’s no need to for me to create a FSM with a state change graph and all that when I could just set an animation index. If I want to change which animation is currently playing. I can just do this:

playerAnimation.index = 0; //Or the index of the animation that I want

And the animation component will just change over to the new animation and continue handling the playback.

Now, it is perhaps a bit cumbersome if I want to think about things in terms of the names of the animations, as the code is not particularly illuminating on this front, but that can either be handled by just adding a comment to the code, or by creating a lookup that maps from the name to the index.

Either way, it just works better for me.

Additionally, as with the Puzzle Panel editor, reducing the overall complexity on both the editor end and the code end leaves me with much more room to add, without having an overwhelming amount of unnecessary complexity. For the time being, the only frame animation in the game is the player’s walking animations (which need to be redone), so I don’t really need more functionality than this.

That may also mean that this was a misappropriation of my limited time to work on the game, but time will tell.

After making the changes to the “dice face” puzzles which I described in a previous blog post, I ended up with a few edge case puzzles which didn’t work under the new mechanic, but were still within the boundary of the game’s subject matter. This meant that I would need to do some extra engineering to keep these puzzles working the same way. This caused me to confront some of the growing problems with my puzzle design tool.

Here’s a screenshot of the old interface:

This is the tool that I use to design all of the puzzles in Taiji. Although it has been perfectly serviceable, it was starting to take up a bunch of vertical space, and there are additionally a bunch of very subtle details which were starting to make it icky to work with on a regular basis. Additionally, if I want to add more functionality (which I do), it was becoming very unclear how I was going to add it, both in the interface, and the underlying code.

So I have done a bunch of under-the-hood work, which although completely invisible to players, allows me to clean up the code andrevise the puzzle designer interface.

This is how it looks now:

Although also somewhat complex, it actually has more functionality than the interface shown above, while taking up a bit less space. (Admittedly, these aren’t the same puzzle, so it’s not a 1:1 comparison, but I don’t really want to take the extra time to grab a better screenshot right now.

There are still some more improvements that I’d like to make, including basic ones like making sure all the input boxes still line up when there are disabled tiles on the panel, but overall I am much happier with the interface and the underlying structure of the code going forward, and I think it will definitely be more amenable to adding new functionality.

You may have noticed that I haven’t been posting updates for the past few weeks. My computer hasn’t been hooked up and so I couldn’t work on the game. Instead I’ve been finishing off a major move.

The house we’ve moved into really should have been cleaned before we moved into it, so it’s been a bit of a challenge to clean thoroughly with all our stuff in the house. So a lot of that has been happening, as well as repairs and general moving stuff. Still hard to relax as most things are not really “in their right place.”

I did finish setting up my computer and desk and did a short test stream earlier this week to see if the internet here was decent enough to use for streaming (in short: it isn’t). So, barring a miracle, if I do any work streams going forward, they will be more of the Starbucks variety that they were a few years ago.

Unfortunately, I didn’t really find the gumption to sit down and work on the game any more than just that short test stream. On the stream, I added a little bit of a color difference for the puzzle panel backgrounds depending on whether or not there are active tiles.

It’s a pretty small change, but it should make panels a bit less confusing for new players. I’m still not 100% happy with the look, but it’s a step in the right direction.

I’m hoping to get some more done on the game in this next week. Still lots to do around the house though, so we’ll see.

Seems like I’m writing these things on Mondays most of the time now…

Didn’t get a whole lot done over the weekend, at least not visibly. Most of the work was under the hood or maintenance. I repaired the puzzles which mix the “dice” and “dot” mechanics, after having changed the way the dice mechanics work. The combined puzzle sequence stills need a lot of work to be enjoyable to solve, but at least the puzzles aren’t actively broken anymore.

I got them working again through a small change to how puzzle solutions are validated. Previously, with the dot mechanic, whenever the color of two dots needed to be checked, the code would use an arbitrary number which specified which color dot we were talking about. (i.e. 60 = blue dot, 61 = yellow dot, 62 = red dot, etc.) The change I decided to make is to have it actually directly compare the color values of the two symbols in question. (Technically I compare an integer hash of the color to avoid the == operator overhead of Unity’s built-in color class) Directly comparing colors has a couple benefits when it comes to simplifying the code and also makes future puzzle possibilities much easier.

I didn’t end up revamping the entire puzzle panel system, because after some further investigation, there are some good reasons that I architected it the way that I did, in spite of the fact that it’s unwieldy at times. The main reason is that I’m relying on the Unity serialization system to save the panel layouts, and certain data formats just serialize more straightforwardly and quickly. One dimensional data type arrays are the most easily serializable format. So, even though it would be more useful to have a single tile structure which stores all the relevant data, including references to spawned GameObjects at runtime, it is a bit more challenging to implement than it would immediately seem.

Furthermore, serialization can get real nasty when dealing with null references, as stated on this page in the Unity docs:

Consider how many allocations are made when deserializing a MonoBehaviour that uses the following script.

class Test : MonoBehaviour
{
    public Trouble t;
}
[Serializable]
class Trouble
{
   public Trouble t1;
   public Trouble t2;
   public Trouble t3;
}

It wouldn’t be strange to expect one allocation: That of the Test object. It also wouldn’t be strange to expect two allocations: One for the Test object and one for a Trouble object.

However, Unity actually makes more than a thousand allocations. The serializer does not support null. If it serializes an object, and a field is null, Unity instantiates a new object of that type, and serializes that. Obviously this could lead to infinite cycles, so there is a depth limit of seven levels. At that point Unity stops serializing fields that have types of custom classes, structs, lists, or arrays.

Since so many of Unity’s subsystems build on top of the serialization system, this unexpectedly large serialization stream for the Test MonoBehaviour causes all these subsystems to perform more slowly than necessary.

I may yet return to make some more of those changes, but you can see that the water is fraught with peril. A good approach would probably be to have two formats, one for all of the runtime code, and one that is used for serialization, but this would also create a bunch of potentially slow startup code every time the game was run in order to translate between the data formats (and there’s already more initialization code for the panels than I really want there to be)

On a humorous note, before some of the changes I made, I had this monstrosity of a line of code:

symbol = litSquares[p.x+width*p.y].GetComponent().transform.GetChild(1).gameObject.GetComponent();

And now, with some data restructuring and a few helper aliases, it becomes the much more manageable:

symbol = tiles[p.x+width*p.y].symbols[0]