The Game

The board game is a two-player game. Player 1 owns the upper left-hand corner and Player 2 owns the lower right-hand corner. They each take turns switching the colors like in the original game. Each player cannot take over another player's territory. Once the board is completely owned, the player who owns the majority of the board wins.

Model The Game

At a first glance, I'd guess that the following are necessary to model the game:

• The size of the board
• The color of each tile
• The owner of each tile

At a second glance, I'd guess that the following would be nice to know:

• Each player's last selected color
• Each player's score

I'm sure we'll find out that more is needed, but it's always good to design a start and then to iterate to a final design.

In fillGridModel.h, right below the "DECLARE_CONOBJECT(FillGridModel);" line, add these member data variables to the class:

protected:
  S32 mySizeX;
  S32 mySizeY;
  S32 **myColor;
  S32 **myOwner;
  S32 myScore[2];

Try to use Torque's definitions as much as possible. Personally, I think it's silly to use "S32" instead of "int", but it's more portable if you use "S32". (You can find all definitions in platform/types.h.)

Oh no! The dreaded double pointer! Why, oh why, would I put you through this? I promise that I'll make it very, very easy on you to make these arrays.

One convention that we'll use for this class is that we will use "0" for the first player and "1" for the second player. That way we can just use "myScore[0]" for the first player and "myScore[1]" for the second player. We'll use "-1" when we want to say that nobody owns a tile. Colors, likewise, will start at "0" and go to "5".

The "protected:" just means that you can't modify these values willy-nilly: you have to be a function inside this class or a function inside of a class that derives off of FillGridModel.

Now, we'll add functions to access/modify these values. Add this just below the "void onRemove();" line:

  void initialize( S32 x, S32 y );
  S32 sizeX();
  S32 sizeY();
  S32 color( S32 x, S32 y );
  S32 owner( S32 x, S32 y );
  S32 lastSelectedColor( S32 owner );
  S32 score( S32 owner );
  void floodFill( S32 owner, S32 color );
  S32 bestMove( S32 owner, S32 plies );

"initialize" will set the size, fill the grid with random colors, and set all tiles to unowned. "sizeX" and "sizeY" will return the size of the grid. "color" will return the color for a tile. "owner" will return the owner for a tile. "lastSelectedColor" will return the color selected by the given owner. "score" will return a player's score. "floodFill" will fill a player's area with the given color and expand his ownership to adjacent, matching colors. "bestMove" will return the best choice for color to maximize the player's score after a number of plies (a ply is a single player's turn, 2 plies would be a round). "bestMove" will be the focus of the next lesson.

Alright! Let's mosey on over to fillGridModel.cc. First, let's modify the constructor:

FillGridModel::FillGridModel() : ScriptObject(),
  mySizeX( 0 ),
  mySizeY( 0 ),
  myColor( NULL ),
  myOwner( NULL )
{
  myScore[0] = 0;
  myScore[1] = 0;
}

This just makes sure that everything has an initial value.

At the end of the file, after the "nRemove" function, add the following:

void FillGridModel::initialize( S32 x, S32 y )
{
  // In case we were already initialized, clean up the old stuff.
  cleanup();

  mySizeX = x;
  mySizeY = y;

  // Create an array for colors.
  myColor = new S32*[mySizeX];
  for( S32 col = 0; col < mySizeX; ++col )
    myColor[col] = new S32[mySizeY];

  // Assign random colors to the array.
  for( S32 col = 0; col < mySizeX; ++col )
    for( S32 row = 0; row < mySizeY; ++row )
      myColor[col][row] = gRandGen.randI( 0, 5 );

  // Create an array for owners.
  myOwner = new S32*[mySizeX];
  for( S32 col = 0; col < mySizeX; ++col )
    myOwner[col] = new S32[mySizeY];

  // Assign "-1" to all owners to show a lack of ownership.
  for( S32 col = 0; col < mySizeX; ++col )
    for( S32 row = 0; row < mySizeY; ++row )
      myOwner[col][row] = -1;

  // Reset the scores.
  myScore[0] = 0;
  myScore[1] = 0;

  // An easy way to assign the initial ownership and scores.
  floodFill( 0, myColor[0][0] );
  floodFill( 1, myColor[mySizeX-1][mySizeY-1] );
}

It's mostly self-explanatory. There are a couple of things that need to be fixed, though. First, you'll see we called a function called "cleanup"; we'll need to implement that. Second, we got a random number, but we haven't included that functionality in this class.

At the top of the file add "#include "math/mRandom.h"" with the other includes.

Back to fillGridModel.h, add this below "FillGridModel();"

~FillGridModel();
void cleanup();

This is the destructor. Back to the fillGridModel.cc, add this below the constructor and above "onAdd":

FillGridModel::~FillGridModel()
{
  cleanup();
}

void FillGridModel::cleanup()
{
  if( myColor != NULL )
  {
    for( S32 col = 0; col < mySizeX; ++col )
      delete[] myColor[col];
    delete[] myColor;
    myColor = NULL;
  }

  if( myOwner != NULL )
  {
    for( S32 col = 0; col < mySizeX; ++col )
      delete[] myOwner[col];
    delete[] myOwner;
    myOwner = NULL;
  }
}

Now we'll not leak memory when we finish using this class! Excellent!

The next several functions are very self-explanatory and you can just copy these in and take a quick glance and figure them out:

S32 FillGridModel::sizeX()
{
  return mySizeX;
}

S32 FillGridModel::sizeY()
{
  return mySizeY;
}

S32 FillGridModel::color( S32 x, S32 y )
{
  if( x < 0 || x >= mySizeX || y < 0 || y >= mySizeY )
    return -1;
  return myColor[x][y];
}

S32 FillGridModel::owner( S32 x, S32 y )
{
  if( x < 0 || x >= mySizeX || y < 0 || y >= mySizeY )
    return -1;
  return myOwner[x][y];
}

S32 FillGridModel::lastSelectedColor( S32 owner )
{
  if( owner == 0 ) return myColor[0][0];
  return myColor[mySizeX-1][mySizeY-1];
}

S32 FillGridModel::score( S32 owner )
{
  return myScore[owner];
}

Finally, let's put stubs of the final two functions in:

void FillGridModel::floodFill( S32 owner, S32 color )
{
}

S32 FillGridModel::bestMove( S32 owner, S32 plies )
{
  return -1;
}

We won't be implementing "bestMove" in this lesson, so we'll just have it return a dummy value to make sure that it compiles.

The function "floodFill" will be doing most of the work. Here's the code:

void FillGridModel::floodFill( S32 owner, S32 color )
{
  // Create a "visited" array to keep track of where we've been.
  bool **visited;
  visited = new bool*[mySizeX];
  for( S32 col = 0; col < mySizeX; ++col )
    visited[col] = new bool[mySizeY];

  // Initialize the "visited" array to false.
  for( S32 col = 0; col < mySizeX; ++col )
    for( S32 row = 0; row < mySizeY; ++row )
      visited[col][row] = false;

  // Reset the owner's score to 0.
  myScore[owner] = 0;

  // Get the last selected color for the owner.
  S32 lastColor = lastSelectedColor( owner );

  // Create the position stack
  Vector<Point2I> posStack;

  // Put the owner's starting location on the stack.
  if( owner == 0 )
    posStack.push_back( Point2I( 0, 0 ) );
  else
    posStack.push_back( Point2I( mySizeX - 1, mySizeY - 1 ) );

  // Switch colors
  // As long as there is something to process...
  while( posStack.size() > 0 )
  {
    // Pop off the last item.
    Point2I pos = posStack.last();
    posStack.pop_back();

    // Skip tiles we've already visited!
    if( visited[pos.x][pos.y] )
      continue;

    // Mark this tile as being visited.
    visited[pos.x][pos.y] = true;

    // Skip tiles owned by other people!
    if( myOwner[pos.x][pos.y] != owner && myOwner[pos.x][pos.y] != -1 )
      continue;

    // If we match the old color, set the color/owner.
    if( myColor[pos.x][pos.y] == lastColor )
    {
      myColor[pos.x][pos.y] = color;
      myOwner[pos.x][pos.y] = owner;
    
      // Push adjacent tiles onto the stack
      if( pos.x > 0 && !visited[pos.x - 1][pos.y] )
        posStack.push_back( Point2I( pos.x - 1, pos.y ) );
      if( pos.x < mySizeX - 1 && !visited[pos.x + 1][pos.y] )
        posStack.push_back( Point2I( pos.x + 1, pos.y ) );
      if( pos.y > 0 && !visited[pos.x][pos.y - 1] )
        posStack.push_back( Point2I( pos.x, pos.y - 1 ) );
      if( pos.y < mySizeY - 1 && !visited[pos.x][pos.y + 1] )
        posStack.push_back( Point2I( pos.x, pos.y + 1 ) );
    }
  }

  // Switch owners

  // Initialize the "visited" array to false.
  for( S32 col = 0; col < mySizeX; ++col )
    for( S32 row = 0; row < mySizeY; ++row )
      visited[col][row] = false;

  if( owner == 0 )
    posStack.push_back( Point2I( 0, 0 ) );
  else
    posStack.push_back( Point2I( mySizeX - 1, mySizeY - 1 ) );

  while( posStack.size() > 0 )
  {
    // Pop off the last item.
    Point2I pos = posStack.last();
    posStack.pop_back();

    // Skip tiles we've already visited!
    if( visited[pos.x][pos.y] )
      continue;

    // Skip tiles owned by opponent!
    if( myOwner[pos.x][pos.y] != owner && myOwner[pos.x][pos.y] != -1 )
      continue;

    // Mark this tile as being visited.
    visited[pos.x][pos.y] = true;

    // If we match the new color, set the owner.
    if( myColor[pos.x][pos.y] == color )
    {
      myOwner[pos.x][pos.y] = owner;
      ++myScore[owner];
    
      // Push adjacent tiles onto the stack
      if( pos.x > 0 && !visited[pos.x - 1][pos.y] )
        posStack.push_back( Point2I( pos.x - 1, pos.y ) );
      if( pos.x < mySizeX - 1 && !visited[pos.x + 1][pos.y] )
        posStack.push_back( Point2I( pos.x + 1, pos.y ) );
      if( pos.y > 0 && !visited[pos.x][pos.y - 1] )
        posStack.push_back( Point2I( pos.x, pos.y - 1 ) );
      if( pos.y < mySizeY - 1 && !visited[pos.x][pos.y + 1] )
        posStack.push_back( Point2I( pos.x, pos.y + 1 ) );
    }
  }

  // Delete the visited array.
  for( S32 col = 0; col < mySizeX; ++col )
    delete[] visited[col];
  delete[] visited;
}

You'll probably notice a few things different from the TorqueScript version of this code.

First, we use a "visited" array. This allows us to handle both the coloring and the ownership in the same function. These are very common in depth-first searches, and allow us to make further optimizations.

Second, we use a Vector of Point2I's as a stack. The Vector class is very handy and can easily stand in for a stack. The Point2I is a simple wrapper around two integers "x" and "y". To be able to use these, add the following lines at the top with the other includes:

#include "core/tVector.h"
#include "math/mPoint.h"

The code is a little ugly right now, with some copy-and-paste duplication. We'll fix these sections in the next lesson.

Finally, you'll see that the if-statements are different. We test that the new location we want to push onto the stack hasn't already been visited (!visited[x][y]). This will speed up the algorithm by over 2 times! It also makes the first check ("Skip tiles we've already visited") unnecessary. So why did I leave it in? Fear. Sad, but true.

Build -> Build Solution.

And there we have it, a class that implements all of the scripting functionality!

But wait! How do we tie this into the scripts? ConsoleMethods! Add the following to the bottom of your fillGridModel.cc file:

ConsoleMethod( FillGridModel, initialize, void, 3, 4, "( <x y> )" )
{
  S32 x, y;

  if( argc == 3 ) // Space separated vector
    dSscanf( argv[2], "%d %d", &x, &y );
  else if( argc == 4 ) // Two arguments passed in
  {
    x = dAtoi( argv[2] );
    y = dAtoi( argv[3] );
  }

  object->initialize( x, y );
}

ConsoleMethod( FillGridModel, color, S32, 3, 4, "( <x y> )" )
{
  S32 x, y;

  if( argc == 3 )
    dSscanf( argv[2], "%d %d", &x, &y );
  else if( argc == 4 )
  {
    x = dAtoi( argv[2] );
    y = dAtoi( argv[3] );
  }

  return object->color( x, y );
}

ConsoleMethod( FillGridModel, owner, S32, 3, 4, "( <x y> )" )
{
  S32 x, y;

  if( argc == 3 )
    dSscanf( argv[2], "%d %d", &x, &y );
  else if( argc == 4 )
  {
    x = dAtoi( argv[2] );
    y = dAtoi( argv[3] );
  }

  return object->owner( x, y );
}

ConsoleMethod( FillGridModel, lastSelectedColor, S32, 3, 3, "( <owner> )" )
{
  return object->lastSelectedColor( dAtoi( argv[2] ) );
}

ConsoleMethod( FillGridModel, score, S32, 3, 3, "( <owner> )" )
{
  return object->score( dAtoi( argv[2] ) );
}

ConsoleMethod( FillGridModel, floodFill, void, 4, 4, "( <owner>, <color> )" )
{
  object->floodFill( dAtoi( argv[2] ), dAtoi( argv[3] ) );
}

ConsoleMethod( FillGridModel, bestMove, S32, 4, 4, "( <owner>, <plies> )" )
{
  return object->bestMove( dAtoi( argv[2] ), dAtoi( argv[3] ) );
}

ConsoleMethods are macros that do a lot of ugly, ugly work for you. What you define are the class name, function name (anything you want, but I try to match 1-for-1), the return value (S32 or void in these examples), the minimum number of parameters, the maximum number of parameters, and then text description of the function (I usually just put the parameters).

The minimum/maximum number of parameters is always "plus 2". Argument 0 is the object, Argument 1 is the function name, Argument 2 is the first argument, Argument 3 is the second argument, and so on. That why in "bestMove", we are getting argv[2] and argv[3], because those are the owner/plies strings.

What a ConsoleMethod gives you in return is access to the object created in script through the "object" variable. We can then call public functions inside of FillGridModel using "object".

Everything comes into the ConsoleMethod as a string. That's why we are calling dAtoi a lot, it converts a string into an integer. You'll also see the use of dSscanf<tt>. That scans a string for the format specified (in the case of <tt>"%d %d", we tell it that it will be two integers), and puts the result into the passed in "x" and "y" variables. (If your C/C++ is rusty, the "&" before those mean that we passed the variables in as references so that the dSscanf function could modify the values.)

Let's Integrate!

Now we need to use this model to play the game. Here's the completely new game/gameScripts/game.cs file:

function startGame(%level)
{
   Canvas.setContent(mainScreenGui);
   Canvas.setCursor(DefaultCursor);
   
   new ActionMap(moveMap);   
   moveMap.push();
   
   $enableDirectInput = true;
   activateDirectInput();
   enableJoystick();
   
   sceneWindow2D.loadLevel(%level);
   
   $FillBattle::Logic = new FillGridModel();
   TileBoard.init();
}

function endGame()
{
   sceneWindow2D.endLevel();
   moveMap.pop();
   moveMap.delete();
}

function TileBoard::init( %this )
{
  // Get the size of the TileBoard.
  %width = TileBoard.getTileCountX();
  %height = TileBoard.getTileCountY();

  // Initialize the game  
  $FillBattle::Logic.initialize( %width, %height );

  TileBoard.redraw();
}

function TileBoard::redraw()
{
  // Get the size of the TileBoard.
  %width = TileBoard.getTileCountX();
  %height = TileBoard.getTileCountY();
  
  // Iterate over all of the tiles.
  for( %x = 0; %x < %width; %x++ )
  {
    for( %y = 0; %y < %height; %y++ )
    {
      %color = $FillBattle::Logic.color( %x, %y );
      
      // Assign the current tile to use the SixColors sprite sheet and
      // use the frame that in the FillGridModel.
      TileBoard.setStaticTile( %x, %y, SixColorsImageMap, %color );
    }
  }
}

function Button::onMouseUp( %this, %modifier, %worldPosition, %clicks )
{
  %color = %this.getFrame();
  $FillBattle::Logic.floodFill( 0, %color );
  TileBoard.redraw();
}

Any Brain'll Do

If you play, you'll notice 2 things:

• The computer doesn't play.
• You can't convert the lower-right square to yours.

Since we haven't taught the computer how to play, we don't have anything going yet. Also, the new model (FillGridModel) doesn't capture pieces that belong to the other player.

It would be nice to see the computer play, even if stupidly, and it would be nice to know the territories each player owned.

Back in fillGridModel.cc, let's change the "bestMove" function to just return a random color.

S32 FillGridModel::bestMove( S32 owner, S32 plies )
{
  return gRandGen.randI( 0, 5 );
}

Also, change the Button code to have the A.I. player move immediately after you select a color.

function Button::onMouseUp( %this, %modifier, %worldPosition, %clicks )
{
  %color = %this.getFrame();
  $FillBattle::Logic.floodFill( 0, %color );
  
  %opponentColor = $FillBattle::Logic.bestMove( 1, 0 );
  $FillBattle::Logic.floodFill( 1, %opponentColor );
  
  TileBoard.redraw();
}

After a quick rebuild, you'll see that the computer plays, but you'll be able to beat it.

Let's Keep It In a Cage

Those borders are a little trickier! The FillGridModel class is already keeping track of who owns each square, so let's take advantage of that.

First, let's create modify TileBoard::init.

function TileBoard::init( %this )
{
  // Get the size of the TileBoard.
  %width = TileBoard.getTileCountX();
  %height = TileBoard.getTileCountY();

  // Initialize the game  
  $FillBattle::Logic.initialize( %width, %height );
  
  %sceneGraph = TileBoard.getSceneGraph();
  TileBoard.borders = %sceneGraph.getGlobalTileMap().createTileLayer(
      TileBoard.getTileCount(), TileBoard.getTileSize() );
  TileBoard.borders.setArea( TileBoard.getArea() );
  TileBoard.borders.setBlendColor( 0.25, 0.25, 0.25 );

  TileBoard.redraw();
}

Starting with the %sceneGraph line, here's what's happening:

• We ask the TileBoard (the tile layer we created in the TGB Editor) what scene it's in.
• We then ask the scene for it's TileMap class and then ask that to create us a new Tile Layer with the same number of tiles and size of tiles as our original layer. We create a dynamic variable in TileBoard called "borders" that is this new layer.
• We then set the area of this new "border" layer to be the same as the TileBoard layer. This, coupled with the previous step, will make a duplicate of our TileBoard layer.
• We then set the "blend color" of this layer to a dark gray. Our border graphic (remember from *way* back when?) is all white. We can turn it into any color by using this "blend color" function.

Next, we need to put those borders on in the TileBoard::redraw function.

function TileBoard::redraw()
{
  // Get the size of the TileBoard.
  %width = TileBoard.getTileCountX();
  %height = TileBoard.getTileCountY();
  
  // Iterate over all of the tiles.
  for( %x = 0; %x < %width; %x++ )
  {
    for( %y = 0; %y < %height; %y++ )
    {
      %color = $FillBattle::Logic.color( %x, %y );
      
      // Assign the current tile to use the SixColors sprite sheet and
      // use the frame that in the FillGridModel.
      TileBoard.setStaticTile( %x, %y, SixColorsImageMap, %color );
    }
  }
  
  for( %x = 0; %x < %width; %x++ )
  {
    for( %y = 0; %y < %height; %y++ )
    {
      %owner = $FillBattle::Logic.owner( %x, %y );
      
      // If the tile isn't owned, we don't care about its borders.
      if( %owner == -1 )
      {
        TileBoard.borders.clearTile( %x, %y );
        continue;
      }
      
      %bits = 0;
      %bits |= (%owner != $FillBattle::Logic.owner( %x, %y - 1)) << 0;
      %bits |= (%owner != $FillBattle::Logic.owner( %x + 1, %y)) << 1;
      %bits |= (%owner != $FillBattle::Logic.owner( %x, %y + 1)) << 2;
      %bits |= (%owner != $FillBattle::Logic.owner( %x - 1, %y)) << 3;
      
      TileBoard.borders.setStaticTile( %x, %y, SquareBordersImageMap, %bits );
    }
  }
}

Oof! What's going on here? The first part is the same; we set the colors in the TileBoard layer. In the second part of this function, we look at the "owner" attribute of each square.

First, we get the owner of this square. If it's "-1", then nobody owns it and we can clear any graphic for that tile. We then skip the rest of this code and continue the inner for-loop (the one that goes over "%y").

If somebody does own it, we start some bit manipulation. If there's a different owner in any direction, we want to draw a line between us and them. Let's pretend the owner in the tile above us (at <%x,%y-1>) is different. Then the code changes to this:

%bits = 0;
%bits |= (1) << 0; => %bits |= 1; => %bits = 1;

So %bits now equals 1. We then use this as the frame number within SquareBorderImageMap. Look at frame 1 of the SquareBorderImageMap below. You'll see that it is a line across the top.

If you imagine the top as being "bit 0", the right as being "bit 1", the bottom as being "bit 2", and the left as being "bit 3", you'll see that we are really creating a number with 4 bits ("0000") and setting the appropriate bit.

If the square above us is a different owner (bit 0 or "0001") and the square to the left of us is a different owner (bit 3 or "1000"), and we "or" these together we get "1001" which is binary for 9. Frame 9? A line to the top and to the left.

Run the game and you've got borders!

Complete!

Return to the Fill Battle Home!