Werden wir Helden für einen Tag

PIKR-033 is released and some thoughts

Posted on Jul 23, 2024 by Chung-hong Chan

This is the sequel of my previous blog post on creating a Picross aka nonogram video game.

Previous on this blog: My recent spiritual retreat: Writing a video game

The game PIKR-033, my first game, has been released on itch.io. It is available for free. And this is the only promotion I will do for this game. This game is my therapy and the therapy is now done. That’s the most important part for me. And now, I will talk about the development like I did previously.

At first, I thought that how hard can it be to implement a Picross game. The implementation of the game is actually not that difficult. But the difficult parts of game development are not just about programming. I also do not want to spoil the game too much. Sorry about the cryptic writing style below.

Maths

First, there are many Math problems related to Picross which I was struggled to solve. And it showed my lack of mathematical skill.

The simple Math question is about the number of solutions. I did not know what it is possible to have more than one solution for a puzzle. One example is the 3rd stage. You might wonder why the puzzle is so ugly. It is because the original puzzle for that one has two solutions. Partially because of this, I decided to copy the puzzles from various Mario’s Picross games. Another reason is that I don’t have the artistic talent.

Another math problem that I was struggled with is to derive a way to rank the difficulty of all puzzles. I derived a way to calculate the total number of possible ways to play a row or column. Suppose a row is 5-unit long. And the hint is just: [1]. There are five possible moves: [1,0,0,0,0], [0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,0], and [0,0,0,0,1]. For some hints, there is only one possible move, e.g. for [3,1], the only possible move is [1,1,1,0,1]. For a 5-unit long row, the most difficult hint is [1,1] because it has 6 possible moves: [1,0,1,0,0], [1,0,0,1,0], [1,0,0,0,1], [0,1,0,1,0], [0,1,0,0,1], [0,0,1,0,1].

So, the question is given the row is \(w\)-unit long and the hint \(H\) is a vector, how to count the total number of possible moves?

Now I have the answer ¹. But I struggled with this combinatorics problem during my train ride from Munich to Salzburg when I traveled for the useR! conference. And I could not quite figure out the answer. It took me quite sometime to solve it.

2024-07-24: Updated See Below

There is still one algorithmic issue I am still struggling with, which is about the “partial matching” of hints. Currently, PIKR-033 can only do complete matching of hints. For example, if the hint is [2,2] for a 5-unit row, when I play the row as [2,2,0,2,2] both 2 would be highlighted. However, when I play the row as [2,2,0,0,0], nothing is highlighted. It would be great to be able to partial matching and the first 2 in the hint were highlighted. For simple cases, it is easy. But it quickly becomes difficult for more complex cases. In fact, I asked about it on Mastodon. Maybe I think too much. It sounds easy. Perhaps in the future, I would implement this.

Difficulty

Again, about difficulty. My original reference point for the game was Mario’s Super Picross (SNES). In it, it is possible to Game Over if the player made too many mistakes. The early version of PIKR-033 was also like that. Instead, my wife’s baseline is Jupiter(ジュピター)’s Picross games and those games are in the category of cozy game. She told me she enjoys playing Picross games in a chill, relaxed way. I think that’s what modern players would expect and therefore I made it impossible to game over, just like those Jupiter’s Picross games. One can play PIKR-033 like any other cozy game. However, it is also possible to play for more points (or EH in the game). And I don’t want to talk more about those points because it would spoil the game.

Impactful feeling and smooth control

One of the subgoals for PIKR-033 was to have the so-called “impactful” feeling. What’s “impactful” feeling, you might ask. Some Japanese game makers are quite well-known for this, e.g. Capcom or its offshoot PlatinumGames. The challenges for PIKR-033 to have that impactful feeling are the puzzle game format as well as the retro appearance. But I think the sound design and certain visual display should have delivered such feeling.

Another issue is about smooth control. I have watched too many AVGN episodes to know how frustrated it is to play a game with poor control. But man, programming a good control is the most difficult part for this project. It required a lot of experimentation and adjustment. In the end, I did not use the internal input repetition mechanism provided by love2d to make the input smooth. If you want to play the game in the really “impactful” and smooth manner, it would be nicer to play the game with a joypad. Having said that, keyboard is still supported.

For the input, my baseline, again, was Mario’s Super Picross. Compared with the newer Picross games, that input scheme is brutal. For example, after crossing a box and then you paint that box incorrectly, it counts as incorrect. For newer games, this move is protected. Again, I switched to this new input scheme to match the modern experience.

Nudging players to try “new things”

I argue that PIKR-033 is not just a Picross game. I added something I like in it (no spoiler). Yes, Picross is the main course. But there are other side dishes. Even for the Picross game, there are some new mechanics to make the game (in my opinion) fun.

My wife is the first person to beat the game (not even me). Her first test play (which took her 10+ hours in several sessions, and I observed and took notes) run was quite important for the development of the game. For the first few dozens of stages, she did not even want to try those new mechanics. I also did not want to force her to use those new mechanics.

Unlike old SNES games which players would have to discover these mechanics (or even must read kōrya kubon to know what’s going on), newer players need more hand-holding. They have so many choices, when it comes to digital entertainment. They can easily switch to another game, when they are stuck in a game. So, 90s cryptic games also have no market.

In between each session, I modified the game to nudge the users. Game is a medium for communication. In the end, she realized those new mechanics are fun.

Respect the (test) players

My wife is the test player of the game. My coworker Paul also reported some technical issues of the original prototype. I found it super important to listen to test players’ feedback. As the programmer and “designer”, it is very easy to believe all design decisions are correct and blame the players.

I read the memoir of Sid Meier when I was developing the game. Sid Meier recalled the development of the probability display in the modern game Civilization Revolution. The development team has to break many probability rules to fit the player’s perception. For example, the players might complain as in the Gambler’s fallacy: My previous fight had a 1/3 chance to win and I lose. Now, this fight has a 2/3 chance to win but I am still losing. The team team had to adjust the probability to make it not completely independent. The important message is, how the players perceived that probability is more important than what that probability in science means.

During the development, I talked mostly to my wife about the game, as well as what she found interesting about the game and other puzzle games in general. Those feedback was really important, because otherwise the game development would be a close loop.

Acknowledgements

I would like to thank my wife for the support as well as the help during the development. My coworker Paul also helped me with some technical issues. My collaborator Tim for voicing out his interest in the game.

Based on the nonogram aka picross invented by Non Ishida and Tetsuya Nishio. The visual aesthetic is based on TIS-100 by Zachtronic. Many puzzles are extracted from Mario’s Super Picross (SFC) and Mario’s Picross (GB) by Nintendo Co. Ltd.

The game was written in the Lua programming language. Powered by LÖVE.

Update (2024-07-24)

In the original post, I said I could not solve the issue of partial matching of hints.

For example, if the hint is [2,2] for a 5-unit row, when I play the row as [2,2,0,2,2] both 2 would be highlighted. However, when I play the row as [2,2,0,0,0], nothing is highlighted. It would be great to be able to partial matching and the first 2 in the hint were highlighted.

This is now solved and I have updated the game on itch.io with this feature.

If you are interested in the algorithm. That’s a modified version of the Smith-Waterman Algorithm.

Let’s take a more difficult example: Suppose the \(h = [2,1,3,4,1]\) and you have played \(x = [3,1]\).

Just like the original algorithm, the first step is to determine substitution matrix and gap penalty. For the game, I just replace them with the equivalent concept of “matching bonus” \(a = 3\), “mismatching penalty” \(b = -1\) and “gap penalty” \(W = -1\).

The second step is to create a scoring matrix \(M\) and its size is \(\|x\| + 1 \times \|h\| + 1\). This matrix is zero-indexed (but not \(h\) and \(x\)). Then, we fill the zeroth row and zeroth column with zeros, i.e.

\[M = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & . & . & . & . & .\\ 0 & . & . & . & . & .\\ \end{bmatrix}\]

And then, we fill the remaining cells from left to right and top to bottom.

\[s_{ij} = \begin{cases} M_{i-1,j-1} + a & x_i = h_j \\ M_{i-1,j-1} - b & \, \text{sonst.}\\ \end{cases}\] \[M_{ij} = \max\begin{cases} s_{ij},\\ M_{i-1,j}-W,\\ M_{i,j-1}-W,\\ 0 \end{cases}\]

The math is insane. But it can be thought about with an example. Let’s say \(i = 1\) and \(j = 3\). First, \(h_3 = x_1\). In this case, we just assign \(s_{ij}\) with the value at the upper corner of \(M_{ij}\) and add \(a\) to it. Otherwise when they are not equal, we minus \(b\).

Then, we find the biggest values among these four cases: \(s_{ij}\) is clear. The next two cases are just the value left and above \(M_{ij}\) minus \(W\). And up to \(i = 1\) and \(j = 3\), \(M\) should look like this.

\[M = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 3 & . & .\\ 0 & . & . & . & . & .\\ \end{bmatrix}\]

Repeating this process for the rest of the matrix, we will get

\[M = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 3 & 2 & 1\\ 0 & 0 & 3 & 2 & 1 & 5\\ \end{bmatrix}\]

Initialize a result vector \(g\) with zeros and has the same length as \(\|h\| + 1\), i.e. \(g = [0,0,0,0,0,0]\). For the sake of simplicity, let’s set this vector also as zero-indexed.

First, we find the position with the biggest value in \(M\). In this case, that’s \(i = 2\) and \(j = 5\).

Now, the so-called “backtracking” step. We compare the value in \(M_{i-1,j}\) (i.e. at the left) and \(M_{i-1,j-1}\) (i.e. at the upper corner) ². If the left value is larger, we set \(g_j = 0\) (red case below). If the upper corner value is larger, we set \(g_j = 1\) (green case). If both of them are zero, we stop backtracking. But if it is not the case, we “move” to the position of the larger neighbor and repeat.

\[M = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & \color{red}{3} & \color{green}{2} & 1\\ 0 & 0 & 3 & 2 & 1 & \color{green}{5}\\ \end{bmatrix}\]

And in the end, we will get \(g = [0,0,0,1,0,1]\). Then we remove the first element to get the final result \(g' = [0,0,1,0,1]\). And the answer is correct. With dynamic programming, this algorithm is just \(O(\|h\| \|x\|)\).

It’s a bit annoying to implement this algorithm in Lua. But I did that and now we have partial matching of hints (e.g. the second row below).

Update (2024-08-06)

Some players (on itch as well as my coworker Paul) reported that the Smith-Waterman Algorithm is not correct in some cases. After my investigation, I have also come to the same conclusion.

Using the same notation as above, suppose \(h = [1,2,5,2,1]\) and you have played \(x = [1,2,3,2]\). The expected output would be \([1,1,0,1,0]\). However, it will give an \(M\) like this:

\[M = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \color{green}{3} & 2 & 1 & 0 & 3 \\ 0 & 2 & \color{green}{6} & 5 & 4 & 3 \\ 0 & 1 & 5 & \color{green}{4} & 3 & 2 \\ 0 & 0 & 4 & 3 & \color{green}{7} & 6 \\ \end{bmatrix}\]

And \(g' = [1,1,1,1,0]\). Not nice.

Instead of being smart to use an efficient algorithm but not correct 100% of the time, I figured the best approach is to be less efficient but correct 100% of the time. After all, the maxima of both \(\|h\|\) and \(\|x\|\) are just 10. The number of possible outputs for \(g'\) for 10 is just \(2^{10} = 1024\) (or you can think about it as all possible binary numbers with 10 bits). When using bruteforce to match all possible combinations, the worst case of \(O(2^{\|h\|} 2^{\|x\|})\) is still manageable (1,048,576 comparisons) for this game. Some slight optimizations can prevent this worst case. For example, we do not need to iterate through the entire space of \(2^{\|h\|} \times 2^{\|x\|}\) to get the answer. Early stopping is possible when the best answer is found. In this case, I sorted all \(2^{\|h\|}\) possible binary numbers by the total number of ones and started from the highest one. This ensures that we will always hit the global maximum. Another way to improve the performance is to precalculate many things and make them look-up tables, e.g. all the possible binary numbers.

This is the end result and I have updated the game on itch. Please update and enjoy!

Well, if you click this, I assume you are interested in the answer. The answer is this: \(C(w + 1 - \sum\nolimits_{h \in H} h, \| H \|)\), and \(C(n, r) = \frac{n!}{(r!(n - r)!)}\). ↩
For the original algorithm, we also need to check the upper value, i.e. insertion of a gap in \(x\). But it is not appropriate for this application. ↩