Adaptive random generation of multiple outcomes

Games often want to use randomness to spice up the experience – it can be a lot more exciting to risk something when you are not entirely certain of the result. In my game abstractanks, the power-ups are generated randomly. However, when playing the game, it seemed like it was always generating the same power-ups in a row, which can be kind of frustrating. Tough luck, because this is just how uniform randomness behaves – as anyone who ever played the board game Sorry! or the german class Mensch ärgere dich nicht! can sure testify.

Let’s try that with C# code:

var outcomes = new []{'A', 'B', 'C', 'D', 'E', 'F'};
for (int i = 0; i < 200; ++i)
{
  var index = random.Next(outcomes.Length-1);
  Console.Write(outcomes[index]);
}

This will produce something like this:

ECDDBABCEEBBDDADEDECCAECECEADBBCCCDAEBEECDBCACAEAA
BDEACECBDDBAEDCEEAEAECDEEEECBCCEECEDCBAECCCBDCDDEA
CEAABDEEBDEAEBABABDEBDAACBECBBAACAEDEEBAECECECCBAB
BBAAEEDEDEEBCACDDEBBCBACADDDBAECBAEDACBEAEABBCAEEA

See all those strings of Cs and Es? Horrible! That does not feel random!

Games Dota 2 work with this by tweaking distribution after each “roll”. Specifically, for things like Phantom Assassin’s Coup de Grace, the chance is increased slightly after each unsuccessful attempt, making the 4th or so attempt a guaranteed critical strike.
But this technique only work nicely for one event in a stream of attempts. It fails to make multiple outcomes look better.
For game I devised an algorithm with two properties:
1. The same roll never appears twice in succession
2. No long stretches without a specific roll
Here’s my algorithm to do that:

var outcomes = new []{'A', 'B', 'C', 'D', 'E', 'F'};
var chances = new []{1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
for (int i = 0; i < 200; ++i)
{
  // Normalize chances so they sum up to 1.0, then build their prefix sum
  var total = chances.Sum();
  var prefixSum = chances
    .Select(x => x / total)
    .Aggregate(new List<double>(), (list, x) =>
    {
      list.Add(list.LastOrDefault() + x);
      return list;
    }).ToList();

  // Roll an outcome
  var roll = random.NextDouble();
  var pick = prefixSum.FindIndex(x => x >= roll);
  Console.Write(outcomes[pick]);

  // Now adapt the distribution by removing all chance from
  // the last pick and distributing it to the N-1 others
  var increment = chances[pick] / (chances.Length - 1);
  chances = chances.Select((x, index) =>
  {
    if (index == pick)
      return 0.0;
    else
      return x + increment;
  }).ToArray();
}

And here’s what that produces:

AEDFBCAEFDBAEDFCBDECBFCFDBEACFDECBDAEFCEBACDEAFBDC
AFEBCABFDECDAFBECFADFCEBACFDCEDBFAEDCDBDAFEDBFEABD
CFABEDFBACDEAEFBECADBAFECAFBDACECFAEBDCAFCDBAEDAFA
BDFCDEACDBFEDFCBACDAFBEADFCDEFBEACBEFDCECFABDFCDBE

Much nicer for my needs, but it still looks pretty random. Also, my statistics buddy assured me that this algorithm still guarantees equal outcome probability for all items when run forever. I do now know if this is a new technique, but I did not find anything like this when I was looking for it.
Let me know if this is of any use to you.

Automated vulnerability checking of software dependencies

The OWASP organization is focused on improving the security of software systems and regularly publishes lists with security risks, such as the OWASP Top 10 Most Critical Web Application Security Risks or the Mobile Top 10 Security Risks. Among these are common attack vectors like command injections, buffer overruns, stack buffer overflow attacks and SQL injections.

When developing software you have to be aware of these in order to avoid and prevent them. If your project depends on third-party software components, such as open source libraries, you have to assess those dependencies for security risks as well. It is not enough to do this just once. You have to check them regularly and watch for any known, publicly disclosed, vulnerabilities in these dependencies.

Publicly known information-security vulnerabilities are tracked according to the Common Vulnerabilities and Exposures (CVE) standard. Each vulnerability is assigned an ID, for example CVE-2009-2704, and published in the National Vulnerability Database (NVD) by the U.S. government. Here’s an example for such an entry.

Automated Dependency Checking

There are tools and services to automatically check the dependencies of your project against these publicly known vulnerabilities, for example the OWASP Dependency Check or the Sonatype OSS Index. In order to use them your project has to use a dependency manager, for example Maven in the Java world or NuGet in the .NET ecosystem.

Here’s how to integrate the OWASP Dependency Check into your Maven based project, by adding the following plugin to the pom.xml file:

<plugin>
  <groupId>org.owasp</groupId>
  <artifactId>dependency-check-maven</artifactId>
  <version>5.0.0-M1</version>
  <executions>
    <execution>
      <goals>
        <goal>check</goal>
      </goals>
    </execution>
  </executions>
</plugin>

When you run the Maven goal dependency-check:check you might see an output like this:

One or more dependencies were identified with known vulnerabilities in Project XYZ:

jboss-j2eemgmt-api_1.1_spec-1.0.1.Final.jar (pkg:maven/org.jboss.spec.javax.management.j2ee/jboss-j2eemgmt-api_1.1_spec@1.0.1.Final, cpe:2.3:a:sun:j2ee:1.0.1:*:*:*:*:*:*:*) : CVE-2009-2704, CVE-2009-2705
...

The output tells you which version of a dependency is affected and the CVE ID. Now you can use this ID to look it up in the NVD database and inform yourself about the potential dangers of the vulnerability and take action, like updating the dependency if there is a newer version, which addresses the vulnerability.

Object slicing with Grails and GORM

Some may know the problem called object slicing when passing or assigning polymorphic objects by value in C++. The issue is not limited to C++ as we experienced recently in one of our web application based on Grails. If you are curious just stay awhile and listen…

Our setting

Some of our domain entities use inheritance and their containing entities determine what to do using some properties. You may call that bad design but for now let us take it as it is and show some code to clarify the situation:

@Entity
class Container {
  private A a

  def doSomething() {
    if (hasActuallyB()) {
      return a.bMethod()
    }
    return a.something()
  }
}

@Entity
class A {

  def something() {
    return 'Something A does'
  }
}

@Entity
class B extends A {

  def bMethod() {
    return 'Something only B can do'
  }
}

class ContainerController {

  def save = {
    new Container(b: new B()).save()
  }

  def show = {
    def container = Container.get(params.id)
    [result: container.doSomething()]
  }
}

Such code worked for us without problems in until we upgraded to Grails 3. Suddenly we got exceptions like:

2019-02-18 17:03:43.370 ERROR --- [nio-8080-exec-1] o.g.web.errors.GrailsExceptionResolver   : MissingMethodException occurred when processing request: [GET] /container/show
No signature of method: A.bMethod() is applicable for argument types: () values: []. Stacktrace follows:

Caused by: groovy.lang.MissingMethodException: No signature of method: A.bMethod() is applicable for argument types: () values: []
at Container.doSomething(Container.groovy:123)

Debugging showed our assumptions and checks were still true and the Container member was saved correctly as a B. Still the groovy method call using duck typing did not work…

What is happening here?

Since the domain entities are persistent objects mapped by GORM and (in our case) Hibernate they do not always behave like your average POGO (plain old groovy object). They may in reality be Javassist proxy instances when fetched from the database. These proxies are set up to respond to the declared type and not the actual type of the member! Clearly, an A does not respond to the bMethod().

A workaround

Ok, the class hierarchy is not that great but we cannot rewrite everything. So what now?

Fortunately there is a workaround: You can explicitly unwrap the proxy object using GrailsHibernateUtil.unwrapIfProxy() and you have a real instance of B and your groovy duck typing and polymorphic calls work as expected again.

Makeup on a zombie – Java Swing UX improvements

When I learned Java programming in 1997, the AWT classes were the default way to create graphical user interfaces. The AWT widgets were not very sophisticated and really ugly, so it is no surprise they were replaced by a new widget toolkit, called “Swing”, as soon as possible. At the end of 1998, the Swing graphical API was the default way to develop GUIs for desktop applications on the Java platform.

Today, twenty years later, the Swing API is still part of the Java core SDK and ready for your adventures in GUI creation. But time has taken a toll on the technology. The widgets, once displayed with a state-of-the-art design, look really outdated. Swing introduced the concept of pluggable “Look-and-Feels” (L&F), so you could essentially re-skin your interface with a few lines of code, but all L&Fs look ugly and feel cumbersome now. You can say that Java Swing is a zombie: It is still available and in use in its latest development state, but makes no progress in regard of improvements. If software development follows one rule, it is that software that isn’t actively developed anymore is dead.

My personal date when Java Swing died was the day Chet Haase (author of the Java Swing book “Filthy Rich Clients”) left Sun Microsystems to work for Adobe. That was in 2008. The technology received several important updates since then, but soon after, JavaFX got on the stage (and left it, and went back on, left it again, and is now an optional download for the Java SDK). Desktop GUIs are even more dead than Java Swing, because “mobile first” and “web second” don’t leave much room for “desktop third”. Consequentially, Java FX will not receive support from Oracle after 2022.

But there are still plenty of desktop applications and they won’t go away anytime soon. There is a valid use case for a locally installed program with a graphical user interface on a physical computer. And there are still lots of “legacy systems” that need maintenance and improvements. Most of them are entangled with their UI toolkit of choice – a choice made before 2007, when “mobile first” wasn’t even available as an option.

Because those legacy systems still exist and are used, their users want to experience the look and feel of today’s applications. And this is where the fun begins: You apply makeup on a zombie to let it appear a little bit less ugly than it really is.

Recently, my task was to improve the keyboard handling of a Java Swing desktop application. It was surprisingly easy to add a tad of modern “feel”, and this gives me hope that the zombie might stay semi-alive longer than I thought. As you might already have guessed, StackOverflow is a goldmine for answers on ancient technology. Here are my first few improvements and their respective answer on StackOverflow:

  • Let’s suppose you want or need to interact with your application without a mouse or touchscreen. Your first attempt to start an interaction is to press the “menu” key in order to activate the application menu. This would be the “Alt” key on a windows system. For modern applications, your input focus is now at the menu bar. In Java Swing applications, nothing happens. You have to press “Alt” and a mnemonic character to enter a specific menu. If you want to reduce the initial hurdle to just one key, you need to teach all your Java Swing menus to react to the “Alt” key alone: https://stackoverflow.com/a/8659116
  • Speaking of focus, in modern applications you can move your focus by using the arrow keys. Java Swing still thinks that “Tab” and “Shift+Tab” is the pinnacle of focus control. If you want to improve the behavior (and therefore the “feel”) of your focus traversal, you can do it globally for your application: https://stackoverflow.com/a/8255423
  • And if you want to enable the Return/Enter key for button activation, you can do it with just one line: https://stackoverflow.com/a/440536

If you happen to work on a Java Swing application and want some cheap user experience upgrades, I’ve assembled all the knowledge above into a neat little class that you can use as an add-on utility class: https://github.com/dlindner/java-swing-ux/blob/master/src/com/schneide/swing/ux/KeyboardUX.java

What are your makeup tips for zombies?

A programmer’s report on the Global Game Jam

Last weekend was this year’s global game jam. A game jam is a type of event where the participants – the “jammers” – create a game in a fixed, usually quite short, amount of time with some additional restrictions like a theme. Usually, this means computer games, although you can also make board or pen and paper games.

A worldwide event

As the name implies, the global game jam is a worldwide event. Most bigger cities have “hubs”, i.e. jam locations, where the jammers gather at the beginning of the weekend in their local time zone. Then, a few motivating keynote videos are shown before the theme is announced. Last year’s theme was “Transmission”, while this year’s theme was “What Home means to you”. A game using that theme is to be created within the next 48-hours.

The pitch

People get a few minutes to brainstorm about the theme and maybe get an idea that they want to implement. There is kind of a small stage area, where people with those ideas pitch them to the others in hopes of getting a team assembled. Last year, a guy even made a short power-point presentation to pitch his idea.
While you can make a game on your own, that is pretty hard. You typically need at least programming, graphics, audio, music, project-management and game-design expertise on your team. It is rare to find that in a single person.

Implementation

So if you have a nice idea, or join a team with one – now implementation work starts.

Last year, my team quickly abandoned of using Unity as the engine for our terra-forming game, since no one on the team had any experience with it. We switched to Love2D, a neat little framework based on Lua. It is a very lightweight little framework and Lua is an elegant engine. Given that our team had no dedicated graphics people, I am pretty proud of the little game that we finished: Terraformer

This year, I joined another team and we picked the Godot engine to create our game. Godot comes with its own programming language called “Godot script”. The syntax looks like it borrows heavily from both Python and JavaScript. It is, however, quite pleasant to work with, except that most higher-order functional features that are all so common on most languages seem to be missing. But it does have coroutines, so there’s that.
Either way, working with godot was mostly pretty pleasant, except for its interaction with git. Just opening specific parts of the game in the godot editor would change files, and sometimes we’d get huge nonsensical changes, and merge conflicts, when someone on another platform (i.e. between Mac and Windows) pushed something.
We ended up making this little game: Home God
I’m particularly proud of the character movement controls. I think they turned out quite fluidly.

Not just for game programmers…

The global game jam is an awesome experience for non-game programmers looking to improve their craft. In fact, most participants in my hub where at most hobbyists, from what I could tell. The tight time-budget and the objective of just getting it to work will give many programmers a totally different perspective of how to do things. Things that steal your time will hurt a lot.

Organize complex SQL queries with Common Table Expressions

Complex SQL database queries often contain subqueries.

SELECT * FROM ... 
   WHERE name IN (SELECT name 
         FROM ... 
         WHERE ...)

These can quickly become unreadable, especially if multiple subqueries are involved. A nice way to organise such queries with multiple subqueries is called Common Table Expressions (CTE), or colloquially: “WITH queries”. They are supported by most contemporary SQL databases.

When using Common Table Expressions you list all the subqueries after a WITH keyword in front of the actual query and assign a name to each subquery:

WITH
  <subquery1_name> AS (SELECT ...),
  <subquery2_name> AS (SELECT ...),
  [ ... ]
SELECT ...
FROM ...
[ ... ]

You can now refer to these subqueries in the main query by their names. They are conceptually just like temporary views. You can also refer to a subquery in the main query multiple times, whereas if the subquery was inlined you would have to repeat it. A subquery defined as a Common Table Expression can also refer to the preceding subqueries in the subquery list.

Recursion

A Common Table Expression can even refer to itself, which is a recursive definition. In some database systems you have to add the RECURSIVE keyword after WITH, in others you can leave it out. Here’s a recursive CTE that calculates factorial numbers:

WITH RECURSIVE factorials (n, fact) AS 
  (SELECT 0, 1
   UNION ALL
   SELECT n+1, (n+1)*fact FROM factorials
          WHERE n < 6)
SELECT * FROM factorials;
N FACT
0    1
1    1
2    2
3    6
4   24
5  120

You could also use such a recursive query to descend into a tree hierarchy.

While the use cases for recursive queries are less frequent, I find the general concept of Common Table Expressions very useful to make complex queries more readable.

Unexpected RESTEasy application upgrade surprise

The setting

A few months ago we got to maintain a RESTEasy application running in a Wildfly 10 container. The application uses RESTEasy as both, server and client and contains a few custom interceptors and providers.

Now our client wants to move on to Wildfly 13 as deployment target. Most of the application works out-of-the-box or just by upgrading some dependencies in the new container but some critical parts like the REST client requests stopped working.

The investigation

After some digging through the error messages it became clear our interceptors and providers were not called anymore. What has changed? Wildfly 13 comes with RESTEasy 3.5.1 while we were using 3.0 in Wildfly 10. Looking at the upgrade documentation leaves us puzzled though:

RESTEasy 3.5 series is a spin-off of the old RESTEasy 3.0 series, featuring JAX-RS 2.1 implementation.

The reason why 3.5 comes from 3.0 instead of the 3.1 / 4.0 development streams is basically providing users with a selection of RESTEasy 4 critical / strategic new features, while ensuring full backward compatiblity. As a consequence, no major issues are expected when upgrading RESTEasy from 3.0.x to 3.5.x.

We are using the standard classpath scanning method which discovers annotated RESTEasy classes and registers them for the application. Trying to register them explicitly in the application yielded the message, that our providers are already registered:

RESTEASY002155: Provider class mypackage.MyProvider is already registered. 2nd registration is being ignored.

Scanning and registration seemed to just work alright. So what was happening here?

The resolution

After a bit more investigation we realized the issue was on the client side only! In Wildfly 10/RESTEasy 3.0 the providers were automatically registered for the client, too. This is not the case anymore in Wildfly 13/RESTEasy 3.5! You have to register them with the client either using the ResteasyClientBuilder or the ResteasyClient you are using like mentioned in the documentation:

Client client = new ResteasyClientBuilder() // Activate gzip compression on client:
                    .register(AcceptEncodingGZIPFilter.class)
                    .register(GZIPDecodingInterceptor.class)
                    .register(GZIPEncodingInterceptor.class)
                    .build();

This subtle change in (undocumented?) behaviour took several hours to debug. Nevertheless, we actually like the change because we prefer doing things explicitly instead of using some magic. So now it is clear what interceptors and providers our REST client is using.