8
\$\begingroup\$

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.

\$\endgroup\$
14
  • \$\begingroup\$ 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! \$\endgroup\$ Commented Nov 9, 2016 at 19:18
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 9, 2016 at 19:23
  • \$\begingroup\$ I think you can still edit it, that'd prevent people from commenting on it unnecessarily :) \$\endgroup\$ Commented Nov 9, 2016 at 19:35
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 9, 2016 at 19:43
  • \$\begingroup\$ I think you mean indentation. \$\endgroup\$ Commented Nov 10, 2016 at 10:06

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 9, 2016 at 18:13
  • \$\begingroup\$ 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…)) \$\endgroup\$ Commented Nov 10, 2016 at 3:12
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Nov 10, 2016 at 5:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.