gistfile1.hpp

// MyTronBot.cc
// Author: Nathan - http://experimentgarden.blogspot.com

#include "Map.h"
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>

#define NORTH 1
#define SOUTH 2
#define EAST 3
#define WEST 4

using namespace std;

string lastDirection;

//Basic debuging outputs.
inline void debugOutput(char *output)
{
//  fprintf(stdout,output);
//  fprintf(stdout,"\n");  
}

inline void debugOutput(char *string, int number)
{
//  fprintf(stdout,string);
//  fprintf(stdout,"%d",number);
//  fprintf(stdout,"\n");  
}

//A basic vector search.
bool contains(vector <int> *possibleMoves, int what)
{
  for(int index = 0; index < possibleMoves->size(); index++)
  {
    if(possibleMoves->at(index)==what)
    {
      return true;
    }
  }
  return false;
}

//A loop used by the flood fill procedure below.
void FloodLoop(int *board, int x, int y, int boardWidth, int boardHeight)
{
  int fillL = x;
  int fillR = x;
  bool in_line = true;
  
  while(in_line)
  {
    board[(y*boardWidth)+fillL] = 2;
    fillL--;
    if(fillL<0)
    {
      in_line = false;
    }
    else if (board[(y*boardWidth)+fillL] != 0)
    {
      in_line = false;
    }
  }
  fillL++;
  
  in_line = true;
  while(in_line)
  {
    board[y*boardWidth+fillR] = 2;
    fillR++;
    if(fillR>boardHeight-1)
    {
      in_line = false;
    }
    else if (board[y*boardWidth+fillR] != 0)
    {
      in_line = false;
    }
  }
  fillR--;
  
  for(int i = fillL; i <= fillR; i++)
  {
    if( y > 0 && board[(y-1)*boardWidth + i] == 0 )
      FloodLoop(board, i, y - 1, boardWidth, boardHeight);
    if( y < boardHeight-1 && board[(y+1)*boardWidth + i] == 0 )
      FloodLoop(board, i, y + 1, boardWidth, boardHeight);
  }
}

//This rountine counts the number of free spaces in a room.
int FloodFill(int *board, int x, int y, int boardWidth, int boardHeight)
{
  //Floodfill with 2's starting at the location specified
  FloodLoop(board,x,y,boardWidth,boardHeight);
  
  //Count the two's and return the count.
  int twoCount = 0;
  for(int counter = 0; counter < boardWidth*boardHeight; counter++)
  {
    if(board[counter] == 2)
    {
      board[counter] = 0;
      twoCount++;
    }
  }
  
  return twoCount;
}

inline int countWalls(int *board, int x, int y, int boardWidth)
{
  int count = 0;
  
  if(board[(y-1)*boardWidth+(x-1)]) {count++;}
  if(board[(y)*boardWidth+(x-1)]) {count++;}
  if(board[(y+1)*boardWidth+(x-1)]) {count++;}
  if(board[(y+1)*boardWidth+(x)]) {count++;}
  if(board[(y+1)*boardWidth+(x+1)]) {count++;}
  if(board[(y)*boardWidth+(x+1)]) {count++;}
  if(board[(y-1)*boardWidth+(x+1)]) {count++;}
  if(board[(y-1)*boardWidth+(x)]) {count++;}
  
  return count;
}

bool enemyInside(int *board, int x, int y, int enemyX, int enemyY, int boardWidth, int boardHeight)
{   
  //Floodfill with 2's starting at the location specified
  FloodLoop(board,x,y,boardWidth,boardHeight);
    
  //See if any of the tiles around the enemy position are a two
  if(board[enemyY*boardWidth+(enemyX+1)]==2 | board[enemyY*boardWidth+(enemyX-1)]==2 | board[(enemyY+1)*boardWidth+enemyX]==2 | board[(enemyY-1)*boardWidth+enemyX]==2)
  {
    //Restore the board to its former state.
    for(int counter = 0; counter < boardWidth*boardHeight; counter++)
    {
      if(board[counter] == 2)
      {
        board[counter] = 0;
      }
    }
    return true; //Enemy is inside.
  }
  //Restore the baord to its former state.
  for(int counter = 0; counter < boardWidth*boardHeight; counter++)
  {
    if(board[counter] == 2)
    {
      board[counter] = 0;
    }
  }
  return false;  //Enemy is in a different room.
}

vector <int> *possibleMoves(int *board, int x, int y, int boardWidth, int boardHeight)
{
  int northMoves = 0;
  int eastMoves = 0;
  int southMoves = 0;
  int westMoves = 0;
  
  vector <int> *validMoves = new vector <int>;
  
  if(!board[(y-1)*boardWidth+x])
  {
    northMoves = FloodFill(board, x, y-1, boardWidth, boardHeight);
  }
  
  if(!board[(y+1)*boardWidth+x])
  {
    southMoves = FloodFill(board, x, y+1, boardWidth, boardHeight);
  }
  
  if(!board[y*boardWidth+x+1])
  {
    eastMoves = FloodFill(board, x+1, y, boardWidth, boardHeight);
  }
  
  if(!board[y*boardWidth+x-1])
  {
    westMoves = FloodFill(board, x-1, y, boardWidth, boardHeight);
  }
  
  if(westMoves!=0)
  {
    if(westMoves>=eastMoves)
    {
      if(westMoves>=northMoves)
      {
        if(westMoves>=southMoves)
        {
          validMoves->push_back(WEST);
        }
      }
    }
  }
  
  if(eastMoves!=0)
  {
    if(eastMoves>=westMoves)
    {
      if(eastMoves>=northMoves)
      {
        if(eastMoves>=southMoves)
        {
          validMoves->push_back(EAST);
        }
      }
    }
  }
  
  if(northMoves!=0)
  {
    if(northMoves>=eastMoves)
    {
      if(northMoves>=westMoves)
      {
        if(northMoves>=southMoves)
        {
          validMoves->push_back(NORTH);
        }
      }
    }
  }
  
  if(southMoves!=0)
  {
    if(southMoves>=eastMoves)
    {
      if(southMoves>=northMoves)
      {
        if(southMoves>=westMoves)
        {
          validMoves->push_back(SOUTH);
        }
      }
    }
  }
  
  return validMoves;
}

int worth(int *board, int x, int y, int theirX, int theirY, int boardWidth, int boardHeight, int downCounter)
{
  //Is this a draw?
  if(x==theirX & y==theirY)
  {
    return -100;
  }
  
  //Mark this move on the board.
  board[y*boardWidth+x] = 1;
  
  //Have we reached the bottom branch?
  if(downCounter==0)
  {
    //The heart of the entire operation.   Here is where we evaluate the strength of this move.
    
    //Is the enemy in a different room?
    if(!enemyInside(board, x, y, theirX, theirY, boardWidth, boardHeight))
    {
      debugOutput("Enemy in different room.");
      //Calculate the score based on the relative sizes of the two rooms.
      //A base score of 40 + additional scoring up to 100 for being in a larger room.
      
      int ourRoom = FloodFill(board, x, y, boardWidth, boardHeight);
      int theirRoom = FloodFill(board, theirX, theirY, boardWidth, boardHeight);
      
      if(theirRoom > ourRoom)
      {
        //Not a good suituation.  There is no way to win unless the enemy makes a mistake.
        
        board[y*boardWidth+x] = 0;
        return 0;
      }
      else
      {
        //Find the difference between the two.
        float dif = ourRoom - theirRoom;
        
        //Find the percentage of the entire board that this is and scale it between 1 and 50.
        float percent = dif / (boardWidth*boardHeight) * 50;
        
        board[y*boardWidth+x] = 0;
        return 50 + percent;  
      }
    }
    else
    {
      debugOutput("Enemy in same room.");
      //Calculate the score based on how close we are to the opponent.
      //A base score of 0 + additional scoring for being close.
      //A max of 50 for being close.  This is so that the drive to be close doesn't override a
      //winning scenario.
      
      float difX = theirX - x;
      float difY = theirY - y;
      
      if(difX<0) {difX = -difX;}
      if(difY<0) {difY = -difY;}
      
      //How far away are we in percent of the game board?
      float percentX = difX / boardWidth * 100;  
      float percentY = difY / boardHeight * 100;
      
      //Scale both percentages down to a scale of 1-25 rather than 1-100
      percentX /= 4;
      percentY /= 4;
      
      debugOutput("Worth: ", 50 - percentX - percentY);
      
      board[y*boardWidth+x] = 0;
      return 50 - percentX - percentY;
    }
  }
  
  downCounter--;
  
  //Look at our opponent's possible best moves based on this move.
  //Note that we make the worth negative, because what is a great move for our opponent is a bad move
  //for us, and vice versa.
  
  int westWorth = -101;
  int eastWorth = -101;
  int northWorth = -101;
  int southWorth = -101;
  vector <int> *enemyMoves = possibleMoves(board, theirX, theirY, boardWidth, boardHeight);

  int max = -102; 
  
  //Check to see if this move trapped our opponent
  if(enemyMoves->size() == 0)
  {
    return 100;  //This is a winning move.
  }
  else
  {
    //The opponent still has possible moves.
    if(contains(enemyMoves,WEST))
    {
      westWorth = -worth(board, theirX-1, theirY, x, y, boardWidth, boardHeight, downCounter);
      
      if(westWorth >= max)
      {
        max = westWorth;
      }
    }
    if(contains(enemyMoves,EAST))
    {
      eastWorth = -worth(board, theirX+1, theirY, x, y, boardWidth, boardHeight, downCounter);
      
      if(eastWorth >= max)
      {
        max = eastWorth;
      }
      
    }
    if(contains(enemyMoves,NORTH))
    {
      northWorth = -worth(board, theirX, theirY-1, x, y, boardWidth, boardHeight, downCounter);
      
      if(northWorth >= max)
      {
        max = northWorth;
      }
      
    }
    if(contains(enemyMoves,SOUTH))
    {
      southWorth = -worth(board, theirX, theirY+1, x, y, boardWidth, boardHeight, downCounter);
      
      if(southWorth >= max)
      {
        max = southWorth;
      }
    }
  }
  
  delete enemyMoves;  //We are done with it.
  
  debugOutput("Local results:");
  debugOutput("North: ", northWorth);
  debugOutput("South: ", southWorth);
  debugOutput("East: ", eastWorth);
  debugOutput("West: ", westWorth);
  
  //Unmark this move to return the board to its original state.
  board[y*boardWidth+x] = 0;
  
  return max;
}

std::string MakeMove(const Map& map) {
  int x = map.MyX();
  int y = map.MyY();
  
  int theirX = map.OpponentX();
  int theirY = map.OpponentY();
  
  int boardWidth = map.Width();
  int boardHeight = map.Height();
  
  //Build the board.
  int *board = new int[boardWidth*boardHeight];
  
  for(int yc = 0; yc < boardHeight; yc++)
  {
    for(int xc = 0; xc < boardWidth; xc++)
    {
      board[yc*boardWidth+xc] = map.IsWall(xc,yc);
    }
  }
  
  //Make sure that the bot's positions are marked as walls.
  board[(y*boardWidth+x)]=1;
  board[(theirY*boardWidth+theirX)]=1;
  
  //How many branches down to search.
  int branches = 12;
  
  int westWorth = -100;
  int eastWorth = -100;
  int northWorth = -100;
  int southWorth = -100;
  vector <int> *ourMoves = possibleMoves(board, x, y, boardWidth, boardHeight);
  
  //Check to see if we are trapped.
  if(ourMoves->size() == 0)
  {
    //So sad, we lost.
    return "North";
  }
  else
  {
    //We have possible moves.
    
    if(contains(ourMoves,WEST))
    {
      westWorth = worth(board, x-1, y, theirX, theirY, boardWidth, boardHeight, branches);
    }
    if(contains(ourMoves,EAST))
    {
      eastWorth = worth(board, x+1, y, theirX, theirY, boardWidth, boardHeight, branches);
    }
    if(contains(ourMoves,NORTH))
    {
      northWorth = worth(board, x, y-1, theirX, theirY, boardWidth, boardHeight, branches);
    }
    if(contains(ourMoves,SOUTH))
    {
      southWorth = worth(board, x, y+1, theirX, theirY, boardWidth, boardHeight, branches);
    }
  }
  
  delete ourMoves;  //We are done with it.
  
  debugOutput("Final results:");
  debugOutput("North: ",northWorth);
  debugOutput("South: ",southWorth);
  debugOutput("East: ",eastWorth);
  debugOutput("West: ",westWorth);

  int returnValue = NORTH;
  
  if(southWorth>=eastWorth)
  {
    if(southWorth>=northWorth)
    {
      if(southWorth>=westWorth)
      {
        returnValue = SOUTH;
      }
    }
  }
  
  if(westWorth>=eastWorth)
  {
    if(westWorth>=northWorth)
    {
      if(westWorth>=southWorth)
      {
        returnValue = WEST;
      }
    }
  }
  else if(northWorth>=eastWorth)
  {
    if(northWorth>=westWorth)
    {
      if(northWorth>=southWorth)
      {
        returnValue = NORTH;
      }
    }
  }
  else
  {
    returnValue = EAST;
  }
  
  //Clean up our memory footprint.
  delete board;
  
  //Return our choice.
  if(returnValue == NORTH)
  {
    debugOutput("Going North.");
    return "North";
  }
  else if(returnValue == SOUTH)
  {
    debugOutput("Going South.");
    return "South";
  }
  else if(returnValue==EAST)
  {
    debugOutput("Going East.");
    return "East";
  }
  else
  {
    debugOutput("Going West.");
    return "West";
  }
}

// Ignore this function. It is just handling boring stuff for you, like
// communicating with the Tron tournament engine.
int main() {
  while (true) {
    Map map;
    Map::MakeMove(MakeMove(map));
  }
  return 0;
}