breadthfirstsearch.h

struct Point {
  int x;
  int y;
  char s;
  bool blocks;
  color_t color;
  bool operator==(const Point& other) const {
    return x == other.x && y == other.y;
  }
  bool operator!=(const Point& other) const {
    return x != other.x || y != other.y;
  }
  bool operator<(const Point& other) const {
    return x < other.x || y < other.y;
  }
  Point operator=(Point other) {
      x = other.x;
      y = other.y;
      s = other.s;
      return other;
  }

  Point operator+(Point other) {
    x += other.x;
    y += other.y;
    return Point({x,y,'F'});
  }
};

struct mappingPoint {
  int x, y;
 bool operator==(const Point& other) const {
    return x == other.x && y == other.y;
  }
  bool operator!=(const Point& other) const {
    return x != other.x || y != other.y;
  }
  bool operator<(const Point& other) const {
    return x < other.x || y < other.y;
  }  
 
  bool operator==(const mappingPoint& other) const {
    return x == other.x && y == other.y;
  }
  bool operator!=(const mappingPoint& other) const {
    return x != other.x || y != other.y;
  }
  bool operator<(const mappingPoint& other) const {
    return x < other.x || y < other.y;
  }  
};


class bFirst {
public:
 World* map;
 std::array<Point,4> cdir;
 std::queue<Point> que;
 std::vector<Point> addNeighbors(Point&);
 std::map<mappingPoint, Point> camefrom;
 void bFS(ent* g, Point* playerPos);
 bool inBounds(Point&);
 bool canGo(Point&);
 double long getDistance(Point A, Point B);
 bFirst(World* map);
};


bFirst::bFirst(World* Map)
{ 
  this->map = Map;
  Point N({0,-1,'^'});Point S({0,1,'v'});
  Point E({1,0,'>'});Point W({-1,0,'<'});
  cdir[0] = N; cdir[1] = S; cdir[2]=E; cdir[3]=W; 
}

bool bFirst::canGo(Point& p)
{
  if (this->map->layout[p.x][p.y].blocks == true)
  {
    return false;
  } else {
    return true;
  }
}

bool bFirst::inBounds(Point& p)
{
  return 0 <= p.x && p.x < map->mapW
       && 0 <= p.y && p.y < map->mapH;
}

std::vector<Point> bFirst::addNeighbors(Point& p)
{
   std::vector<Point> results;
   for (auto dir : cdir)
   {
     Point next({p.x + dir.x, p.y + dir.y, dir.s});
     if (inBounds(next) && canGo(next)) {
       results.push_back(next);
     }
   }
   return results;
}

void bFirst::bFS(ent* g, Point* playerPos)
{
 Point start;  //first point 
 Point current; //point being evaluated
 Point next;    //next point to be evaluated
 Point headed; //the point chosen
 mappingPoint m_start;     //because of variable changes, 
 mappingPoint m_current;   //i use a second structure that
 mappingPoint m_next;     // which holds just x/y
 mappingPoint m_headed;   //otherwise the number of nodes in que skyrockets.
  
 start = g->pos; //goblins position is starting point
 que.push(start);//add start to que
 m_start.x = start.x; m_start.y = start.y;
 camefrom[m_start] = start; //add start to visited, 
 while (!que.empty()) //while there is still nodes to examine....
 {
    current = que.front(); //examine first node on que.
    que.pop();             //remove current node from queue
    m_current.x = current.x; m_current.y = current.y;
    for (auto next : addNeighbors(current))  //check all of currents adjacent nodes
    {
      m_next.x = next.x; m_next.y = next.y;
      if (camefrom.find(m_next) == camefrom.end()) //if the neighbor has not been evaluated yet, 
      {
        camefrom[m_current] = next;
        que.push(next);
      }
   }  
   map->layout[current.x][current.y].s = current.s; //Sets the tiles symbol to the direction of the direction 
   drawAll(map);                                    //in relation to target node. It's fun to watch =P
}
}