-- ***********************************************************************
-- *                                                                     *
-- *    MAZE.E                                The Happy Hippy (C) 1998   *
-- *                                                                     *
-- ***********************************************************************

constant VERSION = 1.00 -- DO NOT CHANGE THIS VALUE OR CODE WON'T RUN !

-- ***********************************************************************
-- *                                                                     *
-- *    Description : A Euphoria Pixel Bot Maze Generator                *
-- *    Version     : 1.00 - 20th November 1998                          *
-- *                                                                     *
-- *    Filename    : maze.e                                             *
-- *    Source Code : Euphoria 2.00                                      *
-- *                                                                     *
-- *    Author      : The Happy Hippy                                    *
-- *    Copyright   : The Happy Hippy (C) 1998                           *
-- *    Contact     : hippy@psynet.net                                   *
-- *                                                                     *
-- *    Licence     : You are granted the free right to use the code     *
-- *                  within this file as the basis of a maze generator  *
-- *                  that you are designing providing that you do not   *
-- *                  use the code exactly as it is without including    *
-- *                  all comments in their original format.             *
-- *                                                                     *
-- *                  You may modify this code and comments as you wish  *
-- *                  and may use it as the basis of any maze generator  *
-- *                  that you develop free of charge and royalties.     *
-- *                                                                     *
-- *    Trademarks  : See http://www.psynet.net/hippy/pixelbot.htm for   *
-- *                  details of Copyright and Trademark assignments.    *
-- *                                                                     *
-- *    Y2K Issues  : This code does not use dates for any purpose and   *
-- *                  is therefore, by default, millennium compliant.    *
-- *                                                                     *
-- *    For further information about the Euphoria Pixel Bot project     *
-- *    please look at http://www.psynet.net/hippy/pixelbot.htm          *
-- *                                                                     *
-- *    For further information about the Euphoria language please look  *
-- *    at http://members.aol.com/FilesEu                                *
-- *                                                                     *
-- ***********************************************************************

-- ***********************************************************************
-- *                                                                     *
-- *    KNOWN BUGS                                                       *
-- *                                                                     *
-- *    None                                                             *
-- *                                                                     *
-- ***********************************************************************

-- ***********************************************************************
-- *                                                                     *
-- *    RELEASE HISTORY                                                  *
-- *                                                                     *
-- *    1.00    20 Nov 1998     First public release.                    *
-- *                                                                     *
-- ***********************************************************************

-- ***********************************************************************
-- *                                                                     *
-- *
-- *                                                                     *
-- ***********************************************************************

    constant NN = 1             -- North wall
    constant EE = 2             -- East wall
    constant SS = 4             -- South wall
    constant WW = 8             -- West wall

    constant ROWS    = 12
    constant COLUMNS = 16

-- ***********************************************************************
-- *                                                                     *
-- *
-- *                                                                     *
-- ***********************************************************************

    sequence maze
    sequence done

    integer density

-- ***********************************************************************
-- *                                                                     *
-- *
-- *                                                                     *
-- ***********************************************************************

    procedure move_to(integer r,integer c,integer w)

       if r>=1 and r<=ROWS and c>=1 and c<=COLUMNS then
         maze[r][c]=and_bits( maze[r][c], not_bits(w) )
         if not done[r][c] then
           done[r][c]=TRUE
           if Percent(50) then
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(NN) )
               move_to(r-1,c,SS)
             end if
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(EE) )
               move_to(r,c+1,WW)
             end if
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(SS) )
               move_to(r+1,c,NN)
             end if
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(WW) )
               move_to(r,c-1,EE)
             end if
           else
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(WW) )
               move_to(r,c-1,EE)
             end if
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(NN) )
               move_to(r-1,c,SS)
             end if
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(EE) )
               move_to(r,c+1,WW)
             end if
             if Percent(density) then
               maze[r][c]=and_bits( maze[r][c], not_bits(SS) )
               move_to(r+1,c,NN)
             end if
           end if
         end if
       end if
    end procedure

-- ***********************************************************************
-- *                                                                     *
-- *
-- *                                                                     *
-- ***********************************************************************

-- We need a forward reference because flood_it() calls flood()
-- to continue flooding the maze which also calls flood_it() to
-- complete its work.

    integer flood_id

-- if there isn't a wall in the way of the direction that we are
-- trying to flood; we continue by flooding that square.

-- If there is a wall in the way then, if that square hasn't been
-- flooded or marked for flooding already we must kick down the
-- wall so that flooding can continue.

-- We mark the square for flooding but don't flood it immediately
-- because that would mean that we go off on a different flooding
-- tack that could try and flood the flooding track that we had
-- already started.

    procedure try_flood(integer w,integer r,integer c,integer nr,integer nc)
     if and_bits( maze[r][c] , w ) = 0 then
       call_proc(flood_id, { nr,nc } )
     else
       if done[nr][nc] = 0 then
         maze[r][c] = and_bits( maze[r][c] , not_bits(w) )
         if    w = NN then maze[nr][nc] = and_bits( maze[nr][nc] , not_bits(SS) )
         elsif w = EE then maze[nr][nc] = and_bits( maze[nr][nc] , not_bits(WW) )
         elsif w = SS then maze[nr][nc] = and_bits( maze[nr][nc] , not_bits(NN) )
         elsif w = WW then maze[nr][nc] = and_bits( maze[nr][nc] , not_bits(EE) )
         end if
         done[nr][nc] = 1
       end if
     end if
    end procedure

-- If we haven't already flooded this square we flood it and then
-- flood the squares in other directions ( if there isn't a wall
-- in the way ! ).

-- We choose one of two sub-flooding schemes so we don't always
-- kick down walls to enable flooding to continue in the same
-- direction every time.

    procedure flood(integer r,integer c)
     if done[r][c] >=0 then
       done[r][c] = -1
       if Percent(50) then
         if c-1 >= 1       then try_flood(WW,r,c,r,c-1) end if  -- w
         if r+1 <= ROWS    then try_flood(SS,r,c,r+1,c) end if  -- s
         if c+1 <= COLUMNS then try_flood(EE,r,c,r,c+1) end if  -- e
         if r-1 >= 1       then try_flood(NN,r,c,r-1,c) end if  -- n
       else
         if r-1 >= 1       then try_flood(NN,r,c,r-1,c) end if  -- n
         if c+1 <= COLUMNS then try_flood(EE,r,c,r,c+1) end if  -- e
         if r+1 <= ROWS    then try_flood(SS,r,c,r+1,c) end if  -- s
         if c-1 >= 1       then try_flood(WW,r,c,r,c-1) end if  -- w
       end if
     end if
    end procedure

    flood_id = routine_id("flood")

-- ***********************************************************************
-- *                                                                     *
-- *
-- *                                                                     *
-- ***********************************************************************

    global function Create_A_Maze(integer adensity)

      density = 100 - adensity

      -- Create a maze where each square has all four walls.

      maze = repeat(repeat(NN+EE+SS+WW,COLUMNS),ROWS)

      -- Rip through the maze creating random trails by knocking down
      -- various walls.

      done = repeat(repeat(FALSE,COLUMNS),ROWS)
      for r = 1 to ROWS do
        for c = 1 to COLUMNS do
          move_to(r,c,0)
        end for
      end for

      -- Patch up all the boundary squares so there are always walls at
      -- the top to the north, at the bottom to the south, on the left
      -- to the west and on the right to the east.

      for r=1 to ROWS do
        maze[r][1]       = or_bits(maze[r][1]       , WW )
        maze[r][COLUMNS] = or_bits(maze[r][COLUMNS] , EE )
      end for
      for c=1 to COLUMNS do
        maze[1][c]    = or_bits(maze[1][c]    , NN )
        maze[ROWS][c] = or_bits(maze[ROWS][c] , SS )
      end for

      -- Flood through the maze trails and knock down any walls needed to
      -- break through into other unvisited trails.

      done = repeat(repeat(FALSE,COLUMNS),ROWS)
      for r = 1 to ROWS do
        for c = 1 to COLUMNS do
          flood(r,c)
        end for
      end for

      done = {}     -- Garbage collect the, now redundant, 'done' array.

      return maze   -- Return the generated maze to the caller

    end function

-- ***********************************************************************
-- *                                                                     *
-- *
-- *                                                                     *
-- ***********************************************************************