CS488 Final Project: OpenGL Boat Game

July 24, 2016

Here’s something I’ve been working on for the past few weeks for one of my courses, CS488 – Intro to Computer Graphics. For the final project, you’re allowed to do any OpenGL or raytracing project, as long as it has 10 reasonable graphics related objectives. Here’s a video of mine:

A screenshot:

It’s a simple game where you control a boat and go around a lake collecting coins. When you collect a coin, there’s a bomb that spawns and follows you around. You die when you hit a bomb. Also if two bombs collide then they both explode (although you can’t see that in the video).

Everything is implemented in bare-metal OpenGL, so none of those modern game engines or physics engines. It’s around 1000-ish lines of C++ (difficult to count because there’s a lot of donated code).

Edit (8/10/2016) – I received an Honorable Mention for this project!

Some thoughts about CS488

For those that haven’t heard about CS488, it’s one of the “big three” — fourth year CS courses with the heaviest workload and with large projects (the other two being Real-time and Compilers). It’s one of the hardest courses at Waterloo, but also probably the most rewarding and satisfying course I’ve taken.

There are four assignments, each walking you step by step through graphics techniques, like drawing a cube with OpenGL, or building a puppet with hierarchical modelling, or writing a simple ray tracer. Then there’s the final project, where you can choose to make something with OpenGL or extend your ray tracer. The class is split 50/50, about half the class did OpenGL and the other half did a ray tracer. I personally feel that OpenGL gives you more room to be creative and create something unique whereas ray tracing projects end up implementing a mix of different algorithms.

The first two assignments weren’t too bad (I estimate it took me about 10 hours each), but some time during assignment 3 I realized I was spending a lot of time in the lab, so I got an hours tracking app on my phone to track exactly how much time I was spending working on this course. Assignments 3 and 4 each took me 15 hours. I spent 35 hours on my final project, over a period of 3 weeks. I chose relatively easy objectives that I was confident I could do well, which left time to polish the game and do a few extra objectives. I’m not sure what the average is for time spent on the final project, but it’s common to spend 50-100 hours. Bottom line: you can put in potentially unbounded amounts of time to try to get the gold medal, but the effort actually required to get a good grade is quite reasonable.

Now the bad part about this course (obviously not the instructor’s fault) is OpenGL is so incredibly difficult to work with. Even to draw a line on the screen, you have to deal with a lot of low level concepts like vertex array objects, vertex buffer objects, uniform attributes to pass to shaders, stuff like that. It doesn’t help that when something goes wrong in a shader (which runs on the GPU), there’s no way to pass an error message back to the CPU so you can print out variables and debug it. It also doesn’t help that there’s a lot of incompatible OpenGL versions, and code you find in an online tutorial could be subtly broken for the version you’re using. On the other hand, working with OpenGL really makes you appreciate modern game engines like Unity which takes care of all the low level stuff for you.


Solving the AB Game by Brute Force

November 7, 2011

The AB game, a variant of Mastermind, is played with pencil and paper and with two people. One person chooses a four digit number in which no digit is repeated, say X, and the other person tries to guess it in as few moves as possible. After the guesser guesses some number, say Y, the other person gives information on how closely Y matched with X:

  • If some digit in Y coincides with a digit in X (in the same position), then the guesser scores an A.
  • If some digit in Y exists in X but is in the wrong place, then the guesser scores a B.

For instance, if X is 1234 and we guess 2674, we get an A and a B, because the 4 is in the right place, and the 2 is one of the right numbers but isn’t in the right place.

This proceeds until the guesser gets the exact number.

When humans (or at least beginners) play the AB game, they usually do some form of uncoordinated trial and error, which gets the right answer after some large number of moves. This takes anywhere from about 8 to possibly 30 guesses. When I played this game with a friend, I didn’t have a very systematic strategy, but I wondered if a computer program could solve the game, always entering the optimal guess.

A Bruteforce Solver

My first approach happened to work fairly well. Simply, the computer keeps track of a list of all possible numbers that the answer can be. At random, the computer guesses one of the numbers, and upon receiving feedback, eliminates every number in its list that doesn’t match that feedback. Quickly it eliminates whole swaths of combinations and arrives at the answer.

A typical session might go like this:

Guess 1: 6297. Score: 5040
b
Guess 2: 8512. Score: 1440
abb
Guess 3: 2315. Score: 83
bb
Guess 4: 5842. Score: 29
bb
Guess 5: 9581. Score: 13
ab
Guess 6: 8021. Score: 1

It took only 5 guesses for the computer to narrow down the choices to the only possible answer (8021).

A variant that is usually much harder for humans to solve is to allow the number chosen to have repeats. Although significantly trickier for humans to guess by trial and error, brute force doesn’t seem to be affected too much by it:

Guess 1: 1796. Score: 10000
b
Guess 2: 5881. Score: 3048
a
Guess 3: 0131. Score: 531
abb
Guess 4: 3311. Score: 15
aa
Guess 5: 3201. Score: 9
abb
Guess 6: 2011. Score: 1

The computer’s average of five or six is much better than a human can normally do! (although I haven’t researched possible human algorithms).

Optimal or Not?

At this point you may begin to wonder if this strategy is the optimal one. Unfortunately, it is not — and I only need one counterexample to demonstrate that.

Suppose that instead of four numbers, you were allowed to choose 4 letters from A to Z. You choose the combination ABCW. Now suppose that the computer ‘knows’ that the first three letters are ABC — that is, it has eliminated all other combinations except for ABCD, ABCE, …, ABCZ.

By the random guessing algorithm, the computer is forced to guess ABCJ, ABCP, etc, until it eventually hits on ABCW at random. This may take a very high number of guesses.

A smarter strategy would be to guess combinations of four unknown letters, say DEFG, then HIJK, etc. Instead of eliminating one letter, you eliminate four letters at a time. Although some guesses have no chance of being correct, the number of guesses required is fewer in the long run.

Source Code

I’ll put my somewhat unwieldy java code here for all to see:



import java.util.*;

public class ABSolver{
  
  // Does cc1 and cc2 together match the pattern?
  // If repeats are allowed, cc2 is matched against cc1.
  static boolean fits(char[] cc1, char[] cc2, int A, int B){

    int a = 0;
    int b = 0;
    for(int i=0; i<4; i++){
      if(cc1[i] == cc2[i]) a++;
      else{
        for(int j=0; j<4; j++){
          if(i != j && cc1[j] == cc2[i] && cc1[j]!=cc2[j]){
            b++;
            break;
          }
        }
      }
    }

    return a==A && b==B;
  }

  public static void main(String[] args){
    
    Random rand = new Random();
    Scanner scan = new Scanner(System.in);

    // Combinations that haven't been eliminated yet
    List<char[]> ok = new ArrayList<char[]>(10000);

    // Generate all possible combinations
    for(int i = 0; i <= 9999; i++){
      
      String i_s = Integer.toString(i);
      while(i_s.length() != 4) i_s = "0" + i_s;

      // Check for sameness
      char a = i_s.charAt(0);
      char b = i_s.charAt(1);
      char c = i_s.charAt(2);
      char d = i_s.charAt(3);
      boolean same = a==b || a==c || a==d || b==c || b==d || c==d;

      // Comment this line out if we're allowing repeats
      if(same) continue;

      char[] i_ia = i_s.toCharArray();
      ok.add(i_ia);

    }

    // Pick the first guess randomly
    char[] firstg = ok.get(rand.nextInt(ok.size()));
    char[] guess = null;

    int nguesses = 1;

    // Question answer cycle until we get it right
    while(true){

      // Ask for user response
      if(nguesses > 1){
        String ans = scan.nextLine();
        int A = 0;
        int B = 0;
        for(char cc : ans.toCharArray()){
          if(cc == 'a') A++;
          if(cc == 'b') B++;
        }

        if(A==4) return;

        // For each one check to see if it still fits
        List<char[]> ok_ = new ArrayList<char[]>(ok.size());
        for(char[] zhe : ok){
          if(fits(zhe, guess, A, B))
            ok_.add(zhe);
        }
        ok = ok_;
      }

      char[] nextguess = null;
      if(nguesses == 1)
        nextguess = firstg;
      else nextguess = ok.get(rand.nextInt(ok.size()));

      System.out.println("Guess " + nguesses + ": " + new String(nextguess)
                       + ". Score: " + ok.size());
      
      // we win!
      if(ok.size() == 1)
        return;

      guess = nextguess;
      nguesses++;
    }
    
  }
}

Some mathematical and algorithmic results on a simple puzzle game

July 5, 2010

I once came across this simple puzzle, or game.

You have a board of 7 squares in a single row, three black, and three red pieces. At the initialization of the game, the three black pieces are placed on the first (leftmost) three squares, and the three red pieces on the last (rightmost) three squares. This leaves one square in the middle.

The aim is to get all the red pieces onto the left side, and the black pieces on the right side, or in other words to reverse the position of all the pieces. This is done by executing a sequence of two possible moves:

One, a piece may move onto an empty square adjacent to it.

Two, a piece may hop over a piece of the opposite color adjacent to it, provided that the square on the other side of the second piece is empty.

Furthermore a move may only bring a piece closer to its destination; that is, it is not allowed to backtrack.

This particular instance of the problem (of three pieces each and seven squares) can be completed in 15 moves:

While this sequence completes the puzzle in 15 moves, it is not so obvious that this is the shortest sequence, that there is no shorter sequence that completes the puzzle in fewer than 15 moves. It is possible to prove a generalized result mathematically.

A formula for the number of moves

Let us generalize the game. We define an n-game to be an instance of the puzzle, with n pieces of each color separated by an empty square. For an n-game, the board contains 2n+1 squares.

Proposition: to complete an n-game, exactly n(n+2) moves are required.

In order for the n black pieces to completely trade places with the n red pieces, each black piece must hop over, or be hopped over by n red pieces.

Consider the pieces to be paired up as follows:

In the sequence of the game, each piece trades places with its partner. (Note that this is correct because the order of pieces of the same color cannot change).

It can be seen that the relative displacement between two members of a pair is 2(n+1). This is because each piece travels n+1 squares to get to its destination. In other words a piece travels 2(n+1) squares relative to its partner.

A move by either member of a pair adds a relative displacement of 1, while a hop adds a relative displacement of 2.

We have already shown that each pair must have, between them, n hops. This is equivalent to a relative displacement of 2n. Two additional moves are required to bring the relative displacement up to 2(n+1). Therefore, n+2 moves are required for a pair to exchange places.

As there are n pairs in the game, the total number of moves required to complete the game is n(n+2), as desired.

Implementation of a solver

Using the technique of a recursive depth-first search, it is a fairly easy programming exercise to write a solver for this puzzle. The solver produces the actual sequence of moves to complete an n-game.

The source code, in C:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Number of tokens on each side
#define N 3

// Destination board
char endbd[2*N+1];

// Board representation
char bd[2*N+1];

// Moves found
char **mvs;

// Flag to indicate if recursion has finished
char cont = 1;

// Perform dfs given n byte array
void dfs(int nmvs){
    int i, l;
    char* tm = malloc(20);

    // Found, dump move list
    if(!memcmp(bd,endbd,N+1)){
        for(i=0;i<nmvs;i++) printf("%d. %s\n",i+1,mvs[i]);
        cont = 0;
    }

    if(!cont) return;

    // Check for 1-moves
    for(i=0;i<2*N;i++){
        if(bd[i]!=1) continue;

        // Try moving a square
        if(bd[i+1]==0){

            // Generate notation for piece move
            l=sprintf(tm,"%d -> %d",i+1,i+2);

            // Copy to move list
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);

            // Continue search
            bd[i]=0;
            bd[i+1]=1;
            dfs(nmvs+1);

            // Reset to previous state
            bd[i]=1;
            bd[i+1]=0;
        }

        // Try hopping
        if(i<2*N-1 && bd[i+1]==2 && bd[i+2]==0){
            l=sprintf(tm,"%d -> %d",i+1,i+3);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i+2]=1;
            dfs(nmvs+1);
            bd[i]=1;
            bd[i+2]=0;
        }
    }

    // Check for 2-moves
    for(i=1;i<2*N+1;i++){
        if(bd[i]!=2) continue;
        if(bd[i-1]==0){
            l=sprintf(tm,"%d -> %d",i+1,i);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i-1]=2;
            dfs(nmvs+1);
            bd[i]=2;
            bd[i-1]=0;
        }
        if(i>1 && bd[i-1]==1 && bd[i-2]==0){
            l=sprintf(tm,"%d -> %d",i+1,i-1);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i-2]=2;
            dfs(nmvs+1);
            bd[i]=2;
            bd[i-2]=0;
        }
    }
}

int main(){

    // Board representation. 1's move right, 2's move left.
    // Initialize board here.
    int i;
    for(i=0;i<N;i++){
        bd[i]=1;
        endbd[i]=2;
    }
    bd[++i]=0;
    endbd[i]=0;
    for(;i<2*N+1;i++){
        bd[i]=2;
        endbd[i]=1;
    }

    mvs = malloc(1000*sizeof(char*));
    dfs(0);
    return 0;
}

For instance, the sequence of moves for n=3:

1. 3 -> 4
2. 5 -> 3
3. 6 -> 5
4. 4 -> 6
5. 2 -> 4
6. 1 -> 2
7. 3 -> 1
8. 5 -> 3
9. 7 -> 5
10. 6 -> 7
11. 4 -> 6
12. 2 -> 4
13. 3 -> 2
14. 5 -> 3
15. 4 -> 5