/**
 * Generates a random level using a series of connected rooms.
 * @author Martin Wells
 */

public class LevelGenerator
{
   private static final int LEFT_DIR = 0;
   private static final int RIGHT_DIR = 1;
   private static final int UP_DIR = 2;
   private static final int DOWN_DIR = 3;

   private int width;
   private int height;
   private byte[][] tileMap;
   private int[] roomX;
   private int[] roomY;
   private int[] roomW;
   private int[] roomH;

   private int roomCount;
   private int playerStartX, playerStartY;

   public LevelGenerator()
   {
   }

   private void clear()
   {
      for (int ty = 0; ty < height; ty++)
         for (int tx = 0; tx < width; tx++)
            tileMap[ty][tx] = World.NO_TILE;
   }

   public int getPlayerStartX()
   {
      return playerStartX;
   }

   public int getPlayerStartY()
   {
      return playerStartY;
   }

   /**
    * Generates a new level using a room corridor system. The density of the
    * level is dictated by the level integer.
    * @param level A relative level on density for the level (the higher the
    * number the denser the level.
    * @return A new byte array containing the tiles for the newly generated
    * level.
    */
   public byte[][] generateLevel(int level)
   {
      // Set the size of the level relative to the level number provided.
      width = 30 + (level * 2);
      height = 30 + (level * 2);
      // Cap the level to a reasonable maximum.
      if (width > 100) width = 100;
      if (height > 100) height = 100;

      // Construct a new tile map based on this size and clear it.
      tileMap = new byte[height][width];
      clear();

      // The minRooms is used later to determine when to stop generating new
      // rooms. It's more of a target than an exact number though.
      int totalRooms = 10 + (level * 2);

      System.out.println("Generating level: " + level + " minRooms: " +
                         totalRooms + " width: " + width + " height: " + height);

      // To track all the rooms created in a level we use an array for each
      // room's x, y tile position, the width and height as well as whether the
      // room was a corridor joining two others. This is mostly used by code
      // to determine if there is enough space to place a new room.
      roomX = new int[totalRooms];
      roomY = new int[totalRooms];
      roomW = new int[totalRooms];
      roomH = new int[totalRooms];

      // The minimum size of each room.
      int minRoomHeight = 6;
      int minRoomWidth = 6;
      int maxRoomHeight = 10;
      int maxRoomWidth = 10;

      // Pick the size and location of the first room.
      int corner = Tools.getRand(0, 3);
      int roomStartX = 3;
      int roomStartY = 3;

      switch (corner)
      {
         // case 0 is top left (3,3) (which is already initialised)
         case 1: // top right
            roomStartX = width - maxRoomWidth;
            roomStartY = 3;
            break;
         case 2: // bottom right
            roomStartX = width - maxRoomWidth;
            roomStartY = height - maxRoomHeight;
            break;
         case 3: // bottom left
            roomStartX = 3;
            roomStartY = height - maxRoomHeight;
            break;
      }

      // Add the first room to the map.
      addRoom(level, roomStartX, roomStartY,
              Tools.getRand(minRoomWidth, maxRoomWidth),
              Tools.getRand(minRoomHeight, maxRoomHeight));

      // Set the location where the player's ship will start from.
      playerStartX = roomX[0] + (roomW[0] / 2);
      playerStartY = roomY[0] + (roomH[0] / 2);

      // The addRoom method will fill a room with other objects (such as enemy
      // fighter). This code clears anything that was added to near the player's
      // start point.
      for (int ty = 0; ty < 3; ty++)
         for (int tx = 0; tx < 3; tx++)
            tileMap[playerStartY - 1 + ty][playerStartX - 1 + tx] =
                    World.NO_TILE;

      // Each room added is spaced relative to the previous one so this is
      // an index to keep track of the last full room created (not the last
      // corridor connecting two rooms).
      int lastRoomIndex = 0;

      // Since the code randomly tries different rooms there are cases where
      // a new room is not valid (too big etc). In this case the code will
      // loop around for another go. In order to stop the generation process
      // going for too long the 'tries' counter stops execution after a
      // reasonable number of tries have been executed.
      int tries = 0;

      // Used inside the loop when creating new rooms.
      int newRoomX = 0;
      int newRoomY = 0;

      // Keep tracking of the number of rooms added to the map. Once the room
      // qouta has been reached the level is complete.
      roomCount = 1;

      // As rooms are added they may not fit. If not we try again using a
      // different (random) direction. This array is used to track what
      // directons have previously been tried.
      boolean[] dirsTried = new boolean[4];

      while (roomCount < totalRooms - 1 && tries < 100)
      {
         tries++;

         // Grab the info on the last room created.
         int lastRoomX = roomX[lastRoomIndex];
         int lastRoomY = roomY[lastRoomIndex];
         int lastRoomW = roomW[lastRoomIndex];
         int lastRoomH = roomH[lastRoomIndex];

         // Pick a random size for the new room.
         int newRoomW = Tools.getRand(minRoomWidth, maxRoomWidth);
         int newRoomH = Tools.getRand(minRoomHeight, maxRoomHeight);

         // If the all the previous directions have been tried we reset them
         // and start again.
         if (areAllTrue(dirsTried))
         {
            // reset the tried dirs to have another go
            for (int i = 0; i < 4; i++)
               dirsTried[i] = false;
         }

         // Pick a random dir from the ones that have not previously been tried.
         int dir = getRandDir(dirsTried);

         // Mark this direction as tried.
         dirsTried[dir] = true;

         // Figure the corridor dimensions to connect up this new room.
         int corridorWidth = Tools.getRand(4, 10);
         int corridorHeight = Tools.getRand(4, minRoomHeight - 2);
         if (dir == UP_DIR || dir == DOWN_DIR)
         {
            corridorWidth = Tools.getRand(4, minRoomWidth - 2);
            corridorHeight = Tools.getRand(4, 10);
         }

         // Positioning of the new room. Location is based on the direction
         // picked (randomly from a list of ones previously tried) plus distance
         // for a coridor to connect it up.

         // If the room is to the left or right.
         if (dir == LEFT_DIR || dir == RIGHT_DIR)
         {
            // First choose a new x position (it's relatively fixed based on the
            // position of the previous room and the width of the corridor
            // (already chosen above).
            if (dir == LEFT_DIR)  // to the left
               newRoomX = lastRoomX - newRoomW - corridorWidth + 2;
            if (dir == RIGHT_DIR) // to the right
               newRoomX = lastRoomX + lastRoomW + corridorWidth - 2;

            // Next determine the vertical position of the new room. This code
            // ensures enough space is left availble to fit in the corridor
            // (positioned on the left or right).
            int lowPoint = Math.max(1, lastRoomY + corridorHeight - newRoomH);
            int highPoint = lastRoomY + lastRoomH - corridorHeight;
            newRoomY = Tools.getRand(lowPoint, highPoint);
         }

         // If the room is above or below.
         if (dir == UP_DIR || dir == DOWN_DIR)
         {
            // First choose a new y position (it's relatively fixed based on the
            // position of the previous room and the height of the corridor
            // (already chosen above).
            if (dir == UP_DIR)
               newRoomY = lastRoomY - corridorHeight - newRoomH + 2;
            if (dir == DOWN_DIR)
               newRoomY = lastRoomY + lastRoomH + corridorHeight - 2;

            // Next determine the horizontal position of the new room. This code
            // ensures enough space is left availble to fit in the corridor
            // (positioned on the above or below).
            int lowPoint = Math.max(1, lastRoomX + corridorWidth - newRoomW);
            int highPoint = lastRoomX + lastRoomW - corridorWidth;
            newRoomX = Tools.getRand(lowPoint, highPoint);
         }

         // Check to see if this new room is within the dimensions of the map.
         if (Tools.isRectWithinRect(0, 0, width - 1, height - 1,
                                    newRoomX, newRoomY, newRoomW, newRoomH))
         {
            // Check the room is not too close (or overlapping) another room.
            if (!isRectNearRoom(newRoomX, newRoomY, newRoomW, newRoomH))
            {
               // Clear to add this room to the map.
               addRoom(level, newRoomX, newRoomY, newRoomW, newRoomH);

               // Add the corridor connecting the new room to the last one.
               int corridorX = 0;
               int corridorY = 0;

               // Connect a new room either to the left or right.
               if (dir == LEFT_DIR || dir == RIGHT_DIR)
               {
                  if (dir == LEFT_DIR)
                     corridorX = lastRoomX - corridorWidth + 1;
                  if (dir == RIGHT_DIR)
                     corridorX = lastRoomX + lastRoomW - 1;

                  corridorY = Tools.getRand(Math.max(lastRoomY, newRoomY),
                                            Math.min(lastRoomY + lastRoomH -
                                                     corridorHeight,
                                                     newRoomY + newRoomH -
                                                     corridorHeight));
               }

               // Connect a new room either above or below.
               if (dir == UP_DIR || dir == DOWN_DIR)