Kami 2 Solver in F# - Part 1
This post covers a Kami 2 puzzle solver I wrote in F#. If you haven’t played Kami 2, or its predecasor, I would urge you to check it out on the App Store.
Kami offers beautiful aesthetic, high production value, and wonderful “daily puzzles” feature. But ultimately, it’s fun because of a simple mechanic that requires just the right amount of experimentation to find the solution.
Anyways, a lot of Kami playing goes on at my house. Things were going great until I got stuck on the last few levels.
The game’s makers sell puzzle hints via IAP. So I could just spend a few bucks to get unblocked… but that didn’t seem nearly as much fun as writing my own Kami 2 puzzle solver in F#!
Project Overview
Once you have distilled the puzzle into a colored graph, solving it is actually straightforward. The hard part is actually encoding the puzzle itself.
Solving puzzles and various optimizations will be covered in a future post. For now, I’ll cover the work required to get data.
If I wrote a fancy UI using WinForms or AngularJS, inputting puzzles manually would be error-prone and time intensive. So I needed to automate it.
I could have jailbroken my phone and try to reverse engineer data files. (I guess?) But instead my solver works by just analyzing screen shots from the game. Using some heuristics and a little bit of math, you can reliably extract the puzzle configuration.
Image Processing on .NET Core
The first step was probably the hardest one: how do you read/write images in .NET Core?
On Windows, you would just use System.Drawing and call it a day. However,
as pointed out earlier this year
dealing with images on .NET Core is a trecherous endeavor.
After a couple of false stats trying other libraries, I went with SkiaSharp. Which as an added bonus has some great documentation.
The library is a bit more onerous to work with than System.Drawing,
but once you get the hang of the SKSurface/SKCanvas/SKPaint relationship,
everything is pretty straightforward.
Puzzle Extraction
If you just want to go straight to the code, check it out on GitHub at: chrsmith/kami2-solver. Please poke around and let me know what you think. I’ll go over the more interesting bits here.
Debugging Image
Debugging is hard. Especially with lots of image data.
So rather than writing cumbersome unit tests or logging hooks, I opted create annotated copies of the input images. This allowed me to overlay information and visually check if things were OK. (Of course if this were more than a fun weekend project, both unit tests and logging hooks are always a good investment.)
As for the code, there is nothing out of the ordinary. The only wart is that in
F# you cannot use the use keyword inside of a primary constructor. (Since
the F# compiler has no idea when to actually call Dispose on those objects.)
// Kami2 puzzle image with annotations to aid in debugging.
type AnalysisDebugImage(originalImage : SKBitmap) =
let surface = SKSurface.Create(originalImage.Width,
originalImage.Height,
SKImageInfo.PlatformColorType,
SKAlphaType.Premul)
let canvas = surface.Canvas
let paint = new SKPaint(TextSize = 80.0f,
IsAntialias = true,
Color = kBlack,
StrokeWidth = 5.0f)
do canvas.DrawBitmap(originalImage, 0.0f, 0.0f, paint)
member this.DrawLine(x0, y0, x1, y1, color) =
paint.Color <- color
canvas.DrawLine(x0, y0, x1, y1, paint)
member this.AddCircle(x, y, color) =
paint.IsStroke <- false
paint.Color <- color
canvas.DrawCircle(
x, y, kAnnotationSize,
paint)
member this.AddCircleOutline(x, y, color) =
paint.IsStroke <- true
paint.Color <- color
canvas.DrawCircle(
x, y, kAnnotationSize,
paint)
// Save the image to disk in the PNG format.
member this.Save(filePath) =
let finalImage = surface.Snapshot()
use pngEncodedFile = finalImage.Encode();
File.WriteAllBytes(filePath, pngEncodedFile.ToArray())
// Clean up Skia objects.
interface IDisposable with
member __.Dispose() =
paint.Dispose()
canvas.Dispose()
surface.Dispose()
After sprinkling a few calls to DrawLine, AddCircle, and AddCircleOutline
in the analysis code, you can see beautiful results like the following. (I’ll
explain what the colors and redudnant circles are all about later.)
Color Matching via Linear Algebra
You might notice that the colors aren’t solid, and feature subtle variations with shading. While this makes things more aesthetically pleasing, it also makes comparing pixel data more challenging.
Fortunately a little math can solve this problem for us. (“Maths” if you are in the UK, for some odd reason.)
First, I don’t look at a single pixel when determing a color. Rather I compute at the average of a larger block of nearby pixels. This reduces the impact of these subtle color variations.
Second, because of the averaging done, you cannot just rely on a basic comparision to see if two colors are equal. Instead, you need a way to measure the “closeness” of two colors.
Measuring the closeness of two data points is a well-known problem, and the solution is to compute the dot product (wikipedia). Don’t let all the funky symbols scare you! It’s really a simple concept.
For normalized vectors (length of one), the dot product is the cosine of the
angle between the vectors. So if they are identical (pointing the same
direction), then the dot product is 1.0. If they are orthogonal/
perpendicular, the dot product is 0.0. If two vectors were going in
completely different directions, i.e. 180° from each other, then the dot
product would be -1.0.
Of course a typical RBG color value isn’t a vector in the traditional sense,
but if squint a little, you can think of the RGB value as a vector in three-
dimensional space. (Or, four-dimensional if you factor in an alpha channel.)
// Computes the dot product of the two colors as if they were
// normalized vectors.
let dotProduct colorA colorB =
let colorToNormVec (c : SKColor) =
let valueArray =
[| c.Red; c.Green; c.Blue; c.Alpha |]
|> Array.map float
let w, x, y, z = (valueArray.[0], valueArray.[1], valueArray.[2], valueArray.[3])
let length = Math.Sqrt(w * w + x * x + y * y + z * z)
Array.map (fun x -> (float x) / length) valueArray
let vecA = colorToNormVec colorA
let vecB = colorToNormVec colorB
Array.fold2 (fun acc x y -> acc + x * y) 0.0 vecA vecB
You’ll see this dotProduct function come up in a few places in the code.
Puzzle Colors
Each Kami puzzle has a set of two to five colors that you can use, displayed in the bottom right of the screen.
The heuristic I use to figure out the number of colors the puzzle has is to assume the puzzle has five colors, and then check if any are duplicated. If so, then reduce the number of colors and try again.
This actually works pretty well. You can see why this works when you look at the debugging image below.
The top part shows the original color swatches. The bottom part shows the “probing” done to whiddle down the number of colors. Note that in the cases where it guesses five of four colors, duplicates are found.
Triangle Colors
Once the puzzle’s colors have been determined, next is mapping each individual triangle to a color. This is done by getting the average color of the triangle and checking its dot product against the set of puzzle colors. The highest resulting dot product is the closest match.
However, in the case that no good match is found, e.g. dot product value less
than 0.75, we assume the triangle isn’t part of the puzzle. And instead is
just showing the “background”.
Converting Raw Data into a Graph
The final stage of puzzle extraction is converting our messy color and color-indexed based data into a graph abstraction.
To define the terms used, each contiguous set of triangles sharing the same color is called a region. Each region has a unique ID and color associated with it, along with a list of zero or more adjacent regions.
// Raw puzzle extracted from a screenshot.
type RawKami2Puzzle = {
// Number of colors used in the puzzle.
NumColors: int
// Index of the color of each individual triagle. See other comments for
// translating coordinates to triangles, and adjacency rules.
// Has value of -1 if the triangle doesn't match any puzzle colors.
Triangles: int[,]
}
// Kami2 puzzle represented as a graph.
type Region = {
ID: int
Color: int
// IDs of adjacent regions
AdjacentRegions: HashSet<int>
}
type Kami2Puzzle = {
NumColors: int
Regions: List<Region>
}
Algorithm
We start with a 2D integer array of triangle colors (each integer corresponds to the index of the puzzle color, or -1 if the triangle is not part of the puzzle.)
First, we construct a parallel 2D array of Region option objects. This allows
for quick lookup to see if a given triangle is associated with a region or not. As we
flesh out the regions of the puzzle, we’ll keep this array up to date.
let triangleRegions : Region option[,] = Array2D.zeroCreate 10 29
To start breaking the puzzle into regions, we pick the first triangle not
already associated with a region (Option.isNone triangleRegions.[c, r]).
We then create a new Region object to identify that uncharted region,
and then flood fill all
identically-colored and adjacent triangles.
While walking through the region being flood-filled’s neighbors, if any of them are associated with a different region, then we update both regions to add the “borders” association. i.e. region X borders region Y and vice versa.
Hopefully that was an adaquate description. If not, I’m happy to clarify anything that doesn’t make sense. And the good news is that it fits into less than 50 lines of F# code:
let rec floodFillRegion col row (region : Region) =
match triangleRegions.[col, row] with
// If the triangle's neighbor is already known, mark as neighbor and stop.
| Some(adjacentRegion) ->
region.AddAdjacentRegion(adjacentRegion)
// If the adjacent triangle does not have a region, then we merge it
// into the region being flood filled if it has the same color,
// otherwise we ignore it. (And will get to it later.)
| None ->
let triangleColor = rawData.Triangles.[col, row]
if triangleColor = region.Color then
triangleRegions.[col, row] <- Some(region)
// Mark it on the debug image.
let x, y = getTrianglePoint col row
let regionColor = solidColors.[region.ID % solidColors.Length]
debugImage.AddCircleOutline(x, y, regionColor)
// Recurse
getAdjacentTriangles col row
|> Seq.iter (fun (col', row') -> floodFillRegion col' row' region)
else
// Ignore the diff colored neighbor, as it will be a part
// of a different region constructed later.
()
// Check each triangle and ensure it is apart of a region.
for col = 0 to 9 do
for row = 0 to 28 do
let triangleColor = rawData.Triangles.[col, row]
match triangleRegions.[col, row] with
// Ignore triangles already associated with a region or
// not part of the puzzle.
| Some(_) -> ()
| _ when triangleColor = -1 -> ()
| None ->
let newRegion = {
ID = knownRegions.Count
Color = triangleColor
AdjacentRegions = new HashSet<int>()
}
knownRegions.Add(newRegion)
floodFillRegion col row newRegion
That’s it! And one nice thing is that while we are building up the regions, we mark each triangle with a determinsitic color based on the region’s ID. So you can see by the colors of the circles where regions begin/end.
Next steps
Now that we can extract a Kami 2 puzzle from a screen shot, the next
step is to actually write the solver, which takes our Kami2Puzzle puzzle
objects as input and outputs something useful to humans.
Check back later for Kami 2 Solver in F# - Part 2.