Hash-optimization and Wilson-maze generation algorithm

Question

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.

I will really appreciate any advice or comments about optimization and speed of the both algorithm.

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.

• ferada: 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!
• RussDragon: 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.
• ferada: I think you can still edit it, that'd prevent people from commenting on it unnecessarily :)
• RussDragon: 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.
• Felix Dombek: I think you mean indentation.

Answer 1

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.

• RussDragon: Yes, you are right about it. But the problem is, that Lua has 2 different values for «false». (false itself and nil, which means variable hadn't been declared/defined). The same for true – true is everything, that is not false or nil, so == true / == false are just for clarifying which values program should waiting for.
• greybeard: 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...))
• RussDragon: @greybeard Thank you for your advices. I will edit code when I arrive at home. Intimidation and conditions are important, of course, but the main problem is speed of that code, and it won't help a lot.