diff --git a/src/main/MazeMain.java b/src/main/MazeMain.java index 8610ad1..92c2f68 100644 --- a/src/main/MazeMain.java +++ b/src/main/MazeMain.java @@ -1,3 +1,4 @@ +import net.curtlewis.maze.algorithm.AldousBroder; import net.curtlewis.maze.algorithm.BinaryTree; import net.curtlewis.maze.algorithm.Sidewinder; import net.curtlewis.maze.distance.Distances; @@ -13,8 +14,9 @@ // Grid grid = new Grid(10, 10); // BinaryTree maze = new BinaryTree(grid); - DistanceGrid grid = new DistanceGrid(6, 6); - Sidewinder maze = new Sidewinder(grid); + DistanceGrid grid = new DistanceGrid(7, 7); + // Sidewinder maze = new Sidewinder(grid); + AldousBroder maze = new AldousBroder(grid); Cell root = grid.getCellAt(0, 0); Distances distances = root.calculateDistances(); grid.setDistances(distances); diff --git a/src/main/net/curtlewis/maze/algorithm/AldousBroder.java b/src/main/net/curtlewis/maze/algorithm/AldousBroder.java new file mode 100644 index 0000000..9b2552f --- /dev/null +++ b/src/main/net/curtlewis/maze/algorithm/AldousBroder.java @@ -0,0 +1,30 @@ +package net.curtlewis.maze.algorithm; + +import net.curtlewis.maze.grid.Cell; +import net.curtlewis.maze.grid.Grid; + +public class AldousBroder { + + private Grid grid; + + public AldousBroder(Grid grid) { + this.grid = grid; + init(); + } + + private void init() { + Cell cell = grid.getRandomCell(); + + int unvisited = grid.size() - 1; + + while (unvisited > 0) { + Cell neighbor = cell.getRandomNeighbor(); + + if (neighbor.getLinks().size() == 0) { + cell.link(neighbor); + unvisited--; + } + cell = neighbor; + } + } +} diff --git a/src/main/net/curtlewis/maze/grid/Cell.java b/src/main/net/curtlewis/maze/grid/Cell.java index e8cfc74..d220db5 100644 --- a/src/main/net/curtlewis/maze/grid/Cell.java +++ b/src/main/net/curtlewis/maze/grid/Cell.java @@ -1,6 +1,7 @@ package net.curtlewis.maze.grid; import java.util.Map; +import java.util.Random; import net.curtlewis.maze.distance.Distances; @@ -98,6 +99,15 @@ return list; } + public Cell getRandomNeighbor() { + List neighbors = neighbors(); + int numberOfNeighbors = neighbors.size(); + int randomIndex = new Random().nextInt(numberOfNeighbors); + Cell randomNeighbor = neighbors.get(randomIndex); + + return randomNeighbor; + } + public String toString() { return "Cell[row: " + row + " col: " + col + "]"; } diff --git a/src/main/net/curtlewis/maze/grid/Grid.java b/src/main/net/curtlewis/maze/grid/Grid.java index 35b1167..8669534 100644 --- a/src/main/net/curtlewis/maze/grid/Grid.java +++ b/src/main/net/curtlewis/maze/grid/Grid.java @@ -1,5 +1,7 @@ package net.curtlewis.maze.grid; +import java.util.Random; + public class Grid { private int rows; @@ -68,8 +70,8 @@ public Cell getRandomCell() { - int randomRow = (int)(Math.random()) * (rows - 1); - int randomCol = (int)(Math.random()) * (columns - 1); + int randomRow = new Random().nextInt(rows); + int randomCol = new Random().nextInt(columns); return grid[randomRow][randomCol]; }