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:
Every partition class representing a "wall" must be contiguous (aka connected), in that you can reach any cell from any other.
Every floor space must be surrounded by four partition classes.
Every partition class must be adjacent to two floor spaces.
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.
sraaphorst
commented
6 years ago
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, andv_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 haveC = u_x * v_ycolours. We then assign one colour as floor space, and iterate over all possible partitions of the remainingC-1colours 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
cindmeans thatcis in the neighbourhood ofd. Ifdis a partition class, then we consider the neighbourhood ofdto be the union of the neighbourhoods of all cells ind.Then the rules are as follows:
Every partition class representing a "wall" must be contiguous (aka connected), in that you can reach any cell from any other.
Every floor space must be surrounded by four partition classes.
Every partition class must be adjacent to two floor spaces.
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