public State CalculateState(Location a, IGameState state)
        {
            State s = new State();
            Location l;
            Tile t;
            for (int x = -radius; x <= radius; x++)
            {
                for (int y = -radius; y <= radius; y++)
                {
                    if (x == 0 && y == 0)
                        continue;

                    l = (a + new Location(y, x)) % new Location(state.Height, state.Width);
                    t = state[l];
                    if (t == Tile.Ant)
                    {
                        if(state.MyAnts.Contains(new Ant(l.Row, l.Col, state.MyAnts[0].Team)))
                            s.MyAnt = true;
                        else
                            s.EnemyAnt = true;
                    }
                    else if (t == Tile.Food)
                        s.Food = true;
                    else if (t == Tile.Hill)
                    {
                        if (state.MyHills.Contains(new AntHill(l.Row, l.Col, state.MyHills[0].Team)))
                            s.MyHill = true;
                        else
                            s.EnemyHill = true;
                    }
                }
            }
            s.AirSuperiority = state.MyAnts.Count > state.EnemyAnts.Count;
            return s;
        }

        public State buildState(Location ant)
        {
            Dictionary<StateParameter, int> distances = new Dictionary<StateParameter, int>();
              Dictionary<StateParameter, List<Location>> targets = new
            Dictionary<StateParameter, List<Location>>();

              // Find the closest friends
              int friendDistance = maxDistance;
              List<Location> closestFriends = new List<Location>();
              foreach (Location friend in gameState.MyAnts)
              {
            if (friend == ant) continue;
            int delta = gameState.GetDistance(ant, friend);
            if (delta < friendDistance)
            {
              closestFriends.Clear();
              friendDistance = delta;
            }
            if (delta <= friendDistance)
            {
              closestFriends.Add(friend);
            }
              }

              distances[StateParameter.OwnAnt] = friendDistance;
              targets[StateParameter.OwnAnt] = closestFriends;

              return new State(distances, targets);
        }

 public List<Node> ConnectedNodes(Node current, Location targetLoc)
 {
     //Returns the nodes around a certain node, depending on whether those surrounding nodes are dirt, water or unknown
     //Input requires location of node, with the distance that has been traversed so far
     int x = current.X;
     int y = current.Y;
     //Check left, right, up and down
     List<Node> connected = new List<Node>();
     //Check left
     x--;
     if (x < 0) x = w - 1; //For wrapping around the map
     if (map[x, y].IsPassable)
         connected.Add(new Node(x, y, DistanceToLocation(x, y, targetLoc) + current.DistanceTraversed + 1, current.DistanceTraversed + 1)); //new node has x, y, tentative f score, tentative g score
     //Check right
     x = current.X + 1;
     if (x == w) x = 0; //For wrapping around the map
     if (map[x, y].IsPassable)
         connected.Add(new Node(x, y, DistanceToLocation(x, y, targetLoc) + current.DistanceTraversed + 1, current.DistanceTraversed + 1));
     //Check up
     x = current.X;
     y--;
     if (y < 0) y = h - 1; //For wrapping around the map
     if (map[x, y].IsPassable)
         connected.Add(new Node(x, y, DistanceToLocation(x, y, targetLoc) + current.DistanceTraversed + 1, current.DistanceTraversed + 1));
     //Check down
     y = current.Y + 1;
     if (y == h) y = h - 1; //For wrapping around the map
     if (map[x, y].IsPassable)
         connected.Add(new Node(x, y, DistanceToLocation(x, y, targetLoc) + current.DistanceTraversed + 1, current.DistanceTraversed + 1));
     return connected;
 }

 public void AddLocation(Location location, IGameState state)
 {
     //Sets whether a tile is dirt or water
     char tile = 'u';
     if (state.GetIsPassable(location)) tile = 'd';
     else tile = 'w';
     map[location.Col, location.Row].type = tile;
 }

 public HeatMap(int gridsize, IGameState asdfstate)
 {
     state = asdfstate;
     heatMapGridSize = gridsize;
     heatMap = new float[(int)Math.Ceiling((float)state.Height / heatMapGridSize), (int)Math.Ceiling((float)state.Width / heatMapGridSize)];
     heatMapCentre = new Location[heatMap.GetLength(0), heatMap.GetLength(1)];
     for (int y = 0; y < heatMapCentre.GetLength(0); y++)
         for (int x = 0; x < heatMapCentre.GetLength(1); x++)
             heatMapCentre[y, x] = new Location(y * heatMapGridSize, x * heatMapGridSize);
 }

        public Location SelectRandomLocation(Location lowerLeft, Location upperRight, Random random)
        {
            Location goal;
            do
            {
                goal = new Location(random.Next(upperRight.Row, lowerLeft.Row), random.Next(lowerLeft.Col, upperRight.Col));
            } while (goal == null && !Globals.state.MyHills.Contains(goal) && Globals.state.GetIsPassable(goal));

            return goal;
        }

 public Location GetNextCellCentre(Location centre, IGameState state)
 {
     //return null;
     Location newCentre = new Location(centre.Row, centre.Col + 1);
     if (newCentre.Col % heatMapGridSize == 0)
         newCentre = new Location(centre.Row + 1, centre.Col + 1 - heatMapGridSize);
     if (newCentre.Row % heatMapGridSize == 0)
         return null;
     return newCentre;
 }

        public Location SelectRandomNeighbor(Location loc, Random random)
        {
            Location goal = null;
            // Our locations store their neighbors, making it easy to select a random direction with wrapping behavior.
            // We make sure not to move towards our own hills and make sure the tile is unoccupied.
            // This is a simplified version of our previous exploration strategy, which would plan a path towards a random location.
            while (!Globals.state.GetIsPassable((goal = loc.Neighbors[random.Next(4)])) && Globals.state.MyHills.Contains(goal) && !Globals.state.GetIsUnoccupied(goal))
                continue;

            return goal;
        }

        public GameState(int width, int height, 
		                  int turntime, int loadtime, 
		                  int viewradius2, int attackradius2, int spawnradius2, int seed)
        {
            Width = width;
            Height = height;

            LoadTime = loadtime;
            TurnTime = turntime;
            PlayerSeed = seed;

            ViewRadius2 = viewradius2;
            AttackRadius2 = attackradius2;
            ViewRadius = (int)Math.Sqrt(viewradius2);
            AttackRadius = (int)Math.Sqrt(attackradius2);
            SpawnRadius2 = spawnradius2;

            MyAnts = new List<Location>();
            MyHills = new List<Location>();
            EnemyAnts = new List<Location>();
            EnemyHills = new List<Location>();
            DeadTiles = new List<Location>();
            FoodTiles = new List<Location>();

            map = new Location[height, width];
            for (int i = 0; i < map.GetLength(0); ++i)
            {
                for (int j = 0; j < map.GetLength(1); ++j)
                {
                    map[i, j] = new Location(i, j);
                }
            }

            foreach (Location l in map)
            {
                int col = (l.Col - 1) % width;
                if (col < 0)
                    col += width;
                int row = (l.Row - 1) % height;
                if (row < 0)
                    row += height;

                l.Neighbors[0] = map[row, l.Col];
                l.Neighbors[3] = map[l.Row, col];

                row = (l.Row + 1) % height;
                col = (l.Col + 1) % width;

                l.Neighbors[1] = map[row, l.Col];
                l.Neighbors[2] = map[l.Row, col];
            }
        }

        /// <summary>
        /// call this to plan a path between points
        /// </summary>
        /// <param name="begin"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        public Route FindRoute(Location begin, Location end)
        {
            HashSet<MapTile> tilesToReset = new HashSet<MapTile>();//all tiles that need to be reset

            MapTile mapEnd = Map[end.Row, end.Col];
            MapTile mapBegin = Map[begin.Row, begin.Col];
            tilesToReset.Add(mapBegin);

            mapBegin.CostKnown = 0;
            mapBegin.Heuristic = Globals.state.GetDistance(begin, end);
            mapBegin.CostEstimate = mapBegin.CostKnown + mapBegin.Heuristic;

            MinHeap<MapTile> OpenSet = new MinHeap<MapTile>();
            OpenSet.Add(mapBegin);

            while (!OpenSet.IsEmpty)
            {
                MapTile current = OpenSet.ExtractMin();

                if (current == mapEnd)
                    return BuildRoute(mapEnd, tilesToReset);//reset after the oath is build, we need those pi pointers

                foreach (Direction d in (Direction[])Enum.GetValues(typeof(Direction)))
                {
                    Location tile = Globals.state.GetDestination(current.GetLocation, d);
                    MapTile neighbour = Map[tile.Row, tile.Col];

                    bool succesful = Relax(current, neighbour, mapEnd);
                    tilesToReset.Add(neighbour);//hashset will not contain duplicates

                    if (!neighbour.InOpenSet && succesful)
                    {
                        OpenSet.Add(neighbour);
                        neighbour.InOpenSet = true;//openset is a min heap, no O(1) lookup so store this in the tile
                    }
                    else
                    {

                        if (neighbour.InOpenSet && succesful)
                        {
                            OpenSet.ChangeKey(neighbour, neighbour.CostEstimate);
                        }
                    }
                }
            }

            foreach (MapTile t in tilesToReset)//no route found, still need to reset
                t.Reset();

            return null;
        }

        public Goal(Location startPoint, IEnumerable<Tile> path, Func<GameState, bool> terminationFunc, Strategy? currentStrategy)
        {
            this.CurrentStep = 0;
            this.AntExists = true;
            this.CurrentPath = new Queue<Tile>(path);
            this.CurrentPath.Dequeue();

            this.StartPath = path;

            this.StartPoint = this.CurrentPoint = startPoint;
            this.IsTerminated = terminationFunc;

            this.CurrentStrategy = currentStrategy;
        }

        public Location FindRoute(Location start, Location end)
        {
            //Find a route from start to end, using A* and what we know of the map
            List<Node> closedSet = new List<Node>(); //Set with nodes already evaluated
            List<Node> openSet = new List<Node>(); //Set with nodes that have not yet been evaluated
            //Add the starting node to the openSet
            openSet.Add(new Node(start.Col, start.Row, 0 + DistanceToLocation(start.Col, start.Row, end), 0));

            int counter = 0; //To prevent it from taking too long
            while (openSet.Count > 0 && counter < 50)
            {
                //Sort the openSet, arranging the nodes from high to low and putting the lowest on top of the list
                openSet.Sort(delegate(Node n1, Node n2)
                {
                    return -(int)n1.CompareTo(n2);
                });
                Node current = openSet[openSet.Count - 1]; //Find the last node in the list
                if (current.IsLocation(end))
                {
                    return ReconstructPath(closedSet, end); //Check whether it's the goal
                }
                openSet.RemoveAt(openSet.Count - 1); //Remove the last node from the open list
                closedSet.Add(current); //Add the current node to closed set

                List<Node> neighbours = ConnectedNodes(current, end); //Find the neighbours of the node, aka the traversible nodes
                foreach (Node neighbour in neighbours)
                {
                    double fScore = DistanceToLocation(neighbour.X, neighbour.Y, end); //calculate the f score
                    if (!openSet.Contains(neighbour) || neighbour.TentativeFScore < fScore)
                    {
                        //Ensure that the neighbour knows where it came from
                        neighbour.CameFrom(current);
                        //Add the neighbour to the open set
                        openSet.Add(neighbour);
                    }
                }
                counter++;
            }

            return null;
        }

        protected MoveType doMoveDirection(Location ant, Direction direction)
        {
            Location newLoc = Globals.state.GetDestination(ant, direction);

            if (Globals.state.GetIsUnoccupied(newLoc) && !orders.ContainsKey(newLoc))
            {
                Bot.IssueOrder(ant, direction);
                orders.Add(newLoc, ant);
                return MoveType.Success;
            }
            else
            {
                if (!Globals.state.GetIsPassable(newLoc))
                    return MoveType.FailTerrain;
                if (orders.ContainsKey(newLoc))
                    return MoveType.FailAnt;
                if (!Globals.state.GetIsUnoccupied(newLoc))
                    return MoveType.Fail;
            }

                return MoveType.Fail;
        }

        public Location GetHotDestination(Location loc)
        {
            float d, d2;
            float maxHeat = float.MinValue;
            Location pref = null, l;
            for (int y = 0; y < heatMap.GetLength(0); y++)
            {
                for (int x = 0; x < heatMap.GetLength(1); x++)
                {
                    l = heatMapCentre[y, x];
                    if (l == null)
                        continue;

                    while (!state.GetIsPassable(l))
                    {
                        l = GetNextCellCentre(l, state);
                        heatMapCentre[y, x] = l;
                        if (l == null)
                            break;
                    }

                    if (l == null)
                        continue;

                    d = state.GetDistance(loc, l) / (float)heatMapGridSize;
                    if (d < 1)
                        continue;
                    d2 = heatMap[y, x] - d * 1.5f;
                    if (d2 > maxHeat)
                    {
                        maxHeat = d2;
                        pref = l;
                    }
                }
            }
            return pref;
        }

 public bool GetIsVisible(Location loc)
 {
     List<Location> offsets = new List<Location>();
     int squares = (int)Math.Floor(Math.Sqrt(this.ViewRadius2));
     for (int r = -1 * squares; r <= squares; ++r)
     {
         for (int c = -1 * squares; c <= squares; ++c)
         {
             int square = r * r + c * c;
             if (square < this.ViewRadius2)
             {
                 Location wrap = this.WrapCoordinates(new Location(r, c));
                 r = wrap.Row;
                 c = wrap.Col;
                 offsets.Add(map[r, c]);
             }
         }
     }
     foreach (Location ant in this.MyAnts)
     {
         foreach (Location offset in offsets)
         {
             if ((ant.Col + offset.Col) == loc.Col &&
                 (ant.Row + offset.Row) == loc.Row)
             {
                          return true;
             }
         }
     }
     return false;
 }

 /// <summary>
 /// Gets whether <paramref name="location"/> is occupied or not.
 /// </summary>
 /// <param name="location">The location to check.</param>
 /// <returns><c>true</c> if the location is passable and does not contain an ant, <c>false</c> otherwise.</returns>
 public bool GetIsUnoccupied(Location location)
 {
     return GetIsPassable(location) && map[location.Row, location.Col].Value != Tile.Ant && map[location.Row, location.Col].Value!=Tile.Food;
 }

 /// <summary>
 /// Gets whether <paramref name="location"/> is passable or not.
 /// </summary>
 /// <param name="location">The location to check.</param>
 /// <returns><c>true</c> if the location is not water, <c>false</c> otherwise.</returns>
 /// <seealso cref="GetIsUnoccupied"/>
 public bool GetIsPassable(Location location)
 {
     return map[location.Row, location.Col].Value != Tile.Water;
 }

        /// <summary>
        /// Gets the distance between <paramref name="loc1"/> and <paramref name="loc2"/>.
        /// </summary>
        /// <param name="loc1">The first location to measure with.</param>
        /// <param name="loc2">The second location to measure with.</param>
        /// <returns>The distance between <paramref name="loc1"/> and <paramref name="loc2"/></returns>
        public int GetDistance(Location loc1, Location loc2)
        {
            int d_row = Math.Abs(loc1.Row - loc2.Row);
            d_row = Math.Min(d_row, Height - d_row);

            int d_col = Math.Abs(loc1.Col - loc2.Col);
            d_col = Math.Min(d_col, Width - d_col);

            return d_row + d_col;
        }

        /// <summary>
        /// Gets the closest directions to get from <paramref name="loc1"/> to <paramref name="loc2"/>.
        /// </summary>
        /// <param name="loc1">The location to start from.</param>
        /// <param name="loc2">The location to determine directions towards.</param>
        /// <returns>The 1 or 2 closest directions from <paramref name="loc1"/> to <paramref name="loc2"/></returns>
        public ICollection<Direction> GetDirections(Location loc1, Location loc2)
        {
            List<Direction> directions = new List<Direction>();

                if (loc1.Row < loc2.Row)
                {
                    if (loc2.Row - loc1.Row >= Height / 2)
                        directions.Add(Direction.North);
                    if (loc2.Row - loc1.Row <= Height / 2)
                        directions.Add(Direction.South);
                }
                if (loc2.Row < loc1.Row)
                {
                    if (loc1.Row - loc2.Row >= Height / 2)
                        directions.Add(Direction.South);
                    if (loc1.Row - loc2.Row <= Height / 2)
                        directions.Add(Direction.North);
                }

                if (loc1.Col < loc2.Col)
                {
                    if (loc2.Col - loc1.Col >= Width / 2)
                        directions.Add(Direction.West);
                    if (loc2.Col - loc1.Col <= Width / 2)
                        directions.Add(Direction.East);
                }
                if (loc2.Col < loc1.Col)
                {
                    if (loc1.Col - loc2.Col >= Width / 2)
                        directions.Add(Direction.East);
                    if (loc1.Col - loc2.Col <= Width / 2)
                        directions.Add(Direction.West);
                }

                return directions;
        }

 /// <summary>
 /// Gets the destination if an ant at <paramref name="location"/> goes in <paramref name="direction"/>, accounting for wrap around.
 /// </summary>
 /// <param name="location">The starting location.</param>
 /// <param name="direction">The direction to move.</param>
 /// <returns>The new location, accounting for wrap around.</returns>
 public Location GetDestination(Location location, Direction direction)
 {
     return location.Neighbors[(int)direction];
 }