diff --git a/src/main/MazeMain.java b/src/main/MazeMain.java index 92c2f68..1123447 100644 --- a/src/main/MazeMain.java +++ b/src/main/MazeMain.java @@ -1,6 +1,7 @@ import net.curtlewis.maze.algorithm.AldousBroder; import net.curtlewis.maze.algorithm.BinaryTree; import net.curtlewis.maze.algorithm.Sidewinder; +import net.curtlewis.maze.algorithm.Wilsons; import net.curtlewis.maze.distance.Distances; import net.curtlewis.maze.grid.Cell; import net.curtlewis.maze.grid.DistanceGrid; @@ -14,9 +15,10 @@ // Grid grid = new Grid(10, 10); // BinaryTree maze = new BinaryTree(grid); - DistanceGrid grid = new DistanceGrid(7, 7); + DistanceGrid grid = new DistanceGrid(8, 8); // Sidewinder maze = new Sidewinder(grid); - AldousBroder maze = new AldousBroder(grid); + //AldousBroder maze = new AldousBroder(grid); + Wilsons maze = new Wilsons(grid); Cell root = grid.getCellAt(0, 0); Distances distances = root.calculateDistances(); grid.setDistances(distances); diff --git a/src/main/net/curtlewis/maze/algorithm/Wilsons.java b/src/main/net/curtlewis/maze/algorithm/Wilsons.java new file mode 100644 index 0000000..1b54b2a --- /dev/null +++ b/src/main/net/curtlewis/maze/algorithm/Wilsons.java @@ -0,0 +1,85 @@ +package net.curtlewis.maze.algorithm; + +import java.util.ArrayList; +import java.util.List; +import java.util.Random; + +import net.curtlewis.maze.grid.Cell; +import net.curtlewis.maze.grid.Grid; + +public class Wilsons { + + private Grid grid; + + public Wilsons(Grid grid) { + System.out.println("Wilsons constructor..."); + this.grid = grid; + init(); + } + + private void init() { + + System.out.println("Wilsons init..."); + + List unvisited = new ArrayList<>(); + for(int r = 0; r < grid.getNumberOfRows(); r++) { + for(int c = 0; c < grid.getNumberOfColumns(); c++) { + unvisited.add(grid.getCellAt(r, c)); + } + } + + Cell first = sample(unvisited); + System.out.println("first: " + first + " unvisited size before: " + unvisited.size()); + unvisited.remove(first); + + while(!unvisited.isEmpty()) { + System.out.println("Unvisited size: " + unvisited.size()); + Cell cell = sample(unvisited); + List path = new ArrayList<>(); + path.add(cell); + + // do a random walk until we come to an + // visited cell. + while(unvisited.contains(cell)) { + cell = sample(cell.neighbors()); + int position = path.indexOf(cell); + // check if we visited the cell on the + // current path. If we have we created a loop + // so erase the loop upto position. + if (position > 0) { + + // the book uses Ruby language and the statement: + // path = path[0..position] , position is inclusive + // therefore we have to make it inclusive by adding 1 + // to the position for Java since sublist is not inclusive + // for the last argument. + path = path.subList(0, position + 1); + } else { + path.add(cell); + } + } + + // we found a path to a previously visited cell + // that doesn't create a loop. Carve the path + // to this visited cell in the grid and remove + // each cell on the path from the unvisited list. + for(int i = 0; i < path.size() - 1; i++) { + Cell cellOnPath = path.get(i); + cellOnPath.link(path.get(i + 1)); + unvisited.remove(cellOnPath); + } + + System.out.println("?? " + unvisited.size()); + + } + } + + private Cell sample(List cells) { + int numElements = cells.size(); + Random rand = new Random(); + int randomIndex = rand.nextInt(numElements); + + return cells.get(randomIndex); + } + +}