SPAR/AIModule/SparAIModule/PerceptualState/InfluenceMap/InfluenceMap.h

Go to the documentation of this file.

#pragma once
#include <functional>
#include <set>
#include <BWAPI.h>
#include <utility>
#include <queue>
#include <bitset>
#include <vector>
#include <boost/unordered_set.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/numeric/conversion/bounds.hpp>
#include "../../Utils/Logger.h"

template<class InfluenceType>
class InfluenceMap
{
public:
  InfluenceMap(size_t width, size_t height, BWAPI::Player* player
    )
    : m_map(NULL)
    , m_width(width)
    , m_height(height)
    , m_player(player)
  {
    m_map = new InfluenceType[m_width*m_height];
  }

  ~InfluenceMap()
  {
    delete[] m_map;
  }

  void update()
  {
    InfluenceType::update(*this);
  }

  void display() const
  {
    // FIXME
    assert(m_width  == BWAPI::Broodwar->mapWidth()
        && m_height == BWAPI::Broodwar->mapHeight());

    for (size_t y=0; y<m_height; ++y)
    {
      for (size_t x=0; x<m_width; ++x)
      {
        const InfluenceType& influence = getInfluence(x, y);
        influence.display(x*TILE_SIZE, y*TILE_SIZE, TILE_SIZE, TILE_SIZE, m_player);
      }
    }
  }

  bool isValid(int x, int y) const
  {
    return is_between<int,true>(0, m_width  - 1)(x)
        && is_between<int,true>(0, m_height - 1)(y);
  }

  const InfluenceType& getInfluence(int x, int y) const
  {
    return _getInfluence(x, y);
  }

  const InfluenceType& getInfluence(const BWAPI::Position& position) const
  {
    // FIXME
    assert(m_width  == BWAPI::Broodwar->mapWidth()
        && m_height == BWAPI::Broodwar->mapHeight());

    return _getInfluence(position.x() / TILE_SIZE, position.y() / TILE_SIZE);
  }

  void reset()
  {
    for(size_t i=0; i<m_width*m_height; ++i)
    {
      m_map[i].reset();
    }
  }

  void setInfluence(const BWAPI::Position& position, const InfluenceType& influence)
  {
    // FIXME
    assert(m_wdith  == BWAPI::Broodwar->mapWidth()
        && m_height == BWAPI::Broodwar->mapHeight());

    InfluenceType& inf = _getInfluence(position.x() / TILE_SIZE, position.y() / TILE_SIZE);
    inf = influence;
  }

  void setInfluence(int x, int y, const InfluenceType& influence)
  {
    InfluenceType& inf = _getInfluence(x, y);
    inf = influence;
  }

  template<class Functor>
  Functor for_each(Functor functor) const
  {
    for (size_t y=0; y<m_height; ++y)
      for (size_t x=0; x<m_width; ++x)
        functor(x, y, *this);

    return functor;
  }

  //template<class Evaluator>
  //std::pair<int,int> hill_climbing(int x, int y, Evaluator evaluator, int maxSearchDepth = boost::numeric::bounds<int>::highest())
  //{
  //  typedef std::pair<int,int> Pos;
  //  
  //  std::vector<Pos> succ;
  //  succ.reserve(4);
  //  while (maxSearchDepth-- > 0)
  //  {
  //    succ.clear();
  //    InfluenceMaps::detail::getAdjacentTiles(x, y, succ, *this, true);
  //    
  //    Evaluator::return_type minValue = evaluator(x, y, *this);
  //    std::vector<Pos>::const_iterator minPos = succ.end();
  //    
  //    for (std::vector<Pos>::const_iterator i=succ.begin(); i!=succ.end(); ++i)
  //    { 
  //      Evaluator::return_type value = evaluator(i->first, i->second, *this);
  //      if (value < minValue)
  //      {
  //        minValue = value;
  //        minPos = i;
  //      }
  //    }
  //
  //    if (minPos == succ.end())
  //    {
  //      //SPAR_LOG(LogTypes::PERCEPTUAL_STATE, "[HILL CLIMBING] Reached local minimum (%d,%d)", x, y);
  //      return std::make_pair(x, y);
  //    }
  //    else
  //    {
  //      x = minPos->first;
  //      y = minPos->second;
  //    }
  //  }
  //
  //  return std::make_pair(x, y);
  //}

  size_t getWidth()  const { return m_width;  }

  size_t getHeight() const { return m_height; }

  const BWAPI::Player* const getPlayer() const { return m_player; }

private:
  template<class U> InfluenceMap(const InfluenceMap<U>&);
  template<class U> InfluenceMap& operator=(const InfluenceMap<U>&);
  InfluenceMap(const InfluenceMap<InfluenceType>&);
  InfluenceMap& operator=(const InfluenceMap<InfluenceType>&);

  InfluenceType& _getInfluence(int x, int y) const
  {
    assert(isValid(x, y));

    return m_map[x + y*m_width];
  }

  typedef InfluenceType* matrix; // TODO replace by sparse matrix (SparseLib++?)
  matrix m_map;
  size_t m_width;
  size_t m_height;
  BWAPI::Player* m_player;
};

namespace InfluenceMaps
{
  /**********************************************************************************************/
  /*                                            ALL                                             */
  /**********************************************************************************************/
  namespace detail
  {
    typedef boost::tuples::null_type Nothing;

    struct FunctorAdapter
    {
      template<class Functor, class T0>
      typename Functor::return_type operator()(Functor functor, int x, int y, const boost::tuple<const InfluenceMap<T0>&>& maps) const
      {
        return functor(x, y, maps.get<0>());
      }

      template<class Functor, class T0, class T1>
      typename Functor::return_type operator()(Functor functor, int x, int y, const boost::tuple<const InfluenceMap<T0>&, const InfluenceMap<T1>&>& maps) const
      {
        return functor(x, y, maps.get<0>(), maps.get<1>());
      }

      template<class Functor, class T0, class T1, class T2>
      typename Functor::return_type operator()(Functor functor, int x, int y, const boost::tuple<const InfluenceMap<T0>&, const InfluenceMap<T1>&, const InfluenceMap<T2>&>& maps) const
      {
        return functor(x, y, maps.get<0>(), maps.get<1>(), maps.get<2>());
      }
    };
  };

  /**********************************************************************************************/
  /*                                    BREADTH FIRST SEARCH                                    */
  /**********************************************************************************************/
  namespace detail
  {
    template<class InfluenceType>
    void getAdjacentTiles(int x, int y, std::vector<std::pair<int,int>>& adj, const InfluenceMap<InfluenceType>& map, bool shuffle = false)
    {
      using ::std::make_pair;

      static const int vx[] = {0, 0, -1, 1};
      static const int vy[] = {-1, 1, 0, 0};

      for (int i=0; i<4; ++i)
      {
        if (map.isValid(x+vx[i], y+vy[i])) adj.push_back(make_pair(x+vx[i], y+vy[i]));
      }

      if (shuffle) std::random_shuffle(adj.begin(), adj.end());
    }

    struct VectorOpenList
    {
      VectorOpenList(size_t w, size_t h)
        : m_w(w), m_vector(w*h, false) {}

      bool contains(int x, int y) const
      {
        return m_vector[x + y*m_w];
      }

      void insert(int x, int y)
      {
        m_vector[x + y*m_w] = true;
      }

    private:
      size_t m_w;
      std::vector<bool> m_vector;
    };

    template<size_t N>
    struct BitSetOpenList
    {
      BitSetOpenList(size_t w, size_t h)
        : m_w(w)
      {
        assert(m_bitset.size() >= w*h);
      }

      bool contains(int x, int y) const
      {
        return m_bitset[x + y*m_w];
      }

      void insert(int x, int y)
      {
        m_bitset.set(x + y*m_w);
      }

    private:
      size_t m_w;
      std::bitset<N> m_bitset;
    };

    struct DynamicBitSetOpenList
    {
      DynamicBitSetOpenList(size_t w, size_t h)
        : m_w(w), m_bitset(w * h) {}

      bool contains(int x, int y) const
      {
        return m_bitset[x + y*m_w];
      }

      void insert(int x, int y)
      {
        m_bitset[x + y*m_w] = true;
      }

    private:
      size_t m_w;
      boost::dynamic_bitset<> m_bitset;
    };

    template<class SetType>
    struct SetOpenList
    {
      SetOpenList(size_t w, size_t h)
        : m_w(w) {}

      bool contains(int x, int y) const
      {
        return m_set.find(x + y*m_w) != m_set.end();
      }

      void insert(int x, int y)
      {
        m_set.insert(x + y*m_w);
      }

    private:
      size_t m_w;
      SetType m_set;
    };
    typedef SetOpenList<std::set<int>> StdSetOpenList;
    typedef SetOpenList<boost::unordered_set<int>> UnorderedSetOpenList;

    // Choose open list implementation type
//  typedef VectorOpenList          OpenListType;
    typedef BitSetOpenList<256*256> OpenListType;
//  typedef DynamicBitSetOpenList   OpenListType;
//  typedef StdSetOpenList          OpenListType;
//  typedef UnorderedSetOpenList    OpenListType;

    template<class GoalTest, class T0, class T1=Nothing, class T2=Nothing, class T3=Nothing>
    struct breadth_first_search
    {
      std::pair<int,int> operator()(
        int x,
        int y,
        GoalTest test,
        const boost::tuple<
          const InfluenceMap<typename T0>&,
          typename static_if_else<
            boost::is_same<typename T1,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T1>&>::type,
          typename static_if_else<
            boost::is_same<typename T2,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T2>&>::type,
          typename static_if_else<
            boost::is_same<typename T3,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T3>&>::type
        >& maps)
      {
        FunctorAdapter functor;

        using ::std::pair;
        using ::std::make_pair;

        const InfluenceMap<typename T0>& map0 = maps.get<0>();
        const size_t width  = map0.getWidth();
        const size_t height = map0.getHeight();

        ::std::queue<pair<int,int>> Q;
        OpenListType M(width, height);

        pair<int,int> p(x,y);
        Q.push(p);
        M.insert(x, y);
        
        unsigned long visited = 0L;

        std::vector<pair<int,int>> succ;
        succ.reserve(4);

        while(!Q.empty())
        {
          const pair<int,int> v = Q.front();
          int vx = v.first;
          int vy = v.second;
          Q.pop();

          ++visited;

          if (functor(test, vx, vy, maps))
          {
            x = vx;
            y = vy;
            break;
          }
          else
          {
            succ.clear();
            getAdjacentTiles(vx, vy, succ, map0); // TODO Replace with functor?
            for (std::vector<pair<int,int>>::const_iterator i=succ.begin(); i!=succ.end(); ++i)
            {
              if (!M.contains(i->first, i->second))
              {
                Q.push(*i);
                M.insert(i->first, i->second);
              }
            }
          }
        }

        //SPAR_LOG(LogTypes::PERCEPTUAL_STATE, "[BREADTH FIRST SEARCH] No goal state found! %ul nodes visited, %ul nodes in list", visited, M.size());
        return make_pair(x,y);
      }
    };
  };

  template<class GoalTest, class T0>
  std::pair<int,int> breadth_first_search(int x, int y, GoalTest test, const InfluenceMap<T0>& map)
  {
    return InfluenceMaps::detail::breadth_first_search<GoalTest,T0>()(
      x,
      y,
      test,
      boost::tuple<const InfluenceMap<T0>&>(map));
  }

  template<class GoalTest, class T0, class T1>
  std::pair<int,int> breadth_first_search(int x, int y, GoalTest test, const InfluenceMap<T0>& map0, const InfluenceMap<T1>& map1)
  {
    assert(map0.getWidth()  == map1.getWidth() &&
           map0.getHeight() == map1.getHeight());
    return InfluenceMaps::detail::breadth_first_search<GoalTest,T0,T1>()(
      x,
      y,
      test,
      boost::tuple<
        const InfluenceMap<T0>&,
        const InfluenceMap<T1>&>(map0, map1));
  }

  template<class GoalTest, class T0, class T1, class T2>
  std::pair<int,int> breadth_first_search(int x, int y, GoalTest test, const InfluenceMap<T0>& map0, const InfluenceMap<T1>& map1, const InfluenceMap<T2>& map2)
  {
    assert(map0.getWidth()  == map1.getWidth()  &&
           map1.getWidth()  == map2.getWidth()  &&
           map0.getHeight() == map1.getHeight() &&
           map1.getHeight() == map2.getHeight());
    return InfluenceMaps::detail::breadth_first_search<GoalTest,T0,T1>()(
      x,
      y,
      test,
      boost::tuple<
        const InfluenceMap<T0>&,
        const InfluenceMap<T1>&,
        const InfluenceMap<T2>&>(map0, map1, map2));
  }

  /**********************************************************************************************/
  /*                                      GRADIENT DESCENT                                      */
  /**********************************************************************************************/
  namespace detail
  {
    template<class Gradient, class StopCriterion, class T0, class T1=Nothing, class T2=Nothing, class T3=Nothing>
    struct gradient_descent
    {
      std::pair<int,int> operator()(
        int x,
        int y,
        Gradient gradient,
        StopCriterion stop,
        const boost::tuple<
          const InfluenceMap<typename T0>&,
          typename static_if_else<
            boost::is_same<typename T1,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T1>&>::type,
          typename static_if_else<
            boost::is_same<typename T2,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T2>&>::type,
          typename static_if_else<
            boost::is_same<typename T3,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T3>&>::type
        >& maps)
      {
        FunctorAdapter functor;

        while (true)
        {
          std::pair<float,float> grad = functor(gradient, x, y, maps);
          
          if (stop(grad)) break;

          // TODO Replace with a line search algorithm
          bool ok = false;
          for (float step = 1.f; step > 0.f; step -= 0.0625f)
          {
            int nx = x - static_cast<int>(step * grad.first);
            int ny = y - static_cast<int>(step * grad.second);

            if (maps.get<0>().isValid(nx, ny))
            {
              x = nx;
              y = ny;
              ok = true;
              break;
            }
          }

          if (!ok) break;
        }

        //SPAR_LOG(LogTypes::PERCEPTUAL_STATE, "[GRADIENT DESCENT] Reached local minimum (%d,%d)", x, y);
        return std::make_pair(x, y);
      }
    };
  };

  template<class Gradient, class StopCriterion, class T0>
  std::pair<int,int> gradient_descent(int x, int y, Gradient gradient, StopCriterion stop, const InfluenceMap<T0>& map0)
  {
    return InfluenceMaps::detail::gradient_descent<Gradient,StopCriterion,T0>()(x, y, gradient, stop, boost::tuple<const InfluenceMap<T0>&>(map0));
  }

  template<class Gradient, class StopCriterion, class T0, class T1>
  std::pair<int,int> gradient_descent(int x, int y, Gradient gradient, StopCriterion stop, const InfluenceMap<T0>& map0, const InfluenceMap<T1>& map1)
  {
    assert(map0.getWidth()  == map1.getWidth() &&
           map0.getHeight() == map1.getHeight());
    return InfluenceMaps::detail::gradient_descent<Gradient,StopCriterion,T0,T1>()(x, y, gradient, stop, boost::tuple<const InfluenceMap<T0>&, const InfluenceMap<T1>&>(map0, map1));
  }

  template<class Gradient, class StopCriterion, class T0, class T1, class T2>
  std::pair<int,int> gradient_descent(int x, int y, Gradient gradient, StopCriterion stop, const InfluenceMap<T0>& map0, const InfluenceMap<T1>& map1, const InfluenceMap<T2>& map2)
  {
    assert(map0.getWidth()  == map1.getWidth()  &&
           map1.getWidth()  == map2.getWidth()  &&
           map0.getHeight() == map1.getHeight() &&
           map1.getHeight() == map2.getHeight());
    return InfluenceMaps::detail::gradient_descent<Gradient,StopCriterion,T0,T1,T2>()(x, y, gradient, stop, boost::tuple<const InfluenceMap<T0>&, const InfluenceMap<T1>&, const InfluenceMap<T2>&>(map0, map1, map2));
  }
};