Modules/PlayersLocator/PointsWithValidityAndAge.cpp

Go to the documentation of this file.

/**
 *  @file PointsWithValidityAndAge.cpp
 *
 *  Represents a set of points on the field. 
 *  It is used to determine the location of other players on the field.
 *  If a new point is added and there are as many points in the set as it can held,
 *  the oldest point is overwritten.
 *
 *  @author <A href=mailto:juengel@informatik.hu-berlin.de>Matthias Juengel</A>
 *  @author <A href=mailto:kspiess@informatik.uni-bremen.de>Kai Spiess</A>
 */

#include "PointsWithValidityAndAge.h"

#include <string.h>


/*
PointsWithValidityAndAge::PointsWithValidityAndAge()
{
  this->numberOfPoints = 0;
  this->indexOfNextPoint = 0;
  this->sizeOfSet = 0;

  for(int k = 0; k < this->MAX_NUMBER_OF_POINTS_WITH_AGE; k++)
  {
    x[k] = 9999;
    y[k] = 9999;
    xDistribution[k] = 0;
    yDistribution[k] = 0;
  }
}
*/

/*
PointsWithValidityAndAge::PointsWithValidityAndAge(short int sizeOfSet)
{
  this->numberOfPoints = 0;
  this->indexOfNextPoint = 0;
  this->sizeOfSet = sizeOfSet;
//  this->x = new short int[sizeOfSet];

  for(int k = 0; k < this->sizeOfSet; k++)
  {
    x[k] = 9999;
    y[k] = 9999;
    xDistribution[k] = 0;
    yDistribution[k] = 0;
  }
}
*/

PointsWithValidityAndAge::PointsWithValidityAndAge(short int sizeOfSet)
{
  this->numberOfPoints = 0;
  this->indexOfNextPoint = 0;
  this->sizeOfSet = sizeOfSet;
//  this->x = new short int[sizeOfSet];

  int k;
  for(k = 0; k < this->sizeOfSet; k++)
  {
    x[k] = 9999;
    y[k] = 9999;
  }
  for(k = 0; k < this->NUMBER_OF_GRID_POINTS_X; k++)
  {
    xDistribution[k] = 0;
  }
  for(k = 0; k < this->NUMBER_OF_GRID_POINTS_Y; k++)
  {
    yDistribution[k] = 0;
  }
}

PointsWithValidityAndAge::~PointsWithValidityAndAge()
{
}

void PointsWithValidityAndAge::setSizeOfSet(int size)
{
  this->sizeOfSet = size;
}

void PointsWithValidityAndAge::add(int x, int y)
{
  short int index = getIndexOfNextPoint();
  short int x_position, y_position;

  // remove the old value from the distribution
  if(index < numberOfPoints && this->x[index] != 9999)
  {
    x_position = (int)((this->x[index] - xPosBackFlags) / GRID_SPACING);
    
    if(x_position < 1) x_position = 1;
    if(x_position >= NUMBER_OF_GRID_POINTS_X - 1) x_position = NUMBER_OF_GRID_POINTS_X - 1;
    
    xDistribution[x_position - 1] -= 1;
    xDistribution[x_position]     -= 2;
    xDistribution[x_position + 1] -= 1;
    
    y_position = (int)((this->y[index] - yPosRightFlags) / GRID_SPACING);
    
    if(y_position < 1) y_position = 1;
    if(y_position >= NUMBER_OF_GRID_POINTS_Y - 1) y_position = NUMBER_OF_GRID_POINTS_Y - 1;
    
    yDistribution[y_position - 1] -= 1;
    yDistribution[y_position]     -= 2;
    yDistribution[y_position + 1] -= 1;
  }

  //write the new value to the list
  this->x[index] = x;
  this->y[index] = y;

  // add the new value to the distribution
  if(this->x[index] != 9999)
  {
    x_position = (int)((this->x[index] - xPosBackFlags) / GRID_SPACING);
    
    if(x_position < 1) x_position = 1;
    if(x_position >= NUMBER_OF_GRID_POINTS_X - 1) x_position = NUMBER_OF_GRID_POINTS_X - 1;
    
    xDistribution[x_position - 1] += 1;
    xDistribution[x_position]     += 2;
    xDistribution[x_position + 1] += 1;
    
    y_position = (int)((this->y[index] - yPosRightFlags) / GRID_SPACING);
    
    if(y_position < 1) y_position = 1;
    if(y_position >= NUMBER_OF_GRID_POINTS_Y - 1) y_position = NUMBER_OF_GRID_POINTS_Y - 1;
    
    yDistribution[y_position - 1] += 1;
    yDistribution[y_position]     += 2;
    yDistribution[y_position + 1] += 1;
  }

  //calculate new number of points
  if(numberOfPoints < this->sizeOfSet)
    this->numberOfPoints++;
}


short int PointsWithValidityAndAge::getIndexOfNextPoint()
{
  short int toReturn = this->indexOfNextPoint;
  indexOfNextPoint++;
  if (indexOfNextPoint >= this->sizeOfSet)
  {
    indexOfNextPoint = 0;
  }
  return toReturn;
}


void PointsWithValidityAndAge::calculateXYDistribution()
{
  //reset distributions
  memset(xDistribution, 0, sizeof(xDistribution));
  memset(yDistribution, 0, sizeof(yDistribution));
  
  for(int i = 0; i < this->sizeOfSet; i++)
  {
    if(x[i] != 9999)
    {
      //calculate x position in grid an correct it
      short int x_position = (int)((x[i] - xPosBackFlags) / GRID_SPACING);
      if(x_position < 1) x_position = 1;
      if(x_position >= NUMBER_OF_GRID_POINTS_X - 1) x_position = NUMBER_OF_GRID_POINTS_X - 1;

      //add distribution for the point in x direction
      xDistribution[x_position - 1] += 1;
      xDistribution[x_position]     += 2;
      xDistribution[x_position + 1] += 1;

      //calculate y position in grid an correct it
      short int y_position = (int)((y[i] - yPosRightFlags) / GRID_SPACING);
      if(y_position < 1) y_position = 1;
      if(y_position >= NUMBER_OF_GRID_POINTS_Y - 1) y_position = NUMBER_OF_GRID_POINTS_Y - 1;

      //add distribution for the point in y direction
      yDistribution[y_position - 1] += 1;
      yDistribution[y_position]     += 2;
      yDistribution[y_position + 1] += 1;
    }
  }
}


void PointsWithValidityAndAge::findMaximaInXYDistribution()
{
  int currentMaximum = 0;
  int indexOfCurrentMaximum = 0;
  int indexOfNextHill = 0;
  bool hereIsAHill = false;
  int i;

  for(i = 0; i < NUMBER_OF_GRID_POINTS_X; i++)
  {
    //update index of the maximum in the x distribution
    if(xDistribution[i] > currentMaximum)
    {
      currentMaximum = xDistribution[i];
      indexOfCurrentMaximum = i;
    }
    // detect hilll, if the value of the x distribution is higher than 4 
    // and higher thanmaximum * 0.5
    if(xDistribution[i] > 4 && xDistribution[i] > currentMaximum * 0.5)
    {
      if(!hereIsAHill)
      {
        hereIsAHill = true;
      }
    }
    else
    {
      if(hereIsAHill)
      {
        //store index of located maximum in x distribution in xHills
        xHills[indexOfNextHill] = indexOfCurrentMaximum;
        if(indexOfNextHill < 8)
          indexOfNextHill++;
        currentMaximum = 0;
        hereIsAHill = false;
      }
    }
  }
  // set number of hills in x distribution
  this->numberOf_xHills = indexOfNextHill;

  // find maxima for y distribution
  currentMaximum = 0;
  indexOfCurrentMaximum = 0;
  indexOfNextHill = 0;
  hereIsAHill = false;
  for(i = 0; i < NUMBER_OF_GRID_POINTS_Y; i++)
  {
    //update index of the maximum in the y distribution
    if(yDistribution[i] > currentMaximum)
    {
      currentMaximum = yDistribution[i];
      indexOfCurrentMaximum = i;
    }
    // detect hilll, if the value of the x distribution is higher than 4 
    // and higher thanmaximum * 0.5
    if(yDistribution[i] > 4 && yDistribution[i] > currentMaximum * 0.5)
    {
      if(!hereIsAHill)
      {
        hereIsAHill = true;
      }
    }
    else
    {
      if(hereIsAHill)
      {
        //store index of located maximum in x distribution in xHills
        yHills[indexOfNextHill] = indexOfCurrentMaximum;
        if(indexOfNextHill < 8)
          indexOfNextHill++;
        currentMaximum = 0;
        hereIsAHill = false;
      }
    }
  }
  // set number of hills in y distribution
  this->numberOf_yHills = indexOfNextHill;
}


void PointsWithValidityAndAge::voteForHills()
{
  int xHill, yHill;
  // reset the votes for hills
  memset(voteHills, 0, sizeof(voteHills));
  // calculate for every point in the set the distance to all possible hills
  // the hill with the shortest distance gets a vote
  for(int i = 0; i < this->sizeOfSet; i++)
  {
    int smallestDistance = 999999;
    int currentDistance;
    int x_votum = 0;
    int y_votum = 0;
    if(x[i] != 9999)
    {
      for(int xHill = 0; xHill < numberOf_xHills; xHill++)
      {
        for(int yHill = 0; yHill < numberOf_yHills; yHill++)
        {
          currentDistance = 
            calculateDistance(
            x[i],
            y[i],
            xHills[xHill] * GRID_SPACING + xPosBackFlags,
            yHills[yHill] * GRID_SPACING + yPosRightFlags);
          if(currentDistance < smallestDistance)
          {
            x_votum = xHill; y_votum = yHill;
            smallestDistance = currentDistance;
          }
        }
      }
      voteHills[x_votum][y_votum] += 1;
    }
  }


  int topVote1 = 0;
  int topVote2 = 0;
  int topVote3 = 0;
  int topVote4 = 0;
  numberOfObstacles = 0;
  // make a ranking over all voted hills, best first;
  // the votes must lie over the vote threshold;
  // hills with better votings as the best four are sorted in the topvotes;
  // increase number of detected objects for each vote entered in the ranking;
  for(xHill = 0; xHill < numberOf_xHills; xHill++)
  {
    for(yHill = 0; yHill < numberOf_yHills; yHill++)
    {
      //insert vote at first position
      if(voteHills[xHill][yHill] > topVote1 
        && voteHills[xHill][yHill] > VOTE_THRESHOLD)
      {
        topVote4 = topVote3;
        topVote3 = topVote2;
        topVote2 = topVote1;
        topVote1 = voteHills[xHill][yHill];
        x_vote[3] = x_vote[2];
        y_vote[3] = y_vote[2];
        x_vote[2] = x_vote[1];
        y_vote[2] = y_vote[1];
        x_vote[1] = x_vote[0];
        y_vote[1] = y_vote[0];
        x_vote[0] = xHills[xHill] * GRID_SPACING + xPosBackFlags;
        y_vote[0] = yHills[yHill] * GRID_SPACING + yPosRightFlags;
        numberOfObstacles++;
      }
      //insert vote at second position
      else if(voteHills[xHill][yHill] > topVote2 
        && voteHills[xHill][yHill] > VOTE_THRESHOLD)
      {
        topVote4 = topVote3;
        topVote3 = topVote2;
        topVote2 = voteHills[xHill][yHill];
        x_vote[3] = x_vote[2];
        y_vote[3] = y_vote[2];
        x_vote[2] = x_vote[1];
        y_vote[2] = y_vote[1];
        x_vote[1] = xHills[xHill] * GRID_SPACING + xPosBackFlags;
        y_vote[1] = yHills[yHill] * GRID_SPACING + yPosRightFlags;
        numberOfObstacles++;
      }
      //insert vote at third position
      else if(voteHills[xHill][yHill] > topVote3
        && voteHills[xHill][yHill] > VOTE_THRESHOLD)
      {
        topVote4 = topVote3;
        topVote3 = voteHills[xHill][yHill];
        x_vote[3] = x_vote[2];
        y_vote[3] = y_vote[2];
        x_vote[2] = xHills[xHill] * GRID_SPACING + xPosBackFlags;
        y_vote[2] = yHills[yHill] * GRID_SPACING + yPosRightFlags;
        numberOfObstacles++;
      }
      //insert vote at fourth position
      else if(voteHills[xHill][yHill] > topVote4
        && voteHills[xHill][yHill] > VOTE_THRESHOLD)
      {
        topVote4 = voteHills[xHill][yHill];
        x_vote[3] = xHills[xHill] * GRID_SPACING + xPosBackFlags;
        y_vote[3] = yHills[yHill] * GRID_SPACING + yPosRightFlags;
        numberOfObstacles++;
      }
    }
  }
}


bool PointsWithValidityAndAge::getPositionOfObstacle
(
 int index, int* x_position, int* y_position)
{
  if(index < 0 || index > 3 || index > numberOfObstacles - 1) return false;
  *x_position = this->x_vote[index];
  *y_position = this->y_vote[index];
  return true;
}


int PointsWithValidityAndAge::calculateDistance(int x1, int y1, int x2, int y2)
{
  return (int)sqrt((double)( ((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2)) ));
}


// Streaming operators
In& operator>>(In& stream,PointsWithValidityAndAge& pointsWithValidityAndAge)
{
  stream >> pointsWithValidityAndAge.sizeOfSet;
  stream >> pointsWithValidityAndAge.numberOfPoints;
  stream >> pointsWithValidityAndAge.indexOfNextPoint;
  stream.read(&pointsWithValidityAndAge.x,sizeof(pointsWithValidityAndAge.x));
  stream.read(&pointsWithValidityAndAge.y,sizeof(pointsWithValidityAndAge.y));
  return stream;
}

Out& operator<<(Out& stream, const PointsWithValidityAndAge& pointsWithValidityAndAge)
{
  stream << pointsWithValidityAndAge.sizeOfSet;
  stream << pointsWithValidityAndAge.numberOfPoints;
  stream << pointsWithValidityAndAge.indexOfNextPoint;
  stream.write(&pointsWithValidityAndAge.x, sizeof(pointsWithValidityAndAge.x));
  stream.write(&pointsWithValidityAndAge.y, sizeof(pointsWithValidityAndAge.y));
  return stream;
}


/*
 * Change log :
 * 
 * $Log: PointsWithValidityAndAge.cpp,v $
 * Revision 1.1.1.1  2004/05/22 17:20:40  cvsadm
 * created new repository GT2004_WM
 *
 * Revision 1.1  2003/10/06 14:10:15  cvsadm
 * Created GT2004 (M.J.)
 *
 * Revision 1.1  2003/09/26 11:38:52  juengel
 * - sorted tools
 * - clean-up in DataTypes
 *
 * Revision 1.1.1.1  2003/07/02 09:40:22  cvsadm
 * created new repository for the competitions in Padova from the 
 * tamara CVS (Tuesday 2:00 pm)
 *
 * removed unused solutions
 *
 * Revision 1.4  2003/04/15 15:52:12  risler
 * DDD GO 2003 code integrated
 *
 * Revision 1.4  2003/04/12 23:17:54  dthomas
 * bugfix: initialized with wrong array index
 *
 * Revision 1.3  2002/10/01 09:01:44  kspiess
 * notes removed
 *
 * Revision 1.2  2002/09/22 18:40:51  risler
 * added new math functions, removed GTMath library
 *
 * Revision 1.1  2002/09/10 15:26:39  cvsadm
 * Created new project GT2003 (M.L.)
 * - Cleaned up the /Src/DataTypes directory
 * - Removed Challenge Code
 * - Removed processing of incoming audio data
 * - Renamed AcousticMessage to SoundRequest
 *
 * Revision 1.2  2002/06/07 10:15:46  kspiess
 * constructor changed
 *
 * Revision 1.1.1.1  2002/05/10 12:40:13  cvsadm
 * Moved GT2002 Project from ute to tamara.
 *
 * Revision 1.5  2002/02/08 14:20:33  kspiess
 * Anpassung an die Namenskonventionen
 *
 * Revision 1.4  2002/02/04 13:47:09  kspiess
 * BremenBerlin2001PlayersLocator in GT2001PlayersLocator umbenannt
 * alte Aufrufe in neue geändert
 * DebugDrawing für GT2001PlayersLocator eingebaut
 *
 * Revision 1.3  2002/01/29 18:31:48  kspiess
 * activated
 *
 * Revision 1.2  2002/01/22 11:03:15  kspiess
 * Fehler im Default-Konstruktor behoben und
 * SetSizeOfSet-Methode eingebaut
 *
 * Revision 1.1  2002/01/21 23:18:30  kspiess
 * PointsWithValidityAndAge portiert;
 * wird vom BremenBerlin2001PlayersLocator verwendet
 *
 *
 */

---