February 6, 2017 at 18:49

Classical maze generation algorithms. Part 2: immersion in chance

  • Tutorial


Foreword


→ The first part

So. Assessing the response of the Habr audience and sorting things out, I set about writing the second article from the cycle. The reaction of the public was much more positive than my assumptions, which means that we continue the conversation on one of the most interesting topics of procedural generation - the creation of mazes.

In this part, we will talk about what is random and pseudo-random generation, what algorithms can give us labyrinths that are equally unlike each other, and what are their disadvantages. The heroes of our adventure today will be the Wilson algorithm and the Aldous-Broder algorithm to create a random spanning tree (Uniform Spanning Tree). CAUTION TRAFFIC .

Let's remember what the ideal mazes in question are. If from each vertex of the graph to any other there is exactly one path and it is impossible to go through all the vertices without going through the same edge twice, then we call such a graph a spanning tree . If in the labyrinth under consideration from each cell to any other there is exactly one passage and you cannot visit all the cells without going through the same corridor twice, then we say that such a labyrinth is ideal . The meaning does not change for one simple reason - labyrinths are graphs, which I wrote about in a previous article. If you have not read it yet, I strongly advise you to scroll a little higher, follow the link and familiarize yourself with it before moving on.

And although the algorithms presented in this part are very slow and “stupid”, they need to be dealt with, since they are the foundation for our entire topic and for all my articles. The main reason why I did not immediately start with them is that Wilson is not very easy to implement and understand for beginners, which does not prevent him from being extremely curious.

About Lua
In Wilson's algorithm, and possibly in some others that I will write about, the next (table [, index]) function is used to select a random cell that has not been visited yet. Its description is from the official Lua documentation:
Allows an application to get all the fields in a table. The first parameter is the table, the second is the index in this table. next returns the next index in the table and its corresponding value. If the second parameter is nil, next returns the starting index and the value associated with it. When the last index is called, or with nil in an empty table, next returns nil. If the second parameter is missing, it is interpreted as nil. In particular, you can use next (t) to check if the table is empty or not.

Therefore, instead of selecting a cell using math.random and checking whether it has been processed or using a stack of stack cells with a hash table to track its location, you can use only one hash table, the keys in which will be hashed with coordinates and take elements from it with next. 

key = next(cellsHash, nil)
local start_x, start_y = aux.deHashKey(key)
cellsHash[key] = nil — Напомню, присваивание nil удаляет элемент/поле


Displacement and randomness


What do we mean by random generation? Can we say that if in the second labyrinth, unlike the first, two walls are missing in the south, then they are completely random? Or if the first maze has two horizontal corridors more? Yes and no.

Speaking of randomness in the labyrinths, we must be clearly aware of what we mean. Let's look at the result of the binary tree algorithm:





As you can see, although the labyrinths themselves are completely different, their offset is slightly different.

Did we get a random result? Yes. Can we consider him as such? Well, in my opinion, no.

The problem is bias, which largely determines "randomness." Algorithms that, by definition, should create random labyrinths, eventually create similar ones. If the "similarity" is pronounced, as in a binary tree, we say that such a maze is easily solved. If, when comparing several labyrinths, it is difficult for us to say unequivocally what the algorithm gravitates to, we say that such a labyrinth is more difficult to solve. To find the bias, we need to compare several generation results and build a statistical model, according to which we could write a smarter search for the path or by ourselves, more “smart” to solve labyrinths of this type. For example, we can say that the binary tree algorithm has n times more horizontal passages than vertical passages. This means that it will be possible to take into account the data and speed up the process of finding an exit.

But what if we want no bias at all? So that, for example, from 9 unconnected points of the graph, each time we get a completely different spanning tree from the rest? Then we need each direction for the algorithm to be equivalent. This means that we are allowed to go through the already completed peaks, therefore, in each iteration of the cycle we will randomly choose one of four directions, regardless of whether we were there or not. The only condition is not to go beyond the field.

Speaking of the term Uniform Spanning Tree. We already know what a spanning tree is. Having connected all the vertices of the graph with edges so that it was impossible to get from any vertex to another without passing the same edge twice, we get a spanning tree. But if there are more than two vertices in the graph, then there may be more tree variations, right? So, the Uniform Spanning Tree is one equally likely variation of the spanning tree in a certain graph.

So. We want completely random labyrinths, completely different from each other, and even ready to sacrifice speed. Then let's get acquainted with the Aldous-Broder and Wilson algorithms.

Aldous-Broder Algorithm









Description

Remember I said that the binary tree algorithm is the easiest to understand? So, I was cunning. It is really simpler to implement, since there we always deal with only one direction and one side under consideration, but in the primitive and “stupid” Aldous-Broder algorithm went far ahead. The whole point is to wander aimlessly around the field in the hope of stumbling onto the top of the spanning tree to be created and attach another one, and then again randomly select a point in the maze and walk until you hit one of the connected ones.

Aldous-Broder is free from any bias. Absolutely. All the labyrinths obtained with its help are absolutely random and do not look alike. The algorithm does not have preferences in directionality, complexity or any other characteristics. The resulting mazes are random and equally probable.

The problem may be the imperfection of random number generators, which themselves may gravitate to some values ​​and give them more often. But if you use, for example, a random generator based on natural noise (wind, uranium decay), then, perhaps, you can finally fully enjoy the operation of the algorithm.

Admittedly, observing his work truly gives an awareness of all the perishability and meaninglessness of being. To write a gif with his animation, I spent a lot of time, because he stubbornly did not want to fit in 30 seconds in a 5 × 5 field. When it remained to connect only one last unchecked cell to the spanning tree, Aldous-Broder went to another corner and wrapped circles there. I had to significantly increase the speed of animation and reduce the field so that, finally, he managed to go around all the cells of the maze.

It was created by two independent researchers who studied equiprobable variants of spanning trees: David Aldous, a professor at the University of California, Berkeley and Andrei Broder, a scientist who now works at Google. It is difficult to say unequivocally in which area these studies would be useful. However, in addition to labyrinths, the algorithm often pops up in works on mathematical probability, which, however, is not surprising, given the principle of its operation.

Formal algorithm:

  1. Select a random vertex (cell). Completely random;
  2. Select a random neighboring vertex (cell) and go into it. If it has not been visited, add it to the tree (connect with the previous one, remove the wall between them);
  3. Repeat step 2 until all cells are visited.

Work example
Our current position on the field is highlighted in red.

We start from the upper left corner. Nothing unusual here.



We randomly decide to go to the right and remove the wall between the two cells. Ok, we do.



Bad luck. Our RNG says that we go back, that is, to the left.



Now down. Along the way, we connect all unvisited cells and remove the walls between them.



Lucky again. Way down!



Okay, one return back can be forgiven.


We choose to go to the right and remove the wall.



And here we are twice unlucky and we return to the very beginning.




The choice fell twice to go right. Great, at least some variety.




We go down below and remove the wall.



And here, although we move to the next cell, we do not remove the wall, since they are already in the same tree.



It's time to wander aimlessly, to walk.






We return to cell 2-2 and go down below, removing the wall.



We complete our sweeping and get the generated maze.



Pros:

  • There is no bias;
  • Labyrinths are absolutely random, therefore it is impossible to create a specific algorithm for solving them;
  • The complexity of the decision for the person;
  • Simple implementation;

Minuses:

  • Speed. While the maze will be generated, you will have time to grow old and die;
  • It does not allow generating endless labyrinths;
  • A strong drop in efficiency at the end of generation;

Implementation
local mod = {}
local aux = {}
aux.width = false
aux.height = false
aux.sx = false
aux.sy = false
aux.grid = false
aux.dirs = {"UP", "DOWN", "LEFT", "RIGHT"}
function aux.createGrid (rows, columns)
  local MazeGrid = {}
  for y = 1, rows do 
   MazeGrid[y] = {}
   for x = 1, columns do
    MazeGrid[y][x] = {visited = false, bottom_wall = true, right_wall = true}
  end
end  
return MazeGrid
end
function mod.createMaze(x1, y1, x2, y2, grid)
  aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1
  aux.grid = grid or aux.createGrid(y2, x2)
  aux.aldous_broder()
  return aux.grid
end
function aux.aldous_broder()
  local unvisited_cells = aux.width * aux.height
  local ix = math.random(aux.sx, aux.width)
  local iy = math.random(aux.sy, aux.height)
  aux.grid[iy][ix].visited = true
  unvisited_cells = unvisited_cells - 1
  while unvisited_cells ~= 0 do
   local dir = aux.dirs[math.random(1, 4)]
   if dir == "UP" then
    if iy-1 >= aux.sy then
     if aux.grid[iy-1][ix].visited == false then
      aux.grid[iy-1][ix].bottom_wall = false
      aux.grid[iy-1][ix].visited = true 
      unvisited_cells = unvisited_cells - 1 
    end
    iy = iy-1
  end
  elseif dir == "DOWN" then
    if iy+1 <= aux.height then 
     if aux.grid[iy+1][ix].visited == false then 
      aux.grid[iy][ix].bottom_wall = false 
      aux.grid[iy+1][ix].visited = true
      unvisited_cells = unvisited_cells - 1 
    end
    iy = iy+1
  end
  elseif dir == "RIGHT" then
    if ix+1 <= aux.width then
     if aux.grid[iy][ix+1].visited == false then 
      aux.grid[iy][ix].right_wall = false
      aux.grid[iy][ix+1].visited = true
      unvisited_cells = unvisited_cells - 1 
    end
    ix = ix+1
  end
  elseif dir == "LEFT" then
    if ix-1 >= aux.sx then
     if aux.grid[iy][ix-1].visited == false then
      aux.grid[iy][ix-1].right_wall = false
      aux.grid[iy][ix-1].visited = true
      unvisited_cells = unvisited_cells - 1 
    end
    ix = ix-1
    end
  end
  end
end
return mod


Wilson Algorithm








Description

Congratulations, we finally got to something more serious. Wilson's algorithm is much more complicated than all the previous ones both in implementation and in understanding. Wilson's goal, like that of his stupider partner Aldous-Broder, is to generate an equally probable random spanning tree. And although the principle of operation is somewhat similar, the details vary greatly.

The algorithm is still based on the equally probable random choice of the side of movement in the maze (graph), with two important differences:

Moving around the field, we “remember” all the vertices we visited before the vertex of the spanning tree was found. As soon as we come across an already added vertex, we attach the resulting subgraph (branch) to our generated tree. If a loop is created in the subgraph, then delete it. By a loop I mean a connection of some vertex that is already in a temporary subgraph with it, but at a different point. In other words, there should not be vertices with more than 2 edges. If you don’t understand now, it’s not scary - you will clearly see further on the example of work.

After attaching the subgraph to the spanning tree, the choice of the next random point occurs exclusively from the vertices not yet attached. Consequently, unlike Aldous-Broder, Wilson is devoid of the lack of aimless wandering around already processed peaks.

Wilson's algorithm, like Aldous-Broder, generates absolutely random labyrinths without any bias. The algorithm does not have preferences in directionality, complexity or any other characteristics. Unfortunately, to obtain the best results, you should use hardware random number generators that do not have preferences in numbers.

The algorithm itself was published by David Wilson in 1996 in his work on generating equiprobable random spanning trees. As before, in addition to labyrinths, materials pop up on various sites devoted to mathematical probabilities. Moreover, I came across several interesting publications regarding the Uniform Spanning Tree and the Wilson algorithm in particular. If in one of them the algorithm itself is described more, then in the other as a whole the concept itself and the mathematical basis of spanning trees.

If readers will be interested, perhaps I will write part 2a, where I will cite the works themselves and their partial translation. The main reason why I avoid mathematical justification here is that my articles are aimed at beginners and people who are more interested in programming than dry mathematics.

Formal algorithm:

  1. Select a random vertex that does not belong to the spanning tree and add it to the tree;
  2. Select a random vertex that does not belong to the spanning tree and start traversing the graph (maze) until we arrive at the already added vertex of the tree; If a cycle forms, remove it;
  3. Add all vertices of the resulting subgraph to the spanning tree;
  4. Repeat steps 2-3 until all vertices are added to the spanning tree.

Work example
The first vertex of the tree is highlighted in green. Red - the created branch (subgraph).

Traditionally, you need to get into the upper left corner. We begin to build a branch from coordinate 3-2.






Now is an interesting and important point. The algorithm decides to go up, thereby closing the branch at coordinate 2-2.



We delete the resulting cycle and start from 2-2 to build again.


habrastorage.org/files/e9c/8e6/46a/e9c8e646af564a42bbb391fbe263044b.png

Great, the algorithm decided to go up and thereby joined the main tree. We remove the walls on the way and select the next cell.




Again, they touched a recently created tree, removed the walls and started again.






We closed, removed the cycle, continued with 2-3 again.



Connected to a tree, cleared the walls of the path. We continued our journey in a new cage.





Again connected to the main tree, removed the walls, finished the maze.



Pros:

  • There is no bias;
  • Labyrinths are absolutely random, therefore it is impossible to create a specific algorithm for solving them;
  • The complexity of the decision for the person;
  • There is no meaningless wandering;
  • Speed ​​compared to Oldos-Broder is several times faster;

Minuses:

  • Difficult implementation;
  • Speed ​​drops at the beginning of generation;
  • Greater memory requirements than Aldous-Broder;

Implementation
local mod = {}
local aux = {}
aux.width = false
aux.height = false
aux.sx = false
aux.sy = false
aux.grid = false
aux.dirs = {"UP", "DOWN", "LEFT", "RIGHT"}
function aux.createGrid (rows, columns)
 local MazeGrid = {}
 for y = 1, rows do 
	MazeGrid[y] = {}
	for x = 1, columns do
		MazeGrid[y][x] = {visited = false, bottom_wall = true, right_wall = true}
	end
end  
 return MazeGrid
end
function mod.createMaze(x1, y1, x2, y2, grid)
aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1
aux.grid = grid or aux.createGrid(y2, x2)
aux.wilson()
return aux.grid
end
function aux.hashKey(x, y)
 return x * aux.height + (y - 1)
end
function aux.deHashKey(value)
 return math.floor(value/aux.height), value%aux.height + 1
end
function aux.hashCells(grid)
 local vtable = {}
 for yk, yv in pairs(grid) do
	for xk, xv in pairs(yv) do
		if xv.visited == false then
			vtable[aux.hashKey(xk, yk)] = xv
		end
	end
 end
 return vtable
end
function aux.wilson()
 local cellsHash = aux.hashCells(aux.grid) -- Вершины, не находящиеся в дереве
 local dirsStack = {} -- Стак направлений
 local dsHash = {}
 local dsSize = 0
-- Создаем дерево
 local key, v = next(cellsHash, nil)
 v.visited = true
 cellsHash[key] = nil
 while next(cellsHash) do -- Пока есть необработанные вершины, работает
	key = next(cellsHash, nil) -- Получаем ключ и по нему координаты клетки
	local start_x, start_y = aux.deHashKey(key)
	local ix, iy = start_x, start_y
	while not aux.grid[iy][ix].visited do  -- Ходим, пока не найдем относящуюся к дереву клетку
		local dir = aux.dirs[math.random(1, 4)]
		local isMoved = false
		key = aux.hashKey(ix, iy)
		if dir == "UP" and iy-1 >= aux.sy then iy = iy - 1 isMoved = true
		elseif dir == "DOWN" and iy+1 <= aux.height then iy = iy + 1 isMoved = true
		elseif dir == "LEFT" and ix-1 >= aux.sx then ix = ix - 1 isMoved = true
                elseif dir == "RIGHT" and ix+1 <= aux.width then ix = ix + 1 isMoved = true end
		if isMoved then -- Если мы можем двигаться, тогда проверяем на циклы
			if dsHash[key] then -- Удаление циклов
				dirsStack[dsHash[key]].dir = dir
				for i = dsHash[key]+1, dsSize do
					local x, y = aux.deHashKey(dirsStack[i].hashref)
					dsHash[dirsStack[i].hashref] = nil
					dirsStack[i] = nil
					dsSize = dsSize - 1
				end
			else
				local x, y = aux.deHashKey(key) -- Добавление в стак направлений
				dsSize = dsSize + 1
				dsHash[key] = dsSize
				dirsStack[dsSize] = {dir = dir, hashref = key}
			end
		end
	end
	for i = 1, dsSize do -- Проквапывание пути
		aux.grid[start_y][start_x].visited = true
		cellsHash[aux.hashKey(start_x, start_y)] = nil
		aux.grid[start_y][start_x].point = false
		local dir = dirsStack[i].dir
		if dir == "UP" then
			aux.grid[start_y-1][start_x].bottom_wall = false
			start_y = start_y - 1
		elseif dir == "DOWN" then
			aux.grid[start_y][start_x].bottom_wall = false
			start_y = start_y + 1
		elseif dir == "LEFT" then
			aux.grid[start_y][start_x-1].right_wall = false
			start_x = start_x - 1
		elseif dir == "RIGHT" then 
			aux.grid[start_y][start_x].right_wall = false
			start_x = start_x + 1
		end
	end
	dsHash, dirsStack, dsSize = {}, {}, 0 -- Обнуление стака направлений
 end
end
return mod


Epilogue:


Summarizing all of the above, it is worth noting that although we got to more complex algorithms and figured out some new (for someone) graph concepts, the main difficulties are still to come. The unobviously confusing algorithms of Eller, Kraskal and Prima, based solely on working with graphs and trees, are preparing for us complicated, albeit interesting, publications. However, before you start writing them, you should look at the search algorithms with a return and something called "Catch & Kill", whose work on generating the maze is very different from everyone else. I gave a hint about the next article.

What else. In the comments to the previous part, some people asked or threw off their generation algorithms, which was extremely entertaining and joyful. If you once implemented the creation of labyrinths in your own invented way and can remember it now - please share. Perhaps, with your permission, in some of the articles I will write about him. In general, I am happy with any interesting stories and recollections on the topic. It doesn’t matter if you remember how to draw labyrinths in a notebook at school or on a computer at a university.

Well, and as always. Suggestions, criticism, comments are always welcome and if you like the topic and want to see the next part, write about it in the comments.

Sources of algorithms on Lua + render on Love2D (the code is laid out at the request in the comments. Not refactored):
Github
Tags:

Also popular now: