title: Issue Implementing A* in C++ with Priority Queues
body: <p>I'm currently working on a homework assignment to implement A* for the sliding brick puzzle. I have previously implemented BFS and DFS for this puzzle, but an now having problems. I attempted to write my A* code by adapting the BFS code I already had working using a priority queue and Manhattan distance as the heuristic. In order to have the program open the node with the lowest f value (g+h), I had to override the operator for the priority queue, as it contains a defined structure. When I compile the code, no errors arise, but when I run it the program just crashed. My guess is that it is getting stuck in a loop somewhere. Maybe I implemented the operator override incorrectly. Can anyone help me figure out what is going wrong? I have pasted my code below. </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;vector&gt;
  #include &lt;iostream&gt;
  #include &lt;fstream&gt;
  #include &lt;string&gt;
  #include &lt;cstring&gt;
  #include &lt;list&gt;
  #include &lt;queue&gt;
  #include &lt;set&gt;
  #include &lt;stack&gt;
  #include &lt;map&gt;
  #include &lt;time.h&gt;
  
  using namespace std;
  
  struct move //creates structure for a move containing a pice number and direction to move
  {
      int piece;
      char direction;
  };
  
  struct parentmove
  {
      vector&lt; vector&lt;int&gt; &gt; par;
      move mo;
  };
  
  struct position
  {
      int row;
      int column;
  };
  
  struct node
  {
      vector&lt; vector&lt;int&gt; &gt; par;
      vector&lt; vector&lt;int&gt; &gt; state;
      position pos;
      int g;
      int h;
      int f;
  };
  
  bool operator&lt;(const node&amp; a, const node&amp; b)
  {
      return a.f &gt; b.f;
  }
  
  void SBP::Astar(vector &lt;vector&lt;int&gt; &gt; st)
  {
      position goalpos = getposition(st, -1);
      node stnode;
      stnode.state = st;
      stnode.g = 0;
      position stpos = getposition(st, 2);
      stnode.h = abs(goalpos.row - stpos.row) + abs(goalpos.column - stpos.column);
      stnode.f = stnode.g + stnode.h;
      stnode.pos = stpos;
      list&lt;move&gt; allm;
      priority_queue&lt; node &gt; unexplored, explored;
      set&lt; vector &lt;vector&lt;int&gt; &gt; &gt; closedset; //contains explored states in a set, 
      map &lt; vector &lt;vector&lt;int&gt; &gt;, parentmove &gt; pathdict;
      allm = (*this).allmoves(st);
      list&lt;move&gt;::iterator it = allm.begin();
      for (int i = 0; i &lt; allm.size(); i++)
      {
          move m;
          m.piece = (*it).piece;
          m.direction = (*it).direction;
          vector&lt; vector&lt;int&gt; &gt; newst = (*this).applyMove(st, m);
          newst = (*this).normalization(newst);
          node newnode;
          newnode.par = st;
          newnode.state = newst;
          newnode.g = 1;
          position newpos = getposition(newst, 2);
          newnode.h = abs(goalpos.row - newpos.row) + abs(goalpos.column - newpos.column);
          newnode.f = newnode.h + newnode.g;
          newnode.pos = newpos;
          unexplored.push(newnode);
  
          parentmove pm = { st,m };
          pathdict[newst] = pm;
          ++it;
      }
      explored.push(stnode);
      closedset.insert(st);
      while (!unexplored.empty())
      {
          node currentnode = unexplored.top();
          vector&lt; vector&lt;int&gt; &gt; currentst = currentnode.state;
          unexplored.pop();
          bool iscomplete = (*this).complete(currentst);
          if (iscomplete)
          {
              explored.push(currentnode);
              closedset.insert(currentst);
              list&lt;move&gt; path = (*this).constructpath(currentst, pathdict, st);
              (*this).display(currentst);
              printf("A* explored %i nodes\n", explored.size());
              printf("The length of the path solution is %i moves\n", path.size());
              return;
          }
          else
          {
              set&lt; vector&lt; vector&lt;int&gt; &gt; &gt;::iterator ite = closedset.find(currentst);
              if (ite == closedset.end()) //does not already exist in queue
              {
                  list&lt;move&gt; possm;
                  possm = (*this).allmoves(currentst);
                  list&lt;move&gt;::iterator iter = possm.begin();
                  for (int j = 0; j &lt; possm.size(); j++)
                  {
                      move m;
                      m.piece = (*iter).piece;
                      m.direction = (*iter).direction;
                      vector&lt; vector&lt;int&gt; &gt; newst = (*this).applyMove(currentst, m);
                      vector&lt; vector&lt;int&gt; &gt; normst = (*this).normalization(newst);;
                      node normnode;
                      normnode.state = normst;
                      normnode.par = currentst;
                      normnode.g = currentnode.g + 1;
                      position p = getposition(normst, 2);
                      normnode.h = abs(goalpos.row - p.row) + abs(goalpos.column - p.column);
                      normnode.f = normnode.g + normnode.h;
                      normnode.pos = p;
                      unexplored.push(normnode);
                      if (pathdict.find(normst) == pathdict.end())
                      {
                          parentmove pm = { currentst,m };
                          pathdict[normst] = pm;
                      }
                      ++iter;
                  }
                  explored.push(currentnode);
                  closedset.insert(currentst);
              }
          }
      }
  
      return;
  }
  </code></pre>