#include <owl\owlpch.h>
#include <owl\applicat.h>
#include <owl\framewin.h>
#include <owl\dc.h>
#include "oracle.h"
#include "cell.h"
#include "sqrmaze.h"
 
#ifndef TRUE
#define TRUE -1
#endif
#ifndef FALSE
#define FALSE 0
#endif
 
typedef cell *cell_ptr;
 
sqrmaze::sqrmaze(int row_count,int column_count,int thickness_of_wall,
 char *seed,TFrameWindow *win_ptr)
//      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 [4];
    int  mud_filled_room_found;
    struct
      {
         int row_num;
         int column_num;
      }  next;
    char wall [24] [4];
    char wall_to_check;
    char wall_num;
    char way_out;
 
    // Allocate a two dimensional array of rooms.
    window_ptr=win_ptr;
    num_rows=row_count;
    num_columns=column_count;
    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;
            window_ptr->MessageBox("Cannot allocate maze!",
             window_ptr->GetApplication()->GetName(),
             MB_OK | MB_ICONEXCLAMATION);
          }
      }
    if (memory_allocated)
      {
         wall_thickness=thickness_of_wall;
         // Set up the directions by which a room can be exited.
         delta[0].row_num=-1;    // north
         delta[0].column_num=0;
         delta[1].row_num=0;     // west
         delta[1].column_num=-1;
         delta[2].row_num=1;     // south
         delta[2].column_num=0;
         delta[3].row_num=0;     // east
         delta[3].column_num=1;
         int order_num=0;
         // Set up the 4! orders in which the wall of a room can be accessed.
         for (int wall_num_1=0; wall_num_1 < 4; wall_num_1++)
           for (int wall_num_2=0; wall_num_2 < 4; wall_num_2++)
             if (wall_num_2 != wall_num_1)
               for (int wall_num_3=0; wall_num_3 < 4; 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 < 4; wall_num_4++)
                     if ((wall_num_4 != wall_num_3)
                     &&  (wall_num_4 != wall_num_2)
                     &&  (wall_num_4 != wall_num_1))
                       {
                         wall[order_num][wall_num_4]='\0';
                         wall[order_num][wall_num_3]='\1';
                         wall[order_num][wall_num_2]='\2';
                         wall[order_num][wall_num_1]='\3';
                         order_num++;
                       }
         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.row_num=row_selector->random_number();
              first.column_num=column_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());
              // 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 < '\4')
                          {
                             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.row_num=current.row_num
                                   +delta[wall_to_check].row_num;
                                  if ((next.row_num >= 0)
                                  &&  (next.row_num < num_rows))
                                    {
                                      next.column_num=current.column_num
                                       +delta[wall_to_check].column_num;
                                      if ((next.column_num >= 0)
                                      &&  (next.column_num < num_columns))
                                        {
                                           if (room[next.row_num][
                                            next.column_num].mark() 
                                            == 'M')
                                             mud_filled_room_found=TRUE;
                                        }
                                    }
                               }
                          }
                     }
                   while ((wall_num < '\4')
                   &&     (! 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+2)%4);
                        // 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))
                        // not in starting room
                          {
                             // Go back to the room from which you entered
                             // the current room.
                             next.row_num=current.row_num+delta[
                              room[current.row_num][
                              current.column_num].way_back()].row_num;
                             next.column_num=current.column_num+delta[
                              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 < '\4'));
              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(2);

         delete column_selector;
         delete row_selector;
         delete order_selector;
      }
  }
 
sqrmaze::~sqrmaze()
  {
    if (memory_allocated)
      {
        // Free the two dimensional array of rooms.
        for (int row_num=0; row_num < num_rows; row_num++)
          delete [] room[row_num];
        delete [] room;
      }
  }
 
int sqrmaze::maze_okay()
  {
    int  adjacency;
    struct
      {
         int row_num;
         int column_num;
      }  delta [4];
    struct
      {
         int row_num;
         int column_num;
      }  next;
    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.
    delta[0].row_num=-1;    // north
    delta[0].column_num=0;
    delta[1].row_num=0;     // west
    delta[1].column_num=-1;
    delta[2].row_num=1;     // south
    delta[2].column_num=0;
    delta[3].row_num=0;     // east
    delta[3].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=FALSE;
        do
          {
            wall_to_check
             =room[current.row_num][current.column_num].next_wall_num();
            if (wall_to_check < '\4')
              {
                 if (! (room[current.row_num][
                  current.column_num].wall_up(wall_to_check)))
                   {
                      next.row_num=current.row_num
                       +delta[wall_to_check].row_num;
                      if ((next.row_num >= 0)
                      &&  (next.row_num < num_rows))
                        {
                          next.column_num=current.column_num
                           +delta[wall_to_check].column_num;
                          if ((next.column_num >= 0)
                          &&  (next.column_num < num_columns))
                            {
                               if (room[next.row_num][
                                next.column_num].mark() 
                                == ' ')
                                 passage_found=TRUE;
                            }
                        }
                   }
              }
          }
        while ((! passage_found) && (wall_to_check < '\4'));
        if (passage_found)
        // passage to room not currently part of proposed solution found
          {
            // Enter the room.
            current.row_num=next.row_num;
            current.column_num=next.column_num; 
            // Record the way back to the previous room.
            way_out=char(((int) wall_to_check+2)%4);
            room[current.row_num][current.column_num].set_way_out(way_out);
            // Mark the room as part of the proposed solution.
            room[current.row_num][current.column_num].mark_floor('S');
            num_rooms_in_solution++;
            // Prepare to consider all the walls of the room.
            room[current.row_num][current.column_num].zero_wall_to_check();
          }
        else
        // dead end
          {
            // Mark current room as not part of proposed solution.
            room[current.row_num][current.column_num].mark_floor(' ');
            num_rooms_in_solution--;
            // Go back to the room from which this room was entered.
            next.row_num=current.row_num+delta[
             room[current.row_num][current.column_num].way_back()].row_num;
            next.column_num=current.column_num+delta[
             room[current.row_num][current.column_num].way_back()].column_num;
            current.row_num=next.row_num;
            current.column_num=next.column_num;
          }
      }
    while((current.row_num != num_rows-1)
    ||    (current.column_num != num_columns-1));

    // Now that the maze is solved, calculate the number of rooms in the
    // solution (or outside the maze) that are adjacent to the rooms in
    // the solution.
    adjacency=0;
    previous.row_num=-1;
    previous.column_num=0;
    current.row_num=0;
    current.column_num=0;
    do
      {
        for (wall_to_check='\0'; wall_to_check < '\4'; wall_to_check++)
          if (room[current.row_num][current.column_num].wall_up(wall_to_check))
            {
               next.row_num=current.row_num+delta[wall_to_check].row_num;
               if ((next.row_num >= 0)
               &&  (next.row_num < num_rows))
                 {
                    next.column_num=current.column_num
                     +delta[wall_to_check].column_num;
                    if ((next.column_num >= 0)
                    &&  (next.column_num < num_columns))
                      {
                         if (room[next.row_num][next.column_num].mark() == 'S')
                           adjacency++;
                      }
                    else
                      adjacency++;
                 }
               else
                 adjacency++;
            }
          else
            {
               next.row_num=current.row_num+delta[wall_to_check].row_num;
               if ((next.row_num >= 0)
               &&  (next.row_num < num_rows))
                 {
                   next.column_num=current.column_num
                    +delta[wall_to_check].column_num;
                   if ((next.column_num >= 0)
                   &&  (next.column_num < num_columns))
                     {
                        if ((room[next.row_num][next.column_num].mark() == 'S')
                        &&  ((previous.row_num != next.row_num)
                          || (previous.column_num != next.column_num)))
                          {
                            saved.row_num=next.row_num;
                            saved.column_num=next.column_num;
                          }
                     }
                 }
            }
        previous.row_num=current.row_num;
        previous.column_num=current.column_num;
        current.row_num=saved.row_num;
        current.column_num=saved.column_num;
      }
    while((current.row_num != num_rows-1)
    ||    (current.column_num != num_columns-1));
    for (wall_to_check='\0'; wall_to_check < '\4'; wall_to_check++)
      if (room[current.row_num][current.column_num].wall_up(wall_to_check))
        {
           next.row_num=current.row_num+delta[wall_to_check].row_num;
           if ((next.row_num >= 0)
           &&  (next.row_num < num_rows))
             {
                next.column_num=current.column_num
                 +delta[wall_to_check].column_num;
                if ((next.column_num >= 0)
                &&  (next.column_num < num_columns))
                  {
                     if (room[next.row_num][next.column_num].mark() == 'S')
                       adjacency++;
                  }
                else
                  adjacency++;
             }
           else
             adjacency++;
        }

    // The maze is hard to solve (from the outside) if more than a third of its
    // rooms are part of its solution and rooms not part of its solution tend to
    // be next to rooms in its solution.
    if ((3*num_rooms_in_solution >= num_rows*num_columns)
    &&  (9*adjacency <= 8*num_rooms_in_solution))
      result=TRUE;
    else
      result=FALSE;
    return result;
  }
 
int sqrmaze::external_to_maze(double x,double y)
//      Return TRUE if and only if a point (x,y) is external to the maze.
  {
    int result;
 
    if (y < 0.0)
      result=TRUE;
    else
      if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
        result=TRUE;
      else
        if (x < 0.0)
          result=TRUE;
        else
          if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
            result=TRUE;
          else
            result=FALSE;
    return result;
  }
 
double sqrmaze::f(double x,double y)
//      Return 6.0*wall_thickness if a point (x,y) is on a wall, 0.0 otherwise.
  {
    double z;
 
    if (y < 0.0)
      z=0.0;
    else
      if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
        z=0.0;
      else
        if (x < 0.0)
          z=0.0;
        else
          if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
            z=0.0;
          else
            {  
              int tem_int=int(y);
              int column_num=tem_int/(3*wall_thickness);
              int y_mod_3_wall_thickness=tem_int-3*wall_thickness*column_num;
              tem_int=int(x);
              int row_num=tem_int/(3*wall_thickness);
              int x_mod_3_wall_thickness=tem_int-3*wall_thickness*row_num;
              if (row_num < num_rows)
                if (column_num < num_columns)
                  if (x_mod_3_wall_thickness < wall_thickness)
                    if (y_mod_3_wall_thickness < wall_thickness)
                    // northwest corner
                      z=1.0;
                    else
                    // north wall
                      if (room[row_num][column_num].wall_up('\0'))
                        z=1.0;
                      else
                        z=0.0;
                  else
                    if (y_mod_3_wall_thickness < wall_thickness)
                    // west wall
                      if (room[row_num][column_num].wall_up('\1'))
                        z=1.0;
                      else
                        z=0.0;
                    else
                    // in room
                      z=0.0;
                else
                  // east most wall
                  z=1.0;
              else
                // south most wall
                if (column_num < num_columns)
                  if (y_mod_3_wall_thickness < wall_thickness)
                    // southwest corner
                    z=1.0;
                  else
                    // south wall
                    if (room[num_rows-1][column_num].wall_up('\2'))
                      z=1.0;
                    else
                      z=0.0;
                else
                  // southeast most corner
                  z=1.0;
            }
    return z*double(6*wall_thickness);
  }
 
int sqrmaze::part_of_solution(double x,double y)
//      Return TRUE if and only if a point (x,y) is on a wall outlining the
// solution to the maze.
  {
    int result;
 
    if (y < 0.0)
      result=FALSE;
    else
      if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
        result=FALSE;
      else
        if (x < 0.0)
          result=FALSE;
        else
          if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
            result=FALSE;
          else
            {  
              int tem_int=int(y);
              int column_num=tem_int/(3*wall_thickness);
              int y_mod_3_wall_thickness=tem_int-3*wall_thickness*column_num;
              tem_int=int(x);
              int row_num=tem_int/(3*wall_thickness);
              int x_mod_3_wall_thickness=tem_int-3*wall_thickness*row_num;
              if (row_num < num_rows)
                if (column_num < num_columns)
                  if (x_mod_3_wall_thickness < wall_thickness)
                    if (y_mod_3_wall_thickness < wall_thickness)
                      // northwest corner
                      if ((room[row_num][column_num].mark() == 'S')
                      ||  ((row_num > 0) 
                        && (room[row_num-1][column_num].mark() == 'S'))
                      ||  ((column_num > 0)
                        && (room[row_num][column_num-1].mark() == 'S'))
                      ||  ((row_num > 0) && (column_num > 0)
                        && (room[row_num-1][column_num-1].mark() == 'S')))
                        result=TRUE;
                      else
                        result=FALSE;
                    else
                      // north wall
                      if (room[row_num][column_num].wall_up('\0'))
                        if ((room[row_num][column_num].mark() == 'S')
                        ||  ((row_num > 0)
                          && (room[row_num-1][column_num].mark() == 'S')))
                          result=TRUE;
                        else
                          result=FALSE;
                      else
                        result=FALSE;
                  else
                    if (y_mod_3_wall_thickness < wall_thickness)
                    // west wall
                      if (room[row_num][column_num].wall_up('\1'))
                        if ((room[row_num][column_num].mark() == 'S')
                        ||  ((column_num > 0)
                          && (room[row_num][column_num-1].mark() == 'S')))
                          result=TRUE;
                        else
                          result=FALSE;
                      else
                        result=FALSE;
                    else
                    // in room
                      result=FALSE;
                else
                  // east most wall
                  if (x_mod_3_wall_thickness < wall_thickness)
                    // northeast corner
                    if ((room[row_num][num_columns-1].mark() == 'S')
                    ||  ((row_num > 0)
                      && (room[row_num-1][num_columns-1].mark() == 'S')))
                      result=TRUE;
                    else
                      result=FALSE;
                  else
                    // east wall
                    if (room[row_num][num_columns-1].mark() == 'S')
                      result=TRUE;
                    else
                      result=FALSE;
              else
                // south most wall
                if (column_num < num_columns)
                  if (y_mod_3_wall_thickness < wall_thickness)
                    // southwest corner
                    if ((room[num_rows-1][column_num].mark() == 'S')
                    ||  ((column_num > 0)
                      && (room[num_rows-1][column_num-1].mark() == 'S')))
                      result=TRUE;
                    else
                      result=FALSE;
                  else
                    // south wall
                    if (room[num_rows-1][column_num].wall_up('\2'))
                      if (room[num_rows-1][column_num].mark() == 'S')
                        result=TRUE;
                      else
                        result=FALSE;
                    else
                      result=FALSE;
                else
                  // southeast most corner
                  if (room[num_rows-1][num_columns-1].mark() == 'S')
                    result=TRUE;
                  else
                    result=FALSE;
            }
    return result;
  }