#include <stdlib.h>
#include <iostream.h>
#include "oracle.h"
#include "cell.h"
#include "titillat.h"
#include "hexmaze.h"
 
#define TRUE -1
#define FALSE 0
 
typedef cell *cell_ptr;
typedef char *char_ptr;
 
maze::maze(int row_count,int column_count,int thickness_of_wall,char *seed)
//      Contruct a maze having "row_count" rows and "column_count" columns of
// rooms.  The walls should be "thickness_of_wall" (bricks) thick.  A different
// (8 character of less) "seed" generally yields a different maze.
  {
    struct
      {
         int row_num;
         int column_num;
      }  delta [2] [6];
    int  mud_filled_room_found;
    struct
      {
         int row_num;
         int column_num;
      }  next;
    char wall [720] [6];
    char wall_to_check;
    char wall_num;
    char way_out;
    int  x1;
    int  x2;
    int  y1;
    int  y2;
 
    wall_thickness=thickness_of_wall;
    num_rows=row_count;
    num_y_dots=wall_thickness*(4*num_rows+1);
    y_dot_max=num_y_dots-1;
    num_columns=column_count;
    max_x=8*(num_columns/2)+6;
    num_x_dots=wall_thickness*(max_x+1);
    x_dot_max=num_x_dots-1;
    // Allocate a two dimensional array of rooms.
    if (memory_allocated=((room=new cell_ptr[num_rows]) != NULL))
      {
              int row_num=0;
        while (memory_allocated && (row_num < num_rows))
          if (memory_allocated=((room[row_num]=new cell [num_columns]) != NULL))
            row_num++;
        if (! memory_allocated)
          {
            while (row_num)
              delete [] room[--row_num];
            delete [] room;
            cerr << "Fatal error:  cannot allocate maze.\n";
          }
      }
    if (memory_allocated)
      {
         // Allocate a two dimensional array for plotting the maze in
         // terms of "bricks" where a wall is "wall_thickness" bricks
         // thick.
         if (memory_allocated=((page=new char_ptr [num_y_dots]) != NULL))
           {
             int y_dot_num=0;
             while (memory_allocated && (y_dot_num < num_y_dots))
               if (memory_allocated=((page[y_dot_num]=new char [num_x_dots])
                != NULL))
                 y_dot_num++;
             if (! memory_allocated)
               {
                  while (y_dot_num)
                    delete [] page[--y_dot_num];
                  delete [] page;
                  for (int row_num=num_rows-1; row_num >= 0; row_num--)
                    delete [] room[row_num];
                  delete [] room;
                  cerr << "Fatal error:  cannot allocate maze.\n";
               }
           }
         else
           {
              for (int row_num=num_rows-1; row_num >= 0; row_num--)
                delete [] room[row_num];
              delete [] room;
              cerr << "Fatal error:  cannot allocate maze.\n";
           }
      }
    if (memory_allocated)
      {
         // Set up the directions by which a room can be exited.
         // Directions for even columns.
         delta[0][0].row_num=-1;    // north
         delta[0][0].column_num=0;
         delta[0][1].row_num=-1;    // northwest
         delta[0][1].column_num=-1;
         delta[0][2].row_num=0;     // southwest
         delta[0][2].column_num=-1;
         delta[0][3].row_num=1;     // south
         delta[0][3].column_num=0;
         delta[0][4].row_num=0;     // southeast
         delta[0][4].column_num=1;
         delta[0][5].row_num=-1;    // northeast
         delta[0][5].column_num=1;
         // Directions for odd columns.
         delta[1][0].row_num=-1;    // north
         delta[1][0].column_num=0;
         delta[1][1].row_num=0;     // northwest
         delta[1][1].column_num=-1;
         delta[1][2].row_num=1;     // southwest
         delta[1][2].column_num=-1;
         delta[1][3].row_num=1;     // south
         delta[1][3].column_num=0;
         delta[1][4].row_num=1;     // southeast
         delta[1][4].column_num=1;
         delta[1][5].row_num=0;     // northeast
         delta[1][5].column_num=1;
         // Set up the 6! orders in which the wall of a room can be accessed.
         int order_num=0;
         for (int wall_num_1=0; wall_num_1 < 6; wall_num_1++)
           for (int wall_num_2=0; wall_num_2 < 6; wall_num_2++)
             if (wall_num_2 != wall_num_1)
               for (int wall_num_3=0; wall_num_3 < 6; wall_num_3++)
                 if ((wall_num_3 != wall_num_2)
                 &&  (wall_num_3 != wall_num_1))
                   for (int wall_num_4=0; wall_num_4 < 6; wall_num_4++)
                     if ((wall_num_4 != wall_num_3)
                     &&  (wall_num_4 != wall_num_2)
                     &&  (wall_num_4 != wall_num_1))
                       for (int wall_num_5=0; wall_num_5 < 6; wall_num_5++)
                         if ((wall_num_5 != wall_num_4)
                         &&  (wall_num_5 != wall_num_3)
                         &&  (wall_num_5 != wall_num_2)
                         &&  (wall_num_5 != wall_num_1))
                           for (int wall_num_6=0; wall_num_6 < 6; wall_num_6++)
                             if ((wall_num_6 != wall_num_5)
                             &&  (wall_num_6 != wall_num_4)
                             &&  (wall_num_6 != wall_num_3)
                             &&  (wall_num_6 != wall_num_2)
                             &&  (wall_num_6 != wall_num_1))
                               {
                                 wall[order_num][wall_num_6]='\0';
                                 wall[order_num][wall_num_5]='\1';
                                 wall[order_num][wall_num_4]='\2';
                                 wall[order_num][wall_num_3]='\3';
                                 wall[order_num][wall_num_2]='\4';
                                 wall[order_num][wall_num_1]='\5';
                                 order_num++;
                               }
         titillator_ptr=new titillator;
         order_selector=new oracle(&seed[0],order_num);
         row_selector=new oracle(&seed[0],num_rows);
         column_selector=new oracle(&seed[0],num_columns);
         int finished=FALSE;
         // Generate mazes until you have one that is hard to solve.
         do
           {
              // Pick a starting room.
              first.column_num=column_selector->random_number();
              if ((first.column_num)%2)
                do
                  {
                    first.row_num=row_selector->random_number();
                  }
                while (first.row_num == (num_rows-1));
              else
                first.row_num=row_selector->random_number();
              current.row_num=first.row_num;
              current.column_num=first.column_num;
              // Excavate the starting room.
              room[current.row_num][current.column_num].mark_floor(' ');
              // Pick the order in which the walls of the starting room will be
              // considered.
              room[current.row_num][current.column_num].set_order(
               order_selector->random_number());
              titillator_ptr->titillate();
              // Excavate rooms until there are no more to excavate.
              do
                {
                   mud_filled_room_found=FALSE;
                   // Find an adjacent room (not yet considered) that needs
                   // excavating.
                   do
                     {
                        wall_num=room[current.row_num][
                         current.column_num].next_wall_num();
                        if (wall_num < '\6')
                          {
                             wall_to_check=wall[room[current.row_num][
                              current.column_num].order_to_check()][wall_num];
                             if (room[current.row_num][
                              current.column_num].wall_up(wall_to_check))
                               {
                                  next.column_num=current.column_num
                                   +delta[(current.column_num)%2]
                                   [wall_to_check].column_num;
                                  if ((next.column_num >= 0)
                                  &&  (next.column_num < num_columns))
                                    {
                                      next.row_num=current.row_num
                                       +delta[(current.column_num)%2]
                                       [wall_to_check].row_num;
                                      if ((next.row_num >= 0)
                                      &&  ((((next.column_num)%2 == 1)
                                         && (next.row_num < (num_rows-1)))
                                       ||  (((next.column_num)%2 == 0)
                                         && (next.row_num < num_rows))))
                                        {
                                           if (room[next.row_num][
                                            next.column_num].mark()
                                            == 'M')
                                             mud_filled_room_found=TRUE;
                                        }
                                    }
                               }
                          }
                     }
                   while ((wall_num < '\6')
                   &&     (! mud_filled_room_found));
                   if (mud_filled_room_found)
                   // an adjacent room needs excavating
                     {
                        // Exit the current room, knocking down a wall.
                        room[current.row_num][
                         current.column_num].knock_down_wall(wall_to_check);
                        way_out=char(((int) wall_to_check+3)%6);
                        // Enter the adjacent room, knocking down a wall.
                        room[next.row_num][next.column_num].knock_down_wall(
                         way_out);
                        // Record how to return to the previous room.
                        room[next.row_num][next.column_num].set_way_out(
                         way_out);
                        current.row_num=next.row_num;
                        current.column_num=next.column_num;
                        // Excavate the room.
                        room[current.row_num][current.column_num].mark_floor(
                         ' ');
                        // Select the order in which the walls of the room will
                        // be considered.
                        room[current.row_num][current.column_num].set_order(
                         order_selector->random_number());
                     }
                   else
                   // no adjacent room needs excavating
                     {
                        if ((first.row_num != current.row_num)
                        ||  (first.column_num != current.column_num))
                          {
                             // Go back to the room from which you entered
                             // the current room.
                             next.row_num=current.row_num+delta[
                              (current.column_num)%2]
                              [room[current.row_num]
                              [current.column_num].way_back()].row_num;
                             next.column_num=current.column_num+delta[
                              (current.column_num)%2]
                              [room[current.row_num]
                              [current.column_num].way_back()].column_num;
                             current.row_num=next.row_num;
                             current.column_num=next.column_num;
                          }
                     }
                }
              while ((first.row_num != current.row_num)
              ||     (first.column_num != current.column_num)
              ||     (wall_num < '\6'));
              if (maze_okay()) // Maze is hard to solve.
                finished=TRUE;
              else             // Prepare to try another maze.
                for (int row_num=0; row_num < num_rows; row_num++)
                  for (int column_num=0; column_num < num_columns; column_num++)
                    room[row_num][column_num].reinitialize();
           }
         while (! finished);
         // Knock down walls blocking the entrance and exit to the maze.
         room[0][0].knock_down_wall(0);
         room[num_rows-1][num_columns-1].knock_down_wall(3);

         delete column_selector;
         delete row_selector;
         delete order_selector;

         // Generate a 2D plot of the maze.  Each element of "page" corresponds
         // to a possible position of a brick composing the maze.  An element
         // has value 'W' if a brick is present and value ' ' otherwise.  Each
         // wall is "wall_thickness" bricks thick.
         for (y1=0; y1 < num_y_dots; y1++)
           for (x1=0; x1 < num_x_dots; x1++)
             page[y1][x1]=' ';
         for (int row_num=0; row_num < num_rows; row_num++)
           {
             int half_column_num=0;
             for (int column_num=0; column_num < num_columns; column_num+=2)
               {
                 if (room[row_num][column_num].wall_up('\0'))
                   {
                      x1=8*half_column_num+2;
                      y1=4*row_num;
                      x2=x1+2;
                      y2=y1;
                      draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                       wall_thickness*x2,wall_thickness*y2);
                      //    ***
                      //   O   O
                      //  O     OOO
                      //   O   O
                      //    OOO
                   }
                 half_column_num++;
               }
             half_column_num=0;
             for (column_num=0; column_num < num_columns; column_num+=2)
               {
                 if (room[row_num][column_num].wall_up('\1'))
                   {
                      x1=8*half_column_num;
                      y1=4*row_num+2;
                      x2=x1+2;
                      y2=y1-2;
                      draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                       wall_thickness*x2,wall_thickness*y2);
                      //    *OO
                      //   *   O
                      //  *     OOO
                      //   O   O
                      //    OOO
                   }
                 if (room[row_num][column_num].wall_up('\5'))
                   {
                      x1=8*half_column_num+4;
                      y1=4*row_num;
                      x2=x1+2;
                      y2=y1+2;
                      draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                       wall_thickness*x2,wall_thickness*y2);
                      //    OO*
                      //   O   *
                      //  O     *OO
                      //   O   O
                      //    OOO
                   }
                 half_column_num++;
               }
             half_column_num=0;
             for (column_num=0; column_num < (num_columns-1); column_num+=2)
               {
                  if (row_num != (num_rows-1))
                    {
                      if (room[row_num][column_num+1].wall_up('\0'))
                        {
                           x1=8*half_column_num+6;
                           y1=4*row_num+2;
                           x2=x1+2;
                           y2=y1;
                           draw_line_on_page(wall_thickness*x1,
                            wall_thickness*y1,wall_thickness*x2,
                            wall_thickness*y2);
                           //    OOO
                           //   O   O
                           //  O     ***
                           //   O   O
                           //    OOO
                        }
                    }
                 half_column_num++;
               }
             half_column_num=0;
             for (column_num=0; column_num < num_columns; column_num+=2)
               {
                 if (room[row_num][column_num].wall_up('\2'))
                   {
                      x1=8*half_column_num;
                      y1=4*row_num+2;
                      x2=x1+2;
                      y2=y1+2;
                      draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                       wall_thickness*x2,wall_thickness*y2);
                      //    OOO
                      //   O   O
                      //  *     OOO
                      //   *   O
                      //    *OO
                   }
                 if (room[row_num][column_num].wall_up('\4'))
                   {
                      x1=8*half_column_num+4;
                      y1=4*row_num+4;
                      x2=x1+2;
                      y2=y1-2;
                      draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                       wall_thickness*x2,wall_thickness*y2);
                      //    OOO
                      //   O   O
                      //  O     *OO
                      //   O   *
                      //    OO*
                   }
                 half_column_num++;
               }
           }
         int half_column_num=0;
         for (int column_num=0; column_num < num_columns; column_num+=2)
           {
              if (room[num_rows-1][column_num].wall_up('\3'))
                {
                   x1=8*half_column_num+2;
                   y1=4*(num_rows-1)+4;
                   x2=x1+2;
                   y2=y1;
                   draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                    wall_thickness*x2,wall_thickness*y2);
                   //    OOO
                   //   O   O
                   //  O     OOO
                   //   O   O
                   //    ***
                }
              if (column_num+1 < num_columns)
                {
                   if (room[num_rows-2][column_num+1].wall_up('\3'))
                     {
                        x1=8*half_column_num+6;
                        y1=4*(num_rows-1)+2;
                        x2=x1+2;
                        y2=y1;
                        draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
                         wall_thickness*x2,wall_thickness*y2);
                        //    OOO
                        //   O   O
                        //  O     ***
                        //   O   O
                        //    OOO
                     }
                }
             half_column_num++;
           }
         delete titillator_ptr;
      }
  }
 
maze::~maze()
  {
    if (memory_allocated)
      {
        // Free dynamically allocated memory.
        for (int y_dot_num=num_y_dots-1; y_dot_num >= 0; y_dot_num--)
          delete [] page[y_dot_num];
        delete [] page;
        for (int row_num=num_rows-1; row_num >= 0; row_num--)
          delete [] room[row_num];
        delete [] room;
      }
  }
 
void maze::draw_line_on_page(
  int  x1,
  int  y1,
  int  x2,
  int  y2)
//      Draw wall (of bricks) on "page".
    {
      int error;
      int error_prime_x;
      int error_prime_y;
      int permissible_delta_x;
      int permissible_delta_y;
      int x;
      int x_diff;
      int y;
      int y_diff;
 
      error=0;
      if (x2 >= x1)
        permissible_delta_x=1;
      else
        permissible_delta_x=-1;
      if (y2 >= y1)
        permissible_delta_y=1;
      else
        permissible_delta_y=-1;
      x=x1;
      y=y1;
      x_diff=x2-x1;
      y_diff=y2-y1;
      set_point_on_page(x,y);
      while ((x != x2) || (y != y2))
        {
          error_prime_x=error+permissible_delta_x*y_diff;
          error_prime_y=error-permissible_delta_y*x_diff;
          if (abs(error_prime_x) <= abs(error_prime_y))
            {
              x+=permissible_delta_x;
              error=error_prime_x;
            }
          else
            {
              y+=permissible_delta_y;
              error=error_prime_y;
            }
          set_point_on_page(x,y);
        }
      return;
    }
 
int maze::maze_okay()
  {
    int  adjacency;
    struct
      {
         int row_num;
         int column_num;
      }  delta [2] [6];
    struct
      {
         int row_num;
         int column_num;
      }  next;
    int  num_rooms_in_maze;
    int  num_rooms_in_solution;
    int  passage_found;
    struct
      {
         int row_num;
         int column_num;
      }  previous;
    int  result;
    struct
      {
         int row_num;
         int column_num;
      }  saved;
    char wall_to_check;
    char way_out;
 
    // Set up the directions by which a room can be exited.
    // Even columns.
    delta[0][0].row_num=-1;    // north
    delta[0][0].column_num=0;
    delta[0][1].row_num=-1;    // northwest
    delta[0][1].column_num=-1;
    delta[0][2].row_num=0;     // southwest
    delta[0][2].column_num=-1;
    delta[0][3].row_num=1;     // south
    delta[0][3].column_num=0;
    delta[0][4].row_num=0;     // southeast
    delta[0][4].column_num=1;
    delta[0][5].row_num=-1;    // northeast
    delta[0][5].column_num=1;
    // Odd columns.
    delta[1][0].row_num=-1;    // north
    delta[1][0].column_num=0;
    delta[1][1].row_num=0;     // northwest
    delta[1][1].column_num=-1;
    delta[1][2].row_num=1;     // southwest
    delta[1][2].column_num=-1;
    delta[1][3].row_num=1;     // south
    delta[1][3].column_num=0;
    delta[1][4].row_num=1;     // southeast
    delta[1][4].column_num=1;
    delta[1][5].row_num=0;     // northeast
    delta[1][5].column_num=1;
    // Solve the maze.

    // Start at the entrance.
    current.row_num=0;
    current.column_num=0;
    // Mark the room as part of the solution.
    room[current.row_num][current.column_num].mark_floor('S');
    num_rooms_in_solution=1;
    // Prepare to consider all the walls of the room.
    room[current.row_num][current.column_num].zero_wall_to_check();
    // Try rooms until you get to the exit.
    do
      {
        // Find a passage (not yet considered) out of the current room leading
        // to a room not part of the proposed solution.
        passage_found=