Single post in Dev Log 204

I wanted to do something a little different today. I'd like to talk about the programmer's mindset in general. How a project goes from initial concept to finished result, with all the steps in between. Before anything else, I will say that the Scour update is in progress, it's just taking a fair bit longer than I would have liked due to Scours being one of the very first features to be implemented in PFQ, and hasn't really been touched since. It's an older code, but it checks out. So I am working on it, but it'll be a little longer. Thank you for your patience. Now on to the story! I was playing a game called Opus Magnum. It's a puzzle game in which you "program" autonomous arms with simple instructions to make a complex machine that performs alchemy. Fantastic game, definitely worth playing. Within that game is a mini-game, designed to give you a much-needed break from programming. Programming is an extremely intensive mental activity, and it's very important to take breaks to prevent burn-out, and the mini-game does just that. It's a Mahjong-like game played on a hexagonal board, where you have to match pairs of tiles to remove them. You can only match tiles that are "open", ie. not surrounded by other tiles. There's other quirks too, such as a limited number of wildcards. The Metal tiles must be matched with a generic "base" tile and even then only in strict order. There's also "Life" and "Death" tiles, which must be matched with each other rather than themselves. Finally there's the "Gold" tile, which is always in the centre of the board, matches by itself without a pair, and usually marks the end of the game as you clear the board. The board is always solvable, but the challenge comes in that often you have several choices for which pairs to match, and matching the wrong pair can lead to becoming stuck as there isn't a free tile to match. After playing a few rounds, I wondered if it would be possible to have a program solve it. A program would be able to simulate moves to figure out what would happen. It could work out which moves would lead to success, and which would lead to getting stuck. This sounded cool, so I got to work. The first challenge was figuring out how to represent the board in code! A square grid would have been easy, you can just use simple coordinates for that. But when your grid is a hexagon, there isn't really a convenient coordinate system for that. Each cell would need to be aware of its six neighbors, to determine if they were empty so that it could figure out if it was playable. I decided to represent the board as a list of rows. This meant that instead of being like this:The board would instead be handled like this:This makes it easy enough to determine left/right neighbors, but up-down would be a little trickier. I broke that down further into the top half and bottom half of the board, shifting the X coordinate differently according to which half the code was looking at, and the problem was solved. Each type of tile was then represented by a letter or number. The element tiles would have their initial as their letter. Metals would have the number indicating their position in the order they must be matched. Simple enough. I can now provide the board as input to the program, by writing out the letters of the board in order. So far, so good. Then I had to actually solve the board. When approaching a problem, there are two possible scenarios: - You know how to solve the problem, or - You can break down the problem into smaller problems. In the second case, you can repeat as many times as needed, until all the pieces individually fit the first case. I didn't know how to solve the board, but I instead worked out how to frame it as a problem I could solve. In this case, I made it into a "path-finding" problem. Bit of a sideways leap there, but it makes sense: - The layout of the board is the "point" you're currently at. - The "destination" is an empty board. - Making a match moves you from your current board to a new board. - Winning the game involves finding a set of moves that leads you on a path to the empty board. There are plenty of path-finding algorithms out there, but many of them didn't really work in this case. After all, each step would remove two tiles from the board, so it wasn't really possible to measure "how close to solved" the board is, all moves are equal in that regard. This means all the "fancy" and efficient path-finders wouldn't be able to handle this very well. Instead, I went for a simpler and more naïve algorithm, the Depth-First Search. DFS basically involves picking a path, and charging straight ahead. If it works, great! If it gets stuck, it backs up until it finds another choice, and charges headlong into that new path instead. Repeat over and over until you find the solution (or run out of paths, but the board is always solvable in this game). I set about implementing this, and by sheer luck the board I tested it with presented its solution relatively easily. Unfortunately, after a few boards, I ran one and it seemed to get stuck. Other boards took just seconds to run, but this one was running for several minutes with no result. In the example illustration above, I showed a hexagon of size 3, but the real game uses one of size 6, and there's a total of 53 tiles to be removed. As they're removed in pairs (except the Gold tile), that's 27 moves to win. Sometimes you'll have only one option for a move, but more often than not there'll be several options available to you. Even if we assume there's only 2 moves available at once, that's still 2²⁶ paths - that's 67,108,864 options to check, and the real number was much, much higher! Of course the program will stop if it happens on the right solution, but if it keeps taking wrong paths, that can take a very, very long time! Clearly something had to be done. Until this point I hadn't really considered what order to check paths in, it just picked one and went with it, exploring all options. After adding some debugging code so I could see what paths were being taken, I noticed that the program was using a Wildcard very early in the game, which led to it getting stuck when the Wildcard was actually needed, very late into the game. It was trying so hard to get to the solution, but it would need to evaluate billions of game states before it realised, maybe it shouldn't be consuming that Wildcard so early. In this case, the solution was to add a priority system. Before picking a path, it would sort the options based on the move being made. Moves that didn't use a Wildcard would be prioritised over moves that did. This worked well, because most of the time a Wildcard would only actually be needed if you were close to being stuck. This fixed the issue for that board, and it solved in seconds again. This ran happily for a few more boards, and then it got stuck again. Back to debugging, I found that in a rare case, all of the tiles of a particular type were "playable" at the same time. This meant that a total of 28 ("=8 choose 2") moves were available for that tile alone! And as many of them led to similar situations, it was having to check the same boards quite a lot of times. This is because I hadn't implemented any kind of memory of where it had already checked. I had just assumed that different moves would lead to different boards, but this is quite obviously not the case. If you have two moves available, independent of each other, doing A then B would lead to the exact same result as doing B then A. And if "A then B" was already determined to lead to failure, then there would be no point in even trying "B then A" since we already know the outcome. This turned out to be fairly simple to solve, thankfully. Just remember every board that has been checked. Since the program stops when the solution is found, if we ever encounter a board that has been encountered before, then it must be a failure and so we can just skip straight to the next option. This "pruning" was the real time-saver, and after that I had no problems with the program taking too long to solve boards, even after solving hundreds of them.

---

This is quite typical of the development process. You have a problem, you throw together an attempt to solve it. At some point, it'll start to work, until it doesn't. When it breaks, you figure out why it broke and how to solve it. Eventually, it'll either work perfectly, or it'll work well enough that it either doesn't break, or nobody notices it breaking. Programming can be a very intimidating thing, but if you're interested in getting started, then the best advice I can give is get started. The hardest part of any project is the "figuring out how to start" phase. And the best solution is to just do something, and fix it when it breaks. Eventually you'll go back and make the start better, but so long as it works you're all good.

---

So that was step one. I had a program that I could tell what the board looked like, and it would tell me what sequence of moves would let me clear it. But I wasn't done. Step two was simple enough. I fed the sequence of moves into another program that would move the mouse and click on the appropriate positions to actually solve the board automatically. Saved me having to do it myself. No issues there. Step three was the real challenge: I wanted to have the program figure out what the board was, without me having to tell it. This was a challenge I wasn't prepared for! But I just applied the process of breaking it down until I could in fact solve it. My first attempt at this was to get the images from the game files, but unfortunately they weren't simple sprites like I had hoped. They were made of various layers to produce a beautiful visual result. So no luck there. My second attempt was to grab a section of the tile from the screenshot, and match it against a "database" of tiles. If it didn't recognise a tile, it would show it to me and I would tell it what it is. The idea being, eventually it wouldn't need to ask any more. This also failed, as it would be asking me for tiles I'd identified several times already. Turns out, the tiles had some subtle variations to make for a beautiful aesthetic. Unfortunately, totally impractical for my attempted solution. Time to break out the big guns. Each tile has a unique symbol in its centre. I reasoned that if I could identify that symbol, I could identify the tile. So step one, Edge Detection. This is an easily solvable problem, after a quick Google! For each pixel of the tile, compare its brightness to the eight surrounding pixels. Recolour the current pixel according to the total difference. This results in a dark grey image, but the symbol in the cell would appear very bright, surrounded by an almost black edge. Then came the challenge of figuring out which symbol had been found. Due to the game using nice graphics, with fancy lighting effects, every symbol matched was subtly different. This is something I had never had to solve before, and I had no idea how to break it down! But Google had my back. The algorithm I wound up using was "Peak Signal-to-Noise Ratio". I don't know what it's for, or how it works, but I did work out how to apply that to an image. Since the image was already grey, it didn't have colours - it had "intensity". This could also be compared to the "amplitude" (strength) of a signal. The "signal" would then be the sequence of pixels. I implemented the maths involved - barely understanding any of it - and ran a test. I had an example of each symbol that I had identified manually, and the code would run this PSNR algorithm against each one. Where the images matched, that would be "Signal", and where they differed, that was "Noise". Peak Signal-to-Noise Ratio, therefore, would be the image that had the most matching and the least difference. And there we go! The reference tile that was the closest match for the tile being examined, was the tile! So I chained the programs together: identify, solve, complete. I set it running, and it ran for hours, solving hundreds of boards, completely automated with no mistakes. That was incredibly satisfying. Seeing the results of my work come together was the best feeling I'd had in quite some time. ... I still don't understand how PSNR works, but it didn't matter. It worked.

---

I hope you found this interesting to read. If you did, let me know! And if you didn't... also let me know so I know not to do this again :p I just thought it might be interesting to share "the developer mindset" through a thing I did. Dev Log Discussion