#include "empire.h"
#include "ranges.h"
#include "empai_path.h"

extern int building_here(int tx, int ty);
extern int any_unit_here(int tx, int ty);
extern int moves_needed(int mtype, int tx, int ty);
extern int can_attack(_unit a, _unit d);
extern int needy(int unit_id);
extern int get_set(int mapdat);
extern int can_unload_from_here(int x, int y, int mountains);
extern int intmax(int a, int b);

extern vector<_unit*> lander;
extern vector<_connectedlocs> beaches;

int pathmap[50][50];
int tempmap[50][50];

vector<_aipath> best_aipath(int plyr, int mtype, int ox, int oy, int dx, int dy)//, bool path_filled)
{  //assumes fill_pathmap_for_unit() has been called
  vector<_aipath> best, orig;
  int x, y, z, b, d, i, s;
  best.clear();
  best.reserve(25);
  orig.clear();
  orig.reserve(25);
  x = dx;
  y = dy;  //going from target to destination is much easier than vice-versa
  if ((dx < 0) || (dx >= l) || (dy < 0) || (dy >= h))
  {
    best.push_back();
    best[0].dir = -1;
    best[0].total_moves = 0;
    return best;
  }
  if (pathmap[x][y] == 999)
  {  //if the destination is unreachable
    best.push_back();
    best[0].dir = -1;
    best[0].total_moves = 0;
    return best;
  }
  while ((dx != ox) || (dy != oy))
  {
    d = -1;
    b = 999;
    i = 1;
    while (i < 5)
    {
      switch(i)
      {
        case UP:
          x = dx;
          y = dy - 1;
          break;
        case DOWN:
          x = dx;
          y = dy + 1;
          break;
        case LEFT:
          x = dx - 1;
          y = dy;
          break;
        case RIGHT:
          x = dx + 1;
          y = dy;
          break;
      }
      if ((x > -1) && (x < l))
      {
        if ((y > -1) && (y < h))
        {
          z = pathmap[x][y];
          s = any_unit_here(x, y);
          if ((s != -1) && (s / 100 != plyr))
          {
            z = 999;
          }
          if (z < b)
          {
            d = i;
            b = z;
          }
          /*if (z == b)  UNCOMMENT THIS WHEN DEBUGGING IS FINISHED
          {  //if both directions are the same
            z = rand()%2;  //the direction taken is random
            if (z == 0)
            {
              d = i;
            }
          }*/
        }
      }
      i++;
    }
    orig.push_back();
    s = orig.size();
    orig[s - 1].dir = d;
    orig[s - 1].total_moves = pathmap[dx][dy];
    switch(d)
    {
      case UP:
        dy--;
        break;
      case DOWN:
        dy++;
        break;
      case LEFT:
        dx--;
        break;
      case RIGHT:
        dx++;
        break;
    }
  }
  i = orig.size() - 1;
  while (i >= 0)
  {  //reverse the list, so it goes from unit to destination
    best.push_back(orig[i]);
    i--;
  }
  s = best.size();
  i = 0;
  while (i < s)
  {  //the directions have to be reversed also
    switch(best[i].dir)
    {
      case UP:
        best[i].dir = DOWN;
        break;
      case DOWN:
        best[i].dir = UP;
        break;
      case LEFT:
        best[i].dir = RIGHT;
        break;
      case RIGHT:
        best[i].dir = LEFT;
        break;
    }
    i++;
  }
  return best;
}

_loc open_build_loc(int plyr, int type)
{
  _loc loc;
  loc.x = -1;
  loc.y = -1;
  int x = 0;
  int y = 0;
  int i, z, q;
  vector<int> btype[3];
  vector<_loc> good;
  btype[0].reserve(10);
  btype[1].reserve(4);
  btype[2].reserve(4);
  btype[0].push_back(0);
  btype[0].push_back(1);
  btype[0].push_back(2);
  btype[0].push_back(8);
  btype[0].push_back(10);
  btype[0].push_back(11);
  btype[0].push_back(12);
  btype[0].push_back(13);
  btype[0].push_back(14);
  btype[0].push_back(17);
  btype[1].push_back(3);
  btype[1].push_back(5);
  btype[1].push_back(7);
  btype[1].push_back(16);
  btype[2].push_back(4);
  btype[2].push_back(6);
  btype[2].push_back(9);
  btype[2].push_back(15);  //this makes a list of the units each base type builds
  while (y < h)
  {
    x = 0;
    while (x < l)
    {
      z = any_unit_here(x, y);
      if (z == -1)
      {
        z = building_here(x, y);
        if (z > 8)
        {  //if there is a building here that can make units
          if ((z - 4) % 5 == plyr + 1)
          {  //if it belongs to the player
            q = ((z - 4) / 5) - 1;
            i = 0;
            while (i < btype[q].size())
            {
              if (btype[q][i] == type)
              {
                loc.x = x;
                loc.y = y;
                good.push_back(loc);  //put the location into a vector
                i = 100;
              }
              i++;
            }
          }
        }
      }
      x++;
    }
    y++;
  }
  if (good.size() > 0)  //if there is one or more good build location
  {
    q = rand()%(good.size());  //randomly pick one of the locations
    loc.x = good[q].x;
    loc.y = good[q].y;
  }
  else
  {
    loc.x = -1;
    loc.y = -1;
  }
  return loc;
}


_loc loc_to_attack(_unit u, _aitarget t)
{
  _loc l;
  int i, q;
  if (in_range(u, t.loc.x + 1, t.loc.y) == 1)
  {  //if this adjacent location to the target is in range
    q = any_unit_here(t.loc.x + 1, t.loc.y);
    if ((q == -1) || (q == (u.color * 100) + u.number))
    {  //if there is no unit, or it is the unit that is attacking
      l.x = t.loc.x + 1;
      l.y = t.loc.y;
      return l;
    }
  }
  if (in_range(u, t.loc.x - 1, t.loc.y) == 1)
  {
    q = any_unit_here(t.loc.x - 1, t.loc.y);
    if ((q == -1) || (q == (u.color * 100) + u.number))
    {
      l.x = t.loc.x - 1;
      l.y = t.loc.y;
      return l;
    }
  }
  if (in_range(u, t.loc.x, t.loc.y + 1) == 1)
  {
    q = any_unit_here(t.loc.x, t.loc.y + 1);
    if ((q == -1) || (q == (u.color * 100) + u.number))
    {
      l.x = t.loc.x;
      l.y = t.loc.y + 1;
      return l;
    }
  }
  if (in_range(u, t.loc.x, t.loc.y - 1) == 1)
  {
    q = any_unit_here(t.loc.x, t.loc.y - 1);
    if ((q == -1) || (q == (u.color * 100) + u.number))
    {
      l.x = t.loc.x;
      l.y = t.loc.y - 1;
      return l;
    }
  }
  l.x = -1;
  l.y = -1;
  return l;
}


_loc capturable_building(_unit u)
{  //this function assumes that u is either infantry or mech (can capture)
  _loc l;
  int x = u.tilex - 3;  //3 is max movement for infantry
  int y = u.tiley - 3;
  int b;
  int priority = 0;
  int p = 0;
  l.x = -1;
  l.y = -1;
  while (y <= u.tiley + 3)
  {
    x = u.tilex - 3;
    while (x <= u.tilex + 3)
    {
      if (in_range(u, x, y) == 1)
      {  //if the unit can actually get to this location
        b = any_unit_here(x, y);
        if ((b == -1) || (b == (u.color * 100) + u.number))
        {  //if there is no unit here except possibly the one using this function
          b = building_here(x, y);
          if (b != -1)  //if there is a building here
          {
            p = u.move + 1 - tile_distance(x, y, u.tilex, u.tiley);  //priority based on distance
            if (b < 4)  //if the building is a capital
            {
              if (b % 4 != u.color)  //if it is an enemy capital
              {
                p += 7;  //this building has a higher priority than others
              }
              else
              {
                p = 0;  //if it is the unit's team capital, it has 0 capture priority
              }
            }
            else  //not a capital
            {
              if (((b - 4) % 5) - 1 == u.color)  //it is owned by the unit's team
              {
                p = 0;  //capture priority for owned buildings is 0
              }
              else
              {
                if ((b - 4) / 5 != 0)  //if it is not a city (either a base, port, airport)
                {
                  p += 3;  //higher priority for unit-producing buildings
                }
              }
            }
            if (p > priority)
            {  //if this building has greater priority than the last one
              priority = p;
              l.x = x;
              l.y = y;
            }
          }
        }
      }
      x++;
    }
    y++;
  }
  return l;
}


_loc closest_free_building(int plyr, int u, int mtype, int moves, int basetype, int ox, int oy)
{
  _loc best;
  _loc closest;
  int d = 999;
  int y = 0;
  int x;
  int q;
  int ok;
  int t;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  while (y < h)
  {
    x = 0;
    while (x < l)
    {
      q = building_here(x, y);
      if ((q != -1) && (any_unit_here(x, y) == -1))
      {  //if there is a building here without a unit on it
        ok = 0;
        if (q < 4)
        {
          if (q % 4 == plyr)
          {
            if (basetype == LAND)
            {  //only land units can be repaired at the capital
              ok = 1;
            }
          }
        }
        else
        {
          q -= 4;
          if (q % 5 == plyr + 1)  //if the building belongs to the player
          {
            t = q / 5;
            switch(basetype)
            {
              case LAND:
                if ((t == 0) || (t == 1))  //a city or a base
                {
                  ok = 1;
                }
                break;
              case AIR:
                if (t == 2)  //an airport
                {
                  ok = 1;
                }
                break;
              case SEA:
                if (t == 3)  //a seaport
                {
                  ok = 1;
                }
                break;
            }
          }
        }
        if (ok == 1)  //if the unit can be repaired at this building
        {
          t = pathmap[x][y];
          if (t < d)
          {
            d = t;
            best.x = x;
            best.y = y;
          }
        }
      }
      x++;
    }
    y++;
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, -1);
  }
  return closest;
}


_loc closest_move_to_enemy_building(int plyr, int u, int mtype, int moves, int ox, int oy, int capping_unit)
{
  _loc best;
  _loc closest;
  _loc temp;
  vector<_aipath> q;
  vector<_loc> viable;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  viable.clear();
  int i = 0;
  int x, y, z, d, t, a;
  if (player[plyr].unit[u].moving_towards != -1)
  {  //if the unit is already headed somewhere
    a = 0;
    y = 0;
    while (y < h)
    {
      x = 0;
      while (x < l)
      {
        d = (y * 100) + x;
        if (d == player[plyr].unit[u].moving_towards)
        {
          if (capping_unit == 1)
          {  //if this unit intends to capture the building
            d = any_unit_here(x, y);
            if (d != -1)
            {
              if (d / 100 == plyr)
              {  //if there is a friendly unit here
                if (player[plyr].unit[d % 100].capturing != -1)
                {  //if that unit is already taking care of that building
                  player[plyr].unit[u].moving_towards = -1;
                }
              }
            }
          }
          a = 1;
          x = l;
          y = h;
          q = best_aipath(plyr, mtype, ox, oy, x, y);
          if (q[0].dir == -1)
          {  //if the target is now unreachable for some reason
            player[plyr].unit[u].moving_towards = -1;
          }
          else
          {
            best.x = x;
            best.y = y;
          }
        }
        x++;
      }
      y++;
    }
    if (a == 0)
    {  //if the target no longer exists
      player[plyr].unit[u].moving_towards = -1;
    }
  }
  if (player[plyr].unit[u].moving_towards == -1)
  {
    d = 999;
    y = 0;
    while (y < h)
    {
      x = 0;
      while (x < l)
      {
        z = building_here(x, y);
        if (z != -1)
        {  //if there is a building here
          a = 0;
          if (z < 4)
          {
            if (z != plyr)
            {  //if it is an enemy capital
              a = 1;
            }
          }
          else
          {
            if ((z - 4) % 5 != plyr + 1)
            {  //if it doesn't belong to the player already
              a = 1;
            }
          }
          if ((a == 1) && (capping_unit == 1))
          {  //if this unit intends to capture the building
            t = any_unit_here(x, y);
            if (t != -1)
            {
              if (t / 100 == plyr)
              {  //if there is a friendly unit on it
                if (t % 100 != u)
                {  //if it isn't this unit
                  if (player[plyr].unit[t % 100].capturing != -1)
                  {  //if that unit is already taking care of that building
                    a = 0;
                  }
                }
              }
            }
          }
          else if (a == 1)
          {  //if capping_unit is 0, then it shouldn't bother doing after cities
            if ((z > 3) && (z < 9))  //city tiles are 4-8
            {
              a = 0;
            }
            if ((z - 4) % 5 == 0)  //if it is not controlled by anyone
            {  //don't bother with non-enemy bases either
              a = 0;
            }
          }
          if (a == 1)
          {
            temp.x = x;
            temp.y = y;
            viable.push_back(temp);
          }
        }
        x++;
      }
      y++;
    }
    x = 0;
    y = 999;
    z = viable.size();
    while (x < z)
    {
      if (pathmap[viable[x].x][viable[x].y] < y)
      {
        best.x = viable[x].x;
        best.y = viable[x].y;
        y = pathmap[best.x][best.y];
        player[plyr].unit[u].moving_towards = (best.y * 100) + best.x;
      }
      x++;
    }
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, -1);
  }
  return closest;
}


_loc closest_move_to_enemy_unit(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  _loc closest;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  int i = 0;
  int x, y, z, d;
  d = 999;
  i = 0;
  _unit *temp;
  _loc temploc;
  while (i < 4)
  {
    if ((player[i].playing == 1) && (i != plyr))
    {
      y = 0;
      while (y < 50)
      {
        temp = &player[i].unit[y];
        if (temp->exists == 1)
        {
          if (can_attack(player[plyr].unit[u], *temp) == 1)
          {
            temploc = best_pathmap_loc(temp->tilex, temp->tiley);
            if ((temploc.x != -1) && (temploc.y != -1))
            {
              x = pathmap[temploc.x][temploc.y];
              if (x < d)
              {
                d = x;
                best.x = temploc.x;
                best.y = temploc.y;
              }
            }
          }
        }
        y++;
      }
    }
    i++;
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, -1);
  }
  return closest;
}


_loc closest_move_to_friendly_unit(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  _loc closest;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  int i = 0;
  int x, y, z, tx, ty, d;
  d = 0;
  y = 0;
  while (y < 50)
  {
    if (player[plyr].unit[y].exists == 1)
    {
      if (player[plyr].unit[y].attacktype == DIRECT)
      {
        x = tile_distance(player[plyr].unit[y].tilex, player[plyr].unit[y].tiley, ox, oy);
        if (x > d)
        {  //should seek to support the unit that is the farthest away
          q = best_aipath(plyr, mtype, ox, oy, player[plyr].unit[y].tilex, player[plyr].unit[y].tiley);
          if (q[0].dir != -1)
          {
            d = x;
            best.x = player[plyr].unit[y].tilex;
            best.y = player[plyr].unit[y].tiley;
          }
        }
      }
    }
    y++;
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, -1);
  }
  return closest;
}


_loc closest_move_to_needy_friendly(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  _loc closest;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  int i = 0;
  int x, y, z, d;
  d = 999;
  y = 0;
  while (y < 50)
  {
    if (player[plyr].unit[y].exists == 1)
    {
      if (needy((plyr * 100) + y) == 1)
      {
        x = tile_distance(player[plyr].unit[y].tilex, player[plyr].unit[y].tiley, ox, oy);
        if (x < d)
        {
          q = best_aipath(plyr, mtype, ox, oy, player[plyr].unit[y].tilex, player[plyr].unit[y].tiley);
          if (q[0].dir != -1)
          {
            d = x;
            best.x = player[plyr].unit[y].tilex;
            best.y = player[plyr].unit[y].tiley;
            player[plyr].unit[u].moving_towards = (100 * i) + y;
          }
        }
      }
    }
    y++;
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, -1);
  }
  return closest;
}


_loc a_free_space(int plyr, int mtype, int tx, int ty)
{
  int x, y, z, r;
  int q;
  _loc d;
  d.x = -1;
  d.y = -1;
  r = 1;
  while (r < 5)
  {
    y = ty - r;
    if (y < 0) y = 0;
    while (y < ty + r)
    {
      x = tx - r;
      if (x < 0) x = 0;
      while (x < tx + r)
      {
        if (tile_distance(tx, ty, x, y) == r)
        {
          z = any_unit_here(x, y);
          if (z == -1)
          {  //if no units are here
            q = in_range(tx, ty, x, y, 0);
            if (q == 1)
            {  //if the unit can get here
              z = building_here(x, y);
              if (z != -1)
              {  //if this is a building
                if ((z < 4) || ((z - 4) / 5 == 0))
                {  //if the building can't make units
                  d.x = x;
                  d.y = y;
                  return d;
                }
              }
              else
              {
                d.x = x;
                d.y = y;
                return d;
              }
            }
          }
        }
        x++;
        if (x > l) x = tx + r;
      }
      y++;
      if (y > h) y = ty + r;
    }
    r++;
  }
  return d;
}


_loc empty_APC_nearby(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  int x, y, z, d, r, w;
  d = 999;
  if (moves > player[plyr].unit[u].gas)
  {
    moves = player[plyr].unit[u].gas;
  }
  y = oy - moves;
  while (y < oy + moves)
  {
    x = ox - moves;
    while (x < ox + moves)
    {
      w = -1;
      r = any_unit_here(x, y);
      if ((r != -1) && (r / 100 == plyr))
      {
        w = r % 100;
      }
      if (w != -1)
      {
        if (player[plyr].unit[w].type == APC)
        {
          if (player[plyr].unit[w].load[0].loaded == 0)
          {
            z = tile_distance(player[plyr].unit[w].tilex, player[plyr].unit[w].tiley, ox, oy);
            if (z < d)
            {
              q = best_aipath(plyr, mtype, ox, oy, player[plyr].unit[w].tilex, player[plyr].unit[w].tiley);
              if (q[0].dir != -1)
              {
                d = z;
                best.x = player[plyr].unit[w].tilex;
                best.y = player[plyr].unit[w].tiley;
              }
            }
          }
        }
      }
      x++;
    }
    y++;
  }
  return best;
}


_loc closest_move_to_destination(int plyr, int u, int mtype, int moves, int ox, int oy, int moving_towards, int offset)
{
  _loc best;
  _loc closest;
  _loc goodloc;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  goodloc.x = -1;
  goodloc.y = -1;
  int i = 0;
  int x, y, z, d;
  d = 999;
  y = (moving_towards % 100) - offset;
  while (y <= (moving_towards % 100) + offset)
  {
    x = (moving_towards / 100) - offset;
    while (x <= (moving_towards / 100) + offset)
    {
      z = any_unit_here(x, y);
      if ((z == -1) && (x < l) && (x > -1) && (y < h) && (y > -1))
      {
        if (tile_distance(x, y, moving_towards / 100, moving_towards % 100) == offset)
        {  //if the distance from the current tile to the desired one equals the specified offset
          if (pathmap[x][y] < d)
          {
            goodloc.x = x;
            goodloc.y = y;
            d = pathmap[x][y];
          }
        }
      }
      x++;
    }
    y++;
  }
  if (goodloc.x != -1)
  {
    q = best_aipath(plyr, mtype, ox, oy, goodloc.x, goodloc.y);
    if (q[0].dir != -1)
    {
      best.x = goodloc.x;
      best.y = goodloc.y;
    }
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, -1);
  }
  return closest;
}


_loc empty_adjacent_space(int tx, int ty)
{
  _loc d;
  d.x = -1;
  d.y = -1;
  if (any_unit_here(tx - 1, ty) == -1)
  {
    d.x = tx - 1;
    d.y = ty;
  }
  else if (any_unit_here(tx + 1, ty) == -1)
  {
    d.x = tx + 1;
    d.y = ty;
  }
  else if (any_unit_here(tx, ty - 1) == -1)
  {
    d.x = tx;
    d.y = ty - 1;
  }
  else if (any_unit_here(tx, ty + 1) == -1)
  {
    d.x = tx;
    d.y = ty + 1;
  }
  return d;  
}


_loc closest_move_to_empty_copter(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  _loc closest;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  int i = 0;
  int x, y, z, d, dest_id;
  d = 999;
  dest_id = -1;
  y = 0;
  while (y < 50)
  {
    if (player[plyr].unit[y].exists == 1)
    {
      if ((player[plyr].unit[y].type == T_COPTER) && (player[plyr].unit[y].load[0].loaded == 0))
      {
        x = tile_distance(player[plyr].unit[y].tilex, player[plyr].unit[y].tiley, ox, oy);
        if (x < d)
        {
          q = best_aipath(plyr, mtype, ox, oy, player[plyr].unit[y].tilex, player[plyr].unit[y].tiley);
          if (q[0].dir != -1)
          {
            d = x;
            best.x = player[plyr].unit[y].tilex;
            best.y = player[plyr].unit[y].tiley;
            dest_id = (100 * plyr) + y;
          }
        }
      }
    }
    y++;
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, dest_id);
  }
  return closest;
}


_loc closest_move_to_empty_APC(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  _loc closest;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  int i = 0;
  int x, y, z, d;
  int dest_id = -1;
  d = 999;
  y = 0;
  while (y < 50)
  {
    if (player[plyr].unit[y].exists == 1)
    {
      if ((player[plyr].unit[y].type == APC) && (player[plyr].unit[y].load[0].loaded == 0))
      {
        x = tile_distance(player[plyr].unit[y].tilex, player[plyr].unit[y].tiley, ox, oy);
        if (x < d)
        {
          q = best_aipath(plyr, mtype, ox, oy, player[plyr].unit[y].tilex, player[plyr].unit[y].tiley);
          if (q[0].dir != -1)
          {
            d = x;
            best.x = player[plyr].unit[y].tilex;
            best.y = player[plyr].unit[y].tiley;
            dest_id = (100 * plyr) + y;
          }
        }
      }
    }
    y++;
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, dest_id);
  }
  return closest;
}


_loc closest_move_to_available_lander(int plyr, int u, int mtype, int moves, int ox, int oy)
{
  _loc best;
  _loc closest;
  vector<_aipath> q;
  best.x = -1;
  best.y = -1;
  closest.x = -1;
  closest.y = -1;
  int i = 0;
  int x, y, z, d, m;
  d = 999;
  y = 0;
  z = -1;
  m = -1;
  while (y < lander.size())
  {
    if ((lander[y]->load[0].loaded == 0) || (lander[y]->load[1].loaded == 0))
    {
      if (pathmap[lander[y]->tilex][lander[y]->tiley] < d)
      {
        z = y;
        d = pathmap[lander[y]->tilex][lander[y]->tiley];
      }
    }
    y++;
  }
  if (z != -1)
  {
    q = best_aipath(plyr, mtype, ox, oy, lander[z]->tilex, lander[z]->tiley);
    if (q[0].dir != -1)
    {
      d = x;
      best.x = lander[z]->tilex;
      best.y = lander[z]->tiley;
      m = (100 * plyr) + lander[z]->number;
    }
  }
  if (best.x != -1)
  {  //if there is a path to the targeted tile
    closest = closest_move(plyr, u, mtype, ox, oy, best.x, best.y, m);
  }
  return closest;
}


_loc nearest_enemy_building(int plyr, int tx, int ty)
{
  int x, y, z, d, a, t;
  _loc theloc;
  theloc.x = -1;
  theloc.y = -1;
  d = 999;
  y = 0;
  while (y < h)
  {
    x = 0;
    while (x < l)
    {
      z = building_here(x, y);
      if (z != -1)
      {  //if there is a building here
        a = 0;
        if (z < 4)
        {
          if (z != plyr)
          {  //if it is an enemy capital
            a = 1;
          }
        }
        else
        {
          if ((z - 4) % 5 != plyr + 1)
          {  //if it doesn't belong to the player already
            a = 1;
          }
        }
        t = any_unit_here(x, y);
        if (t != -1)
        {
          if (t / 100 == plyr)
          {  //if there is a friendly unit on it
            if ((x != tx) || (y != ty))
            {  //if it isn't this unit
              if (player[plyr].unit[t % 100].capturing != -1)
              {  //if that unit is already taking care of that building
                a = 0;
              }
            }
          }
        }
        if (a == 1)
        {
          t = tile_distance(x, y, tx, ty);
          if (t < d)
          {
            theloc.x = x;
            theloc.y = y;
            d = t;
          }
        }
      }
      x++;
    }
    y++;
  }
  return theloc;
}


_loc unhealthy_unit_nearby(int plyr, int type, int tx, int ty)
{
  int i, j, q;
  _loc d;
  d.x = -1;
  d.y = -1;
  j = ty - 9;
  while (j <= ty + 9)
  {
    i = tx - 9;
    while (i <= tx + 9)
    {
      if ((i != tx) || (j != ty))
      {
        q = any_unit_here(i, j);
        if ((q != -1) && (in_range(tx, ty, i, j, 0) == 1))
        {  //if there is a unit here and it is in range
          if (q / 100 == plyr)
          {
            if (player[plyr].unit[q % 100].type == type)
            {  //if it is the same unit type
              if (player[plyr].unit[q % 100].health < 7)
              {  //if it could benefit from a merge
                d.x = i;
                d.y = j;
                return d;
              }
            }
          }
        }
      }
      i++;
    }
    j++;
  }
  return d;   
}


_loc closest_beach_for_lander(int plyr, int tx, int ty)
{
  int x, y, z, t, r;
  _loc d;
  vector<_unit*> goodlander;
  vector<_aipath> q;
  d.x = -1;
  d.y = -1;
  r = 1;
  y = 0;
  while (y < lander.size())
  {
    if ((lander[y]->load[0].loaded == 0) || (lander[y]->load[1].loaded == 0))
    {  //create a vector of pointers to good (can load) landers
      goodlander.push_back(lander[y]);
    }
    y++;
  }
  if (goodlander.size() == 0)
  {  //if there aren't any landers, don't bother looking for a beach for them
    return d;
  }
  tempmap = pathmap;  //pathmap is changed, so store a copy of it in tempmap
  z = 0;
  while (z < goodlander.size())
  {
    fill_pathmap_for_unit(plyr, goodlander[z]->movetype, goodlander[z]->tilex, goodlander[z]->tiley);
    r = 0;
    while ((r < intmax(l, h)) && (d.x == -1))
    {  //start looking for a good beach at 1 distance away and move outward
      y = ty - r;
      while (y <= ty + r)
      {
        x = tx - r;
        while (x <= tx + r)
        {
          if ((x >= 0) && (x < l) && (y >= 0) && (y < h) && (tile_distance(x, y, tx, ty) == r))
          {
            t = get_set(map[x][y]);
            if (t == 3)  //3 is the set for shoal (beach) tiles
            {
              q = best_aipath(plyr, goodlander[z]->movetype, goodlander[z]->tilex, goodlander[z]->tiley, x, y);
              if (q[0].dir != -1)
              {  //if a lander can get to this beach
                d.x = x;
                d.y = y;
                pathmap = tempmap;  //set pathmap back to what it was originally
                return d;
              }
            }
          }
          x++;
        }
        y++;
      }
      r++;
    }
    z++;
  }
  pathmap = tempmap;
  return d;    
}


_loc closest_enemy_beach(int plyr, int ox, int oy, int mountain_climber)
{  //if mountain_climber == 1, then the lander is carrying all infantries or mechs
  vector<_loc> closest_ones;
  vector<_loc> viable;
  vector<_aipath> q;
  _loc d;
  _loc best;
  int i = 0;
  int j;
  int b;
  int t;
  int wtype;
  closest_ones.reserve(10);
  viable.reserve(5);
  if (mountain_climber == 1)
  {
    wtype = M_INFANTRY;
  }
  else
  {
    wtype = M_TREAD;
  }
  while (i < beaches.size())
  {
    if (pathmap[beaches[i].loc[0].x][beaches[i].loc[0].y] < 999)
    {  //if the lander can reach this beach (and, therefore, all connected beaches)
      b = 999;
      j = 0;
      d.x = -1;
      d.y = -1;
      while (j < beaches[i].loc.size())
      {  //put the closest beach to the lander in this set into the closest_ones vector
        t = pathmap[beaches[i].loc[j].x][beaches[i].loc[j].y];//tile_distance(ox, oy, beaches[i].loc[j].x, beaches[i].loc[j].y);
        if ((t < b) && (can_unload_from_here(beaches[i].loc[j].x, beaches[i].loc[j].y, mountain_climber) == 1))
        {
          if (any_unit_here(beaches[i].loc[j].x, beaches[i].loc[j].y) == -1)
          {
            b = t;
            d.x = beaches[i].loc[j].x;
            d.y = beaches[i].loc[j].y;
          }
        }
        j++;
      }
      if (d.x != -1)
      {
        closest_ones.push_back(d);
      }
    }
    i++;
  }
  i = 0;
  while (i < closest_ones.size())
  {  //from these _locs, find ones that lead to an enemy building or unit
    d = reachable_enemy_building(plyr, wtype, closest_ones[i].x, closest_ones[i].y, mountain_climber);
    if (d.x != -1)
    {
      viable.push_back(closest_ones[i]);
    }
    i++;
  }
  best.x = -1;
  best.y = -1;
  b = 999;
  i = 0;
  while (i < viable.size())
  {
    if (pathmap[viable[i].x][viable[i].y] < b)
    {  //find the viable beach location closest to the lander
      best = viable[i];
      b = pathmap[viable[i].x][viable[i].y];
    }
    i++;
  }
  return best;
}

_loc reachable_friendly_beach(int plyr, int u, int ox, int oy, int moves)
{
  _loc d;
  _loc temp;
  d.x = -1;
  d.y = -1;
  int i = 0;
  int j;
  int b;
  int t;
  int q;
  if (moves > player[plyr].unit[u].gas)
  {
    moves = player[plyr].unit[u].gas;
  }
  q = building_here(ox, oy);
  if (q == -1)
  {  //if it is not on a port
    d.x = ox;
    d.y = oy;
    return d;  //stay right there
  }
  b = moves + 1;
  while (i < beaches.size())
  {
    j = 0;
    while (j < beaches[i].loc.size())
    {
      q = building_here(beaches[i].loc[j].x, beaches[i].loc[j].y);
      if ((q == -1) && (any_unit_here(beaches[i].loc[j].x, beaches[i].loc[j].y) == -1))
      {  //if there is not a building here (which must be a port) or a unit here
        t = pathmap[beaches[i].loc[j].x][beaches[i].loc[j].y];
        if (t < b)
        {
          temp = reachable_friendly_building(plyr, M_MECH, beaches[i].loc[j].x, beaches[i].loc[j].y);
          if (temp.x != -1)
          {
            b = t;
            d.x = beaches[i].loc[j].x;
            d.y = beaches[i].loc[j].y;
          }
        }
      }
      j++;
    }
    i++;
  }
  return d;
}

_loc reachable_enemy_building(int plyr, int mtype, int ox, int oy, int cap)
{
  return reachable_enemy_building(plyr, mtype, ox, oy, cap, 0);
}

_loc reachable_enemy_building(int plyr, int mtype, int ox, int oy, int cap, int non_city)
{  //if cap == 1 it counts neutral buildings as enemies
  int x, y, z;
  _loc d;
  d.x = -1;
  d.y = -1;
  y = 0;
  while (y < h)
  {
    x = 0;
    while (x < l)
    {
      tempmap[x][y] = 999;
      x++;
    }
    y++;
  }
  if (enemy_building(plyr, ox, oy, cap, non_city) == 1)
  {
    d.x = ox;
    d.y = oy;
    return d;
  }
  z = 0;
  while ((d.x == -1) && (z < 4))
  {
    switch(z)
    {
      case 0:
        x = ox + 1;
        y = oy;
        break;
      case 1:
        x = ox - 1;
        y = oy;
        break;
      case 2:
        x = ox;
        y = oy - 1;
        break;
      case 3:
        x = ox;
        y = oy + 1;
        break;
    }
    if ((x >= 0) && (x < l) && (y >= 0) && (y < h))
    {
      d = reachable_enemy_building_recursive(plyr, mtype, x, y, cap, non_city, 0);
    }
    z++;
  }
  return d;
}

_loc reachable_enemy_building_recursive(int plyr, int mtype, int ox, int oy, int cap, int non_city, int moves)
{
  _loc d;
  int m = moves_needed(mtype, ox, oy);
  int x, y, z;
  d.x = -1;
  d.y = -1;
  moves += m;
  if ((moves >= tempmap[ox][oy]) || (m == 99))
  {
    return d;
  }
  tempmap[ox][oy] = moves;
  if (enemy_building(plyr, ox, oy, cap, non_city) == 1)
  {
    d.x = ox;
    d.y = oy;
    return d;
  }
  z = 0;
  while ((d.x == -1) && (z < 4))
  {
    switch(z)
    {
      case 0:
        x = ox + 1;
        y = oy;
        break;
      case 1:
        x = ox - 1;
        y = oy;
        break;
      case 2:
        x = ox;
        y = oy - 1;
        break;
      case 3:
        x = ox;
        y = oy + 1;
        break;
    }
    if ((x >= 0) && (x < l) && (y >= 0) && (y < h))
    {
      d = reachable_enemy_building_recursive(plyr, mtype, x, y, cap, non_city, moves);
    }
    z++;
  }
  return d;
}

_loc reachable_friendly_building(int plyr, int mtype, int ox, int oy)
{
  int x, y, z;
  _loc d;
  d.x = -1;
  d.y = -1;
  y = 0;
  while (y < h)
  {
    x = 0;
    while (x < l)
    {
      tempmap[x][y] = 999;
      x++;
    }
    y++;
  }
  if (friendly_building(plyr, ox, oy) == 1)
  {
    d.x = ox;
    d.y = oy;
    return d;
  }
  z = 0;
  while ((d.x == -1) && (z < 4))
  {
    switch(z)
    {
      case 0:
        x = ox + 1;
        y = oy;
        break;
      case 1:
        x = ox - 1;
        y = oy;
        break;
      case 2:
        x = ox;
        y = oy - 1;
        break;
      case 3:
        x = ox;
        y = oy + 1;
        break;
    }
    if ((x >= 0) && (x < l) && (y >= 0) && (y < h))
    {
      d = reachable_friendly_building_recursive(plyr, mtype, x, y, 0);
    }
    z++;
  }
  return d;
}

_loc reachable_friendly_building_recursive(int plyr, int mtype, int ox, int oy, int moves)
{
  _loc d;
  int m = moves_needed(mtype, ox, oy);
  int x, y, z;
  d.x = -1;
  d.y = -1;
  moves += m;
  if ((moves >= tempmap[ox][oy]) || (m == 99))
  {
    return d;
  }
  tempmap[ox][oy] = moves;
  if (friendly_building(plyr, ox, oy) == 1)
  {
    d.x = ox;
    d.y = oy;
    return d;
  }
  z = 0;
  while ((d.x == -1) && (z < 4))
  {
    switch(z)
    {
      case 0:
        x = ox + 1;
        y = oy;
        break;
      case 1:
        x = ox - 1;
        y = oy;
        break;
      case 2:
        x = ox;
        y = oy - 1;
        break;
      case 3:
        x = ox;
        y = oy + 1;
        break;
    }
    if ((x >= 0) && (x < l) && (y >= 0) && (y < h))
    {
      d = reachable_friendly_building_recursive(plyr, mtype, x, y, moves);
    }
    z++;
  }
  return d;
}

int enemy_building(int plyr, int x, int y, int cap)
{
  return enemy_building(plyr, x, y, cap, 0);
}

int enemy_building(int plyr, int x, int y, int cap, int non_city)
{
  int z = building_here(x, y);
  if (z != -1)
  {
    if (z < 4)
    {
      if (z != plyr)
      {
        return 1;
      }
    }
    else
    {
      z -= 4;
      if (z % 5 != plyr + 1)
      {  //if it is not the player's building
        if ((z % 5 != 0) || (cap == 1))
        {  //if it is not neutral, or is neutral and cap == 1
          if (non_city == 0)
          {
            return 1;
          }
          else
          {
            if (z / 5 == 0)
            {  //if it is a city
              return 0;
            }
            else
            {
              return 1;
            }
          }
        }
      }
    }
  }
  return 0;
}

int friendly_building(int plyr, int x, int y)
{
  int z = building_here(x, y);
  if (z != -1)
  {
    if (z < 4)
    {
      if (z == plyr)
      {
        return 1;
      }
    }
    else
    {
      z -= 4;
      if (z % 5 == plyr + 1)
      {
        return 1;
      }
    }
  }
  return 0;
}

_loc unloadable_point(int x, int y, int mountains)
{
  _loc i;
  i.x = -1;
  i.y = -1;
  return unloadable_point(x, y, mountains, i);
}

_loc unloadable_point(int x, int y, int mountains, _loc ignore)
{
  int a, b, i, m;
  _loc d;
  d.x = -1;
  d.y = -1;
  if (mountains == 1)
  {
    m = M_MECH;
  }
  else
  {
    m = M_TREAD;
  }
  i = 0;
  while (i < 4)
  {
    switch(i)
    {
      case 0:
        a = x - 1;
        b = y;
        break;
      case 1:
        a = x + 1;
        b = y;
        break;
      case 2:
        a = x;
        b = y - 1;
        break;
      case 3:
        a = x;
        b = y + 1;
        break;
    }
    if ((ignore.x != a) || (ignore.y != b))
    {  //if it is not the ignored location
      if (any_unit_here(a, b) == -1)
      {  //if there is no unit here to obstruct unloading
        if ((x > -1) && (y > -1) && (x < l) && (y < h))
        {
          if (moves_needed(m, a, b) < 99)
          {  //if the unit to be unloaded can actually go on this tile
            d.x = a;
            d.y = b;
            return d;
          }
        }
      }
    }
    i++;
  }
  return d;
}

void fill_pathmap_for_unit(int plyr, int mtype, int ox, int oy)
{
  int x, y, z;
  y = 0;
  while (y < h)
  {
    x = 0;
    while (x < l)
    {
      pathmap[x][y] = 999;
      x++;
    }
    y++;
  }
  z = 0;
  while (z < 4)
  {
    switch(z)
    {
      case 0:
        x = ox + 1;
        y = oy;
        break;
      case 1:
        x = ox - 1;
        y = oy;
        break;
      case 2:
        x = ox;
        y = oy - 1;
        break;
      case 3:
        x = ox;
        y = oy + 1;
        break;
    }
    if ((x >= 0) && (x < l) && (y >= 0) && (y < h))
    {
      fill_pathmap_recursive(plyr, mtype, x, y, 0);
    }
    z++;
  }
  pathmap[ox][oy] = 0;
}

void fill_pathmap_recursive(int plyr, int mtype, int ox, int oy, int moves)
{
  int m = moves_needed(mtype, ox, oy);
  int x, y, z;
  z = any_unit_here(ox, oy);
  if ((z != -1) && (z / 100 != plyr))
  {
    m = 99;
  }
  moves += m;
  if ((moves >= pathmap[ox][oy]) || (m == 99))
  {
    return;
  }
  pathmap[ox][oy] = moves;
  z = 0;
  while (z < 4)
  {
    switch(z)
    {
      case 0:
        x = ox + 1;
        y = oy;
        break;
      case 1:
        x = ox - 1;
        y = oy;
        break;
      case 2:
        x = ox;
        y = oy - 1;
        break;
      case 3:
        x = ox;
        y = oy + 1;
        break;
    }
    if ((x >= 0) && (x < l) && (y >= 0) && (y < h))
    {
      fill_pathmap_recursive(plyr, mtype, x, y, moves);
    }
    z++;
  }
}

_loc best_target_for_ranged_attack(int plyr, int u, int ox, int oy, int rmin, int rmax)
{
  int x, y, r, a, b, z, final;
  int d = 999;
  _loc t;
  t.x = -1;
  t.y = -1;
  r = rmin - 1;  //first check spaces close by that can't be hit right now
  while (r > 0)
  {
    x = ox + r;
    y = oy;
    while(x >= ox)
    {  //loop around in diagonal lines, looking for an enemy
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x--;
      y--;
    }
    while (x >= ox - r)
    {
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x--;
      y++;
    }
    while (x <= ox)
    {
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x++;
      y++;
    }
    while (x < ox + r)
    {
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x++;
      y--;
    }
    r--;  
  }
  a = intmax(l - ox, ox);
  b = intmax(h - oy, oy);
  final = intmax(a, b);
  r = rmax;
  while (r < final)  //now check outside the max range for an enemy
  {
    x = ox + r;
    y = oy;
    while(x >= ox)
    {  //loop around in diagonal lines, looking for an enemy
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x--;
      y--;
    }
    while (x >= ox - r)
    {
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x--;
      y++;
    }
    while (x <= ox)
    {
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x++;
      y++;
    }
    while (x < ox + r)
    {
      if (check_ranged_attack_here(plyr, u, x, y) == true)
      {
        t.x = x;
        t.y = y;
        return t;
      }
      x++;
      y--;
    }
    r++;
  }
  return t;
}

bool check_ranged_attack_here(int plyr, int n, int x, int y)
{
  _loc d;
  _unit* u = &player[plyr].unit[n];
  int z = any_unit_here(x, y);
  int temp1 = u->move;
  if (u->gas < temp1)
  {
    temp1 = u->gas;
  }
  if ((z != -1) && (z / 100 != plyr))
  {
    if (can_attack(*u, player[z / 100].unit[z % 100]) == 1)
    {
      d = closest_move_to_destination(u->color, u->number, u->movetype, temp1, u->tilex, u->tiley, x * 100 + y, get_rangemax(u->type));
      if (d.x == -1)
      {
        d = closest_move_to_destination(u->color, u->number, u->movetype, temp1, u->tilex, u->tiley, x * 100 + y, get_rangemin(u->type));
        if (d.x == -1)
        {
          return false;
        }
      }
      return true;
    }
  }
  return false;
}

_loc closest_move(int plyr, int u, int mtype, int ox, int oy, int dx, int dy, int ignore)
{
  _loc closest;
  vector<_loc> loclist;
  vector<_aipath> b;
  int x, y, z, tx, ty;
  b = best_aipath(plyr, mtype, ox, oy, dx, dy);
  loclist.push_back();
  loclist[0].x = ox;
  loclist[0].y = oy;
  x = b.size();
  tx = ox;
  ty = oy;
  z = player[plyr].unit[u].move;
  if (z > player[plyr].unit[u].gas)
  {
    z = player[plyr].unit[u].gas;
  }
  y = 0;
  while ((y < x) && (z > 0))
  {  //put all move locations in one vector of _loc's
    switch(b[y].dir)
    {
      case UP:
        ty--;
        break;
      case DOWN:
        ty++;
        break;
      case LEFT:
        tx--;
        break;
      case RIGHT:
        tx++;
        break;
    }
    z -= moves_needed(mtype, tx, ty);
    if (z >= 0)  //make sure the final 'best' location is reachable this turn
    {  //because if it isn't, the game will crash quite horribly
      loclist.push_back();
      loclist[y + 1].x = tx;
      loclist[y + 1].y = ty;
      y++;
    }
  }
  y = loclist.size() - 1;
  z = any_unit_here(loclist[y].x, loclist[y].y);
  while ((y > 0) && (z != -1) && (z != ignore))
  {  //goes back from the last _loc until no other unit is on this tile
    loclist.pop_back();
    y--;
    if (y > 0)
    {
      z = any_unit_here(loclist[y].x, loclist[y].y);
    }
  }  //a worst case scenario returns the tile the unit is already on
  closest.x = loclist[y].x;
  closest.y = loclist[y].y;
  return closest;
}

_loc best_pathmap_loc(int tx, int ty)
{
  _loc a, b, c, d, best;
  int ia, ib, ic, id, ibest;
  ibest = ia = ib = ic = id = 999;
  d.x = -1;
  d.y = -1;
  best = a = b = c = d;
  if (tx > 0)
  {
    a.x = tx - 1;
    a.y = ty;
    ia = pathmap[a.x][a.y];
  }
  if (tx < l)
  {
    b.x = tx + 1;
    b.y = ty;
    ib = pathmap[b.x][b.y];
  }
  if (ty > 0)
  {
    c.x = tx;
    c.y = ty - 1;
    ic = pathmap[c.x][c.y];
  }
  if (ty < h)
  {
    d.x = tx;
    d.y = ty + 1;
    id = pathmap[d.x][d.y];
  }
  if (ia < ibest)
  {
    best = a;
    ibest = ia;
  }
  if (ib < ibest)
  {
    best = b;
    ibest = ib;
  }
  if (ic < ibest)
  {
    best = c;
    ibest = ic;
  }
  if (id = ibest)
  {
    best = d;
    ibest = id;
  }
  return best;
}

bool friendly_unit_maker_here(int tx, int ty, int plyr)
{
  int temp1 = building_here(tx, ty);
  if (temp1 != -1)
  {  //if it's on a building
    if ((temp1 > 3) && ((temp1 - 4) % 5 == plyr + 1))
    {  //if it belongs to the player
      if ((temp1 - 4) / 5 != 0)
      {  //if it's a building that can make units, get off of it
        return true;
      }
    }
  }
  return false;
}
