sraaphorst / spelunker Goto Github PK

Examples:

1. Average branching factor.

2. Path length from NW-to-SE corner.

3. Longest path.

Others forthcoming.

Right now, the implementation of RNG only allows subclasses to implement two methods, namely:

• randomRangeImpl

• randomProbabilityImpl

and it then uses these on a concrete, registered instance of a subclass of RNG to handle all tasks requiring randomness.

This is not very good, for example, when it comes to shuffling a container, or picking a random element from a container.

Instead, RNG should have static methods that call default virtual protected Impl methods. The current static implementation will be moved to these Impl methods, and subclasses of RNG can override them with more efficient implementations.

For example, right now we have:

public static auto RNG::randomElement

which uses the concrete RNG subclass implementation's randomRangeImpl to get the element in an inefficient way.

Instead, we should have, in RNG:

• public static auto RNG::randomElement that simply calls:

• protected virtual auto RNG::randomElementImpl, which contains the code currently in the static method.

Then DefaultRNG will override this with a more efficient implementation.

In order to accomplish task #53, we need to first exploit graph colourings to determine what constitute valid "walls" to remove in ThickMazes. This entails:

Accept parameters u_x, v_x, and v_y, which determine the colouring of the grid as follows:

A cell (x, y) then has the same colouring as every cell:

(x, y) + m(u_x, 0) + n(v_x, v_y) = (x + m * u_x + n * v_x, y + n * v_y)

where addition is performed in the group Z_{u_v} x Z_{u_x * v_y / gcd(v_x, v_y)}.

We can think of this as (x, y) having the same colour of all cells that can be reached from it through adding a linear combination of the vectors (u_x, 0) and (v_x, v_y), and fully determines the grid colouring up to isomorphism, which will have C = u_x * v_y colours. We then assign one colour as floor space, and iterate over all possible partitions of the remaining C-1 colours into labeled partition classes.

Each possible partition is generated and examined. If a partition class passes the rules below, it is an aggregate wall, i.e. multiple cells comprising a wall. If it does not, then we consider it a class of pillars, i.e. fixed walls that cannot be removed.

Adjacency of c in d means that c is in the neighbourhood of d. If d is a partition class, then we consider the neighbourhood of d to be the union of the neighbourhoods of all cells in d.

Then the rules are as follows:

1. Every partition class representing a "wall" must be contiguous (aka connected), in that you can reach any cell from any other.

2. Every floor space must be surrounded by four partition classes.

3. Every partition class must be adjacent to two floor spaces.

4. A partition class is adjacent to a floor space if and only if the floor space is adjacent to the partition class.

(Note that with regards to adjacency, we ignore the border and pretend that the maze is infinite in size for the purposes of adjacency and neighbourhood calculations.)

If these criterion are met by a wall partition, we then consider the partition classes to be aggregate walls consisting of multiple cells as mentioned above.

We can then run the wall-based Prim's algorithm on the structure to get a perfect maze, although some walls and rooms may be larger than in normal Prim's. It may be possible to run other maze generation algorithms that iterate over walls as well.

The approach is detailed here:
https://www.gamasutra.com/blogs/HermanTulleken/20161005/282629/Algorithms_for_making_more_interesting_mazes.php

Given an existing perfect maze and an objective function O(M) on mazes (e.g. branching factor, distance from start to end, etc):

1. Perturb by adding a number of walls to the maze.

2. Carve passages using some algorithm to result in a number of perfect maze children.

3. Breed the child mazes in some way. (Could be via dividing mazes into quadrants and swapping diagonal quadrants, or something similar.)

4. Kill off the worst children with respect to O(M).

5. Iterate for some number of generations.

From Wikipedia:

A binary tree maze is a standard orthogonal maze where each cell always has a passage leading up or leading left, but never both. To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left. Always pick the same direction for cells on the boundary, and the end result will be a valid simply connected maze that looks like a binary tree, with the upper left corner its root.

Given a maze, you can make it unicursal by choosing an entrance on the boundary, and then bisecting each passageway. For every dead end, carve a gap.

This will give a unicursal maze (aka labyrinth) of 2w x 2h.

https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method

I need to learn more about CMake before doing this, but I feel that - while the project builds - it could be much better.

Right now, we have the source split up into multiple directories as I want, but I'm not sure how this will affect installation or what needs to be done for this. Look into this.

Right now, I'm just using the basic doxygen config and haven't even yet generated the documentation so I have no idea what it will look like.

Idea:

• Start in NW corner.

• With probability p, carve walls to the east, keeping track of the grouping of cells.

• When probability fails, pick one amongst the grouping of cells at random and carve to the south.

• Step east through the wall and continue until the end of the row.

• Iterate over rows.

This is relevant for #25 and #26.

More test cases via https://github.com/catchorg/Catch2 are needed.

The BinaryTreeMazeGenerator should accept a probability for burrowing EAST vs. burrowing SOUTH.

...using JSON? Unsure as of yet.

This is an umbrella task for PRs that are related to adding documentation to the library.

http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm

Clearly, the standard braiding approach of "remove one cell" is not going to work on the grid colouring mazes of #53 and #54. It will be necessary to braid them actually removing larger numbers of walls, and preferably, wall segments that are the same as the ones used to build them in the first place.

Look into this and see what can be done.

http://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm

See note in #25.

Make it possible for a maze to reflect itself in the horizontal, vertical, and diagonals, and all rotations by multiples of 90 degrees.

https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim's_algorithm

A ThickMaze is a maze where the walls themselves do not have zero thickness as in Maze.

Implementing ThickMaze will allow implementation of the cellular automata algorithms (see #23), and the injective mapping between Maze and a subset of ThickMaze (see #25, #26).

http://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm.html

See here:

http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm

Create a visualization interface (preferably in Qt5) that shows:

1. Mazes being created step-by-step through a listener - publisher method.

2. Mazes being similarly solved.

A number of MazeAttributes and Exceptions are applicable to ThickMaze as well as Maze, and should be in a shared namespace, say vorpal::shared.

http://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm

Add a listener implementation for use by the MazeGenerator class and forthcoming MazeSolver class, and have those algorithms publish each step as they run.

This will be done with the Boost Signals2 library.

This is a placeholder task, as I'm not sure to what extent I want to use Boost.Graph in the code.

For now, I will create a third class of maze (that are equivalent to regular thin Maze) called GraphMaze that will use Boost.Graph.

This deals with issue #23.

After the cellular automata algorithms have run, seldom do they generate usable mazes.

What we should do is determine connected components (using disjoint sets?), and then carve passages between them so that they can actually be mazes. This won't make them perfect spanning trees, but it will help.

A maze is a braid maze if it contains no dead ends; it must then not be a perfect maze.

The simplest way to make any maze into a braid maze is to iterate over the dead ends and remove one interior wall from each.

Implement braid mazes for ThickMaze.

The CMakeLists.txt files for the projects within src are too repetitive. They should instead just need to define public headers, private headers, and source files, and then call a function to do the rest.

Similarly, in the src/CMakeLists.txt file, we should only have to have a list of subpackages, and use functions to do all the rest of the work to avoid the repetition.

Some resources here:

https://github.com/theJollySin/mazelib/blob/master/docs/MAZE_SOLVE_ALGOS.md

Write cellular automata maze generation algorithms to produce ThickMaze instances using:

• Maze 12345/3

• Mazectric 1234/3

Is there a way that we can use cellular automata to produce regular Mazes?

Select a good C++ testing framework and move existing test cases to use it.

Example:

https://github.com/google/googletest/blob/master/googletest/docs/Primer.md

See Maze for how this is done there: do the same for ThickMaze.

These need to be more globally available for purposes such as homomorphisms.

Refactor GridColouring to offer a begin and an end method so that it can be used with for range based loops.

There is an injective mapping from a Maze of dimension (w, h) to a ThickMaze of dimension (2w+1, 2h+1), and thus, every MazeGenerator implemented so far can be used to implement a subset of ThickMaze, i.e. the one where wall segments always occur in contiguous odd numbers > 1.

This mapping is invertible, so if a ThickMaze has the property that all wall segments occur in contiguous odd numbers > 1, we should be able to map it to a unique Maze, but I'm not sure yet I'll bother to implement that mapping. See #26.

We could easily create a parameterized superclass of the various MazeGenerators instead of the three unrelated ones that there will be when I create GraphMazeGenerator.

This could be extended to various other things, like the maze types themselves, which would force and encapsulate some standard functions, like starting cell, ending cells, walls, etc.

We can extend Prim's wall variation algorithm for thick mazes (and possibly any other wall processing algorithm) by using grid colourings, and then determining which sets of colours can be identified as walls, thus making walls bigger than one cell.

See the algorithms here:
https://www.gamasutra.com/blogs/HermanTulleken/20161005/282629/Algorithms_for_making_more_interesting_mazes.php

This class is rather slow: analyze the current approach's complexity and see if we can do anything significant to optimize it.

A maze is a braid maze if it contains no dead ends; it must then not be a perfect maze.

The simplest way to make any maze into a braid maze is to iterate over the dead ends and remove one interior wall from each.

Implement braid mazes for Maze.

Having everything in one large directory is hardly ideal: organize by namespace and create the necessary cmake files.

Also use this opportunity to clean up namespaces.

Think about this further and the best way to do it. It isn't as immediately obvious to me as it is with regular Mazes.

We should be able to implement at least four algorithms, namely:

1. DFS

2. BFS

3. Kruskal

4. Prim

using the Boost.Graph algorithms. I'm unsure if these will work , as they may be deterministic, in which case, they will give consistent results, which is not what we want.