# Hash-optimization and Wilson-maze generation algorithm

I've finished optimization of Wilson algorithm (maze generation) from "silly and slow" algorithm of choosing unvisited cells:

function aux.wilson()
local unvisited_cells = aux.width * aux.height

local y, x = math.random(aux.sy, aux.height), math.random(aux.sx, aux.width)
aux.grid[y][x].visited = true
unvisited_cells = unvisited_cells - 1

local stx, sty
while true do
stx, sty = math.random(aux.sx, aux.width), math.random(aux.sy, aux.height) -- Start point
if aux.grid[sty][stx].visited == false then break end
end

local ix, iy = stx, sty -- sub-vertecies

while unvisited_cells ~= 0 do
if aux.grid[iy][ix].visited == true then
aux.grid[sty][stx].visited = true
while unvisited_cells ~= 0 do
if stx == ix and sty == iy then
while true do
stx, sty = math.random(aux.sx, aux.width), math.random(aux.sy, aux.height)
if aux.grid[sty][stx].visited == false then break end
end
break
else unvisited_cells = unvisited_cells - 1 end

local dir = aux.grid[sty][stx].dir
if dir == "UP" then
aux.grid[sty-1][stx].visited = true
aux.grid[sty-1][stx].bottom_wall = false
sty = sty - 1
elseif dir == "DOWN" then
aux.grid[sty+1][stx].visited = true
aux.grid[sty][stx].bottom_wall = false
sty = sty + 1
elseif dir == "LEFT" then
aux.grid[sty][stx-1].visited = true
aux.grid[sty][stx-1].right_wall = false
stx = stx - 1
elseif dir == "RIGHT" then
aux.grid[sty][stx+1].visited = true
aux.grid[sty][stx].right_wall = false
stx = stx + 1
end
end
ix, iy = stx, sty
end

local dir = aux.dirs[math.random(1, 4)]
if dir == "UP" then -- UP
if iy-1 >= aux.sy then
aux.grid[iy][ix].dir = "UP"
iy = iy - 1
end
elseif dir == "DOWN" then -- DOWN
if iy+1 <= aux.height then
aux.grid[iy][ix].dir = "DOWN"
iy = iy + 1
end
elseif dir == "RIGHT" then -- RIGHT
if ix+1 <= aux.width then
aux.grid[iy][ix].dir = "RIGHT"
ix = ix + 1
end
elseif dir == "LEFT" then -- LEFT
if ix-1 >= aux.sx then
aux.grid[iy][ix].dir = "LEFT"
ix = ix - 1
end
end
end
end


to a little bit more clever:

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 unvisited_cells = aux.width * aux.height
local CellsHash = aux.hashCells(aux.grid)
local key = next(CellsHash, nil)
local vx, vy = aux.deHashKey(key)
CellsHash[key] = nil
aux.grid[vy][vx].visited = true

unvisited_cells = unvisited_cells - 1

key = next(CellsHash, nil)
vx, vy = aux.deHashKey(key)
CellsHash[key] = nil

local stx, sty = vx, vy

local ix, iy = stx, sty -- sub-vertecies

while unvisited_cells ~= 0 do
if aux.grid[iy][ix].visited == true then
aux.grid[sty][stx].visited = true
CellsHash[aux.hashKey(stx, sty)] = nil
while unvisited_cells ~= 0 do
if stx == ix and sty == iy then
key = next(CellsHash, nil)
vx, vy = aux.deHashKey(key)
CellsHash[key] = nil

stx, sty = vx, vy
break
else unvisited_cells = unvisited_cells - 1 end

local dir = aux.grid[sty][stx].dir
if dir == "UP" then
aux.grid[sty-1][stx].visited = true
CellsHash[aux.hashKey(stx, sty-1)] = nil
aux.grid[sty-1][stx].bottom_wall = false
sty = sty - 1
elseif dir == "DOWN" then
aux.grid[sty+1][stx].visited = true
CellsHash[aux.hashKey(stx, sty+1)] = nil
aux.grid[sty][stx].bottom_wall = false
sty = sty + 1
elseif dir == "LEFT" then
aux.grid[sty][stx-1].visited = true
CellsHash[aux.hashKey(stx-1, sty)] = nil
aux.grid[sty][stx-1].right_wall = false
stx = stx - 1
elseif dir == "RIGHT" then
aux.grid[sty][stx+1].visited = true
CellsHash[aux.hashKey(stx+1, sty)] = nil
aux.grid[sty][stx].right_wall = false
stx = stx + 1
end
end
ix, iy = stx, sty
end

local dir = aux.dirs[math.random(1, 4)]
if dir == "UP" then -- UP
if iy-1 >= aux.sy then
aux.grid[iy][ix].dir = "UP"
iy = iy - 1
end
elseif dir == "DOWN" then -- DOWN
if iy+1 <= aux.height then
aux.grid[iy][ix].dir = "DOWN"
iy = iy + 1
end
elseif dir == "RIGHT" then -- RIGHT
if ix+1 <= aux.width then
aux.grid[iy][ix].dir = "RIGHT"
ix = ix + 1
end
elseif dir == "LEFT" then -- LEFT
if ix-1 >= aux.sx then
aux.grid[iy][ix].dir = "LEFT"
ix = ix - 1
end
end
end
end


And I noticed, that on the small grid (100x100), it works almost the same, but on the bigger grid (like 1000x1000), first version works in about 3-4 seconds, but the second version just freezes. And I really can' understand why. I don't see any operations, that can cause big-time issues.

UPD1: I forgot to say, that there is no problem in creating hash-table or grid itself, it is done in 2-3 seconds always. So, I suspect problem either in "next" function, or, maybe, in hash-function, that creates conflicts and make endless-loop.

UPD2: Ok, after some research and profiling I've found, that the problem was in a next function. Hash-table and collision solving-mechanism that are hidden behind Lua next-function are really slow for this purpose.

• Welcome to Code Review, your first post looks good except perhaps the indentation suffered a bit while pasting here? Otherwise hope you get some good answers! Nov 9, 2016 at 19:18
• Thank you! About indentation, I think, the problem is in the Lua itself. It has many "do"/"end" blocks, that makes code slightly unreadable. And something went wrong with pasting from Sublime Text 3 too, as I can see. But, anyway, next time I will try to reindent it better. Nov 9, 2016 at 19:23
• I think you can still edit it, that'd prevent people from commenting on it unnecessarily :) Nov 9, 2016 at 19:35
• I don't really know how to fix it, because it is original Lua intimidation, and any attempt to change it will probably make code fully unreadable. Nov 9, 2016 at 19:43
• I think you mean indentation. Nov 10, 2016 at 10:06

I don't know Lua, but one thing that stands out is your use of == true/== false in if statements.
Code in any language gets more readable by omitting == true and substituting not x for x == false. The expressions are already usable as booleans, you don't have to explicitly compare them to a constant.
• so == true / == false are just for clarifying which values program should waiting for my opinion: Don't. - it is bound to irritate readers (Just why do other values need to be excluded here?) and may introduce errors if other values interpreted the same do occur and shouldn't be handled differently after all. (If and when you are convinced standard evaluation to be inappropriate, leave a (code-) comment. (Formulating that may even lead to an insight/cleaner code…)) Nov 10, 2016 at 3:12