The graph and resulting tree can be visualized more readily by running the algorithm on a small, 5x5 grid of cells as demonstrated in the images and video below.Ī The initial graph G where each cell - or node - depicted as a blue circle is connected to its neighbors by an edge depicted as a black line. The algorithm then finds, based upon a random seed, a spanning tree - or tree composed of all vertices but only some of the edges - of this graph G. When considered in this manner, the grid can be considered a graph Gin which each cell is a node connected to each of its four neighbors by a wall the exception to this rule is for edge and corner cells which have 3 and 2 neighbors, respectively.
Minecraft maze generator algorithm series#
In two dimensions, a maze is a series of paths separated by walls, and to simplify the generation one can think of the maze as a 2-dimensional grid. To understand this type of maze generation algorithm in more detail, it helps to understand how the maze is represented as a tree, followed by how the traversal algorithm can be used to generate the maze. To generate the tree, a random depth-first search is used - an algorithm which builds the tree randomly until the tree, or maze, is complete. In this tutorial I discuss one particular maze generation algorithm that treats a completed maze as a tree, the branches of the tree representing paths through the maze. There are several maze generation algorithms that can be used to randomly generate n-dimensional mazes.
0 kommentar(er)
