sraaphorst / spelunker-graphmaze Goto Github PK

Implement the BFS flood colouring. We can do this with a gradient, given two colours and a start point.

Right now, the output mazes are identical in definition to the template that is given for maze production. This may contain some information that is not needed by the maze (e.g. the binary tree function). There is no reason for these two to be the same, and we may want the output maze to contain additional information, such as start position and end position.

Related to #1.

For colouring purposes, we need the start vertex from where the maze generation began. Modify MazeGenerator::generate to return a pair consisting of the maze and start vertex.

Right now, the graph properties contain important information, namely the map from cell type to directions, as well as ranking information for graphs that can have a sensible two dimensional ordering placed on their cells.

We need to clean this up considerably. Ideas:

1. Make the BTCandidateFunction a template based on the type of tessellation, so that we are not operating on arbitrary ints for vertex type.
2. Make the VertexInfo a template based on the type of tessellation, so that the type member is not an arbitrary int.
3. Improve / clean up the ranking function in the GraphInfo.
4. Improve the way that these are populated.

Right now, HuntAndKillMazeGenerator works under the assumption that vertices are integers: while this is the case, we shouldn't assume it, and we should be working with iterators instead.

This is dependent on #12 being done first.

Figure out how we want to implement ThickMazes.

The biggest question is if it makes sense to model it using BGL.

Note: we will still have a homomorphism from regular mazes to thick mazes as in the old implementation.

Check connectivity, and preferably, determine the connected components. This should be done as a decorator for mazes, and integrated into tests to make sure that algorithms that should be perfect are indeed perfect.

There are probably routines in BGL to do this already. Investigate whether or not this is the case.

It seems that a BinaryTree function would be the perfect way to enhance a template maze, and then we could have a type called BinaryTreeTemplateMaze that could be used exclusively by binary tree and hunt and kill maze generators to make mazes.

We work under the assumption in GraphUtils::randomStartVertex that vertices are of type int. While this is true, we should not assume it, and should instead work with iterators.

Implement randomized Prim's algorithm for generating mazes.