Tag: Maze generator

Maze Generator

The maze is basically a X * X grid that has 1 route from the start to the end of the grid.

Here is a picture of the output of a grid with a path/route from the start to the finish.

Maze Generator
CS106B Assignment 2 Part 3

As you can see from the above there is basically one route which can be worked out if you start off with all of the grid cells being classed as blocked (e.g. all walls around the cell are there) and if you then process this grid and make it so that all of the grid cells are linkable so that there is a way around the grid to reach every cell, of course you would only have one way from start to finish.

Then all you need to do is to random check each cell wall and see if it is within the same set of chambers (set of cells that already linked) if not then delete that cell wall else check another wall. So taken from the assignment PDF file (attached) the process, in full, is

  • choose a dimension
  • generate all walls, and shuffle them
  • generate all chambers, where each chamber includes one unique cell
    1. foreach wall in randomly-ordered-walls
    2. if wall separates two chambers
    3. remove wall

I generated the walls and shuffled them by to start with create a grid of cells in a loop (for loops) which build up the horizontal and vertical cells and then go through a for loop again that loops to the size of the cells and this time randomally pick a cell to swap with another cell, this will generated the randomally list of walls to check to see if it separates two chambers.

The way that I checked to see if the wall was between two chambers was to first find the cell on the left within the chambers array (this array would be the dimension * dimension of the grid since there would be a chamber for each cell) and then see if the second cell that is linked to that wall to check is part of the same chamber as the left.

I could have used a Set which contains the method “containsAt” so could find the second cell is within the same chamber as the first, but I used a Vector array because then I could show two ways of doing the find, either using a for loop or a recursive function, I have done this below, the first is the for loop method that will search a Vector of cells (col/row) of a chamber(subChamber) to find a cell (findThisCell), the index is used with the recursive function so just disregard that at present, it will return true if it finds it, else false.

bool findCellInSubChambers(Vector<cell> &subChambers, cell findThisCell, int index)
{
	for (int mainSubSubChamber = 0; mainSubSubChamber < subChambers.size(); mainSubSubChamber++)
	{
		if (subChambers[mainSubSubChamber] == findThisCell)
		{
			return true;
		}
	}
	return false;
}

here is the recursive function that will loop through the chamber of cells (subChamber) the index is started with a value of 0 as the function definition shows below as well. What it does is to go through the array of cells within the chamber (vector array) with using the index value, if has not found at the present index within the array recall this function again with a new index value, but if the index value is higher than the size of the array then return false.

bool findCellInSubChambers(Vector<cell> &subChambers, cell findThisCell, int index =0);
// return true if the cell is within the vector of cells
bool findCellInSubChambers(Vector<cell> &subChambers, cell findThisCell, int index)
{
	if (index < subChambers.size())
	{
		if (subChambers[index] == findThisCell)
			return true;
		else 
			return findCellInSubChambers(subChambers, findThisCell, ++index);
	}
	return false;
}

I did do another for loop and recursive function for searching all of chambers for the first cell of the wall to check for as well, just for fun.

Anyway, here is the main loop code, what it does is to first find the index value of the sub chamber within the main chambers array (findCellInChambers function) which holds the value of the index within the array of chambers, if it is found (it should always be found to be honest, but to just be on the safe side), then check to see if the second cell to check (the other side of the wall) is in the same chamber as the first cell, if not, then remove the wall and add the array of cells that was attached to the second cell to the first cell chamber array, so that we can build up a list of chambers (this should finish off with a all of the chambers being linked).

Vector<wall>::Iterator wallIter = theWalls.iterator();
while (wallIter.hasNext() && (wallI < ((dimension * dimension)-1)))
{
	wall checkThisWall = wallIter.next();
 
	int firstFound = findCellInChambers(chambers, checkThisWall.one);
	if (firstFound >= 0)
	{
		if (!findCellInSubChambers(chambers[firstFound], checkThisWall.two))
		{
			wallI++;
			RemoveWall(checkThisWall);
			int found = findCellInChambers(chambers, checkThisWall.two);
			if (found >= 0)
			{
				for (int foundI = 0; foundI < chambers[found].size(); foundI++)
					chambers[firstFound].add(chambers[found][foundI]);
				chambers.removeAt(found);
			}
		}
	}
}

I have attached the full source code and also the PDF of the assignment.