I am given a project and would like some help/guidance from the community. I am not asking for any code just a direction and little advice on how to approach this project or how these things work per-say. I am behind in my classes due to me having missed 2-3 weeks of classes because of a broken bone prohibiting mobility.
The project description:
I am to design a program that will generate a random maze.
My implementation should do the following. View the maze as a grid of cells
where each cell is enclosed by four walls separating it from all adjoining cells
Me: Hence why they are called disjoint sets?
Continue randomly removing walls between two cells not currently joined by a path until all cells are reachable from every other cell. Then randomly select on one edge of the maze and a cell on the opposing edge to be the entrance and exit.
I must implement a Union-Find class which uses a forest of trees formed by the partition of a set via the parent pointer array implementation. I must utilize the weighted union rule and path compression.
Here I am assuming the grid is a 2D array i.e rows and columns, quit obviously.
So far by doing some researching on google I was able to find a C++ implementation of a disjoint data structure class
My problem is 1. I do not like using/copying someone else's work because I don't feel like I learned anything 2. This class doesn't seem to fit my project approach it is looking for I am not familiar with the C++ STL vector class.
So on the agenda is to create a Union-Find class using the weighted union rule and path compression. Once this is created I should test the class by using 2-3 trees and testing the weighted union rule and path compression rule. How could I test these? If one tree has 3 children and another has 1 child the union rule will go to the larger tree? and Path compression when I union two trees together all children(elements) will point to the parent/root node?
Secondly, create a grid of cells, easily done.
At this exact moment I am confused on the maze generation algorithm
What exactly is meant by the parent pointer array method?
Each cell has its own parent pointer until that cell is randomly selected along with another to be unioned together? I see many complications with my thought process on how to design and implement a proper algorithm
Also what is the forest of trees exactly to be in this case? Each cell being a root node and the adjoining walls being its children?
Sorry for the mass confusion fellow programmers. And Yes I have searched this forum for similar posts however, many of them not being recent I can't or do not want to post in them. I just have few questions, well many, too ask :). I hope not to be too bothersome :(
Edited 6 Years Ago by power_computer: n/a