42. Non-Uniform Tiles

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.