JESSICA BARON

    /**
     * A brute force approach to placing Rooms within the given Graph.  Uses overlaps() method to
     *      avoid overlapping Rooms (whereas the BSP approach avoids overlapping through binary space partitioning).
     * @param aGraph A Graph to place Room objects within.
     * @param maxPercentOfRooms An integer defining how much percent of the Graph the Rooms within it should occupy.
     *         (This number should be lower with using drunkard's walk for corridors than with random point connect for corridors.)
     * @return An updated Graph with Rooms drawn.
     */
    public static Graph randomRoomPlacement(Graph aGraph, int maxPercentOfRooms)
    {
        Random randomGen = new Random();
        Graph graph = aGraph;
        int totalOnArea = 0;
        int graphW = graph.getWidth();
        int graphH = graph.getHeight();
        int graphArea = graph.getArea();
        int maxPercent = maxPercentOfRooms;        // 40% as a MAX cutoff when doing random point connections later (rooms will usually make up less than this amount).
        double onPercent = 0.0;                    //          Drunkard's takes a 20% max room percentage.  FINAL ratio of on-off Vertexs should be around 40-60.
        ArrayList<Room> roomList = new ArrayList<Room>();
        int cnt = 0;

        while ((onPercent < maxPercent) && (cnt < 100))
        {
            int[] wh = generateRandomRoomSize(graphW, graphH);
            int w = wh[0];
            int h = wh[1];
    
        // Generate random starting coords;
            int x = randomGen.nextInt(graphW);
            int y = randomGen.nextInt(graphH);
            Room aRoom = new Room(x,y,w,h);
            
            int count = 0;
            while (count < 100)
            { // Generate new random starting coords and check overlaps again
                x = randomGen.nextInt(graphW);
                y = randomGen.nextInt(graphH);
                aRoom = new Room(x,y,w,h);
                
                if (!overlaps(aRoom, graph))
                { break; }
                else
                { count ++; }
            }
            
            if (count < 100)            // If exited from previous loop due to determining no overlaps
            { 
                graph.updateRoomList(aRoom);        // ISSUE: This used to cause overlapping as more dungeons are generated because the roomlist was static.
                //roomList.add(aRoom);
                graph = drawRoom(aRoom, graph);
                totalOnArea += w * h;
                double onFloat = totalOnArea * 1.0;
                onPercent = (onFloat / graphArea)*100;
                cnt = 0;                // Reset outer loop counter that keeps track of unsuccessful placements.
            }
            else
            { cnt ++; }                    // Counter for outer loop to keep track of unsuccessful placement.
        }
        //graph.setRoomList(roomList);        // Instead of using Graph.updateRoomList() one room at a time. Works the same now that Graph.roomlist is not static.
        
        return graph;
    }

    
    /**
     * Places Rooms in a Graph by using a Binary Space Partitioning tree (BSPTree) to
     *   split a Graph into subgraphs as BSPLeafs and fit Rooms into those Leaf objects.
     *   This approach handles overlapping prevention within the BSPTree.
     * @param aGraph A Graph to place Room objects within.
     * @return An updated Graph with Rooms drawn.
     */
    public static Graph BSP(Graph aGraph, int minLeafWModifier, int minLeafHModifier)
    {
        Graph graph = aGraph;
        Random randGen = new Random();
        int[] maxesAndMins = generateMinAndMaxRoomSizes(graph.getWidth(), graph.getHeight());
        int maxWidth = maxesAndMins[1];
        int maxHeight = maxesAndMins[3];
        ArrayList<Room> roomList = new ArrayList<Room>();
        BSPTree tree = new BSPTree(graph, maxWidth, maxHeight, minLeafWModifier, minLeafHModifier);
    // ^ BSPTree constructor handles splitting automatically.
        
        ArrayList<BSPLeaf> children = tree.getBottomChildrenList();
        for (BSPLeaf child : children)
        {
            int[] randomSize = generateRandomRoomSize(graph.getWidth(), graph.getHeight());
            int randX = randGen.nextInt(child.getWidth()-randomSize[0])+1;
            int randY = randGen.nextInt(child.getHeight()-randomSize[1])+1;
        // Random x and y coords according to whatever is left over in Leaf w and h, after Room width and height.
            Room randomRoom = new Room(child.getX()+randX, child.getY()+randY, randomSize[0], randomSize[1]);
            roomList.add(randomRoom);
            child.setRoom(randomRoom);
        }
        tree.clearLeafLists();
        tree.getLeafLists(tree.getRoot());        // Re-evaluate children and parents lists since Rooms are now added.
        
        for (Room room : roomList)
        { graph = drawRoom(room, graph); }
        
        graph.setTree(tree);
        graph.setRoomList(roomList);
        return graph;
    }
    
    

    /**
     * Brute force approach to connecting Rooms of a graph, two at a time.  Calls 
     *      pickRandomSidePoint twice to determine a Vertex on each Room to connect to each
     *   other, carving a corridor straight along the difference between the x-coordinates 
     *   or the y-coordinates first (which is randomly decided), then along the other coordinate difference.
     * @param aGraph The Graph containing the Rooms to connect.
     * @return An updated Graph with the new corridors drawn.
     */
    public static Graph randomPointConnect(Graph aGraph)
    {    
        Graph graph = aGraph;
        ArrayList<Room> roomlist = graph.getRoomList();
        Random randomGen = new Random();
        Room room1;
        Room room2;
        int[] room1point;
        int[] room2point;
        int xDifference;
        int yDifference;
        int howToStart;        // Randomly decide whether to start horizontally or vertically.
        int x=0;
        int y=0;
        Vertex v;

        for (int index=0; index<roomlist.size()-1; index++)
        {
            howToStart = randomGen.nextInt(2);
            room1 = roomlist.get(index);                // Connect consecutive pairs (which aren't necessarily beside
            room2 = roomlist.get(index+1);                //        each other due to random room placement).
            room1.setIsConnected(true);    
            room2.setIsConnected(true);
            
            room1point = pickRandomSidePoint(graph, room1);
            room2point = pickRandomSidePoint(graph, room2);
            
            int room1x = room1point[0];
            int room1y = room1point[1];
            int room2x = room2point[0];
            int room2y = room2point[1];
                
            xDifference = room1x - room2x;
            yDifference = room1y - room2y;
            
            int xSign;                                // Use to determine whether to increment or decrement x-coordinate value.
            if (xDifference < 0)                        // if room1 to the left of room2
            {
                xSign = 1;
                xDifference *= -1;
            }
            else                                        // if room1 to the right of room2
            { xSign = -1; }
            
            int ySign;                                // Use to determine whether to increment or decrement y-coordinate value.
            if (yDifference < 0)                                // if room1 above room2
            { ySign = 1; }
            else                                                // if room1 below right room2
            { ySign = -1; }

            if (howToStart == 0)                                // Start in horizontal direction.
            {
                y = room1point[1];
                for (int i=0; i<Math.abs(xDifference)+1; i++)    // Increment or decrement x-coord starting at room1point going to room2point.
                {
                    x = room1x + (i*xSign);                        // Draw horizontal part of corridor first.
                    v = graph.getAVertex(x, y);
                    v.setState(true);
                    v.setType("corridor");
                }
                
                for (int j=0; j<Math.abs(yDifference)+1; j++)
                {
                    y = room1y + (j*ySign);
                    v = graph.getAVertex(x, y);
                    v.setState(true);
                    v.setType("corridor");
                }
            }
                
            else                            // Start in vertical direction.
            {
                x = room1point[0];
                for (int j=0; j<Math.abs(yDifference)+1; j++)
                {
                    y = room1y + (j*ySign);        // Draw vertical part of corridor first.
                    v = graph.getAVertex(x, y);
                    v.setState(true);
                    v.setType("corridor");
                }
                
                for (int i=0; i<Math.abs(xDifference)+1; i++)
                {
                    x = room1x + (i*xSign);
                    v = graph.getAVertex(x, y);
                    v.setState(true);
                    v.setType("corridor");
                }
            }
        }
        return graph;
    }

    
    /**
     * Connects all Rooms in a given Graph, two at a time.  Starting from the
     *    first room, moves horizontally or vertically 2, 3, 4, 5, or 6 Vertexs 
     *    at a time until reaching the second Room. 
     * @param aGraph The Graph containing the Rooms to connect.
     * @return An updated Graph with the new corridors drawn.
     */
    public static Graph drunkardsWalk(Graph aGraph)
    {
        Graph drunkGraph = aGraph; 
        ArrayList<Room> drunkRoomList = drunkGraph.getRoomList();
        Random randGen = new Random();
        int drunkHeight = drunkGraph.getHeight();
        int drunkWidth = drunkGraph.getWidth();
        int youreDone = drunkGraph.getArea()/20;
        Room room1;
        Room room2;
        int[] room1point;
        int[] room2point;
        int xDifference;
        int yDifference;
        Vertex v;
        int x=0;
        int y=0;
        int steps = 0;        //Helps to quantify drunkard's walk.
        
        for (int index=0; index<drunkRoomList.size()-1; index++)
        {
            room1 = drunkRoomList.get(index);                // Connect consecutive pairs (which aren't necessarily beside
            room2 = drunkRoomList.get(index+1);                //        each other due to random room placement).
            room1.setIsConnected(true);
            room2.setIsConnected(true);
            
            room1point = pickRandomSidePoint(drunkGraph, room1);
            room2point = pickRandomSidePoint(drunkGraph, room2);
            
            int room1x = room1point[0];
            int room1y = room1point[1];
            int room2xStart = room2.getX();
            int room2xEnd = room2.getX() + room2.getWidth();
            int room2yStart = room2.getY();
            int room2yEnd = room2.getY() + room2.getHeight();
            int room2x = room2point[0];
            int room2y = room2point[1];
            xDifference = room1x - room2x;
            yDifference = room1y - room2y;        
            
            int xSign;                                    // Use to determine which x direction to begin with.
            if (xDifference < 0)                        // If room1 to the left of room2
            { xSign = 1; }
            else                                        // If room1 to the right of room2
            { xSign = -1; }
            
            int ySign;                                    // Use to determine which y direction to begin with.
            if (yDifference < 0)                        // If room1 above room2
            { ySign = 1; }
            else                                        // If room1 below right room2
            { ySign = -1; }

            x = room1point[0];
            y = room1point[1];
            steps = 0;                         //Clear steps for each pair of Rooms.
            int lastXDelta = 0;
            int lastYDelta = 0;

            while (!((x > room2xStart+1 && x < room2xEnd-1) && (y > room2yStart+1 && y < room2yEnd-1)) && steps < youreDone)        // If not anywhere in second Room.
            {
                lastXDelta = randGen.nextInt(5)+2;                                                    // Move by 2, 3, 4, 5, or 6 Vertexs each time.
                lastYDelta = randGen.nextInt(5)+2;    
                if ((x+(xSign*lastXDelta)) > drunkWidth-2 || (x+(xSign*lastXDelta)) < 2)            // If x too close to border, change x direction.
                {
                    xSign *= -1;
                    if ((y+(ySign*lastYDelta)) > drunkHeight-2 || (y+(ySign*lastYDelta)) < 2)        // If y too close to border, change y direction.
                    { ySign *= -1; }
                    continue;
                }
                
                if ((y+(ySign*lastYDelta)) > drunkHeight-5 || (y+(ySign*lastYDelta)) < 5)            // If y too close to border, change y direction.
                {
                    ySign *= -1;
                    continue;
                }
                
                int whichDirection = randGen.nextInt(2);                    
                if (whichDirection == 0)                    // Making a brief horizontal line.
                { 
                    for (int i=0; i<lastXDelta; i++)
                    {
                        x += xSign;
                        v = drunkGraph.getAVertex(x, y);
                        v.setState(true);
                        v.setType("corridor");
                    }
                }
                
                else // if (whichDirection == 1)            // Making a brief vertical line.
                {
                    for (int j=0; j<lastYDelta; j++)
                    {
                        y += ySign;
                        v = drunkGraph.getAVertex(x, y);
                        v.setState(true);
                        v.setType("corridor");
                    }
                }
                steps ++;
            } // end while
            //System.out.println("Steps: "+steps);
            
            
            if (steps == youreDone)        // If still haven't found other room
            {
                int xDist = x-room2xStart;
                int yDist = y-room2yStart;
                
            // Redetermine signs with these new points to connect.
                if (xDist < 0)            
                { xSign = 1; }
                else                                
                { xSign = -1; }
                            
                if (yDist < 0)                    
                { ySign = 1; }
                else                            
                { ySign = -1; }
                
                for (int j=0; j<Math.abs(yDist)+1; j++)
                { 
                    y += ySign;
                    v = drunkGraph.getAVertex(x, y);
                    v.setState(true);
                }
                
                for (int yoo=0; yoo<Math.abs(xDist)+1; yoo++)
                {
                    x += xSign;
                    v = drunkGraph.getAVertex(x,y);
                    v.setState(true);
                }
            }
        }    
        return drunkGraph;
    }