koobas.hobune.stream
Creating a maze within a grid
Hello, so I'm trying to make a maze where the walls will constantly be shifting/changing location as the player progresses. I've tried quite a few different ways (starting from a modified DFS algorithm) but cannot seem to get the level to generate a maze around the sections I pre-built. I make a grid and go through if each cell should be a wall or passage, but it always creates deadzones and islands within the generated area.
Fourth or Fifth Attempt:
void GenerateMaze() {
MazeWall tempWall;
Cell checkCell = null;
Cell currentCell = null;
List<Cell> neighbors = new List<Cell> ();
int totalCells = TotalCellsToIterate(cellList);
int visitedCells = 0;
for (int i = 0; i < cellList.Count; ++i)
if (!cellList [i].hasWall && !cellList [i].isEdge && !cellList [i].isCenter && !cellList [i].visited && !cellList[i].isOuterEdge) {
currentCell = cellList [i];
break;
}
while (visitedCells < totalCells) {
neighbors = GetNeighbors (currentCell);
if (neighbors.Count > 0) {
checkCell = neighbors [(Random.Range (0, neighbors.Count))];
neighbors.Remove (checkCell);
for (int i = 0; i < neighbors.Count; ++i) {
tempWall = Instantiate (wallPrefab, neighbors [i].transform.position, neighbors [i].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (neighbors [i].transform.position.x, neighbors [i].transform.position.y + 5, neighbors [i].transform.position.z);
tempWall.transform.parent = transform;
neighbors [i].hasWall = true;
neighbors [i].visited = true;
neighbors [i].wall = tempWall;
//manipulatableCells.Add (neighbors [i]);
}
} else {
for (int i = 0; i < MazeDirections.Count; ++i) {
MazeDirection direction = (MazeDirection)i;
IntVector2 coords = currentCell.coordinates + direction.ToIntVector2 ();
if (ContainsCoordinates (coords)) {
Cell test = GetCell (coords);
if (test.hasWall && !test.isCenter && !test.isEdge && !test.isOuterEdge) {
Destroy (test.wall);
test.hasWall = false;
checkCell = test;
}
}
}
}
//manipulatableCells.Add (checkCell);
currentCell.visited = true;
checkCell.visited = true;
currentCell = checkCell;
++visitedCells;
}
}
List<Cell> GetNeighbors(Cell currentCell) {
List<Cell> neighbors = new List<Cell> ();
for (int i = 0; i < MazeDirections.Count; ++i) {
Cell neighborCell;
MazeDirection direction = (MazeDirection)i;
IntVector2 coords = currentCell.coordinates + direction.ToIntVector2 ();
if (ContainsCoordinates (coords)) {
neighborCell = GetCell (coords);
if (!neighborCell.hasWall && !neighborCell.isCenter && !neighborCell.visited && !neighborCell.isOuterEdge)
neighbors.Add (neighborCell);
}
}
return neighbors;
}
Cell GetCell(IntVector2 coordinates) {
return cells [coordinates.x, coordinates.z];
}
int TotalCellsToIterate(List<Cell> cellList) {
List<Cell> internalCellList = new List<Cell>();
internalCellList = cellList;
for (int i = 0; i < internalCellList.Count; ++i)
if (internalCellList [i].isEdge || internalCellList [i].isCenter || internalCellList [i].isOuterEdge) {
internalCellList.Remove (internalCellList [i]);
cellList.Remove (internalCellList [i]);
}
return internalCellList.Count;
}
Final attempt thus far:
void GenerateMaze2() {
MazeWall tempWall;
Cell checkCell;
Cell currentCell;
List<Cell> neighbors = new List<Cell> ();
int totalCells = TotalCellsToIterate (cellList);
for (int i = 0; i < totalCells; ++i) {
if (!cellList [i].hasWall)
passageCells.Add (cellList [i]);
neighbors = GetNeighbors (cellList [i]);
if (neighbors.Count > 1) {
checkCell = neighbors [Random.Range (0, neighbors.Count)];
if (!passageCells.Contains (checkCell)) {
neighbors.Remove (checkCell);
}
for (int j = 0; j < neighbors.Count; ++j) {
tempWall = Instantiate (wallPrefab, neighbors [j].transform.position, neighbors [j].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (neighbors [j].transform.position.x, neighbors [j].transform.position.y + 5, neighbors [j].transform.position.z);
tempWall.transform.parent = transform;
neighbors [j].hasWall = true;
neighbors [j].visited = true;
neighbors [j].wall = tempWall;
walledCells.Add (neighbors [j]);
}
}
cellList [i].visited = true;
}
}
which makes this show up when running the game: picture
Does anyone know of a better way to go about achieving what I am describing?
EDIT Here is the entire class with further attempts made to get this generation to work how I described (still not working as I would like);
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class Maze : MonoBehaviour {
public MazeWall wallPrefab;
public Cell cellPrefab;
public int numberOfTiles = 400;
public int numberOfRows = 20;
public float distanceBetweenTiles = 10.0f;
public double percentToWall = 0.1;
Grid grid;
Cell[,] cells;
List<Cell> cellList = new List<Cell> ();
List<Cell> centerOuterCells = new List<Cell>();
List<MazeWall> outerWalls = new List<MazeWall> ();
List<Cell> passageCells = new List<Cell>();
List<Cell> walledCells = new List<Cell>();
List<Cell> moddableCells = new List<Cell>();
void Start () {
grid = gameObject.AddComponent<Grid>();
grid.tilePrefab = cellPrefab;
grid.numberOfTiles = numberOfTiles;
grid.numberOfRows = numberOfRows;
grid.distanceBetweenTiles = distanceBetweenTiles;
grid.CreateTiles ();
cells = grid.cells;
centerOuterCells = grid.outerCenterCells;
cellList = grid.cellList;
moddableCells = cellList;
CreateStaticWalls ();
GenerateMaze5 ();
}
void Update () {
}
void CreateStaticWalls() {
MazeWall tempWall;
for (int i = 0; i < cellList.Count; ++i) {
if (moddableCells [i].isEdge) {
tempWall = Instantiate (wallPrefab, moddableCells [i].transform.position, moddableCells [i].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (moddableCells [i].transform.position.x, moddableCells [i].transform.position.y + 5, moddableCells [i].transform.position.z);
tempWall.transform.parent = transform;
outerWalls.Add (tempWall);
moddableCells [i].hasWall = true;
moddableCells [i].wall = tempWall;
//moddableCells.Remove (cellList [i]);
}
}
/**
for (int i = 0; i < centerOuterCells.Count; ++i) {
tempWall = Instantiate (wallPrefab, centerOuterCells [i].transform.position, centerOuterCells [i].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (centerOuterCells [i].transform.position.x, centerOuterCells [i].transform.position.y + 5, centerOuterCells [i].transform.position.z);
tempWall.transform.parent = transform;
centerOuterCells [i].hasWall = true;
centerOuterCells [i].wall = tempWall;
//moddableCells.Remove (centerOuterCells [i]);
}
**/
}
void GenerateMaze5() {
MazeWall tempWall;
Cell checkCell;
Cell currentCell;
List<Cell> neighbors = new List<Cell> ();
int totalCells = TotalCellsToIterate (cellList);
currentCell = cellList [Random.Range(0, cellList.Count)];
passageCells.Add (currentCell);
currentCell.visited = true;
Cell prevCell = currentCell;
int visitedCells = 1;
for (int i = 0; visitedCells < totalCells; ++i) {
neighbors = GetWalledNeighbors (currentCell);
if (neighbors.Count > 1) {
checkCell = GetCell (neighbors [Random.Range (0, neighbors.Count)].coordinates);
neighbors.Remove (checkCell);
if (neighbors.Count > 0) {
for (int j = 0; j < neighbors.Count; ++j) {
tempWall = Instantiate (wallPrefab, new Vector3 (neighbors [j].transform.position.x, neighbors [j].transform.position.y + 5, neighbors [j].transform.position.z), neighbors [j].transform.rotation) as MazeWall;
tempWall.transform.parent = transform;
neighbors [j].hasWall = true;
neighbors [j].wall = tempWall;
neighbors [j].visited = true;
}
}
checkCell.visited = true;
passageCells.Add (checkCell);
prevCell = checkCell;
currentCell = checkCell;
++visitedCells;
} else {
currentCell = prevCell;
}
}
}
void GenerateMaze4() {
MazeWall tempWall;
Cell checkCell;
Cell currentCell = null;
List<Cell> neighbors = new List<Cell> ();
List<Cell> walledNeighbors = new List<Cell> ();
int tilesPerRow = numberOfTiles / numberOfRows;
for (int i = 1; i < numberOfRows; ++i) {
for (int j = 1; j < tilesPerRow; ++j) {
checkCell = GetCell (new IntVector2 (j, i));
if (i != 18 || j != 18)
if (i % 2 == 0 || j % 2 == 0) {
tempWall = Instantiate (wallPrefab, new Vector3 (checkCell.transform.position.x, checkCell.transform.position.y + 5, checkCell.transform.position.z), checkCell.transform.rotation) as MazeWall;
tempWall.transform.parent = transform;
checkCell.hasWall = true;
checkCell.wall = tempWall;
}
}
}
int totalCells = TotalCellsToIterate (cellList);
currentCell = cellList [Random.Range(0, cellList.Count)];
passageCells.Add (currentCell);
currentCell.visited = true;
Cell prevCell = currentCell;
for (int visitedCells = 1; visitedCells < totalCells; ++visitedCells) {
neighbors = GetNeighbors (currentCell);
if (neighbors.Count > 1) {
checkCell = neighbors [Random.Range (0, neighbors.Count)];
walledNeighbors = GetWalledNeighbors (checkCell);
Cell walled = GetCell (new IntVector2 (checkCell.coordinates.x + (checkCell.coordinates.x - currentCell.coordinates.x), checkCell.coordinates.z + (checkCell.coordinates.z - currentCell.coordinates.z)));
Destroy (walled.wall);
walled.wall = null;
walled.hasWall = false;
passageCells.Add (walled);
walled.visited = true;
checkCell.visited = true;
prevCell = checkCell;
currentCell = checkCell;
++visitedCells;
} else {
currentCell = prevCell;
}
}
}
void GenerateMaze3() {
MazeWall tempWall;
Cell checkCell;
int startCells = TotalCellsToIterate(cellList);
int totalCells = (int) (startCells * percentToWall);
while (startCells > totalCells) {
int randomIndex = Random.Range (0, moddableCells.Count);
checkCell = cellList [randomIndex];
walledCells.Add (checkCell);
--startCells;
}
for (int i = 0; i < walledCells.Count; ++i) {
tempWall = Instantiate (wallPrefab, walledCells [i].transform.position, walledCells [i].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (walledCells [i].transform.position.x, walledCells [i].transform.position.y + 5, walledCells [i].transform.position.z);
tempWall.transform.parent = transform;
walledCells [i].hasWall = true;
walledCells [i].wall = tempWall;
}
}
void GenerateMaze2() {
MazeWall tempWall;
Cell checkCell;
Cell currentCell;
List<Cell> neighbors = new List<Cell> ();
int totalCells = TotalCellsToIterate (moddableCells);
for (int i = 0; i < totalCells; ++i) {
if (!moddableCells [i].hasWall)
passageCells.Add (moddableCells [i]);
neighbors = GetNeighbors (moddableCells [i]);
if (neighbors.Count > 1) {
checkCell = neighbors [Random.Range (0, neighbors.Count)];
if (!passageCells.Contains (checkCell) && neighbors.Count <= 2) {
neighbors.Remove (checkCell);
passageCells.Add (checkCell);
} else if (!passageCells.Contains (checkCell) && neighbors.Count >= 2) {
neighbors.Remove (checkCell);
Cell check2 = neighbors [Random.Range (0, neighbors.Count)];
neighbors.Remove (check2);
passageCells.Add (checkCell);
passageCells.Add (check2);
}
for (int j = 0; j < neighbors.Count; ++j) {
tempWall = Instantiate (wallPrefab, neighbors [j].transform.position, neighbors [j].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (neighbors [j].transform.position.x, neighbors [j].transform.position.y + 5, neighbors [j].transform.position.z);
tempWall.transform.parent = transform;
neighbors [j].hasWall = true;
neighbors [j].visited = true;
neighbors [j].wall = tempWall;
walledCells.Add (neighbors [j]);
}
}
moddableCells [i].visited = true;
}
}
void GenerateMaze() {
MazeWall tempWall;
Cell checkCell = null;
Cell currentCell = null;
List<Cell> neighbors = new List<Cell> ();
int totalCells = TotalCellsToIterate(cellList);
int visitedCells = 0;
for (int i = 0; i < cellList.Count; ++i)
if (!cellList [i].hasWall && !cellList [i].isEdge && !cellList [i].visited) {
currentCell = cellList [i];
break;
}
while (visitedCells < totalCells) {
neighbors = GetNeighbors (currentCell);
if (neighbors.Count > 0) {
checkCell = neighbors [(Random.Range (0, neighbors.Count))];
neighbors.Remove (checkCell);
for (int i = 0; i < neighbors.Count; ++i) {
tempWall = Instantiate (wallPrefab, neighbors [i].transform.position, neighbors [i].transform.rotation) as MazeWall;
tempWall.transform.localPosition = new Vector3 (neighbors [i].transform.position.x, neighbors [i].transform.position.y + 5, neighbors [i].transform.position.z);
tempWall.transform.parent = transform;
neighbors [i].hasWall = true;
neighbors [i].visited = true;
neighbors [i].wall = tempWall;
//manipulatableCells.Add (neighbors [i]);
}
} else {
for (int i = 0; i < MazeDirections.Count; ++i) {
MazeDirection direction = (MazeDirection)i;
IntVector2 coords = currentCell.coordinates + direction.ToIntVector2 ();
if (ContainsCoordinates (coords)) {
Cell test = GetCell (coords);
if (test.hasWall && !test.isEdge) {
Destroy (test.wall);
test.hasWall = false;
checkCell = test;
}
}
}
}
//manipulatableCells.Add (checkCell);
currentCell.visited = true;
checkCell.visited = true;
currentCell = checkCell;
++visitedCells;
}
}
List<Cell> GetNeighbors(Cell currentCell) {
List<Cell> neighbors = new List<Cell> ();
for (int i = 0; i < MazeDirections.Count; ++i) {
Cell neighborCell;
MazeDirection direction = (MazeDirection)i;
IntVector2 coords = currentCell.coordinates + direction.ToIntVector2 ();
if (ContainsCoordinates (coords)) {
neighborCell = GetCell (coords);
if (!neighborCell.hasWall && !neighborCell.visited)
neighbors.Add (neighborCell);
}
}
return neighbors;
}
List<Cell> GetWalledNeighbors(Cell currentCell) {
List<Cell> walledNeighbors = new List<Cell> ();
for (int i = 0; i < MazeDirections.Count; ++i) {
Cell neighborCell;
MazeDirection direction = (MazeDirection)i;
IntVector2 coords = currentCell.coordinates + direction.ToIntVector2Single ();
if (ContainsCoordinates (coords)) {
neighborCell = GetCell (coords);
if (!neighborCell.hasWall)
walledNeighbors.Add (neighborCell);
}
}
return walledNeighbors;
}
Cell GetCell(IntVector2 coordinates) {
return cells [coordinates.x, coordinates.z];
}
int TotalCellsToIterate(List<Cell> cellListIn) {
List<Cell> internalCellList = new List<Cell>();
internalCellList = cellListIn;
for (int i = 0; i < internalCellList.Count; ++i)
if (internalCellList[i].hasWall) {
internalCellList.Remove (internalCellList [i]);
cellList.Remove (internalCellList [i]);
}
return internalCellList.Count;
}
public IntVector2 RandomCoordinates {
get { return new IntVector2 (Random.Range (0, numberOfRows - 1), Random.Range (0, numberOfRows - 1)); }
}
public bool ContainsCoordinates(IntVector2 coords) {
return coords.x >= 0 && coords.x < numberOfRows && coords.z >= 0 && coords.z < numberOfRows;
}
}
