home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / DEMOS / DEMO4.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-12  |  4.4 KB  |  253 lines
  1. #include "demo4.h"
  2.  
  3. PUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *target)
  4.     :BEST_(start, target, 4)
  5. {
  6.     goal = target;
  7. }
  8.  
  9.  
  10.  
  11. PNODE_::PNODE_(const char *b, int empty_x, int empty_y)
  12. {
  13.     char
  14.         *p = *board;
  15.     int
  16.         i;
  17.  
  18.     for (i = 0; i <= 8; i++)
  19.         *(p + i) = *(b + i);
  20.  
  21.     x = empty_x;
  22.     y = empty_y;
  23. }
  24.  
  25.  
  26.  
  27. PNODE_::PNODE_(const char *b, int old_x, int old_y, int new_x, int new_y)
  28. {
  29.     char
  30.         *p = *board;
  31.     int
  32.         i;
  33.  
  34.     for (i = 0; i <= 8; i++)
  35.         *(p + i) = *(b + i);
  36.  
  37.     board[old_x][old_y] = board[new_x][new_y];
  38.     board[new_x][new_y] = 0;
  39.  
  40.     x = new_x;
  41.     y = new_y;
  42. }
  43.  
  44.  
  45.  
  46. void PNODE_::display() const
  47. {
  48.     int
  49.         row,
  50.         col;
  51.  
  52.     for (row = 0; row < 3; row++)
  53.     {
  54.         for (col = 0; col < 3; col++)
  55.             printf("%d ", board[row][col]);
  56.         putchar('\n');
  57.     }
  58.     putchar('\n');
  59. }
  60.  
  61.  
  62.  
  63. int PNODE_::equal(const VOBJECT_ &other) const
  64. {
  65.      if (x != ((const PNODE_ &)other).get_x()
  66.           && y != ((const PNODE_ &)other).get_y())
  67.             return(0);
  68.     return(compare_board(((const PNODE_ &)other).get_board()));
  69. }
  70.  
  71.  
  72.  
  73. const char (*PNODE_::get_board() const)[3]
  74. {
  75.     return(board);
  76. }
  77.  
  78.  
  79.  
  80. int PNODE_::get_x() const
  81. {
  82.     return(x);
  83. }
  84.  
  85.  
  86.  
  87. int PNODE_::get_y() const
  88. {
  89.     return(y);
  90. }
  91.  
  92.  
  93.  
  94. int PNODE_::compare_board(const char bo[3][3]) const
  95. {
  96.     const char
  97.         *p = *board,
  98.         *b = *bo;
  99.  
  100.     int
  101.         i;
  102.  
  103.     for (i = 0; i <= 8; i++)
  104.         if (*(p + i) != *(b + i))
  105.             return(0);
  106.  
  107.     return(1);
  108. }
  109.  
  110.  
  111.  
  112. NODE_ *PNODE_::do_operator(int index) const
  113. {
  114.     switch(index)
  115.     {
  116.         case 0:
  117.             return(do_left());
  118.         case 1:
  119.             return(do_right());
  120.         case 2:
  121.             return(do_up());
  122.     }
  123.     return(do_down());
  124. }
  125.  
  126.  
  127.  
  128. PNODE_ *PNODE_::do_left() const
  129. {
  130.     if (!y)
  131.         return(NULL);
  132.  
  133.     return(new PNODE_(*board, x, y, x, y - 1));
  134. }
  135.  
  136.  
  137.  
  138. PNODE_ *PNODE_::do_right() const
  139. {
  140.     if (y == (2))
  141.         return(NULL);
  142.  
  143.     return(new PNODE_(*board, x, y, x, y + 1));
  144. }
  145.  
  146.  
  147.  
  148. PNODE_ *PNODE_::do_down() const
  149. {
  150.     if (x == (2))
  151.         return(NULL);
  152.  
  153.     return(new PNODE_(*board, x, y, x + 1, y));
  154. }
  155.  
  156.  
  157.  
  158. PNODE_ *PNODE_::do_up() const
  159. {
  160.     if (!x)
  161.         return(NULL);
  162.  
  163.     return(new PNODE_(*board, x, y, x - 1, y));
  164. }
  165.  
  166.  
  167. /*                  COMPUT_G
  168.  
  169.     In this problem all arc costs are 1, so we don't have to do any
  170.     computation in this function.
  171.  
  172. */
  173.  
  174. int PUZZLE_::compute_g(const NODE_ &)
  175. {
  176.     return(1);
  177. }
  178.  
  179.  
  180.  
  181. /*                     COMPUT_H
  182.  
  183.     This function returns the heuristic value associated with each
  184.     node, by calling totdist(). 
  185.  
  186. */
  187.  
  188. int PUZZLE_::compute_h(const NODE_ &node)
  189. {
  190.     return(totdist(((PNODE_ &)node).get_board(), goal->get_board()));
  191. }
  192.  
  193.  
  194.  
  195. /*                  TOTDIST
  196.  
  197.     Computes the total or Manhatten distance of the tiles in the 
  198.     current configuration from their 'home squares' (= the ordering
  199.     of the tiles in the goal configuration). The Manhatten between
  200.     two squares S1 and S2 is the distance between S1 and S2 in the
  201.     horizontal direction plus the distance between S1 and S2 in the
  202.     vertical direction.
  203.  
  204. */
  205.  
  206. int PUZZLE_::totdist(const char now[3][3], const char target[3][3])
  207. {
  208.     int nrow, ncol,
  209.         trow, tcol,
  210.         found, tot = 0;
  211.  
  212.     for (nrow = 0; nrow < 3; nrow++)
  213.         for (ncol = 0; ncol < 3; ncol++)
  214.         {
  215.             found = 0;
  216.             if (now[nrow][ncol] == 0)       // skip empty tile!
  217.                 continue;
  218.             for (trow = 0; trow < 3 && !found; trow++)
  219.                 for (tcol = 0; tcol < 3 && !found; tcol++)
  220.                     if (now[nrow][ncol] == target[trow][tcol])
  221.                     {
  222.                         tot += abs(ncol - tcol) + abs(nrow - trow);
  223.                         found = 1;
  224.                     }
  225.         }
  226.     return(tot);
  227. }
  228.  
  229.  
  230.  
  231. int main()
  232. {
  233.     char
  234.         start[3][3] = {
  235.                         {2, 1, 6},
  236.                         {4, 0, 8},
  237.                         {7, 5, 3},
  238.                       };
  239.  
  240.     char
  241.         goal[3][3] = {
  242.                         {1, 2, 3},
  243.                         {8, 0, 4},
  244.                         {7, 6, 5},
  245.                     };
  246.  
  247.     PUZZLE_
  248.         puzzle(new PNODE_(*start, 1, 1), new PNODE_(*goal, 1, 1));
  249.  
  250.     puzzle.generate();
  251.     return(1);
  252. }
  253.