Skip to content

Instantly share code, notes, and snippets.

@nick-paul

nick-paul/maze_generator.lua

Created November 23, 2016 03:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nick-paul/64abc82130563d5aa7011f38335a7aff to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nick-paul/64abc82130563d5aa7011f38335a7aff to your computer and use it in GitHub Desktop.
Download ZIP
A lua script for generating and solving mazes
Raw
maze_generator.lua
--Maze Generator
--Nicholas Paul
-- ZeroBrane's turtle library
require "turtle"
math.randomseed(os.time())
SIZE = 100 --Width of tiles in the maze
SCALE = 8 --Drawing Scale
----------------------------
-- Tile Object
----------------------------
WALL = true
DOOR = false
Tile = {}
function Tile.new()
local tile = {}
tile.n = WALL
tile.s = WALL
tile.w = WALL
tile.e = WALL
tile.visited = false
tile.on_frontier = false
tile.is_available = true
--tile.solve_state = NONE
return tile
end
----------------------------
-- Point
----------------------------
Point = {}
function Point.new(x,y)
local point = {}
point.x = x
point.y = y
return point
end
----------------------------
-- Frontier
----------------------------
local Frontier = {}
Frontier.__index = Frontier
--Add a tile to the frontier
function Frontier.add(self, p)
self[self.n+1] = p
self.n = self.n+1
end
--Return a random tile from the frontier and remove
function Frontier.next(self)
if self.n == 0 then
io.write("frontier is empty")
return nil
end
i = math.random(1, self.n)
local p = self[i]
--remove last element
self[i] = self[self.n]
self[self.n] = nil
self.n = self.n - 1
return p
end
function Frontier.has_point(self)
return self.n > 0
end
----------------------------
-- Util Functions
----------------------------
opposite_dir = {n = "s", s = "n", w = "e", e = "w"}
--Return the x coordinate after moving in a specified direction
function xmove(dir,x)
local mv = {n = x-1, s = x+1, w = x, e = x}
return mv[dir]
end
--Return the x coordinate after moving in a specified direction
function ymove(dir,y)
local mv = {n = y, s = y, w = y-1, e = y+1}
return mv[dir]
end
function contains_point(points, x,y)
for k,p in pairs(points) do
if p.x == x and p.y == y then
return true
end
end
return false
end
--Generate a random available point on the maze
function randpoint(maze)
local good_tile = false
local xr
local yr
while not good_tile do
xr = math.random(SIZE)
yr = math.random(SIZE)
good_tile = maze[xr][yr].is_available
end
return Point.new(xr,yr)
end
--Create a deep copy of a table
function deepcopy(orig)
local orig_type = type(orig)
local copy
if orig_type == 'table' then
copy = {}
for orig_key, orig_value in next, orig, nil do
copy[deepcopy(orig_key)] = deepcopy(orig_value)
end
setmetatable(copy, deepcopy(getmetatable(orig)))
else -- number, string, boolean, etc
copy = orig
end
return copy
end
----------------------------
-- Filters
----------------------------
--remove a square from the center of the maze
function sq_donut(map)
local lower_q = math.ceil(SIZE*1/4)
local upper_q = math.ceil(SIZE*3/4)
for i = lower_q, upper_q do
for j = lower_q, upper_q do
map[i][j].is_available = false
end
end
return map
end
--remove a circular hole in the center of the maze
function rem_circ(map)
local radius = SIZE/3
local center = math.ceil(SIZE/2)
for i = 1,SIZE do
for j = 1,SIZE do
if math.sqrt( (center - i)^2 + (center-j)^2 ) < radius then
map[i][j].is_available = false
end
end
end
return map
end
--Remove the outer edges of the maze to create a circle
function circ(map)
local radius = SIZE/2.1
local center = math.ceil(SIZE/2)
for i = 1,SIZE do
for j = 1,SIZE do
if not (math.sqrt( (center - i)^2 + (center-j)^2 ) < radius) then
map[i][j].is_available = false
end
end
end
return map
end
----------------------------
-- Generate Maze
----------------------------
function generateMaze()
--Maze is a 2D array of tiles
local maze = {}
for i=1,SIZE do
maze[i] = {}
for j=1,SIZE do
maze[i][j] = Tile.new()
end
end
--Apply a filter here
--maze = sq_donut(maze)
--maze = rem_circ(maze)
maze = circ(maze)
local frontier = setmetatable({}, Frontier)
frontier.n = 0 --Number of elements in the frontier
--Choose a statring point
--Chose a point at random
local good_tile = false
local xr
local yr
while not good_tile do
xr = math.random(SIZE)
yr = math.random(SIZE)
good_tile = maze[xr][yr].is_available
end
--set it to visited
maze[xr][yr].visited = true
--...and add it to the frontier
frontier:add(Point.new(xr,yr))
--while the frontier still has elements, choose a random one
--and iterate through the map
while frontier:has_point() do
--choose a random point in the frontier
local p = frontier:next()
--shortcuts
local x = p.x
local y = p.y
--set current tile to visited
maze[x][y].visited = true
local visited = {}
local unexplored = {}
--if there exists an adjacent tile; if it has been visited and is available, add it to the visited list
if x+1 <= SIZE and maze[x+1][y] ~= nil and maze[x+1][y].is_available then
if maze[x+1][y].visited then table.insert(visited, "s") else table.insert(unexplored, Point.new(x+1,y)) end
end
if x-1 > 0 and maze[x-1][y] ~= nil and maze[x-1][y].is_available then
if maze[x-1][y].visited then table.insert(visited, "n") else table.insert(unexplored, Point.new(x-1,y)) end
end
if y+1 <= SIZE and maze[x][y+1] ~= nil and maze[x][y+1].is_available then
if maze[x][y+1].visited then table.insert(visited, "e") else table.insert(unexplored, Point.new(x,y+1)) end
end
if y-1 > 0 and maze[x][y-1] ~= nil and maze[x][y-1].is_available then
if maze[x][y-1].visited then table.insert(visited, "w") else table.insert(unexplored, Point.new(x,y-1)) end
end
--Choose a visited tile and carve a doorway
if #visited ~= 0 then
local dir = visited[math.random(1, #visited)]
maze[x][y][dir] = DOOR
maze[xmove(dir,x)][ymove(dir,y)][opposite_dir[dir]] = DOOR
end
--add the unexploerd tiles to the frontier
for k,v in pairs(unexplored) do
if not maze[v.x][v.y].on_frontier then
maze[v.x][v.y].on_frontier = true
frontier:add(v)
end
end
end
return maze
end
----------------------------
-- Dwarf
----------------------------
Dwarf = {} --Dwarfs are great at solving mazes
Dwarf.__index = Dwarf
setmetatable(Dwarf, {
__call = function (s, ...)
return s.new(...)
end,
})
-- takes the route of the dwarf that spawned it and the current point it is at
function Dwarf.new(route, point, dir_from)
local self = setmetatable({}, Dwarf)
if route == nil then
self.route = {}
else
self.route = deepcopy(route)
end
self.loc = deepcopy(point)
table.insert(self.route, self.loc)
self.dir_came_through = dir_from
return self
end
----------------------------
-- Solve Maze
----------------------------
--Return an array of Points indicating the solution path
--map::Maze, enterance::Point, exit::Point
function sln_path(map, entrance, exit)
local solved = false
local dwarves = {}
table.insert(dwarves, Dwarf({}, entrance, "start"))
while true do
local newdwarves = {}
--Loop through the dwarves and have them spawn more dwarves
for i,df in pairs(dwarves) do
--Has the dwarf made it to the exit?
if df.loc.x == exit.x and df.loc.y == exit.y then
return df.route
end
--Are there nearby doors
local dirs = {"n", "s", "e", "w"}
for k,dir in pairs(dirs) do
--if this is not the direction the dwarf came through and it is a door, spawn a child dwarf in that tile
if (df.dir_came_through ~= dir)
and (maze[df.loc.x][df.loc.y][dir] == DOOR)
and (maze[xmove(dir, df.loc.x)][ymove(dir, df.loc.y)] ~= nil) then
--If there exists a tile in the potential location, spwan a dwarf there
if (maze[xmove(dir, df.loc.x)][ymove(dir, df.loc.y)].is_available) then
table.insert(newdwarves, Dwarf(df.route, Point.new(xmove(dir, df.loc.x), ymove(dir, df.loc.y)), opposite_dir[dir]))
end
end
end
end
dwarves = newdwarves
end
end
--Draw the maze onto the canvas
function draw_maze(maze, spath)
local hypot = math.sqrt(SCALE*SCALE + SCALE*SCALE)
--Initialize the turtle (move to top left)
size(SIZE*SCALE+1, SIZE*SCALE+1)
turn(180); jump(SIZE*SCALE/2)
turn(90); jump(SIZE*SCALE/2-SCALE)
turn(90)
--draw the tiles
for i = 1,SIZE do
for j = 1,SIZE do
jump(SCALE)
if maze[i][j].is_available then
turn(180) --face left
if maze[i][j].s then move(SCALE) else jump(SCALE) end --south wall
turn(90) --face up
if maze[i][j].w then move(SCALE) else jump(SCALE) end --west wall
turn(90) --face right
if maze[i][j].n then move(SCALE) else jump(SCALE) end --north wall
turn(90) --face down
if maze[i][j].e then move(SCALE) else jump(SCALE) end --east wall
turn(-90) --face right
if contains_point(spath, i, j) then
turn(-1*(90+45)) --face NW
jump(hypot/2)
turn(180) --face SE
--Draw a crumb in the tile
turn(-45) --face right
move(2); turn(90)
move(1); turn(90)
move(2); turn(90)
move(1); turn(90)
move(2); turn(180)
jump(2); turn(-1*(90+45))
jump(hypot/2)
turn(-45) --face right
end
end
end
turn(180) --face left
jump(SIZE*SCALE)
turn(-90) --face down
jump(SCALE)
turn(-90) --face right
end
end
--Generate a new maze
maze = generateMaze()
--Generate a path between two random points
--spath = sln_path(maze, randpoint(maze), randpoint(maze))
spath = sln_path(maze, Point.new(SIZE/2, 3), Point.new(SIZE/2, SIZE-3))
--Generate a path from the top left to the lower right corners
--spath = sln_path(maze, Point.new(1,1), Point.new(SIZE,SIZE))
--Draw the maze
draw_maze(maze, spath)
wait()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment