Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

A* and IDA* searches to solve a Sliding-Block puzzle

By: a guest on Dec 6th, 2010  |  syntax: C++  |  size: 3.40 KB  |  views: 1,017  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. class Compare
  2. {
  3. public:
  4.  bool operator()(shared_ptr<Puzzle> puzzA, shared_ptr<Puzzle> puzzB)
  5.  {
  6.          if (Search::F(puzzA) > Search::F(puzzB))
  7.                 return true;
  8.         else
  9.                 return false;
  10.  
  11.  }
  12. };
  13.  
  14. shared_ptr<Puzzle> Search::AStar(shared_ptr<Puzzle> puzzle)
  15. {
  16.         //Phase IV: A* Graph Search.
  17.         shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
  18.         priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
  19.         set<string> closedlist;
  20.  
  21.         fringe.push(puzzle);
  22.         while (!fringe.empty())
  23.         {
  24.                 shared_ptr<Puzzle> current = fringe.top();
  25.                 fringe.pop();
  26.                 if (current->isSolved())
  27.                 {
  28.                         solution = current;
  29.                         break;
  30.                 }
  31.                 else
  32.                 {
  33.                         if (!closedlist.count(current->uniqueID())) //if not in closedlist
  34.                         {
  35.                                 closedlist.insert(current->uniqueID());
  36.                                 vector<shared_ptr<Puzzle> > successors = current->Successors();
  37.                                 vector<shared_ptr<Puzzle> >::iterator it;
  38.                                 for (it = successors.begin(); it != successors.end(); it++)
  39.                                 {
  40.                                         if (!closedlist.count((*it)->uniqueID()))
  41.                                         {
  42.                                                 if ((*it)->isSolved())
  43.                                                         return (*it);
  44.                                                 else
  45.                                                         fringe.push((*it)); //add successor if not in closedlist
  46.                                         }
  47.                                 }
  48.                         }
  49.                 }
  50.         }
  51.         return solution;
  52. }
  53.  
  54.  
  55. int Search::heuristic(shared_ptr<Puzzle> puzzle)
  56. {
  57.         //h(n); Manhattan distance heuristic.
  58.         int distance = 0;
  59.         int counter = 1;
  60.         for (int i = 1; i < puzzle->N+1; i++)
  61.         {
  62.                 for (int j = 1; j < puzzle->N+1; j++)
  63.                 {
  64.                         //For each block in order:
  65.                         //Look at its coordinates.
  66.                         //What's the difference along each axis to the correct place?
  67.                         int diffx = abs(i - puzzle->index[counter]->posX);
  68.                         int diffy = abs(j - puzzle->index[counter]->posY);
  69.                         int manhattan = diffx + diffy;
  70.                         distance += manhattan;
  71.                         counter++;
  72.                 }
  73.         }
  74.         return distance;
  75. }
  76.  
  77. int Search::pathCost(shared_ptr<Puzzle> puzzle)
  78. {
  79.         //g(n); Path cost function. Distance from initial to current state.
  80.         //We count the number of moves made so far.
  81.         return puzzle->moveQueue.size();
  82. }
  83.  
  84. int Search::F(shared_ptr<Puzzle> puzzle)
  85. {
  86.         //f(n) Total cost; used by A*.
  87.         //f(n) = g(n) + h(n)
  88.         return pathCost(puzzle) + heuristic(puzzle);
  89. }
  90.  
  91. shared_ptr<Puzzle> Search::IDAStar(shared_ptr<Puzzle> puzzle)
  92. {
  93.         //Phase IV Bonus: Iterative Deepening A* Graph Search.
  94.         shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
  95.         priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
  96.         set<string> closedlist;
  97.  
  98.         int Flimit = 0;
  99.         while (!solution)
  100.         {
  101.                 Flimit++;
  102.                 //cout << "Current F limit: " <<Flimit <<endl;
  103.                 closedlist.clear();
  104.                 while (!fringe.empty())
  105.                         fringe.pop(); //empty the fringe
  106.                 fringe.push(puzzle);
  107.                 while (!fringe.empty())
  108.                 {
  109.                         shared_ptr<Puzzle> current = fringe.top();
  110.                         fringe.pop();
  111.                         if (current->isSolved())
  112.                         {
  113.                                 solution = current;
  114.                                 break;
  115.                         }
  116.                         else
  117.                         {
  118.                                 if (!closedlist.count(current->uniqueID())) //if not in closedlist
  119.                                 {
  120.                                         closedlist.insert(current->uniqueID());
  121.                                         if (F(current) < Flimit) //if within F limit
  122.                                         {
  123.                                                 vector<shared_ptr<Puzzle> > successors = current->Successors();
  124.                                                 vector<shared_ptr<Puzzle> >::iterator it;
  125.                                                 for (it = successors.begin(); it != successors.end(); it++)
  126.                                                 {
  127.                                                         if (!closedlist.count((*it)->uniqueID()))
  128.                                                         {
  129.                                                                 if ((*it)->isSolved())
  130.                                                                         return (*it);
  131.                                                                 else
  132.                                                                         fringe.push((*it)); //add successor if not in closedlist
  133.                                                         }
  134.                                                 }
  135.                                         }
  136.                                 }
  137.                         }
  138.                 }
  139.         }
  140.         return solution;
  141. }