Disjoint sets and maze

[nah094020]

Ok final project of semester is to make a maze with gui , i started with the disjoint class already but am a bit confused on how the walls or cells will work with disjoint sets, has in how do i go about creating them

will this work? , my thinking is making all of them true, has in they exist at the beggining and false when one is knocked down.

  protected boolean[][] horizontalWalls;
  protected boolean[][] verticalWalls;

Now how would i go about combining this with my disjoint sets that keep track of the cells that are connected.

Do i have to create a cell class too? with walls has its attrubutes or something?

[JamesCherrill]

Most versions of this seems to be pre-OO indesign, with lots of arrays and no classes. Maybe this is a gmood time to do it in proper OO style?
I haven't done this myself, but of I were to try, I would start with a Cell class. That makes it easy to create the disjoint sets of Cells. Then I would have a Wall class, and each Wall would have as instance variables the Cells (1 or 2) that it belongs to. That makes it easy to maintain a list of Walls, pick a random Wall and find the Cells it joins.
At first I thought each Cell would need a list of its (0-4) Walls, but now I can't see a use for that. On the other hand each Cell would benefit from a list of the (0-4, initially 0) Cells it's connected to, so you could traverse the Maze later. As you remove each Wall all you need to do is to add each of the two Cells it joined to the other Cell's "connected to" list. In other words, from the Cells viewpoint a Wall is just the absence of a connection (!).
You may also want to add some geometry info to the Cell class (eg row/col) to help display it nicely, although the logic doesn't need the Cells to be linear, grid-like, or even 2 dimensional.
This is my first exposure to the disjoint set patern for maze creation. It's really neat!

[nah094020]

Ok so heres what i got so far, am still having troubel with the walls tough

import java.util.*;

/**
 * This program creates a maze given a number of rows
 * and columns.
 * @author Nestor Alejandto Hernandez
 */
public class Maze 
{

    public static class Cell
    {
        int cell;
        private  boolean n ;//top wall, north
        private  boolean e ;//right wall, east
        private  boolean s ;//bottom wall,south
        private  boolean w ;//left wall, west
        // creates a cell with 4 walls set to true, the int indicates what cell it is
        public Cell(int cell)
        {
            this.cell = cell;
            n = true;
            e = true;
            s = true;
            w = true;

        }
        public void setWalls(boolean n,boolean e, boolean s,boolean w)
        {
            this.n = n;
            this.e = e;
            this.s = s;
            this.w = s;
        }
        public boolean hasAllWalls()
        {
            return(n&&e&&s&&w);
        }

    }

    //returns random ineger from 0 to n-1 given n choices
    private static Random random;
    private static int randN(int choices)
    {
        if (random == null)
        {
            random = new Random();

        }
        int r = random.nextInt()%choices;
        if(r<0)
        {
           r = -r; 
        }
        return r;
    }

    public Maze (int rows, int columns)
    {
        Maze maze = new Maze(rows, columns);
        //arrays for walls  
        boolean harray[][] = new boolean[rows][columns];
        boolean varray[][] = new boolean[rows][columns];

        for(int i =0; i < rows-1;i++)
        {
            for(int k = 0;k<columns-1;k++)
            {
                harray[i][k] = true;
                varray[i][k] = true;
            }
        }


         DisjSets dSet=  new DisjSets(rows*columns);
         ArrayList<Maze.Cell> cellList = new ArrayList<>();

         for(int i =0;i <rows*columns-1;i++)
         {
             cellList.add(new Maze.Cell(i));
         }
         Maze.Cell begin =  cellList.get(0);
         begin.n =false;
         Maze.Cell end = cellList.get(rows*columns-1);
         end.s =false;

         while(dSet.find(0)!=dSet.find(rows*columns-1))
         {

         }

    }
     /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
    {
        // TODO code application logic here
    }
}

am really stuck on the removing of walls, hence its got to be a random wall, i understand the concept of connecting the cells with the disjoint set once the wall between them has been removed, just not sure how am i suppose to implement that, my head is a bit messy atm xD, thx for the help tough!

[JamesCherrill]

Like I said before, you could have a Wall class. All it needs is two variables for the two Cells that this wall separates.