Quo Vadis, Games?

This is how Khaled Helioui, the new Managing Director of Bigpoint, changed the title of this talk from “Quo Vadis, Browsergames?”. According to Helioui, browser games are no genre, the browser is just a new platform for many kinds of games.

And there were others at Quo Vadis 2013, one of the biggest game development conferences in Germany: Richard Garriot was talking about how he tripled his father’s yearly salary in a few weeks with his first successful game, and how players ripped apart his carefully designed economy system of Ultima Online in minutes after release. Garriot stressed the importance of social gaming (which he was calling tribal gaming), stating that we seem to care so much more about playing with our friends than with strangers. Our friends, and the friends of our friends are so important to us, that the people on the streets of Berlin seem pretty much like NPCs roaming our real life.

Quo Vadis 2013 - Teut Weidemann. Ubisoft Blue Byte. Why touch will win.

Ed Fries was wondering where free-to-play would be going from now: To him, free-to-play shouldn’t mean “play the game and then buy some stuff” – that’s what he calls “play the game and then buy some stuff”.

Additionally, both Hendrik Klindworth and Steve Collins talked about the importance of server-side A/B Testing, especially in the case of mobile apps who can take weeks before they’ve passed the approval process of the respective app store again.

Jens Begemann doesn’t understand why we keep trying to put our existing games on mobile platforms. He reminded us that each new input pattern allowed us to create unique new game experiences, such as the mouse more or less introducing real-time strategy games, for example. In his opinion, we should focus on creating games that are made for mobile devices – and then, these games will be awesome.

Finally, Andre Weissflog explained how to cross-compile C++ games into JavaScript-based web games. The code is translated into byte code and optimized first, before JavaScript is generated that is very similar to Assembler code: No classes, no high-level concepts – just functions and local variables. The memory heap is realized just with a big array, pointers are nothing else than indices into that array.

It’s been a long and exciting week for Christian and me – for those of you who might have missed one or another of those talks, take a look at the slides. They’re worth it!

  • Khaled Helioui. Bigpoint. Quo Vadis Browsergames.
  • Hendrik Klindworth. InnoGames. Entering cross platform gaming – A developer’s journey
  • Steve Collins. SWRVE. Data Driven Optimization for Mobile Games.
  • Teut Weidemann. Ubisoft Blue Byte. Why touch will win.
  • Klaas Kersting. flaregames. Mobile Games Marketing – like a Samurai.
  • Jens Begemann. Wooga. From Keyboards to Fingertips – Rethink Game Design!
  • Andre Weissflog. Bigpoint. C++ on the Web: Run your big 3D game in the browser!

Grab Bag Release: Priority Queues

After having finished the Hamburg Relay Marathon with Christian, Nils and Florian yesterday, I’ve got a new part of my Grab Bag of Useful Stuff for you: Priority Queues.

This week we’ll be attending the Quo Vadis developer conference in Berlin. If you feel like chatting a little, just send me an e-mail and I’m sure we’ll find some time!

Priority Queues

Priority Queues (or heaps) consist of a set of items, each with a real-valued key, and provide the following operations:

  • Clear() clears the priority queue, removing all items.
  • Insert(item, key) inserts the passed item with the specified key into the priority queue.
  • FindMin() returns the item with the minimum key in the priority queue.
  • DeleteMin() deletes and returns the item with the minimum key in the priority queue.
  • DecreaseKey(item, delta) decreases the key of the specified item in the priority queue by subtracting the passed non-negative real number delta.
  • DecreaseKeyTo(item, newKey) decreases the key of the specified item in the priority queue to the passed non-negative real number.
  • Delete(item) deletes the specified item from the priority queue.

My implementation is based on Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms by Michael L. Fredman and Robert Endre Tarjan. Given a heap with n items, deleting an arbitrary item is done in O(log n) amortized time. All other heap operations are performed in O(1) amortized time.

Fast heaps are incredibly helpful for speeding up pathfinding algorithms such as Dijkstra and A*.

Grab Bag Release: Union-Find

It’s been quite a while since my last post, and that is mostly because of the lot of hard work Christian and me have put into our very first project at slash games, which I’m going to tell you more about soon.

In the meantime, I’ve started to entirely rework my Grab Bag of Useful Stuff: While the old version was a loose compilation of unrelated Java and C# classes, the new one is organized as a collection of .NET libraries, all of which have been developed according to the best practices presented in Framework Design Guidelines by Cwalina and Abrams. They fully adhere to the C# Code Conventions, are all CLS-compliant and come with a load of unit tests to ensure code quality.

I’m going to release a new part of the Grab Bag every week now – head over to the Grab Bag page and check out the development roadmap now. For the first release, I’m gonna start with union-find structures.

Union-Find Structures

Union-find structures provide two operations for manipulating disjoint sets:

  • Find(x) finds the unique set containing the element x.
  • Union(A, B) combines the sets A and B into a new set.

My implementation is based on Efficiency of a Good But Not Linear Set Union Algorithm by Robert Endre Tarjan. Given a union-find universe with n elements, each in a singleton set, a sequence of m > n finds and n-1 intermixed unions has a worst-case running time of O(ma(m, n)), where a(m, n) is related to a functional inverse of Ackermann’s function and is very slow-growing.

Union-find structures are useful in many contexts, including the computation of minimum spanning trees.