Maze generation: Difference between revisions

Content added Content deleted

Inline

@@ Line 3,328: / Line 3,328: @@
 -- Fisher-Yates shuffle from http://santos.nfshost.com/shuffling.html
 function shuffle(t)
-	for i = 1, #t - 1 do
+  for i = 1, #t - 1 do
-		local r = math.random(i, #t)
+    local r = math.random(i, #t)
-		t[i], t[r] = t[r], t[i]
+    t[i], t[r] = t[r], t[i]
-	end
+  end
 end
--- builds a width-by-height grid of falses
+-- builds a width-by-height grid of trues
 function initialize_grid(w, h)
-	local a = {}
+  local a = {}
-	for i = 1, h do
+  for i = 1, h do
-		table.insert(a, {})
+    table.insert(a, {})
-		for j = 1, w do
+    for j = 1, w do
-			table.insert(a[i], false)
+      table.insert(a[i], true)
-		end
+    end
-	end
+  end
-	return a
+  return a
 end
 -- average of a and b
 function avg(a, b)
-	return (a + b) / 2
+  return (a + b) / 2
 end
+dirs = {
+  {x = 0, y = -2}, -- north
+  {x = 2, y = 0}, -- east
+  {x = -2, y = 0}, -- west
+  {x = 0, y = 2}, -- south
+}
 function make_maze(w, h)
-	w = w or 16
+  w = w or 16
-	h = h or 8
+  h = h or 8
-	local map = initialize_grid(w*2+1, h*2+1)
+  local map = initialize_grid(w*2+1, h*2+1)
-	function walk(x, y)
+  function walk(x, y)
-		map[y][x] = true
+    map[y][x] = false
-		local d = {
+    local d = { 1, 2, 3, 4 }
+    shuffle(d)
-			{x = x, y = y-2}, -- north
+    for i, dirnum in ipairs(d) do
-			{x = x+2, y = y}, -- east
+      local xx = x + dirs[dirnum].x
-			{x = x-2, y = y}, -- west
+      local yy = y + dirs[dirnum].y
-			{x = x, y = y+2}, -- south
+      if map[yy] and map[yy][xx] then
-		}
+        map[avg(y, yy)][avg(x, xx)] = false
-		shuffle(d)
+        walk(xx, yy)
-		for i, dir in ipairs(d) do
+      end
-			local xx = dir.x
+    end
-			local yy = dir.y
+  end
-			if map[yy] == nil then
-				-- out of bounds north or south
-			elseif map[yy][xx] == nil then
-				-- out of bounds east or west
-			elseif map[yy][xx] then
-				-- already visited
-			else
-				if xx == x then
-					map[avg(y, yy)][x] = true
-				else -- by elimination, yy == y
-					map[y][avg(x, xx)] = true
-				end
-				walk(xx, yy)
-			end
-		end
-	end
-	walk(math.random(1, w)*2, math.random(1, h)*2)
+  walk(math.random(1, w)*2, math.random(1, h)*2)
-	local s = {}
+  local s = {}
-	for i = 1, h*2+1 do
+  for i = 1, h*2+1 do
-		for j = 1, w*2+1 do
+    for j = 1, w*2+1 do
-			if map[i][j] then
+      if map[i][j] then
-				table.insert(s, ' ')
+        table.insert(s, '#')
-			else
+      else
-				table.insert(s, '#')
+        table.insert(s, ' ')
-			end
+      end
-		end
+    end
-		table.insert(s, '\n')
+    table.insert(s, '\n')
-	end
+  end
-	return table.concat(s)
+  return table.concat(s)
 end