function Pathfinding::getClosestConquerableField(%player, %targetField)
{
   // determine player id
   if(isObject(%player))
      %playerId = %player.getId();
   else
      return "";
   
   // open field queue with the target field enqueued
   %fieldQueue = %targetField;
   %enqueued[%targetField] = true;
   
   // repeat until queue is empty
   while(getWordCount(%fieldQueue) > 0)
   {
      // take first element from the queue
      %targetField = getWord(%fieldQueue, 0);
      %fieldQueue = removeWord(%fieldQueue, 0);
      
      // determine fieldowner
      %fieldowner = %targetField.getOwner();
      if(isObject(%fieldowner))
         %fieldownerId = %fieldowner.getId();
      
      // if this field is owned by the player, return this field
      if(%fieldownerId == %playerId)
         return %targetField;
         
      // determine all neighbors of this field
      %directNeighbors = %targetField.getAllNeighbors();
      
      // randomize order (to make AI less predictable)
      %neighborCount = getWordCount(%directNeighbors);
      for(%i = 0; %i < %neighborCount; %i++)
      {
         %randomI = getRandom(0, %neighborCount - 1);
         %changedWord = getWord(%directNeighbors, %randomI);
         %directNeighbors = setWord(%directNeighbors, %randomI, getWord(%directNeighbors, %i));
         %directNeighbors = setWord(%directNeighbors, %i, %changedWord);
      }
      
      // check if one of the neighbors is owned by the player
      %directNeighborCount = getWordCount(%directNeighbors);
      for(%i = 0; %i < %directNeighborCount; %i++)
      {
         %thisNeighbor = getWord(%directNeighbors, %i);
         
         // only work on neighbors not yet enqueued
         if(!%enqueued[%thisNeighbor])
         {
            // determine fieldowner
            %neighborOwner = %thisNeighbor.getOwner();
            if(isObject(%neighborOwner))
               %neighborOwnerId = %neighborOwner.getId();
            
            // if the neighbor is owned by the player, return this field, else enqueue neighbor if not enqueued
            if(%neighborOwnerId == %playerId)
               return %targetField;
            else
            {
               %fieldQueue = setWord(%fieldQueue, getWordCount(%fieldQueue), %thisNeighbor);
               %enqueued[%thisNeighbor] = true;
            }
         }
      }
   }
   
   // no path to the target field could be found, return empty field
   return "";
}

function Pathfinding::getClosestOpposingField(%player, %targetField)
{
   // determine player id
   %opponent = %player.getOpponent();
   if(isObject(%opponent))
      %opponentId = %opponent.getId();
   else
      return "";
   
   // open field queue with the target field enqueued
   %fieldQueue = %targetField;
   %enqueued[%targetField] = true;
   
   // repeat until queue is empty
   while(getWordCount(%fieldQueue) > 0)
   {
      // take first element from the queue
      %targetField = getWord(%fieldQueue, 0);
      %fieldQueue = removeWord(%fieldQueue, 0);
      
      // determine fieldowner
      %fieldowner = %targetField.getOwner();
      if(isObject(%fieldowner))
         %fieldownerId = %fieldowner.getId();
      
      // if this field is owned by the opponent, return this field
      if(%fieldownerId == %opponentId)
         return %targetField;
         
      // determine all neighbors of this field
      %directNeighbors = %targetField.getAllNeighbors();
      
      // randomize order (to make AI less predictable)
      %neighborCount = getWordCount(%directNeighbors);
      for(%i = 0; %i < %neighborCount; %i++)
      {
         %randomI = getRandom(0, %neighborCount - 1);
         %changedWord = getWord(%directNeighbors, %randomI);
         %directNeighbors = setWord(%directNeighbors, %randomI, getWord(%directNeighbors, %i));
         %directNeighbors = setWord(%directNeighbors, %i, %changedWord);
      }
      
      // check if one of the neighbors is owned by the opponent
      %directNeighborCount = getWordCount(%directNeighbors);
      for(%i = 0; %i < %directNeighborCount; %i++)
      {
         %thisNeighbor = getWord(%directNeighbors, %i);
         
         // only work on neighbors not yet enqueued
         if(!%enqueued[%thisNeighbor])
         {
            // determine fieldowner
            %neighborOwner = %thisNeighbor.getOwner();
            if(isObject(%neighborOwner))
               %neighborOwnerId = %neighborOwner.getId();
            
            // if the neighbor is owned by the opponent, return that field, else enqueue neighbor if not enqueued
            if(%neighborOwnerId == %opponentId)
               return %thisNeighbor;
            else
            {
               %fieldQueue = setWord(%fieldQueue, getWordCount(%fieldQueue), %thisNeighbor);
               %enqueued[%thisNeighbor] = true;
            }
         }
      }
   }
   
   // no path to the target field could be found, return empty field
   return "";
}

function Pathfinding::getClosestOwnedField(%player, %targetField)
{
   // determine player id
   if(isObject(%player))
      %playerId = %player.getId();
   else
      return "";
   
   // open field queue with the target field enqueued
   %fieldQueue = %targetField;
   %enqueued[%targetField] = true;
   
   // repeat until queue is empty
   while(getWordCount(%fieldQueue) > 0)
   {
      // take first element from the queue
      %targetField = getWord(%fieldQueue, 0);
      %fieldQueue = removeWord(%fieldQueue, 0);
      
      // determine fieldowner
      %fieldowner = %targetField.getOwner();
      if(isObject(%fieldowner))
         %fieldownerId = %fieldowner.getId();
      
      // if this field is owned by the player, return this field
      if(%fieldownerId == %playerId)
         return %targetField;
         
      // determine all neighbors of this field
      %directNeighbors = %targetField.getAllNeighbors();
      
      // randomize order (to make AI less predictable)
      %neighborCount = getWordCount(%directNeighbors);
      for(%i = 0; %i < %neighborCount; %i++)
      {
         %randomI = getRandom(0, %neighborCount - 1);
         %changedWord = getWord(%directNeighbors, %randomI);
         %directNeighbors = setWord(%directNeighbors, %randomI, getWord(%directNeighbors, %i));
         %directNeighbors = setWord(%directNeighbors, %i, %changedWord);
      }
      
      // check if one of the neighbors is owned by the opponent
      %directNeighborCount = getWordCount(%directNeighbors);
      for(%i = 0; %i < %directNeighborCount; %i++)
      {
         %thisNeighbor = getWord(%directNeighbors, %i);
         
         // only work on neighbors not yet enqueued
         if(!%enqueued[%thisNeighbor])
         {
            // determine fieldowner
            %neighborOwner = %thisNeighbor.getOwner();
            if(isObject(%neighborOwner))
               %neighborOwnerId = %neighborOwner.getId();
            
            // if the neighbor is owned by the player, return that field, else enqueue neighbor if not enqueued
            if(%neighborOwnerId == %playerId)
               return %thisNeighbor;
            else
            {
               %fieldQueue = setWord(%fieldQueue, getWordCount(%fieldQueue), %thisNeighbor);
               %enqueued[%thisNeighbor] = true;
            }
         }
      }
   }
   
   // no path to the target field could be found, return empty field
   return "";
}

function Pathfinding::getFieldDistance(%fieldA, %fieldB)
{
   // extract coordinates
   %fieldA = strreplace(%fieldA.getName(), "_", " ");
   %fieldACoordX = getWord(%fieldA, 1);
   %fieldACoordY = getWord(%fieldA, 2);
   
   %fieldB = strreplace(%fieldB.getName(), "_", " ");
   %fieldBCoordX = getWord(%fieldB, 1);
   %fieldBCoordY = getWord(%fieldB, 2);
   
   // calculate distance
   %majorDistance = 0;
   
   %distanceX = mAbs(%fieldACoordX - %fieldBCoordX);
   %distanceY = mAbs(%fieldACoordY - %fieldBCoordY);

   %totalDistance = 0;
   
   while(%distanceX > 0)
   {
      %distanceX--;
      %distanceY--;
      %totalDistance++;
   }
   
   while(%distanceY > 0)
   {
      %distanceY -= 2;
      %totalDistance++;
   }
   
   return %totalDistance;
}