Developing Secant

Secant, our latest release, is a minimalist geometric puzzle game (see the trailer below). Today I’d like to share a bit about what it was like to develop it, from inspiration to design to implementation, along with some road bumps and their solutions.

Backstory + inspiration: In machine learning and statistics one type of problem is classification, which is basically what it sounds like. This can be tricky, because data can be noisy or arranged in some strange shape. A particular type of classifier called a support vector machine (SVM) tries to classify data by cutting it up with planes (or, in the 2D case, with straight lines), so that each region has only a single class. We might say the SVM uses hyperplanes as its basis functions, and because of this support vector machines are inherently limited. So the question emerges: what if you allow other shapes? Secant is just that, played in two dimensions only, where you get circles and lines as your basis functions and your job is to separate data points into regions based on their class (color). Or at least, that’s how I originally thought about it.

Crux problem: With SVMs, all you ever have to worry about for each point is whether it is ‘above’ or ‘below’ each plane (or line). Since planes carve up the plane very nicely (notably, into convex regions) you can simply look at two points, P and Q and ask are they above or below each plane. If they match up on all counts, then they must be in the same region. Now, this is still true with circles and lines, but what doesn’t hold is that is that if they do not match up then they must be in different regions. Evie (aka Evdog) came up with the following situation during her first play through the game:

photo1

Notice that the green and yellow are in different geometric regions (clearly!) yet they are both inside the big circle, outside the small one, and above the line. Since the game doesn’t see this as a win, it doesn’t allow the player to progress (how sad) until they find a solution that doesn’t use such geometric tricks. Since disallowing geometric tricks would surely make for a worse game, I realised that what Evie had done was most assuredly a valid solution. But the question remained: how to correct it?

Two approaches and a decision: There were two ways to go about it. One was to use a flood fill algorithm (think paint bucket in photoshop) which checks if you paint-bucket from each point you don’t get regions with multiple colors painted on them. This was pretty clear to be a solution, but I thought running it on device was going to be a nightmare (it would involve iterating through all of the pixels onscreen and I didn’t even have access to the pixels and would have to redraw it from scratch). So I kept thinking about it, and came up with an alternate solution based on the original logic of being inside or outside each closed region: compute all intersections as vertices, link them up in a graph (where edges are adjacencies between intersections on a shape), find the cycles, and then check the winding number of each data point with respect to each cycle. This would give all the funky weird regions as loops, and then verify that these loops either did/did not go around each point. The main problem with this: it was going to be even worse than flood fill because, while computationally far simpler (with not too many shapes on the board, mind) it would involve finding all cycles and then computing the winding numbers (which would involve making polygonal proxy shapes for the circles or casting a ray from the data point in question and ‘walking’ the circuit to find a minimal enclosing region). In short: this was not going to be any better than flood fill if I could get flood fill to perform reasonably on device.

Solution -> Aesthetic: I tested out the performance of flood fill which was disheartening at first, read up about coroutines in Lua, and ultimately used a grid that was a quarter of the size in each direction (resulting in a ~16x speedup) which, while a bit crude and not so pure, worked in practice. And a magical thing that popped out of this cruder grid? When you beat a level, it fills it in (at half of that resolution, every 8 pixels, for performance reasons with the display–this ain’t being done with shaders y’all) with circles of the appropriate color to show you the regions that you carved the space into. A nice reward for finishing a level (and something a few people asked about only to discover that it had already been implemented)!

w1

If you like these sorts of things, you might enjoy hearing about new releases by joining the google group.

Leave a Reply

Your email address will not be published. Required fields are marked *