Tuesday, December 31, 2013

2013: another successful year for The Little Crane.

I have proclaimed the year 2012 as The Year of the Crane. And 2013 was another smash hit year. A legion of people (a touch under 5M) downloaded the free version of The Little Crane That Could in 2013.

2013 2012 2011
iOS 3199K 3454K 1550K
Android 1579K 1656K -
Mac 53K 81K -
OUYA 15K - -
Kindle 95K - -
Rasp Pi 6K - -

Even though the game is now available for Windows and Ubuntu, they do not show up as those download counts round down to 0K.

These marvellous figures mean that the grand total for the lifetime free downloads of The Little Crane That Could is now a whopping 11.7 million. Thank you gamers! I look forward to bringing you The Little Crane That Could II in 2014/2015.

Sunday, December 29, 2013

Game Lobby

I am porting my game Buggy Bang! Bang! to Android. The leaderboard/matchmaking in Android has no NDK support and looks complicated. So I think I will need to roll my own online game lobby. I've written a leaderboard service before, in Python, for some of my earliest iOS games. It worked pretty well, except for the unreliable web hosting I have, causing outages of the leaderboards. Writing a lobby should not be much more difficult than a leaderboard service. I will write down my thoughts in this weblog.

  • I think this can be done based on UDP, to avoid managing connections.
  • When a client wants to setup an online game, it could send a datagram with its gamer tag and IP to the lobby server.
  • The lobby server can then respond when a second client sends a similar datagram, and create a match up between the two.
  • It would send the IP and tag name of each to the other, so that from then on, the match can be played peer to peer.
  • I would still need unique gamer tags. Where to get this? Use google plus account names?
  • Alternatively, I could have the server assign unique IDs for the first time a client connects, and cache the ID in the client for use with subsequent sessions. Then I could just skip the gamer tag altogether and make the ID user-facing. If the ID increments from 1, it may become a form of pride, like low digit slashdot user IDs.
  • What about NAT?

Monday, December 23, 2013

Emscripten

Could I possibly get The Little Crane That Could to run in a browser window? If a modest Raspberry Pi can run it, why not a 'lowly' browser?

Inspired by a blog posting from Dirk Krause over at web3dblog, I decided to look into this. And my weapon of choice: emscripten, because I grow fonder of the C programming language each year, and have no appetite for Javascript. Hurdle number one is the outdated build instructions on linux that I found here. So in this blog posting I will document the attempt to emscripten my game.

  • Instead of building llvm/clang from source, I simply install those from the ubuntu repository using 'apt-get install clang-3.2'.
  • It turned out that emcc cannot find llvm-link on my system. This is because ubuntu installs it as llvm-link-3.2 so this needs fixing.
  • Like clang and llvm, node.js can also be obtained from Ubuntu's repository using the 'apt-get install nodejs' command.
  • With those modifications, the compiler seems to work just fine.
    $ nodejs a.out.js
    hello, world!
    
  • To target ASM.JS you can use this command line:
    $ ./emcc -O1 -s ASM_JS=1 tests/hello_world.c
  • There is an emar archiver tool, but combining bytecode objects into an archive gives unresolved symbols when I link against this archive. fixed by using -L. flag.
  • You can put files onto a virtual file system using the --embed-file compiler flag. I've not yet figured out how to successfully use dlopen() though.

Lastly, these slides on an emscripten talk are very interesting.

Wednesday, November 27, 2013

OpenDE and Bullet

I would like my simulation of tracked vehicles to be faster, so it could possible run on mobile hardware. Currently, you need a modern desktop to do it, at the bare minimum my mid 2011 MacBook Air is even struggling. The 1.7 GHz Intel Core i5 struggles to run the physics simulation when a lot of dirt is active. Additionally, the integrated graphics HD 3000 struggles to render it at full screen resolution.

OpenDE lacks support for SIMD processing. However, there is another physics library, Bullet, which is streamlined for things like Neon, Cell SPU, multithreading, etc. And there is even an OpenCL version. Here I try to summarize the implications of a potential switch:

✪ Bullet builds out of box for all platforms with minimal dependencies. The dependencies it has, come included.
✪ Bullet supports cylinders, capsule, boxes, meshes: all the shapes I use with OpenDE.
✪ Bullet supports (even though it is missing from the manual) the OpenDE style hinge2 joint, crucial for my vehicle simulations.
✪ Bullet uses OpenDE's ERP (Error Reduction Parameter) and CFM (Constraint Force Mixing).
✪ Bullet comes with SIMD implementations, so should be faster in theory. It's probably still AoS though, and not SoA.
☹ Bullet has a C++ API, not a C API.
☹ Bullet lacks the concept of collision spaces to quickly ignore collisions within spaces.
☹ Bullet advices against differences in mass. OpenDE does this too, but at least I know OpenDE handles it well. You can never create a realistic vehicle simulation if your wheels have weigh the same as the chassis, no matter what you do.
☹ The bulk of my game development comes down to endless tuning of the physics parameters. Switching physics library means retuning pretty much everything.

I am still on the fence about this, and will probably hold off on a port. Maybe it would be better to use it in case I start a project from scratch.

UPDATE

Here is How Wolfire switched from OpenDE to Bullet. Also, Bullet3 seems yet to be released, and its development branch seems to still lack the C-API unfortunately.

UPDATE

I switched! Colliding and solving are both multi-threaded, which is great. Unlike ODE, Bullet does proper collision detection on convex-versus-convex. Something that tripped me up: Bullet's transformation matrices have the axes stored as columns, not as rows which I am used to.

Wednesday, November 20, 2013

Making a mess

I call this composition "Making a mess." It takes a bit of manoeuvring, but after 15 minutes of playing in the sand, the landscape looks considerably changed.

But the sad news is, I am still having a hard time finding a game play design for it. I've got this incredibly advanced simulation technology, but that does not make a game in its self. Should I just hide some treasure in the mud, and have the player dig it up? Maybe with a "warmer" "colder" hint system? Do I create a fancier version of the "Yukon Gold" level in The Little Crane That Could? I don't know at this moment.

Then there is the problem of hardware platform. Mobile is far too underpowered to do this. Even my second generation Mac Book Air is struggling to get fluid frame rates. So PC then? Well, steam greenlighting is not working out for me. And Amazon's app store keeps rejecting my PC build of Little Crane v1. Should I shelf it for a few years, and release it for iOS9 when cpu performance has increased another order of magnitude?

Thursday, November 14, 2013

Lean Code

I guess my code is pretty lean.
$ find ~/apps/LittleCrane -name \*.cpp -exec wc -l {} \; | awk '{total = total + $1}END{print total}'
19653

Compared to these monstrous code bases. This would designate my game as a 'simple iPhone game app' according to their classification. Also, I do not believe their assessment of the code size of a modern car.

Sunday, October 20, 2013

First release of Little Crane for MS Windows.

I'm happy to announce my very first release of The Little Crane That Could for MS Windows. You can try the first 6 levels for free, in the Free-To-Try distribution. If you want to play all the 25 levels in the game, I urge you to vote in the green light campaign and tell all your friends.

In case you try this out, please drop a comment in this posting. I love to see feedback on it. In case of troubles, copy the console output and paste it into a comment please.

Requirements:
  • 64 bit Windows OS.
  • OpenGL capabable graphics card.
  • Support for GLSL (shading language) V1.1 or higher.

DOWNLOAD LINK
LCFREE-516.msi

README
The Little Crane That Could.
Free-To-Try release v5.16 for Win64.


KEYBOARD CONTROL:

CURSOR KEYS: Drive truck
Q/A:         ROTATE
W/S:         ELEVATE
E/D:         BEND
R/F:         EXTEND
T/G:         GRAPPLE

+/-:         ZOOM CAMERA
ESC:         RETURN TO MENU / QUIT


JOYSTICK CONTROL:

ONLY XBOX360 COMPATIBLE CONTROLLERS ARE SUPPORTED.
Tested with Logitech F310.

Support: http://thelittleengineerthatcould.blogspot.com/
gmail user: b.stolk

Wednesday, October 16, 2013

LOD, Clipping.

This week I have been adding LOD (which is pretty hard for terrains, because cracks appear between the high resolution chunks and the low resolution ones.) Easier was adding frustum clipping. Actually I simply clip against the left/right/top/bottom planes, and don't bother with near/far planes.

I also did some profiling and optimization. My old Mac Book Air with HD3000 graphics is struggling. Both the GPU and the CPU are a bit too slow, especially when a lot of dirt particles are created.

Wednesday, October 9, 2013

Digging it.

After the dozer, I now added a digger as well. It's already pretty convincing I think. Although it does have some difficulties with boulders getting stuck between the jaws, and then suddenly and violently get expelled from the bucket. Movements are jerky, mainly because the app would not sync to the 60fps display. Even though I used glfwSwapInterval() to make it sync. Maybe it is a GLFW3 bug.

Sunday, September 29, 2013

3 millionth user on Google Play milestone cracked.

Today, the 3 millionth Google Play user installed The Little Crane That Could. The iOS user base is still quite bigger, but it's nice to note the milestone. The promotion service AppOfTheDay gave a nice bump on aug 28th. But its effect has worn off by now.

Monday, September 23, 2013

Bad ass dozer

Today, I have been adding caterpillar tracks to the dozer for Little Crane 2. Personally, I think this little dozer is pretty bad ass now. The caterpillar tracks make depressions in the ground.

Tuesday, September 17, 2013

Brand new PC

I've bought a brand new PC yesterday, the last time I did that was in 2005. Since 2008 or so I switched to Mac. But porting my Little Crane game to Windows was too much of a lure, and my Mac Mini with Windows installed was not cutting it.

Building your own PC from components was, and still is a lot of fun. This is what I ended up with:

Intel core i5 4570 CPU. I would have preferred a low power T or S model, but those were not in stock at NCIX.

To keep the 84W CPU heat out of the case, I went with a maintenance free water cooling kit: Corsair H100i.

To keep the system relatively compact, I chose a mATX motherboard with H87 chipset: the Asus H87M-PLUS. The more expense Z87 chipset is really only req'd if you want to do overclocking.

A premium mATX case (Corsair 350D) with a nice aluminium front on a steel casing.

Wireless network adapter PCIe from Asus.

8 Gbyte of ram from Kingston.

Samsung 840 Evo SSD, and also a very cheap DVD writer.

Sunday, September 1, 2013

Scraping and Dumping

I made a new video on the development of The Little Crane That Could 2. It shows a dozer that creates tyre marks in the terrain, scrapes terrain, and dumps dirt onto the terrain.

Saturday, August 24, 2013

To the Dark Side.

I've been eschewing Microsoft for a long time now. I'm in and in a UNIX guy, and despise the horrible practices of Microsoft, in what they do to standards. Also I have been totally unimpressed by the quality of their Operating Systems. So why did I buy a copy of Windows 7 today? Well, PC gaming is alive and kicking, so I want to see if I can get my hit game The Little Crane That Could to the Windows platform. Here are my trials and tribulations of installing Windows7 on a 2007 Mac Mini.

When installing 64 bit Windows on a Mac Mini, you get greeted by a cryptic message. "Select CD-ROM boot type". Whatever option you choose, 1 or 2, nothing happens. The machine is just frozen. It turns out you need to burn a new copy of your Windows installation DVD with some special options. More info on fluxbox.co.uk.

Using iPads and OSX a lot, I can now only use a mouse with "Natural Scrolling." Getting natural scrolling to work involves touching the murkiest and most vile part of the Windows Operating System: the Registry. For expert users only.

After installation, audio is not working. The driver CD that Boot Camp created does not seem to be any help with it. I still have to find a solution for this.

First order of business was to get some development going. After downloading Visual Studio Express, git, cmake and make, I was able to build GLFW3 from sources in the git repo.

UPDATE I had to reinstall windows after buying a new computer. Here are some issues to consider:

  • When building gl3w, you first need to install python2.7
  • When building glfw, you first need to install cmake.
  • To build glfw, make sure you run vcallvars.bat from the Visual Studio program. Then you can run 'cmake .' followed by 'nmake'
  • IE is super slow, and so is chrome. I fixed the slow chrome by unselecting all proxy options in the network settings.

Monday, August 19, 2013

Digging Dirt

Now spawning dirt when voxels are scraped away from the terrain. It adds a lot to the visual appeal.

Saturday, August 17, 2013

Terrain Modification -- TAKE1

It is far from perfect, but at least it is a start. Dynamic terrain modification using a digger in a voxel terrain. For now I use straight voxels, and not the marching cubes surface, as it is easier to debug.

My plan is to spawn cube-lets as the terrain is modified. This single cubes will be merged back into the terrain after inactivity. It will look prettier with an iso-surface.

Friday, August 9, 2013

Packaging

With the use of PortAudio I was able to get sound working on the linux port of The Little Crane That Could. And GLFW enabled me to support a joystick (currently I only support PS3 controllers.) I did have to change the GLFW source code so that it would not invert uneven numbered axes.

So now it comes to packaging the game for Ubuntu. Man, what a challenge that is. I've wasted a lot of time creating a .deb file. I did manage to find a good resource for making binary packages.

Wednesday, August 7, 2013

OpenGL and Ubuntu

So I am dusting off my old GNU/Linux PC. It's pretty antique, as I had brought it over from the old country when I immigrated into Canada so long ago. It turns out that it is so old (from 2005 or so), that it can't do 64 bit. (It has an Intel Pentium M at 1.6GHz.) I gave it a fresh copy of Ubuntu 13.04 to see if I can port Little Crane to GNU/Linux.

Initially, I thought it would be easy because I already ported it to Raspbian (which is Debian running on the Raspberry Pi.) But the Raspberry Pi makes it easy, since you can get straight access to the GPU via OpenGL-ES2. There is no need to go through Xwindow, courtesy of the videocore libraries (libvcos) that comes with the little computer. On vanilla GNU/Linux, this is not so easy. First, I have yet to figure out: should I go the GLES2 route? Or can I somehow get access to OpenGL3 Core Profile on Ubuntu? So far, I'm not really sure how to do OpenGL3 on Ubuntu. The only reference to gl3.h header file in Ubuntu, is in a GLES package, strangely enough. However, I stumbled onto GLFW which promises a painless access to GL on UNIX. I will evaluate this framework.

To start off: GLFW is best retrieved from GIT, because the version in Ubuntu (2.7.x) is old. Furthermore, it is incompatible with the current version in GIT. Next, to build it, you need to use cmake. Then you can test by running the examples.

When it comes to building your own app on top of GLFW, it looks like you can force the use of GLES2 by doing:

#define GLFW_INCLUDE_ES2
#include <GLFW/glfw3.h>
Also, it turns out you need to force extension prototypes with:
#define GL_GLEXT_PROTOTYPES 1
...before including the GLFW header.

Friday, August 2, 2013

Going viral without marketing... it can happen.

There is a common saying in the #indiegames scene that goes like this: Build it and the players will come. This translates to 'A good game will sell itself (without marketing.)' The current crowd wisdom in my circles is that this is utterly false.

It is only a single data point, but allow me to present an argument for 'Build it and they will come.' This is a case study of my game The Little Crane That Could. The game was released end of january 2011 on Apple's app store. Upon launch, the game had zero marketing and zero press. So what happened to this game?

  • On day 1: I made 1 (one!) sale that day.¹
  • On day 2: 10 sales.
  • On day 3: 100 sales.
  • It might have been day 5 or 6, but in the first week it got to 1000 sales per day.

The free downloads trend was even more dramatic, hitting 1M total in a few weeks. If this is not a text book pattern for viral distribution, I do not know what is. Since there was no marketing² behind it, it must have been word of mouth at play³. Here is how it works: Every player that downloads your game convinces N friends to download and try it as well. If N > 1.0 then you have a viral game. Even with N = 1.1 you will have a smash hit on your hands.

So this was in 2011. Does today's App Store still work this way? I think it does, but the bar has been raised. Nowadays to stand out, it needs to be really really good. In the early days, the demand/supply was out of balance. The demand is still there, but the supply has come in like a tsunami. To scare indie game developers: tell them how many game titles are published per month.

¹ So disheartening, I decided to quit game development, and start contracting.
² The only marketing was a single post on touch arcade forums that announced the game.
³ After initial break through, another force takes over: When in Apple's top ranks, visibility jumps up aggressively. Still: the viral phase got me in the ranks, the ranks propelled me further.

Wednesday, July 31, 2013

Marching Cubes with demarcated polygons

I've made more progress with the evaluation of PolyVox. PolyVox comes with a Marching Cubes algorithm that can extract surfaces from voxel volumes. Paul Bourke calls this polygonising a scalar field. This surface extraction works just fine in Polyvox. However, it does lack that distinctive visual style of Little Crane. My signature renderer draws the outline of the polygons in the 3D model. So I decided to add the demarcation of the polygons to the Marching Cubes algorithm in Polyvox. This has been partly successful, as I was able to reconstruct the complete polygons from the triangle list in most of the 256 cases in the Marching Cubes algorithm. Below you can see what it now looks like. I think the visual is usable as terrain for Little Crane II. I still need to add fading of the edges, so that the lines disappear at larger distances to the viewer. This will reduce the clutter caused by the edge drawing.

To reassemble the polygons from the triangles, I used my trusty Python interpreter. Nothing beats Python in productivity for complex processing. For posterity, here is the source code for reassembling most of the cases. The basic idea behind the code is to fuse triangles that share a common edge.

#!/usr/bin/python

import os
import sys

triTable = [
  [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  8,  3,  9,  8,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0, 11,  2,  8, 11,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  9,  0,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1, 11,  2,  1,  9, 11,  9,  8, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  2, 10,  0,  2,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  8,  3,  2, 10,  8, 10,  9,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3, 10,  1, 11, 10,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0, 10,  1,  0,  8, 10,  8, 11, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  9,  0,  3, 11,  9, 11, 10,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  3,  0,  7,  3,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  1,  9,  4,  7,  1,  7,  3,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  4,  7,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  4,  7, 11,  2,  4,  2,  0,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  0,  1,  8,  4,  7,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  7, 11,  9,  4, 11,  9, 11,  2,  9,  2,  1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  4,  7,  3,  0,  4,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  2, 10,  9,  0,  2,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2, 10,  9,  2,  9,  7,  2,  7,  3,  7,  9,  4, -1, -1, -1, -1, ],
  [ 3, 10,  1,  3, 11, 10,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1, 11, 10,  1,  4, 11,  1,  0,  4,  7, 11,  4, -1, -1, -1, -1, ],
  [ 4,  7,  8,  9,  0, 11,  9, 11, 10, 11,  0,  3, -1, -1, -1, -1, ],
  [ 4,  7, 11,  4, 11,  9,  9, 11, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  5,  4,  1,  5,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  5,  4,  8,  3,  5,  3,  1,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0, 11,  2,  0,  8, 11,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  5,  4,  0,  1,  5,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  1,  5,  2,  5,  8,  2,  8, 11,  4,  8,  5, -1, -1, -1, -1, ],
  [ 1,  2, 10,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  8,  1,  2, 10,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  2, 10,  5,  4,  2,  4,  0,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2, 10,  5,  3,  2,  5,  3,  5,  4,  3,  4,  8, -1, -1, -1, -1, ],
  [10,  3, 11, 10,  1,  3,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  9,  5,  0,  8,  1,  8, 10,  1,  8, 11, 10, -1, -1, -1, -1, ],
  [ 5,  4,  0,  5,  0, 11,  5, 11, 10, 11,  0,  3, -1, -1, -1, -1, ],
  [ 5,  4,  8,  5,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  7,  8,  5,  7,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  3,  0,  9,  5,  3,  5,  7,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  7,  8,  0,  1,  7,  1,  5,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  9,  5,  7,  8,  9,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  7,  9,  7,  2,  9,  2,  0,  2,  7, 11, -1, -1, -1, -1, ],
  [ 2,  3, 11,  0,  1,  8,  1,  7,  8,  1,  5,  7, -1, -1, -1, -1, ],
  [11,  2,  1, 11,  1,  7,  7,  1,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  7,  8,  9,  5,  7, 10,  1,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  1,  2,  9,  5,  0,  5,  3,  0,  5,  7,  3, -1, -1, -1, -1, ],
  [ 8,  0,  2,  8,  2,  5,  8,  5,  7, 10,  5,  2, -1, -1, -1, -1, ],
  [ 2, 10,  5,  2,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  8,  8,  5,  7, 10,  1,  3, 10,  3, 11, -1, -1, -1, -1, ],
  [ 5,  7,  0,  5,  0,  9,  7, 11,  0,  1,  0, 10, 11, 10,  0, -1, ],
  [11, 10,  0, 11,  0,  3, 10,  5,  0,  8,  0,  7,  5,  7,  0, -1, ],
  [11, 10,  5,  7, 11,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  8, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  1,  9,  8,  3,  1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  2,  3,  6,  2,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  0,  8,  7,  6,  0,  6,  2,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  7,  6,  2,  3,  7,  0,  1,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  6,  2,  1,  8,  6,  1,  9,  8,  8,  7,  6, -1, -1, -1, -1, ],
  [10,  1,  2,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  3,  0,  8,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  9,  0,  2, 10,  9,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6, 11,  7,  2, 10,  3, 10,  8,  3, 10,  9,  8, -1, -1, -1, -1, ],
  [10,  7,  6, 10,  1,  7,  1,  3,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  7,  6,  1,  7, 10,  1,  8,  7,  1,  0,  8, -1, -1, -1, -1, ],
  [ 0,  3,  7,  0,  7, 10,  0, 10,  9,  6, 10,  7, -1, -1, -1, -1, ],
  [ 7,  6, 10,  7, 10,  8,  8, 10,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6,  8,  4, 11,  8,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  6, 11,  3,  0,  6,  0,  4,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  6, 11,  8,  4,  6,  9,  0,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  4,  6,  9,  6,  3,  9,  3,  1, 11,  3,  6, -1, -1, -1, -1, ],
  [ 8,  2,  3,  8,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  9,  0,  2,  3,  4,  2,  4,  6,  4,  3,  8, -1, -1, -1, -1, ],
  [ 1,  9,  4,  1,  4,  2,  2,  4,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6,  8,  4,  6, 11,  8,  2, 10,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  3,  0, 11,  0,  6, 11,  0,  4,  6, -1, -1, -1, -1, ],
  [ 4, 11,  8,  4,  6, 11,  0,  2,  9,  2, 10,  9, -1, -1, -1, -1, ],
  [10,  9,  3, 10,  3,  2,  9,  4,  3, 11,  3,  6,  4,  6,  3, -1, ],
  [ 8,  1,  3,  8,  6,  1,  8,  4,  6,  6, 10,  1, -1, -1, -1, -1, ],
  [10,  1,  0, 10,  0,  6,  6,  0,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  6,  3,  4,  3,  8,  6, 10,  3,  0,  3,  9, 10,  9,  3, -1, ],
  [10,  9,  4,  6, 10,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  9,  5,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  4,  9,  5, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  0,  1,  5,  4,  0,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  7,  6,  8,  3,  4,  3,  5,  4,  3,  1,  5, -1, -1, -1, -1, ],
  [ 7,  2,  3,  7,  6,  2,  5,  4,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4,  0,  8,  6,  0,  6,  2,  6,  8,  7, -1, -1, -1, -1, ],
  [ 3,  6,  2,  3,  7,  6,  1,  5,  0,  5,  4,  0, -1, -1, -1, -1, ],
  [ 6,  2,  8,  6,  8,  7,  2,  1,  8,  4,  8,  5,  1,  5,  8, -1, ],
  [ 9,  5,  4, 10,  1,  2,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6, 11,  7,  1,  2, 10,  0,  8,  3,  4,  9,  5, -1, -1, -1, -1, ],
  [ 7,  6, 11,  5,  4, 10,  4,  2, 10,  4,  0,  2, -1, -1, -1, -1, ],
  [ 3,  4,  8,  3,  5,  4,  3,  2,  5, 10,  5,  2, 11,  7,  6, -1, ],
  [ 9,  5,  4, 10,  1,  6,  1,  7,  6,  1,  3,  7, -1, -1, -1, -1, ],
  [ 1,  6, 10,  1,  7,  6,  1,  0,  7,  8,  7,  0,  9,  5,  4, -1, ],
  [ 4,  0, 10,  4, 10,  5,  0,  3, 10,  6, 10,  7,  3,  7, 10, -1, ],
  [ 7,  6, 10,  7, 10,  8,  5,  4, 10,  4,  8, 10, -1, -1, -1, -1, ],
  [ 6,  9,  5,  6, 11,  9, 11,  8,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  6, 11,  0,  6,  3,  0,  5,  6,  0,  9,  5, -1, -1, -1, -1, ],
  [ 0, 11,  8,  0,  5, 11,  0,  1,  5,  5,  6, 11, -1, -1, -1, -1, ],
  [ 6, 11,  3,  6,  3,  5,  5,  3,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  8,  9,  5,  2,  8,  5,  6,  2,  3,  8,  2, -1, -1, -1, -1, ],
  [ 9,  5,  6,  9,  6,  0,  0,  6,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  5,  8,  1,  8,  0,  5,  6,  8,  3,  8,  2,  6,  2,  8, -1, ],
  [ 1,  5,  6,  2,  1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  9,  5, 11,  9, 11,  8, 11,  5,  6, -1, -1, -1, -1, ],
  [ 0, 11,  3,  0,  6, 11,  0,  9,  6,  5,  6,  9,  1,  2, 10, -1, ],
  [11,  8,  5, 11,  5,  6,  8,  0,  5, 10,  5,  2,  0,  2,  5, -1, ],
  [ 6, 11,  3,  6,  3,  5,  2, 10,  3, 10,  5,  3, -1, -1, -1, -1, ],
  [ 1,  3,  6,  1,  6, 10,  3,  8,  6,  5,  6,  9,  8,  9,  6, -1, ],
  [10,  1,  0, 10,  0,  6,  9,  5,  0,  5,  6,  0, -1, -1, -1, -1, ],
  [ 0,  3,  8,  5,  6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  5,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  0,  1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  8,  3,  1,  9,  8,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3, 11, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  0,  8, 11,  2,  0, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9,  2,  3, 11,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 10,  6,  1,  9,  2,  9, 11,  2,  9,  8, 11, -1, -1, -1, -1, ],
  [ 1,  6,  5,  2,  6,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  6,  5,  1,  2,  6,  3,  0,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  6,  5,  9,  0,  6,  0,  2,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  9,  8,  5,  8,  2,  5,  2,  6,  3,  2,  8, -1, -1, -1, -1, ],
  [ 6,  3, 11,  6,  5,  3,  5,  1,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8, 11,  0, 11,  5,  0,  5,  1,  5, 11,  6, -1, -1, -1, -1, ],
  [ 3, 11,  6,  0,  3,  6,  0,  6,  5,  0,  5,  9, -1, -1, -1, -1, ],
  [ 6,  5,  9,  6,  9, 11, 11,  9,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 10,  6,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  3,  0,  4,  7,  3,  6,  5, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  9,  0,  5, 10,  6,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  6,  5,  1,  9,  7,  1,  7,  3,  7,  9,  4, -1, -1, -1, -1, ],
  [ 3, 11,  2,  7,  8,  4, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 10,  6,  4,  7,  2,  4,  2,  0,  2,  7, 11, -1, -1, -1, -1, ],
  [ 0,  1,  9,  4,  7,  8,  2,  3, 11,  5, 10,  6, -1, -1, -1, -1, ],
  [ 9,  2,  1,  9, 11,  2,  9,  4, 11,  7, 11,  4,  5, 10,  6, -1, ],
  [ 6,  1,  2,  6,  5,  1,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2,  5,  5,  2,  6,  3,  0,  4,  3,  4,  7, -1, -1, -1, -1, ],
  [ 8,  4,  7,  9,  0,  5,  0,  6,  5,  0,  2,  6, -1, -1, -1, -1, ],
  [ 7,  3,  9,  7,  9,  4,  3,  2,  9,  5,  9,  6,  2,  6,  9, -1, ],
  [ 8,  4,  7,  3, 11,  5,  3,  5,  1,  5, 11,  6, -1, -1, -1, -1, ],
  [ 5,  1, 11,  5, 11,  6,  1,  0, 11,  7, 11,  4,  0,  4, 11, -1, ],
  [ 0,  5,  9,  0,  6,  5,  0,  3,  6, 11,  6,  3,  8,  4,  7, -1, ],
  [ 6,  5,  9,  6,  9, 11,  4,  7,  9,  7, 11,  9, -1, -1, -1, -1, ],
  [10,  4,  9,  6,  4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4, 10,  6,  4,  9, 10,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  0,  1, 10,  6,  0,  6,  4,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  3,  1,  8,  1,  6,  8,  6,  4,  6,  1, 10, -1, -1, -1, -1, ],
  [10,  4,  9, 10,  6,  4, 11,  2,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  2,  2,  8, 11,  4,  9, 10,  4, 10,  6, -1, -1, -1, -1, ],
  [ 3, 11,  2,  0,  1,  6,  0,  6,  4,  6,  1, 10, -1, -1, -1, -1, ],
  [ 6,  4,  1,  6,  1, 10,  4,  8,  1,  2,  1, 11,  8, 11,  1, -1, ],
  [ 1,  4,  9,  1,  2,  4,  2,  6,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  8,  1,  2,  9,  2,  4,  9,  2,  6,  4, -1, -1, -1, -1, ],
  [ 0,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  3,  2,  8,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  6,  4,  9,  3,  6,  9,  1,  3, 11,  6,  3, -1, -1, -1, -1, ],
  [ 8, 11,  1,  8,  1,  0, 11,  6,  1,  9,  1,  4,  6,  4,  1, -1, ],
  [ 3, 11,  6,  3,  6,  0,  0,  6,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6,  4,  8, 11,  6,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7, 10,  6,  7,  8, 10,  8,  9, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  7,  3,  0, 10,  7,  0,  9, 10,  6,  7, 10, -1, -1, -1, -1, ],
  [10,  6,  7,  1, 10,  7,  1,  7,  8,  1,  8,  0, -1, -1, -1, -1, ],
  [10,  6,  7, 10,  7,  1,  1,  7,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3, 11, 10,  6,  8, 10,  8,  9,  8,  6,  7, -1, -1, -1, -1, ],
  [ 2,  0,  7,  2,  7, 11,  0,  9,  7,  6,  7, 10,  9, 10,  7, -1, ],
  [ 1,  8,  0,  1,  7,  8,  1, 10,  7,  6,  7, 10,  2,  3, 11, -1, ],
  [11,  2,  1, 11,  1,  7, 10,  6,  1,  6,  7,  1, -1, -1, -1, -1, ],
  [ 1,  2,  6,  1,  6,  8,  1,  8,  9,  8,  6,  7, -1, -1, -1, -1, ],
  [ 2,  6,  9,  2,  9,  1,  6,  7,  9,  0,  9,  3,  7,  3,  9, -1, ],
  [ 7,  8,  0,  7,  0,  6,  6,  0,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  3,  2,  6,  7,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  9,  6,  8,  6,  7,  9,  1,  6, 11,  6,  3,  1,  3,  6, -1, ],
  [ 0,  9,  1, 11,  6,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  8,  0,  7,  0,  6,  3, 11,  0, 11,  6,  0, -1, -1, -1, -1, ],
  [ 7, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  5, 10,  7,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  5, 10, 11,  7,  5,  8,  3,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 11,  7,  5, 10, 11,  1,  9,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  7,  5, 10, 11,  7,  9,  8,  1,  8,  3,  1, -1, -1, -1, -1, ],
  [ 2,  5, 10,  2,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  2,  0,  8,  5,  2,  8,  7,  5, 10,  2,  5, -1, -1, -1, -1, ],
  [ 9,  0,  1,  5, 10,  3,  5,  3,  7,  3, 10,  2, -1, -1, -1, -1, ],
  [ 9,  8,  2,  9,  2,  1,  8,  7,  2, 10,  2,  5,  7,  5,  2, -1, ],
  [11,  1,  2, 11,  7,  1,  7,  5,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  1,  2,  7,  1,  7,  5,  7,  2, 11, -1, -1, -1, -1, ],
  [ 9,  7,  5,  9,  2,  7,  9,  0,  2,  2, 11,  7, -1, -1, -1, -1, ],
  [ 7,  5,  2,  7,  2, 11,  5,  9,  2,  3,  2,  8,  9,  8,  2, -1, ],
  [ 1,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  7,  0,  7,  1,  1,  7,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  0,  3,  9,  3,  5,  5,  3,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  8,  7,  5,  9,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  8,  4,  5, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  0,  4,  5, 11,  0,  5, 10, 11, 11,  3,  0, -1, -1, -1, -1, ],
  [ 0,  1,  9,  8,  4, 10,  8, 10, 11, 10,  4,  5, -1, -1, -1, -1, ],
  [10, 11,  4, 10,  4,  5, 11,  3,  4,  9,  4,  1,  3,  1,  4, -1, ],
  [ 2,  5, 10,  3,  5,  2,  3,  4,  5,  3,  8,  4, -1, -1, -1, -1, ],
  [ 5, 10,  2,  5,  2,  4,  4,  2,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3, 10,  2,  3,  5, 10,  3,  8,  5,  4,  5,  8,  0,  1,  9, -1, ],
  [ 5, 10,  2,  5,  2,  4,  1,  9,  2,  9,  4,  2, -1, -1, -1, -1, ],
  [ 2,  5,  1,  2,  8,  5,  2, 11,  8,  4,  5,  8, -1, -1, -1, -1, ],
  [ 0,  4, 11,  0, 11,  3,  4,  5, 11,  2, 11,  1,  5,  1, 11, -1, ],
  [ 0,  2,  5,  0,  5,  9,  2, 11,  5,  4,  5,  8, 11,  8,  5, -1, ],
  [ 9,  4,  5,  2, 11,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  4,  5,  8,  5,  3,  3,  5,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  4,  5,  1,  0,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  4,  5,  8,  5,  3,  9,  0,  5,  0,  3,  5, -1, -1, -1, -1, ],
  [ 9,  4,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4, 11,  7,  4,  9, 11,  9, 10, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  4,  9,  7,  9, 11,  7,  9, 10, 11, -1, -1, -1, -1, ],
  [ 1, 10, 11,  1, 11,  4,  1,  4,  0,  7,  4, 11, -1, -1, -1, -1, ],
  [ 3,  1,  4,  3,  4,  8,  1, 10,  4,  7,  4, 11, 10, 11,  4, -1, ],
  [ 2,  9, 10,  2,  7,  9,  2,  3,  7,  7,  4,  9, -1, -1, -1, -1, ],
  [ 9, 10,  7,  9,  7,  4, 10,  2,  7,  8,  7,  0,  2,  0,  7, -1, ],
  [ 3,  7, 10,  3, 10,  2,  7,  4, 10,  1, 10,  0,  4,  0, 10, -1, ],
  [ 1, 10,  2,  8,  7,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4, 11,  7,  9, 11,  4,  9,  2, 11,  9,  1,  2, -1, -1, -1, -1, ],
  [ 9,  7,  4,  9, 11,  7,  9,  1, 11,  2, 11,  1,  0,  8,  3, -1, ],
  [11,  7,  4, 11,  4,  2,  2,  4,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  7,  4, 11,  4,  2,  8,  3,  4,  3,  2,  4, -1, -1, -1, -1, ],
  [ 4,  9,  1,  4,  1,  7,  7,  1,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  9,  1,  4,  1,  7,  0,  8,  1,  8,  7,  1, -1, -1, -1, -1, ],
  [ 4,  0,  3,  7,  4,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  8,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  9,  3,  9, 11, 11,  9, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1, 10,  0, 10,  8,  8, 10, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  1, 10, 11,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3,  8,  2,  8, 10, 10,  8,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9, 10,  2,  0,  9,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3,  8,  2,  8, 10,  0,  1,  8,  1, 10,  8, -1, -1, -1, -1, ],
  [ 1, 10,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 11,  1, 11,  9,  9, 11,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  9,  3,  9, 11,  1,  2,  9,  2, 11,  9, -1, -1, -1, -1, ],
  [ 0,  2, 11,  8,  0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  3,  8,  9,  1,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  9,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  3,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ]
 ]

for idx, verts in enumerate( triTable ) :
 verts = [ x for x in verts if x != -1 ]
 triTable[ idx ] = verts


def merge_triangles( a, b ) :
 assert a
 assert b
 isshared = [ x in a for x in b ]
 shared   = [ x for x in b if x in a ]
 unshared = [ x for x in b if not x in a ]
 numshared = len( shared )
 if numshared == 0 :
  return False
 if numshared == 1 :
  return False
 if numshared == 2 :
  edge = [-1,-1]
  if not isshared[ 0 ] :
   edge = [ shared[1], shared[0] ]
  if not isshared[ 1 ] :
   edge = [ shared[0], shared[1] ]
  if not isshared[ 2 ] :
   edge = [ shared[1], shared[0] ]
  face = list( a )
  idx = face.index( edge[1] )
  face.insert( idx, unshared[0] )
  assert face
  return face


polyTable = []
lineTable = []

for casenr, verts in enumerate(triTable) :
 vc = len( verts )
 if vc == 0 :
  polyTable.append( None )
  continue
 if vc == 3 :
  polyTable.append( ( verts, ) )
  #print vc, verts
  continue
 if vc == 6 :
  a = verts[ :3 ]
  b = verts[ 3: ]
  face = merge_triangles( a, b )
  if face :
   polyTable.append( ( face, ) )
   #print "4",face
  else :
   polyTable.append( ( a, b ) )
   #print "3+3",a,b
 if vc == 9 :
  # This could be one quad and one triangle or a pentagon?
  a = verts[ 0:3 ]
  b = verts[ 3:6 ]
  c = verts[ 6:9 ]
  face_ab = merge_triangles( a, b )
  face_bc = merge_triangles( b, c )
  if face_ab and face_bc :
   face = merge_triangles( face_ab, c )
   #print "5", face
   assert face
   polyTable.append( ( face, ) )
   continue
  if face_ab :
   polyTable.append( ( face_ab, c ) )
   #print "4+3", face_ab, c
   continue
  if face_bc :
   polyTable.append( ( a, face_bc ) )
   #print "3+4", a,face_bc
   continue
  # just three triangles
  #print "3+3+3", a,b,c
  polyTable.append( ( a, b, c ) )
  continue
 if vc == 12 :
  # This could be two quads, or a hexagon?
  a = list(verts[ 0:3 ])
  b = list(verts[ 3:6 ])
  c = list(verts[ 6:9 ])
  d = list(verts[ 9:12])
  face_ab = merge_triangles( a, b )
  face_bc = merge_triangles( b, c )
  face_cd = merge_triangles( c, d )
  if face_ab and face_cd and not face_bc :
   polyTable.append( ( face_ab, face_cd ) )
   #print "4+4", face_ab, face_cd
   continue
  if face_ab and face_cd and face_bc :
   # One big hexagon
   face_abc = merge_triangles( face_ab, c )
   assert face_abc
   face_abcd = merge_triangles( face_abc, d )
   assert face_abcd
   #print "6", face_abcd
   polyTable.append( ( face_abcd, ) )
   continue
  if face_ab and face_bc :
   face_abc = merge_triangles( face_ab, c )
   #print "5+3", face_abc, d
   polyTable.append( ( face_abc, d ) )
   continue
  if face_bc and face_cd :
   face_bcd = merge_triangles( face_bc, d )
   #print "3+5", a, face_bcd
   polyTable.append( ( a, face_bcd ) )
   continue
  if face_ab and face_cd :
   #print "4+4", face_ab, face_cd
   polyTable.append( ( face_ab, face_cd ) )
   continue
  # Difficult case: give up.
  polyTable.append( None )

 if vc == 15 :
  # Five triangles.
  a = list(verts[ 0:3 ])
  b = list(verts[ 3:6 ])
  c = list(verts[ 6:9 ])
  d = list(verts[ 9:12])
  e = list(verts[12:15])
  face_ab = merge_triangles( a, b )
  face_bc = merge_triangles( b, c )
  face_cd = merge_triangles( c, d )
  face_de = merge_triangles( d, e )
  #print a,b,c,d,e
  #print face_ab, face_bc, face_cd, face_de
  # Difficult case: give up
  polyTable.append( None )
#print len( polyTable )
#print polyTable

for polies in polyTable :
 print polies
 v = []
 if polies :
  for p in polies :
   l = len( p )
   for i in range( l ) :
    v.append( p[ i       ] )
    v.append( p[ (i+1)%l ] )
 while len( v ) < 20 :
  v.append( -1 )
 lineTable.append( v )

print len( lineTable )

s = repr(lineTable)
s = s.replace( '[', '{' )
s = s.replace( ']', '}' )
s = s.replace( '},', '},\n' )

print s


Saturday, July 27, 2013

Evaluating PolyVox

In my pursuit of simulating soil digging, I started to evaluate the PolyVox library. This is a report on that evaluation.

Building on MacOSX is tricky. With LLVM version 4.2 (clang-425.0.28) installed, this error comes up when compiling the very first file: fatal error: 'cstdint' file not found. According to this StackOverflow thread this should be solved by invoking with: /usr/bin/clang++ -std=c++11 but I found this not to be the case. So instead I decided to just drag in the source files into a new XCode project.

After dragging in sources and headers, you need to set the project's header include path. It needs to find its way to polyvox/library/PolyVoxCore/include/ e.g.

In PolyVoxCore two warnings are issued by the compiler for SurfaceMesh::addVertex() and SurfaceMesh::getNoOfIndices() because they return 32 bit ints, and vector::size() returns 64 bit ints. Other than this, the code is very clean. Even LLVM's Analyzer does not find anything else on it.

PolyVox can store the volume as a series of 32x32x32 blocks. It would make sense to do the surface extraction on a per-block basis. That way, if voxels change, you only have to create new OpenGL VBOs for the blocks that are affected. It's not entirely clear how to do this. It may be enough to create multiple extractors on 32/32/32 boundaries, and then only execute extractors for blocks that have changed.

Redux

So, my opus magnum is the game The Little Crane That Could. Every day, people tell me that they want more levels for it. The truth is, my inspiration for new tasks/puzzles to be solved with a crane is now exhausted. That is why I released a level editor for the game. Still, people want more. Others suggest a sequel to the game. But I think there can only be a sequel if there is a significant improvement to the current game. So let's talk about this sequel. First, how to name it?

  • The Little Crane Reloaded
  • The Little Crane: Redux
  • The Little Crane Strikes Back
  • The Little Crane 2014 edition
  • The Little Crane That Could: The Diggening (thanks Matt)

With whatever name it ends up, some serious new tech needs to be part of it. A logical next step would be to add deformable terrain to it. It needs soil that you can dig into, pile up, move around, maybe even compact. Doing a convincing simulation of soil digging is incredibly hard. I don't think anyone has actually done this properly, and certainly not at a smooth 60fps real time manner. Can I do it? Probably not, but it would sure be fun to try. Let me list a few attempts by others.


Digger Simulator 2011 does not look too convincing at timestamp 27sec. The loading of the scoop is too contrived. Whatever approach they took, it is not worth pursuing judging from this video.

This paper from the university of Aachen looks more promising. However, since they incorporate height fields into their solution, it makes tunnels and overhangs impossible. The video is impressive. And their model supports compacting of the soil.

Atomontage is definitely one of the most impressive demos out there. The rock sections show cliffs and overhangs, but it is hard to judge whether the sand can do overhangs as well. Tyre impressions are done well, could it do digging, tunnelling?

Spin Tires looks pretty, but when closely examining the soil, you will see that they are using a simple height field. Again, this means no overhangs, no tunnelling, etc.

This video of Cubiquity Voxel Engine (using PolyVox) is not a soil simulator. But a powerful voxel engine could possible be a great starting point for simulating soil.

For now, I think I will study PolyVox, and see what is possible with this. If you have come across a good soil simulator (or deformable terrain algorithm) that is convincing and suitable for games, please drop a link in the comments. And thank you for reading.

Introduction

I will use this first post to introduce myself. I am a software developer from Vancouver, British Columbia. I am best known for a hit game I developed for iOS, called The Little Crane That Could. Since then, I've published many other games, none reaching the popularity of Little Crane. This is why I consider myself, for now, a one-hit-wonder. Because game development is so much fun, I will keep publishing new games though. It is more than a job, it is my life's biggest passion.

I graduated at the University of Amsterdam. I've spent a large part of my career specializing in Virtual Reality, and developing VR simulations for industry and academia.

I have kept a weblog before, but since my primary weblog was a mix between development topics and personal articles I decided to branch off a new weblog. The weblog you are reading now will solely be dedicated to documenting my game development efforts. This means less noise, more signal, for my tech oriented audience. Also, I love reading comments from you!