C++, Computer Vision, Retrogaming, Videogames

The Maximum Score in Super Don Quix-ote

000000_bats_01_right

During the golden era of arcade videogames, a remarkable game appeared in one of my beloved local video arcades: Super Don Quix-ote. A laserdisc game, the graphics and gameplay of Super Don Quix-ote basically offered an interactive cartoon; a stark contrast to 1984 raster-graphic contemporaries such as Kung-Fu Master, Pac-Land or Marble Madness.

Another laserdisc game, Dragon’s Lair, was released one year prior to Super Don Quix-ote; in 1983. Both used a similar gameplay mechanism, requiring the player to respond to numerous moments of fleeting danger, in a timely fashion. In contrast to Dragon’s Lair, Super Don Quix-ote was kind enough to display a visual cue at such moments; an icon, inviting either up, down, left, right or button input. Years later, Shenmue used a variation on this mechanism, then dubbed Quick Time Events (QTEs).

I must admit I was pretty handy at Super Don Quix-ote back then; once I was even paid to play it to completion. It seemed obtaining the very best score was conceptually a simple matter of completing the game without losing a life; and this I could do. One day however I was surprised to find a stranger in the arcade; a stranger with a higher score than expected; given his loss of life. The outsider was good enough to explain.

A selection of the QTEs of Super Don Quix-ote would accept an input contrary to the on-screen icon. Choosing such alternative moves would ultimately result in a better score. The visitor showed me all that he knew, and in the weeks that followed, I found a couple more. Soon I was able to complete the game using all the QTE alternatives; again without losing a life.

A few years ago I was delighted to learn of the Daphne emulator: the First Ever Multiple Arcade Laserdisc Emulator; led by Matt Ownby. It’s support for Super Don Quix-ote was the icing on the cake. I had always wondered if I did find all the alternative QTE moves, and noted there was no discussion of these online. Around this time I had the idea that computer vision software engineering methods could be used to automatically play Super Don Quix-ote, and then explore all possible QTE responses.

all_sdq_alternative_moves

Well, to keep a long story story short, I recently got round to it. Using a C++ program I developed (the source code is here), running external to the Daphne emulator, I exhaustively tried all possible QTE responses while also tracking the score; using hand-rolled computer vision routines. So, there are 14 alternative moves. Contrary to the icons shown above, a player can use Button; Left; Button; Left; Left; Button; Down; Left; Left; Right; Left; Button; Left & Button (lexicographical ordering) and will be rewarded with 10,000 bonus points each time.

Of course, suitably armed, I then wanted to attempt the maximum high score. Surprisingly, this was the hardest part of the project. I set a camera and tripod up in my living room, and set aside around an hour a night for what grew to a period of a couple of months. The maximum score in Super Don Quix-ote is 776500. The video of me getting the score is below (and here); a video of the sdq_explorer program doing the same is here. I’ll be presenting a paper on this in more detail at the xCoAx Conference at the CCA in Glasgow this coming Thursday 25th June (2014).

Advertisements
C++

Building, say, indices<6,4,2,0,-2,-4>

A simple indexing class of variadic std::size_t template parameters is often used to provide a structured method to select multiple elements from a C++11 tuple. In this post I present an alternative to this interface, commonly used when building an object of this type, wherein a finite series of indices is now generated according to a numeric range and signed stride; akin to Fortran array section syntax. Let’s look at the common solution first.

A tuple may be created either using the std::tuple constructor, or std::make_tuple function template. Both expect the same variadic series of arguments. In addition, the constructor requires the type of each argument explicitly. Hence, the more concise std::make_tuple, is used throughout the examples. In the example below, the last element of t1 will be an int.

auto t1 = std::make_tuple('z',false,42,"cat",7);
auto t2 = std::tuple<char,bool,int,const char *,long>('z',false,42,"ktn",7);

Selection of a single tuple element is achieved using the standard tuple function template: std::get. The sole template parameter of std::get, a std::size_t, represents an index; and must be a constant expression. Using the t1 tuple from the code above, std::get<4>(t1) evaluates to an int; with a value of 7.

As a variadic function template, std::make_tuple can of course be used to create a new tuple from the elements of another. In the code below, t3, having type tuple<char,int,int>, is formed from copies of the 1st, 3rd, and 5th elements from the earlier tuple, t1.

auto t3 = std::make_tuple(std::get<0>(t1),std::get<2>(t1),std::get<4>(t1));

In the code above, we hard coded the selection using three index values: 0, 2, and 4. How could we instead write a function template, select, that accepts, at least, a tuple argument, and returns another tuple formed from an arbitrary set of its elements? The conventional solution introduces the following simple variadic class template:

template <std::size_t ...Is>
struct indices {};

An object of type indices might then be created with, for example: indices<>; indices<0,2,4>; or indices<1,1,2,3,5,8>. Our select function may then be defined, as shown in the code below.

template <typename ...Ts, std::size_t ...Is>
auto
select(std::tuple<Ts...> t, indices<Is...>) ->
  decltype(std::make_tuple( std::get<Is>(t)... )) {
  return   std::make_tuple( std::get<Is>(t)... );
}

Calling select with the earlier tuple variable t1 and a indices<0,2,4> variable, again results in a tuple with type tuple<char,int,int>.

There are a few C++11 things to notice in this code. The Is template parameter pack is not expanded “directly” in the function body, due to the placement of the ellipsis. So, while indices<Is...>, say, would expand to indices<0,2,4>, in the select function above, the actual expansion becomes std::get<0>(t), std::get<2>(t), std::get<4>(t); three arguments for the variadic make_tuple function. Such ellipses will expand all parameter packs in the pattern to their left. Expanding multiple parameter packs of differing lengths, with a single ellipsis, will cause a compilation error.

Also worth noting: the use of C++11’s trailing return type, and decltype specifier is, here, optional; the select function can be typed just as effectively by the more ornate code below. Often, however, the former typing technique is preferable as it has a simple, mechanical, syntax-based application; and so is generally applicable. With short functions the concise form can also provide a readable symmetry. With luck, perhaps by C++17, or maybe even C++14, we can do away with it altogether; after all, the auto keyword can bind to untyped lambda expressions.

template <typename ...Ts, std::size_t ...Is>
std::tuple<
  typename std::decay<
    typename std::tuple_element<Is,std::tuple<Ts...>>::type
  >::type...
>
select(std::tuple<Ts...> t, indices<Is...>) {
  return std::make_tuple( std::get<Is>(t)... );
}

Finally, as only the template arguments of its type are used, the second function parameter is not bound to a name.

All well and good, but how would I modify every element of an arbitrary-length tuple? A common solution, seen here, here, and here, is to use make_indices, a variadic class template with a typedef member, type, which equates to an instantiation of the indices class template. The std::size_t template parameters of the indices type are instantiated as a zero-based finite arithmetic progression, with length equal to the number of template arguments given to make_indices. For example, make_indices<short,int>::type, would evaluate to indices<0,1>. The code below demonstrates a simple application of make_indices within a function template, id, which “does nothing”; well, it returns a tuple comprised of the same elements as the input. With additional parameters, make_indices can easily be used to create tuple versions of map and zipWith.

template <typename ...Ts>
std::tuple<Ts...> id(std::tuple<Ts...> t) {
  return select(t,typename make_indices<Ts...>::type());
}

Although useful, the make_indices class template has a number of weaknesses:

  • The template parameters of indices are fixed as std::size_t only;
  • The first index created is always 0;
  • The common difference between each index is fixed to 1;
  • The common difference is a positive value only;
  • make_indices can only be applied to type template parameter lists, and not non-type template parameters.

The first point can be addressed by a variadic, generic, index container:

template <typename T, T...>
struct indicesT {};

With tuples, the argument given to the relevant index function, std::get, will commonly have type std::size_t. The following type alias template allows the more straightforward std::size_t specialisation of indicesT to be used; e.g. indices<0,1,2> instead of indicesT<std::size_t,0,1,2>; also, the earlier definition of select can remain unchanged.

template <std::size_t ...Is>
using indices = indicesT<std::size_t, Is...>;

The traditional make_indices class template outlined earlier only allows us to specify the extent of the generated, zero-based, indices. Using the mk_index_range alias template, the same may be achieved using an integral range. For example, like make_indices<int,bool,char>::type, the type expression mk_index_range<0,2> will evaluate to indices<0,1,2>; or [0,2] in interval notation.

The mk_index_range alias template can also use a non-zero based start value; for example mk_index_range<8,10> will evaluate to indices<8,9,10>. A third, optional, template parameter of mk_index_range allows the specification of a stride. So, mk_index_range<1,9,2> will evaluate to indices<1,3,5,7,9>; and mk_index_range<9,1,-2>.

The indices produced by mk_index_range will always have type std::size_t; that is, the same type as the template parameter of the <tuple> function std::get. To produce signed indices, say of type int, a second alias template is provided: mk_index_rangei. Behind the scenes, something like mk_index_rangei<3,-3,-1>, which evaluates to indicesT<3,2,1,0,-1,-2,-3>, is defined as MkIndices<int,int,3,-3,-1>, using a more general alias template, MkIndices.

A fair question is, how many indices are produced by an arbitrary index range? For example, what is produced by mk_index_range<1,9,2> as opposed to mk_index_range<1,10,2>. How about mk_index_range<1,0,1>? The answer comes from the language of the new century: Fortran. With the loop-control of the DO construct defined by the grammar production below,

do-variable = expr1, expr2 [,expr3]

then the number of iterations is defined by the following equation:

niters = max((expr2 − expr1 + expr3)/expr3, 0)

The C++ code for this is a constexpr function which can be used within the template arguments of the mk_index_range implementation.

We’re now in a position to have some fun. The following basic function, tuple_tail is used within the definition of the tuple overload of the insertion operator <<. The tuple_tail function returns a tuple comprised of all elements of the input tuple argument, minus the first element:

template <typename T, typename ...Ts>
tuple<Ts...>
tuple_tail(tuple<T,Ts...> t) {
  return select(t, mk_index_range<1,sizeof...(Ts)>());
}

The following function, tuple_reverse, unsurprisingly returns a tuple constructed from all the elements of the input tuple argument, in reverse order:

template <typename ...Ts>
tuple<Ts...>
tuple_reverse(tuple<Ts...> t) {
  return select(t, mk_index_range<sizeof...(Ts)-1,0,-1>());
}

The mk_index_range function template is now used throughout an updated version of the compile-time FFT code described in the previous post. The map, zipWith and iota functions there now all use mk_index_range; they’re also similar to each other; and are interesting enough. The following function, condenseN, is though more compelling: returning a tuple comprised of every nth element of the input tuple. It is both integral to the FFT implementation; and uses a stride, or common difference, that isn’t 1. Incidentally, the actual instantiation is condenseN<2>, and alas this will crash the current version of Clang; Clang 3.2 snapshot.

template <size_t N, typename ...Ts>
auto
condenseN(tuple<Ts...> t) ->
  decltype(select(t,mk_index_range<0,sizeof...(Ts)-1,N>())) {
  return   select(t,mk_index_range<0,sizeof...(Ts)-1,N>());
}

My personal favourite is also used by the compile-time FFT. The std::tuple_cat is a variadic function template which should catenate all tuples provided as arguments. The implementation below uses a helper function, tuple_cat_helper, which expands two parameter packs, Is and Js, within a single statement:

template <typename ...Ts>
tuple<>
tuple_cat() { return tuple<>(); }

template <typename ...Ts>
tuple<Ts...>
tuple_cat(tuple<Ts...> t) { return t; }

template  <typename Tup1, typename Tup2, std::size_t ...Is, std::size_t ...Js>
auto tuple_cat_helper(Tup1 t1, Tup2 t2, indices<Is...>, indices<Js...>) ->
  decltype(make_tuple(get<Is>(t1)...,get<Js>(t2)...)) {
  return   make_tuple(get<Is>(t1)...,get<Js>(t2)...);
}

template <typename ...Ts, typename ...Us, typename ...Tups>
auto
tuple_cat(tuple<Ts...> t1, tuple<Us...> t2, Tups ...ts) ->
  decltype(tuple_cat(
             tuple_cat_helper(
               t1,t2,
               mk_index_range<0,sizeof...(Ts)-1>(),
               mk_index_range<0,sizeof...(Us)-1>()
             ),
             ts...
           )
          )
{
  return   tuple_cat(
             tuple_cat_helper(
               t1,t2,
               mk_index_range<0,sizeof...(Ts)-1>(),
               mk_index_range<0,sizeof...(Us)-1>()
             ),
             ts...
           );
}

Note that the C++11 standard definition of std::tuple is not defined as constexpr. The non-standard tuple implementation provided with the FFT code is contained within the ctup namespace.

The code for mk_index_range is here and the constexpr-friendly tuple implementation is here.

C++

A compile-time FFT in C++11

Generalised constant expressions are a core language feature introduced to C++ by the recent C++11 standard. A call to a function or method qualified with the new constexpr keyword can now be evaluated at compile-time. Of course there are restrictions: arguments to such a call must also be amenable to compile-time evaluation. The primary restriction is that the body of a constexpr function must comprise of a single return statement. While this initially sounds draconian, the use of recursion, and the ternary operator, can permit essentially any calculation. The language of C++11 generalised constant expressions is that of a functional language.

The code below presents a brief example. Note the call to sqr_int in the second template argument to the C++11 std::array object. Also of interest: the call to sqr_int will prosaically perform floating-point calculations at compile-time. Incidentally, among other restrictions, lambda expressions may not, alas, form part of a C++11 generalised constant expression.

#include <array>
constexpr unsigned sqr_int(double d) { return d*d; }
std::array<bool,sqr_int(4.5)> garr;

Having been impressed by the ctrace and metatrace compile-time ray-tracers, I thought I’d give the fast fourier transform (FFT) a whirl. Seeking an FFT implemented in a functional language, I came across the elegant Single Assignment C (SAC) version shown here. After failing to compile the assembled pieces with the SAC compiler, I converted it to Fortran 9x and verified the results against another Fortran implementation from here.

The next thing I needed was a container data type to stand in for the rank-one, first-class arrays employed by the Fortran. Thoughts of using std::array soon evaporated as I realised that no constexpr element access methods exist; neither operator[] nor std::array::front() comply. Similar issues exist with std::tuple. Furthermore, the FFT only requires a homogeneous container. An implementation using the heterogeneous std::tuple would be inclined to add additional type-checking code. In response, I created the following recursive array container type:

template <typename T, size_t N>
struct recarr {
  constexpr recarr(T x, recarr<T,N-1> a) : m_x(x), m_a(a) {}

  constexpr T             head()   { return m_x; }
  constexpr recarr<T,N-1> tail()   { return m_a; }

private:
  T m_x;
  recarr<T,N-1> m_a;
};

template <typename T>
struct recarr<T,0> {};

The common restriction on recursive data types: members having the same type as the enclosing class must be pointers, is not applicable here; the m_a member is always a different type; i.e. recarr is not the same type as recarr. The zero-length specialisation of recarr has no members.

The list type used routinely in functional languages such as Haskell is a clear inspiration in the design of std::recarr. A cons function for std::recarr, necessary for the construction of higher order functions such as map and zipWith, may be defined as shown below. Rather than the raw recarr constructor, the stand-alone recarr_cons function can infer its template arguments from the runtime arguments.

template <typename T, size_t N>
constexpr
recarr<T,N+1> recarr_cons(T x, recarr<T,N> xs) {
  return recarr<T,N+1>(x,xs);
}

An FFT is an operation on complex numbers. The standard std::complex type, however, delivers another spanner to the works; it too lacks the constexpr methods needed for a compile-time FFT; including the constructors, and arithmetic operators. So, a new complex number class was developed, along with the necessary C++11 generalised constant expression support. Complex number formulae and definitions were drawn from here and here.

GCC and Clang both have excellent support for C++11. Wouldn’t it be nice to find out which is the faster compiler for the evaluation of a constexpr FFT? Some more challenges materialise here: Clang rejects all of the cmath library functions, as being non-constexpr. Functions required by the FFT include sin, sinh, cos, cosh, sqrt, log, exp, atan, atan2 and pow. Initially I though that Clang was being a little cranky here, but this is in fact the correct behaviour; n.b. a constexpr function may not be overloaded with a non-constexpr function; and vice-versa. Standard library functions which are to be constexpr must consequently be specified as such by the relevant C++ standard; the functions in cmath are not. After all, functions comprised of a single return statement may not be the most performant! The N3228 and N3231 documents from the C++ Standards Committee’s November 2010 mailings elaborate on this theme.

So, constexpr versions of the mathematical functions from cmath necessary for the FFT were developed; with reference to the formulae and guidelines of the Algebra Help e-Book.

I am in fact a big fan of the std::tuple class. In the end I couldn’t resist a second, comparative implementation of a constexpr FFT using C++11 tuples; and so the magic of variadic templates. Need I mention that std::tuple is also missing many of the constexpr constructors and support functions necessary for the job? The github code linked below includes a simple recursive version of the std::tuple type, with constexpr constructors; a version of get; a version of make_tuple; and, as the FFT uses concat, a version of tuple_cat. For comparison with recarr_cons above, here is the simple, concise tuple_cons; in constrast to a more verbose definition for tuple_cat provided in the full project.

template <typename T, typename ...Ts>
constexpr
tuple<T,Ts...> tuple_cons(T x, tuple<Ts...> xs) {
  return tuple_cat(make_tuple(x),xs);
}

The code is stored in a github repository here.