1. icon for News
  2. icon for TCHOW


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.

Monday, November 17, 2014

Soon, You Will Fly: a Leap Motion 3D Jam game

Thanks to a soft deadline this morning, I've posted an alpha build (for Windows and OSX) of a weird little game I've been working on for the Leap Motion 3D Jam presented by IndieCade. It's called "Soon, You Will Fly", and -- perhaps unexpectedly -- it's about crawling.

I'm still working on a few things. Among them: tentacles, a heart/eye, the touch of darkness, and more sound design. Oh, and a way to quit without resorting to ALT-F4.

Anyway, please do check it out and let me know what you think. At present, I'm thinking that this probably doesn't extend beyond a simple jam game; but feedback can change that.

Thursday, September 4, 2014

Fragments: a Ludum Dare Jam Game

A few weeks ago, I worked with my friend Aaron Vonderhaar on a bold experiment: to develop a single-page html game framework and then build a game in it for Ludum Dare.

The result is Fragments [Ludum Dare Page] [Source Code]. It's a put-together puzzle in isometric 3d, telling a somewhat fragmented story of mangled memories.

I'm not entirely happy with how the game came out, but as my first Ludum Dare Jam (as opposed to compo) experience, it was a decent one. It was fun working with Aaron on a project, and I think we did some interesting things in the game framework -- though it wasn't nearly complete enough going into the competition.

Two interesting points of trivia about Fragments:

  • There is no lighting in the game. Everything is baked to vertex colors in Blender during export. This is a trick I also used in Rainbow for the landscape.
  • For some reason, 30% of the CPU time in the game is used by 4x4 matrix multiplies. We probably should have been looking at profiling data earlier. It appears that the construction of Mat4's is very expensive.