1. icon for News
  2. icon for TCHOW


Wednesday, February 22, 2017

Come At Me Slow

I can't very well mention last year's New Year's album and not point out that the 2016/2017 album is also out. It's called "Come At Me Slow" and you can listen below, on SoundCloud, or on Spotify.

The standouts for me this year are the amazing cover art by Kathleen and the epic sounds of the title track. It is with some regret that I note that I still haven't been awarded the steam achievement described by "Hate Plus / Love Note", despite sending a verification photo and e'rything.

The New Year We Missed

With the crush of the SIGGRAPH deadline, I failed to both create a New Year's card or even make a post detailing the Jimike New Year's album for 2015/2016. So let's fix that right now, shall we?

Grid Line

My remedial New Year's card for last year is titled "Grid Line", and that about sums it up. The grid gets interesting half-way through. Play here (works on smartphones, too!).

I think this might also be my first New Year's card with sound effects (though those don't work on phones; sorry).

36-Hour Day

Last year's album was titled 36-Hour day, since we were producing it in such widely separated time zones. You can listen on SoundCloud (widget below) or Spotify

Standout tracks for me are "Dear Snails" and "The Only Fi I Have" both of which have honest, if shallow, lyrics.

Tuesday, May 17, 2016

Convex Horizons

Today, I started thinking about the complexity of a certain geometric problem: finding the horizon of a set of convex objects. In this post, I'll first state the problem and then attempt to explain why this is an interesting problem to think about.

The Convex Horizon Problem

Given a list of 2D convex objects, return a function h that maps each x-coordinate to the maximum y-coordinate such that (x, h(x)) is contained in some object. This is the "horizon" or "skyline" of the objects.

First Reduction: when working with convex polygons, this is equivalent to finding the horizon of a series of line segments; or, equivalently, trapezoids with bottom edges at negative infinity. So this is the version of the problem I'll be thinking of:

(The horizon of the many-hued trapezoids is the thick black polyline.)

Thoughts on Complexity

Any algorithm that computes such a horizon must spend time at least linear in the number of output points in the horizon line. So it's interesting to think about how many points this could be. Particularly, I find this intriguing because of two different (related) problems.

The Box Horizon problem pretty clearly has output of size at most 4N (for N boxes). The argument goes something like: the horizon is a chain of line segments alternating between flat segments and vertical segments. The vertical segments correspond to the vertical edges of boxes, and each box edge appears at most once in the list. This means there are at most 2N vertical segments, which must (therefore) separate at most 2N horizontal segments.

(Mind you, the time complexity of an algorithm that computes a box horizon from an unsorted set of boxes is likely O(N log N), given as reducing sorting to box horizon seems likely to be trivial.)

The logic used to argue for the output complexity of box horizon breaks for trapezoid horizon because the topmost trapezoid can switch not just at an edge, but at a line segment intersection. And it's easy to see that there can be quadratically many intersections among lines:

But this standard lines example doesn't have a clear translation to the trapezoid horizon setting! So that leaves an interesting puzzle: is there some other argument that can be used to demonstrate linear output complexity of trapezoid horizon? Or, failing that, what's a super-linear output complexity example for this setting?

I plan to ponder this more over the next few days. If you have some ideas, feel free to get in touch.

Wednesday, April 1, 2015

The Rktcr Benchmark

In preparing Rktcr for release on Steam, I've been making some minor adjustments to the code and art (Steam Achievements! Blinking characters!). As I've made a bit of a fuss about before, Rktcr is a game that plays exactly the same across three compiler/OS combinations (g++/Debian, clang++/OSX, cl.exe/Windows). As such, part of any update is confirming determinism with an extensive test suite.

Specifically, I have the game compute SHA1 hashes of relevant state as it plays itself on a hand-crafted set of ~1,600 par time paths. Yes, there are over 1,600 individual paths segments you might want to play in Rktcr, and I have a plan to add cheat-proof leaderboards for all of those. But that's a topic for another post.

The Benchmark

So how do my Windows and Linux partitions stack up against each-other on this (blended filesystem/compiler optimization) benchmark? (I'm not testing clang++/OSX since that's not installed on the same machine.)

WindowsVS2013, Update 3120 seconds
WindowsVS2013, Update 4121 seconds
WindowsVS2013, Update 4, optimizations off137 seconds
Linuxg++ 4.8.179 seconds
Linuxg++ 4.9.276 seconds

I'm pretty sure that the one-second difference between VS updates is within noise, though I dread that it may be a performance regression. Turning optimizations off demonstrates that they are at least doing something.

Under Linux, there is a noticeable improvement between the steam-runtime-targeting g++ 4.8 and my system-wide g++ 4.9; whether it's a compiler or standard library difference isn't clear; but it is certainly nice when newer compilers make old code faster.

Finally, I'm surprised that the Windows/VS version is doing so poorly compared to Debian/g++ -- my previous experience has been that cl.exe produces code that is a fair bit faster than either g++ or clang++. I'm left wondering if this particular code is something that cl.exe fails to optimize properly, or if the Windows stack is failing somewhere else (filesystem read performance? standard library implementation?). There could even be exotic hardware causes -- Windows and Linux are run from different [though identically-branded, purchased-at-the-same-time] SSDs -- perhaps one is slower.

Saturday, February 21, 2015

Rainbow is a Pocket Gamer 2015 Nominee

My rainbow-driving game, Rainbow (available for iOS and Android for approximately $1) has been nominated for a Pocket Gamer award in the "Most Innovative" category.

Please head over to Pocket Gamer to vote. It's almost certainly not going to win, but one must try, eh?

Thursday, January 1, 2015

New Year Paraphernalia

Each year, my brother and I spend the new year's eve building a new album to release. Also, I've been trying to get in the habit of releasing a little interactive solstice / new year card around the same time. So here they are.


This year's game is a quick implementation of a puzzle interaction involving moving blocks around. The opening animation explains it better than I could:



This year's is called "Sassy Bunny" and you can listen to it right now:

Some highlights: Weird To Me -- a classic one-take Jimike song; Undone -- all sorts of interesting sounds in here; Intro -- really energetic track. Some lowlights: weird mixing in Great In The Future; She -- a track that is perhaps too mellow.

We are starting to accumulate a fair bit of audio gear. This year's album involved two guitars, a banjo, a Monotribe, three mics, and two different midi control devices -- a keyboard and a Push (run through a custom script to make it nice for use in Reason).

As always, expect Spotify links when we get around to pushing the files to our distributer.

Why Rainbow fails on iOS 8

Last week, I received a disturbing bug report from an iOS 8 user: Rainbow, it seems, wasn't properly saving any game state. So, I sat down to see what the problem was.

The culprit seems to be the helper function user_data_dir, which is responsible for figuring out where to store data files for the game:

string user_data_dir(string const &app_name)
    /* ... */
    #elif defined(IOS)
    ret = "../Documents";
    #elif defined(ANDROID)
    /* ... */
    return ret;

Hmm. A hardcoded path. That seems brittle.

Looking up user data paths and iOS 8, I came across a tech note which pretty succinctly explained the situation. Basically, the Documents directory is no longer a sibling of the application, so must be requested using a (ObjC) call, which I ended up dumping into a different (compiled-as-ObjC++) file:

std::string documents_directory() {
    return [[[[[NSFileManager defaultManager] URLsForDirectory:NSDocumentDirectory inDomains:NSUserDomainMask] lastObject] path] UTF8String];

And that seems to have done it. Expect a 1.5.2 version of Rainbow to appear soon.