I'm trying to build a maze using a DisjSet algorithm. I feel like I've got it down but for some reason I can't figure out why I keep getting this null pointer exception in one of the classes I'm using. Any help will be appreciated
This is the Maze class
package project3;
public class Maze2 {
private void nextRoom(int[] room, int wall, int n)
{
int row = wall / (2 * n - 1);
int column = wall % (2 * n - 1);
if (column < n - 1)
{
room[0] = n * row + column;
room[1] = n * row + column + 1;
}
else
{
column += 1 - n;
room[0] = n * row + column;
room[1] = n * (row + 1) + column;
}
}
private void mazeBuild(int m, int n)
{
DisjSets rooms = new DisjSets(m * n);
int wallNumber = 2 * m * n - m - n;
boolean[] is_wall = new boolean[wallNumber];
Permutation wallUntested = new Permutation(wallNumber);
for (int i = 0; i < wallNumber; ++i)
{
is_wall[i] = true;
}
while (rooms.s.length>1 )
{
int wall = wallUntested.next();
int[] room = new int[2];
nextRoom(room, wall, n);
if (rooms.find(room[0]) != rooms.find(room[1]))
{
is_wall[wall] = false;
rooms.union(room[0], room[1]);
}
}
System.out.print("+ +");
for (int i = 0; i < n - 1; ++i)
{
System.out.print("--+");
}
System.out.print("\n");
int wall_counter = 0;
for (int i = 0; i < m - 1; ++i)
{
System.out.print("|");
for (int j = 0; j < n - 1; ++j)
{
if (is_wall[wall_counter])
{
System.out.print(" |");
}
else
{
System.out.print(" ");
}
++wall_counter;
}
System.out.print(" |");
System.out.print("\n");
System.out.print("+");
for (int j = 0; j < n; ++j)
{
if (is_wall[wall_counter])
{
System.out.print("--+");
}
else
{
System.out.print(" +");
}
++wall_counter;
}
System.out.print("\n");
}
System.out.print("|");
for (int j = 0; j < n - 1; ++j)
{
if (is_wall[wall_counter])
{
System.out.print(" |");
}
else
{
System.out.print(" ");
}
++wall_counter;
}
System.out.print(" |");
System.out.print("\n");
for (int i = 0; i < n - 1; ++i)
{
System.out.print("+--");
}
System.out.print("+ +");
System.out.print("\n");
}
public static void main( String [] args){
Maze2 maze = new Maze2();
//input parameters here
maze.mazeBuild(3,3);
}
}
This is the DisjSet class
package project3;
public class DisjSets
{
// DisjSets class
//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// int find( x ) --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed
/**
* Disjoint set class, using union by rank and path compression.
* Elements in the set are numbered starting at 0.
* @author Mark Allen Weiss
*/
/**
* Construct the disjoint sets object.
* @param numElements the initial number of disjoint sets.
*/
public DisjSets( int numElements )
{
s = new int [ numElements ];
for( int i = 0; i < s.length; i++ )
s[ i ] = -1;
}
/**
* Union two disjoint sets using the height heuristic.
* For simplicity, we assume root1 and root2 are distinct
* and represent set names.
* @param root1 the root of set 1.
* @param root2 the root of set 2.
*/
public void union( int root1, int root2 )
{
if( s[ root2 ] < s[ root1 ] ) // root2 is deeper
s[ root1 ] = root2; // Make root2 new root
else
{
if( s[ root1 ] == s[ root2 ] )
s[ root1 ]--; // Update height if same
s[ root2 ] = root1; // Make root1 new root
}
}
/**
* Perform a find with path compression.
* Error checks omitted again for simplicity.
* @param x the element being searched for.
* @return the set containing x.
*/
public int find( int x )
{
if( s[ x ] < 0 )
return x;
else
return s[ x ] = find( s[ x ] );
}
public int [ ] s;
}
this is the permutation class
package project3;
import java.util.*;
public class Permutation{
private static Random random;
int capacity;
int bound;
int[] array;
public Permutation(int n)
{
this.capacity = n;
this.bound = (int) capacity;
this.array = new int[capacity];
for (int i = 0; i < capacity; ++i)
{
array[i] = i;
}
}
public final int next()
{
if (bound == 0)
{
return 0;
}
int index = random.nextInt() % bound;
int result = array[index];
--bound;
array[index] = array[bound];
return result;
}
public final void reset()
{
for (int i = 0; i < capacity; ++i)
{
array[i] = i;
}
bound = capacity;
}
}
The error is
Exception in thread "main" java.lang.NullPointerException
at project3.Permutation.next(Permutation.java:33)
at project3.Maze2.mazeBuild(Maze2.java:50)
at project3.Maze2.main(Maze2.java:159)
And it all points back to this line of code in the permutation class
int index = random.nextInt() % bound;
Thank You in Advance
