Thursday, May 14, 2020

A Random Direction.

A naive way of generating a random direction d(x,y,z) would to take random values for x,y,z and then normalize the resulting vector d. But this will lead to a skewed distribution where too many samples fall in the "cube corners" directions.

A proper way to generate a random direction d(x,y,z) is to do the same, but add rejection-sampling.

  • If the resulting vector has length < 1, then normalize the vector, and use it.
  • If the resulting vector is longer, then reject it, and try again.

The downsides of the proper method are:

  • It is slower.
  • Freak occurrences of having to retry many times.
  • It has branch instructions in it.

I want the fastest possible, 8x SIMD way of generating random vectors. That means, no branching. And that got me thinking about a direction generator that is fast, but less skewed than the naive way. We would tolerate a little bias at the benefit of speed.

An approach I came up with: just generate two sets of coordinates, yielding two candidates. Use the candidate with the shortest length. Picking that candidate can be achieved without any branching, by just using the _mm256_blendv_ps intrinsic.

In pseudo code:

// 8-way vector for the candidates a:
__m256 cand_ax = [random values -1..1]
__m256 cand_bx = [random values -1..1]
__m256 cand_cx = [random values -1..1]
// get lengths for candidates in a and b.
__m256 len_a = length_8way( cand_ax, cand_ay, cand_az );
__m256 len_b = length_8way( cand_bx, cand_by, cand_bz );
// pick the shortest candidates in each lane.
__m256 a_is_shorter = _mm256_cmp_ps( len_a, len_b, _CMP_LE_OS );
__m256 cand_x = _mm256_blend_ps( cand_bx, cand_az, a_is_shorter );
__m256 cand_y = _mm256_blend_ps( cand_by, cand_ay, a_is_shorter );
__m256 cand_z = _mm256_blend_ps( cand_bz, cand_az, a_is_shorter );
__m256 len    = _mm256_blend_ps( len_a, len_b, a_is_shorter );
// normalize
__m256 ilen = _mm256_rcp_ps(len);
__m256 x = _mm256_mul_ps( cand_x, ilen );
__m256 y = _mm256_mul_ps( cand_y, ilen );
__m256 z = _mm256_mul_ps( cand_z, ilen );

What is this all good for? You can generate noise fields with random gradients and not having to resort to lookup tables. No pesky gathers either! Just create the gradient on-the-fly, each time you sample the field. There is no memory bottle neck, it is all plain computing, without any branching. Added bonus: no wrap-around of the field due to limited size of lookup table.

While implementing, I noticed that I forgot something: when sampling the field, I need to construct the random directions at 8 gridpoints, so it will be a lot slower than a table lookup, unfortunately. Oh well.

Sunday, October 27, 2019

It is 2019. How do you develop a native Android app?

Back in 2011, my first attempt on porting to Android was to compile the existing code-base as-is, in Objective-C. With a third party Stella-SDK you could pretend your Android Device was an OpenStep device, very much like an iOS device. However, this never fully worked, so had to be abandoned.

The second approach is the approach I am using to this day, for creating my Android portfolio: Use a sliver of Java, and write the rest in C and C++. And you can use JNI and android_native_app_glue.h to bridge between them. The sliver of Java came in the form of the NativeActivity class, from which you derived your application activity. Building was initially done with ant and ndk-build, but I've moved to AndroidStudio since then.

Skip forward to 2019. I am considering an Android port for my Windows/Linux title Hexa Trains. Unsurprisingly, this is a C/C++ code base, so it would entail another native Android port. Is Java's NativeActivity still the way to do native app development?

Google has been pushing Kotlin for quite some time. I've always held off on that. I wonder if it is still something that has Google's focus, or did they move on from that already? But I guess Kotlin and NDK is an option?

I guess most (sane) gamedevs just use Unity and be done with it?

Tuesday, October 22, 2019

Horror Vacui

Aristotélēs postulated that Nature abhors a vacuum. There is probably an equivalent postulate for the Internet Age about unused computing resources.

I've been dumbfounded many times about the ridiculous amount of bloat in software.

Be it the 18,000 classes in an iOS app. That is 18,000 classes, mind you! Not 18,000 objects.

Or the enormous big ball of mud that imgur uses to serve an image.

Or the 1.2M lines of code to simply boot an OS. Not the OS it self, mind you, just the boot system that lives on top of the OS.

I think these things grew out of control purely by the grace of fast computers. Moore's law makes them faster, more powerful, and immediately sloppy engineers fill it with a plethora of layered frameworks.

It would be better if all software engineers were forced to use a decade old computer, so that teraflop machines will not be brought to their knees trying to load a webpage or something. Leave the modern and fast machinery to the users and clients, but develop the software on Raspberry Pi's maybe?

So, are you a software engineer? Please surrender your dual GPU, 16 core machine to the bureau of software simplification, and compile, link, test your software on the Raspberry Pi that will be provided to you. No ifs and buts... that Raspberry Pi is vastly more capable than the Apollo 11 Guidance Computer. It will do.

Nature abhors unused RAM and CPU cycles.

Thursday, October 10, 2019 achievements.

I got a couple of requests for Hexa Trains to be available from and not just Steam. At first glance, that should be easy enough, I've published stuff there before.

But with Hexa Trains there is a complication in the fact that the end-goal of the game, is to unlock the Steam Achievements. And without achievements, that goal would be missing. has no Achievement/Leader-board API. More than that, it does not even have the concept of User IDs, nor logging in via the game. So what would achievements on an version look like?

I thought "Can you do leader-boards without a log-in system? And then I quickly remembered the 1980s. Getting listed in the leader-boards by writing your three letter initials.

So at the very least, something like this is possible. But in modern times, there is more to record than just a single number for the high score. All sorts of statistics are tracked between sessions. For instance, in my game, the number of rail sections laid down.

So, we still have the problem of tying a player to the statistics. But do so without adding the hurdle of a log in step. And tying the player to a name should be optional, like it was on a PacMan Arcade Cabinet.

Thinking about this problem made me want to see if I could write my own Open Sourced Achievement/Leader-board system. So let's start with the requirements.

  • No log-in stage.
  • No user id.
  • No email address.
  • Name/Initials optional.
  • API similar to existing frameworks (Game Center, Steam, Google Play.)
  • A server to keep track of progress and scores.
  • Don't track between different game titles.

I think something like that could work. Step 1 would be to generate a random number to be used as a unique ID to identify a player for this specific game. All subsequent launches of the game title, should use this ID when reporting scores and achievement progress. There will be no name/initials associated with this ID, until the player chooses to do so.

To preempt any pranksters wanting to be obscene, racist, or otherwise, the optional name should come in the form as 3-letter initials. It is too hard to be obscene in English, using just three letters. (You can be in Dutch, though. But meh.) This removes the need for moderation by humans. (Duplicate initials is not much of a problem. Stats are tracked separately via the ID.) Also, Latin-alphabet only would be a safe choice with respect to obscenities as well. Less expressive means safer.

I also think it would be a good idea to be as lightweight as is conceivably possible. And it doesn't get much lighter-weight than single-UDP-packet fire-and-forget communication. Stat updates could conceivably get lost, as could scores. I think we should just ignore that. If stats are reported in absolute values, it will get corrected in a future report. If it is reported as deltas, meh.

Note that achievements could be a purely local thing. No need for a server. Only high-scores would need to be shared. But for sake of symmetry and versatility, both via a server could have benefits.

There is still the issue of presentation. The player needs to be notified of unlocking an achievement. How? Put that burden 100% on the game developer? A nice thing about Steam/iOS/GooglePlay is that you don't have to think about that as a game developer. You report the stats, the system will tell the player if it is appropriate. But how would you do this without having control over the game's window?

Let me conclude with: what are your thoughts on this? Leave a comment!

Monday, September 30, 2019

Early Results from Google Play Experiment.

I have some early results to share about my Google Play Experiment. To recap: I released a game that requires Android 9+, hence is available for a mere 10% of the devices that use Google Play. So, is store-traffic reduced with -90% as well?

I was baffled to see that store traffic was flat out zero. Worse than that, the title will not show up at all, no matter how you search for it! I have created an un-searchable title!

First order of business, let's verify whether the title actually exists on the store, using the link from the Google Play Developer Console, here:

Ah, phew... it is actually there!

Now, let's search for it in Google Play using it's exact (longish) title:

I guess I should be happy that the first hit is actually on one of my own apps, and not a competitor. But still... the game is not in the search results. It returns 249 results in total, by the way.

Ok, maybe the fans of my older titles will find it by checking out the store page on my company? Let's go to my other game, and click on the "Game Studio Abraham Stolk Inc." link.

Even here, it is not present. Ok, a title that has zero links pointing at it from the Google Play store it self. This is going to be tricky. I need to leverage the existing customer base. So I put an advertisement for Little Crane 2 in my free game 'Six Wheels and a Gun.'

And yes! A big thank you to my first customer from Switzerland. I appreciate your support. So the store is working: you can buy Little Crane 2: Mud Play.

I celebrate every sale. That customer rocks. But hey... wait a minute.... what is that?

Der Nachfolger von "The Little Crane That Could", mit dem Sie im Schlamm graben können.

A German translation of the store page? I never added any translations. The developer console also lets you purchase translations, but I never did that. Who translated this? To me, it seems good enough to be a human translation, not a machine one, by the way.

So there we have it, ladies and gentlemen... A title on Google Play that you cannot search for and cannot find without a direct link taken from the developer console. But somehow, it has been translated.

I complained to Google. It took them a few weeks, but they have half-way fixed it now. It is now possible to get "Little Crane 2: Mud Play" back as a search result. Sadly, only as the 5th title, even when searching the exact name. But hey, at least it is returned, and listed on my portfolio page.

Wednesday, September 25, 2019

Google Play Experiment.

In 2015, I released a successor to The Little Crane That Could on Steam for Windows, Linux, MacOS.

In the sequel, I wanted to do something special, and decided to make the terrain deformable. This means, you can dig into the terrain, anywhere, and deposit soil anywhere. And not just constrained to height-maps, but a real full 3D terrain that includes caves, overhangs, and such.

An ambitious undertaking, but I think it got there. Being on desktop, instead of mobile, meant that there was more CPU power available. The collision of all those dirt particles against a dynamic terrain is far from cheap.

After publishing the Windows/Linux/Mac versions, I decided to push the iOS hardware and see if the latest iOS devices were up to the task. To my surprise, iOS CPUs were surprisingly powerful, and able to pull it off (although often below 60fps, or even 30fps, but the 2015 devices were able to run it.)

Back then I also tried a quick Android port, but the average Android device was trailing so far behind Apple's performance (floating point calculations), that I could not publish it there. An Android tablet would just be bogged down, unable to compute the simulation at interactive rates.

Now, skip to 2019. Four years later, the Android devices are roughly where iOS devices were in 2015, when it comes to running my (OpenDE based) soil simulation. It is time to revisit the Android port!

For the Android port, I decided to do an experimental release. Since I can only afford to run on fast devices, I thought I would cut down massively on supported devices. For starters, 64 bit ARM only. And I will publish for Android version 9 and newer (which is just a 10% marketshare.) To top it off, only for devices with ES3.1 and higher.

One of the questions I want to answer with this experiment is how Google Play would treat such a title. Let's say Google Play decides to promote your title in the "Similar Titles" section on the store. And let's say, the Google Play store algorithm decides to grant you 1000 slots, or views. Will it simply drop 900 of those slots for customers on incompatible devices? Or will it keep trying to find customers with compatible devices to show your app to?

Or in short.... by reducing your compatibility to 10% of the devices, will you reduce the in-store visibility to 10% of its potential, as well? I honestly do not know. And I don't even know if I can reliably measure it? I guess compare store-stats with my other apps? Or after a while, add Android-8 support and see if store hits increase?

UPDATE: It has been released. But somehow, it is impossible to search for it? It will not even show up under the publisher page of Game Studio Abraham Stolk Inc. This is weird.

Tuesday, September 17, 2019

Sanitizing addresses of your Android NDK application.

In my attempt to squash all bugs, I ran my Android app with clang's address sanitizer. Because the steps are not trivial, I thought I would documents the process here.

This recipe makes some assumptions, though:

  • I'm on Linux.
  • I use AndroidStudio with CMake.
  • I run on the Android emulator. (A real device shouldn't be much different.)

First, we need to pass the -fsanitize=address flag to both the compiler and the linker. To compile your C/C++ code with this flag, use this in your CMakefile

target_compile_options(foo PRIVATE

And to link, add "-fsanitize=address" to your target_link_libraries.

Ok, now your shared-object has been built with the address sanitizer. But if you try to run it, you will see: dlopen failed: library "" not found.

Luckily, the Android NDK comes with the correct libraries, you just need to package them with your build. First locate where this library is on your system, doing:

$ locate

You simply need to copy this alongside your own shared object file, as generated by cmake. In my case, it goes in: ./app/build/intermediates/cmake/debug/obj/x86/

If you now build and run your app on the emulator, your addresses will get sanitized. In my first run, it found a free() of a pointer that was never malloc()-ed in the Google Play Games SDK.

Note that if you want to do this on a ARM device, you would need and on a 64-bit ARM device, look for instead.