A finely crafted piece of art.
Out of curiosity, do you plan to make this project open source? I'd be curious to learn about some the technical details.
Regarding Cypher vs Gremlin: serialization could be a thing but what matters among other things are efficient query optimizations, algorithm and (physical) data model. Ultimately, databases are all reading from 1-dimensional spaces (RAM or disk), either randomly or (best) sequentially. If you can colocate vertices with their respective edges, you're fine: this is trivial for graphs with no edges or graphs that form a linear chain. If not, then things start to become fun, especially in a distributed way. This will impact performance; the language, not so much.
Nice piece of game! Any chance you could write a couple blog posts about the technical challenges you had to face, if any? I'm especially interested in the way you generate levels. Thanks.
To clear out a possible minor confusion for readers here - Titan's only API is Gremlin (though there also is a lower level Java API). You guys should also have a look at ArangoDB, which also supports Gremlin.
Linkurious with upcoming TinkerPop3/Gremlin will definitely be quite interesting to use. Keep up the good work.
People too often forget about graph databases when talking about NoSQL solutions. Graph databases offer an interesting and elegant alternative to relational databases and I could definitely see a startup decide to use this kind of technology.
As far as I know, most graph databases support transactions and offer great scalability. Such databases are also schema-less and can be queried with Gremlin, a powerful graph traversal language (see www.tinkerpop.com).
With respect to scalability and transactions, Titan (http://thinkaurelius.com/) looks very promising: it supports various backends for storage (Cassandra, HBase, etc.) and indexing (currently Elastic Search and Lucene). Graph analytics can be done via Faunus (http://thinkaurelius.github.io/faunus/), backed by Hadoop.
There are other vendors out there (Neo4J, OrientDB, etc.) which offer interesting solutions worth looking at - I'm just a bit less familiar with them.
The major downside I see with graph databases is that most of them are fairly recent and their ecosystem is tiny (though growing). Should a startup venture on such young technologies, or stick to mature and battle-tested solutions (ie. relational databases)?
Could startups use this kind of graph "NoSQL" databases? I don't see why not. If your startup is some kind of social network, graph databases are certainly an option worth considering. If I were to create a startup, I'd hardly use a document database like MongoDB but I will really consider using a graph database. In the end, it's all about having the right tool in hand, and knowing how to assert what is "right" for you.