Solving the Sigmar's Garden minigame with C/C++, computer vision (OpenCV),
machine learning (SVM), and mouse movements (X11).
Figure 1:
The first image shows a starting game board. The in-game conversation
introduces the game.
The second image shows a computed solution outputted by drawing lines
and numbers on the input image.
The third image shows an information panel containing the axes in the
grid in green and blue, the coordinates for each hexagon, the
extracted features, and the predicted type of each marble.
The screenshots were taken from a Youtube video by Dexbonus.
Video 1: A recording of the program solving 3 puzzles.
INTRODUCTION
Sigmar's Garden is a minigame in Opus Magnum,
the puzzle game developed by Zachtronics.
Sigmar's Garden presents a hexagonal board with different types of marbles and
the goal is to match two marbles with each other to remove them and clear the
board. Each marble represents an alchemical element and there are rules on how
you can match them. Importantly, only free marbles, marbles that have 3 or
more connected empty neighbours, can be used when matching. The full ruleset
as explained in the game can be seen in Fig 1.
The game constantly teases you to win more games. First it requests you to win
a single game, then win 10 games, then win 25 games and so on. This drove me
crazy and I got the idea to make a program that solves them. Using OpenCV and
X11 libraries, the solver screenshots the game, classifies the marbles, finds
a solution, and performs the solution using mouse movements and clicks.
TECHNICAL DETAILS
The project consists of a single cpp-file that is divided into several
sections: a hashset, the solver, the OpenCV section, the X11 section, and a
main section. I started writing the solver in C but after OpenCV was added the
code turned more into C++ and is now a weird mix between them.
The hashset and the solver work together. The solver is a simple recursive
exhaustive search that identifies possible moves and performs a depth first
search over them. Each board state that is explored is inserted into the
hashset as memoization to prevent exploring previously explored states. This
works really well because it is easy to reach the same state multiple times.
OpenCV is used in two different ways. It is used for manipulation of images
and for its Support Vector Machine (SVM) that I used to classify the marble
types. At first I thought that perhaps it is enough to just use simple
template matching in order to classify the marbles but a closer look shows
that the marbles all have slightly different lighting effects depending on
their position in the board. Having used OpenCVs SVM previously I just chose
to use this again.
The SVM is trained on screenshots of the game from Jonathan Blow
and Dexbonus. One
problem that I encountered is that the marbles have different sprites when
they are free or closed. This forced me to add screenshots of games in
progress so that there are samples of metals that are in the free state when
training the classifier.
The hexagonal grid is created by hardcoding the pixel values for the center
and hexagonal width at 720p for reference. Using the hardcoded values a
hexagonal coordinate system can be built using two axes. A limitation this
causes is that all image inputs are expected to be in 16:9 aspect ratio or the
grid might not be properly aligned. Red Blob Games has an excellent resource
on hexagonal grids.
Features are extracted by cropping a 24x24 pixel square from each hexagon.
These are preprocessed by converting the images to black and white, adding a
bit of gaussian blur and then an adaptive threshold filter.
After classifying and solving a game the solver can output the solution in
text, by drawing on the input image as shown in Fig 1,
or in the form of mouse movements and clicks using X11, the common windowing
system for Unix-like operating systems. The idea is that you bind the solver
to a global hotkey that when pressed executes the solver. The solver will then
take control of the mouse and perform movements and clicks inside the focused
window (presumably the game itself, but for testing purposes YouTube or images
work too, assuming they are correctly sized). The solver will press New Game
before it exits.
RESULTS
The solver managed to solve 100 games of Sigmar's Garden with only minor
issues. Most games where solved is less than a second after invoking the
solver. The time to perform the solution is not included in this. Performing
the solution takes several seconds.
A few games took slightly longer than a second to solve, and only one game
took more than 10 seconds to solve. That game also broke the hardcoded memory
limit which was increased by 4x and never reached again.
During the trial there were no errors with classifying the different marbles.
It should be pointed out that all solved games were solved from the beginning,
and I expect that the biggest problem with the classifier is classifying the
free metal marbles in the later game. Another limitation is in the resolution
of the game. The solver could not manage 900p resolution of game, but 1080p
worked. This is because the resolution option in the game is not a simple
scaling.
FUTURE WORK
In the source code there are several comments regarding future and possible
TODO such as some suggestions on improving the hashset, the solving algorithm,
and improving the structure around labelled data for the SVM.
A large improvement would be to remove OpenCV. OpenCV is a huge 100+ MiB
dependency and a massive overkill for this project. The image loading and
manipulating can probably be replaced by stb_image, lodepng, or similar, and
it is possible to write a new classifier relatively simply.
BUILD AND USAGE
Download code with git clone
https://mvidell.se/opus.git and build sigmars_garden using the included build.sh script. On first start it will train the
classifier and save it to sigmars_garden.svm. Try
it using --images on the included training/test
data!
$ ./sigmars_garden --help
Usage:
sigmars_garden [options]
Starts interactive mode, screenshots focused window and performs a solution
with mouse movements and clicks. Recommended to either bind sigmars_garden to
global hotkey or use sleep to be able to focus a window before it screenshots
and performs a solution.
sigmars_garden [options] --images image...
Transcribes the marbles and solves the garden, outputs a solution to stdout
and shows an image of a solution. Will run out of memory when run with a large
amount of images.
sigmars_garden [options] --text
Reads 91 marbles from stdin separated by whitespace in format 'QUICKSILVER
VITAE EARTH SALT EMPTY' etc (case insensitive) starting in top left corner,
reading left to right. Just copy a transcribed image and pipe it in!
Options:
--new-svm Force generation of a new SVM
--old-rules Solves the game with old rules (salt cannot match salt)
--verbose Prints extra info
-h, --help Shows this help and exits
