· 9 years ago · Nov 23, 2016, 03:48 AM
1--Maze Generator
2--Nicholas Paul
3
4-- ZeroBrane's turtle library
5require "turtle"
6
7math.randomseed(os.time())
8
9SIZE = 100 --Width of tiles in the maze
10SCALE = 8 --Drawing Scale
11
12
13----------------------------
14-- Tile Object
15----------------------------
16
17WALL = true
18DOOR = false
19
20Tile = {}
21
22function Tile.new()
23 local tile = {}
24 tile.n = WALL
25 tile.s = WALL
26 tile.w = WALL
27 tile.e = WALL
28 tile.visited = false
29 tile.on_frontier = false
30 tile.is_available = true
31 --tile.solve_state = NONE
32 return tile
33end
34
35
36
37----------------------------
38-- Point
39----------------------------
40
41Point = {}
42
43function Point.new(x,y)
44 local point = {}
45 point.x = x
46 point.y = y
47 return point
48end
49
50----------------------------
51-- Frontier
52----------------------------
53
54local Frontier = {}
55Frontier.__index = Frontier
56
57
58--Add a tile to the frontier
59function Frontier.add(self, p)
60 self[self.n+1] = p
61 self.n = self.n+1
62end
63
64--Return a random tile from the frontier and remove
65function Frontier.next(self)
66 if self.n == 0 then
67 io.write("frontier is empty")
68 return nil
69 end
70
71 i = math.random(1, self.n)
72 local p = self[i]
73
74 --remove last element
75 self[i] = self[self.n]
76 self[self.n] = nil
77
78 self.n = self.n - 1
79
80 return p
81end
82
83function Frontier.has_point(self)
84 return self.n > 0
85end
86
87----------------------------
88-- Util Functions
89----------------------------
90
91opposite_dir = {n = "s", s = "n", w = "e", e = "w"}
92
93--Return the x coordinate after moving in a specified direction
94function xmove(dir,x)
95 local mv = {n = x-1, s = x+1, w = x, e = x}
96 return mv[dir]
97end
98
99--Return the x coordinate after moving in a specified direction
100function ymove(dir,y)
101 local mv = {n = y, s = y, w = y-1, e = y+1}
102 return mv[dir]
103end
104
105function contains_point(points, x,y)
106 for k,p in pairs(points) do
107 if p.x == x and p.y == y then
108 return true
109 end
110 end
111 return false
112end
113
114--Generate a random available point on the maze
115function randpoint(maze)
116 local good_tile = false
117 local xr
118 local yr
119 while not good_tile do
120 xr = math.random(SIZE)
121 yr = math.random(SIZE)
122 good_tile = maze[xr][yr].is_available
123 end
124 return Point.new(xr,yr)
125end
126
127--Create a deep copy of a table
128function deepcopy(orig)
129 local orig_type = type(orig)
130 local copy
131 if orig_type == 'table' then
132 copy = {}
133 for orig_key, orig_value in next, orig, nil do
134 copy[deepcopy(orig_key)] = deepcopy(orig_value)
135 end
136 setmetatable(copy, deepcopy(getmetatable(orig)))
137 else -- number, string, boolean, etc
138 copy = orig
139 end
140 return copy
141end
142
143
144----------------------------
145-- Filters
146----------------------------
147
148--remove a square from the center of the maze
149function sq_donut(map)
150 local lower_q = math.ceil(SIZE*1/4)
151 local upper_q = math.ceil(SIZE*3/4)
152
153 for i = lower_q, upper_q do
154 for j = lower_q, upper_q do
155 map[i][j].is_available = false
156 end
157 end
158
159 return map
160end
161
162--remove a circular hole in the center of the maze
163function rem_circ(map)
164 local radius = SIZE/3
165 local center = math.ceil(SIZE/2)
166
167 for i = 1,SIZE do
168 for j = 1,SIZE do
169 if math.sqrt( (center - i)^2 + (center-j)^2 ) < radius then
170 map[i][j].is_available = false
171 end
172 end
173 end
174
175 return map
176end
177
178--Remove the outer edges of the maze to create a circle
179function circ(map)
180 local radius = SIZE/2.1
181 local center = math.ceil(SIZE/2)
182
183 for i = 1,SIZE do
184 for j = 1,SIZE do
185 if not (math.sqrt( (center - i)^2 + (center-j)^2 ) < radius) then
186 map[i][j].is_available = false
187 end
188 end
189 end
190
191 return map
192end
193
194
195----------------------------
196-- Generate Maze
197----------------------------
198
199
200function generateMaze()
201 --Maze is a 2D array of tiles
202 local maze = {}
203 for i=1,SIZE do
204 maze[i] = {}
205 for j=1,SIZE do
206 maze[i][j] = Tile.new()
207 end
208 end
209
210 --Apply a filter here
211 --maze = sq_donut(maze)
212 --maze = rem_circ(maze)
213 maze = circ(maze)
214
215 local frontier = setmetatable({}, Frontier)
216 frontier.n = 0 --Number of elements in the frontier
217 --Choose a statring point
218
219 --Chose a point at random
220 local good_tile = false
221 local xr
222 local yr
223 while not good_tile do
224 xr = math.random(SIZE)
225 yr = math.random(SIZE)
226 good_tile = maze[xr][yr].is_available
227 end
228 --set it to visited
229 maze[xr][yr].visited = true
230 --...and add it to the frontier
231 frontier:add(Point.new(xr,yr))
232
233
234 --while the frontier still has elements, choose a random one
235 --and iterate through the map
236 while frontier:has_point() do
237 --choose a random point in the frontier
238 local p = frontier:next()
239
240 --shortcuts
241 local x = p.x
242 local y = p.y
243
244 --set current tile to visited
245 maze[x][y].visited = true
246
247 local visited = {}
248 local unexplored = {}
249
250 --if there exists an adjacent tile; if it has been visited and is available, add it to the visited list
251 if x+1 <= SIZE and maze[x+1][y] ~= nil and maze[x+1][y].is_available then
252 if maze[x+1][y].visited then table.insert(visited, "s") else table.insert(unexplored, Point.new(x+1,y)) end
253 end
254 if x-1 > 0 and maze[x-1][y] ~= nil and maze[x-1][y].is_available then
255 if maze[x-1][y].visited then table.insert(visited, "n") else table.insert(unexplored, Point.new(x-1,y)) end
256 end
257 if y+1 <= SIZE and maze[x][y+1] ~= nil and maze[x][y+1].is_available then
258 if maze[x][y+1].visited then table.insert(visited, "e") else table.insert(unexplored, Point.new(x,y+1)) end
259 end
260 if y-1 > 0 and maze[x][y-1] ~= nil and maze[x][y-1].is_available then
261 if maze[x][y-1].visited then table.insert(visited, "w") else table.insert(unexplored, Point.new(x,y-1)) end
262 end
263
264 --Choose a visited tile and carve a doorway
265 if #visited ~= 0 then
266 local dir = visited[math.random(1, #visited)]
267 maze[x][y][dir] = DOOR
268 maze[xmove(dir,x)][ymove(dir,y)][opposite_dir[dir]] = DOOR
269 end
270
271 --add the unexploerd tiles to the frontier
272 for k,v in pairs(unexplored) do
273 if not maze[v.x][v.y].on_frontier then
274 maze[v.x][v.y].on_frontier = true
275 frontier:add(v)
276 end
277 end
278 end
279
280 return maze
281end
282
283----------------------------
284-- Dwarf
285----------------------------
286
287Dwarf = {} --Dwarfs are great at solving mazes
288Dwarf.__index = Dwarf
289setmetatable(Dwarf, {
290 __call = function (s, ...)
291 return s.new(...)
292 end,
293})
294
295-- takes the route of the dwarf that spawned it and the current point it is at
296function Dwarf.new(route, point, dir_from)
297 local self = setmetatable({}, Dwarf)
298 if route == nil then
299 self.route = {}
300 else
301 self.route = deepcopy(route)
302 end
303
304 self.loc = deepcopy(point)
305 table.insert(self.route, self.loc)
306
307 self.dir_came_through = dir_from
308 return self
309end
310
311----------------------------
312-- Solve Maze
313----------------------------
314
315--Return an array of Points indicating the solution path
316--map::Maze, enterance::Point, exit::Point
317function sln_path(map, entrance, exit)
318 local solved = false
319 local dwarves = {}
320 table.insert(dwarves, Dwarf({}, entrance, "start"))
321
322 while true do
323 local newdwarves = {}
324
325 --Loop through the dwarves and have them spawn more dwarves
326 for i,df in pairs(dwarves) do
327
328 --Has the dwarf made it to the exit?
329 if df.loc.x == exit.x and df.loc.y == exit.y then
330 return df.route
331 end
332
333 --Are there nearby doors
334 local dirs = {"n", "s", "e", "w"}
335 for k,dir in pairs(dirs) do
336 --if this is not the direction the dwarf came through and it is a door, spawn a child dwarf in that tile
337 if (df.dir_came_through ~= dir)
338 and (maze[df.loc.x][df.loc.y][dir] == DOOR)
339 and (maze[xmove(dir, df.loc.x)][ymove(dir, df.loc.y)] ~= nil) then
340
341 --If there exists a tile in the potential location, spwan a dwarf there
342 if (maze[xmove(dir, df.loc.x)][ymove(dir, df.loc.y)].is_available) then
343 table.insert(newdwarves, Dwarf(df.route, Point.new(xmove(dir, df.loc.x), ymove(dir, df.loc.y)), opposite_dir[dir]))
344 end
345
346 end
347 end
348
349 end
350
351 dwarves = newdwarves
352
353 end
354end
355
356
357
358--Draw the maze onto the canvas
359function draw_maze(maze, spath)
360 local hypot = math.sqrt(SCALE*SCALE + SCALE*SCALE)
361
362 --Initialize the turtle (move to top left)
363 size(SIZE*SCALE+1, SIZE*SCALE+1)
364 turn(180); jump(SIZE*SCALE/2)
365 turn(90); jump(SIZE*SCALE/2-SCALE)
366 turn(90)
367
368 --draw the tiles
369 for i = 1,SIZE do
370 for j = 1,SIZE do
371 jump(SCALE)
372
373 if maze[i][j].is_available then
374 turn(180) --face left
375 if maze[i][j].s then move(SCALE) else jump(SCALE) end --south wall
376 turn(90) --face up
377 if maze[i][j].w then move(SCALE) else jump(SCALE) end --west wall
378 turn(90) --face right
379 if maze[i][j].n then move(SCALE) else jump(SCALE) end --north wall
380 turn(90) --face down
381 if maze[i][j].e then move(SCALE) else jump(SCALE) end --east wall
382 turn(-90) --face right
383
384 if contains_point(spath, i, j) then
385 turn(-1*(90+45)) --face NW
386 jump(hypot/2)
387 turn(180) --face SE
388
389 --Draw a crumb in the tile
390 turn(-45) --face right
391 move(2); turn(90)
392 move(1); turn(90)
393 move(2); turn(90)
394 move(1); turn(90)
395 move(2); turn(180)
396 jump(2); turn(-1*(90+45))
397
398 jump(hypot/2)
399 turn(-45) --face right
400 end
401
402
403 end
404
405 end
406 turn(180) --face left
407 jump(SIZE*SCALE)
408 turn(-90) --face down
409 jump(SCALE)
410 turn(-90) --face right
411 end
412end
413
414
415
416--Generate a new maze
417maze = generateMaze()
418
419--Generate a path between two random points
420--spath = sln_path(maze, randpoint(maze), randpoint(maze))
421spath = sln_path(maze, Point.new(SIZE/2, 3), Point.new(SIZE/2, SIZE-3))
422
423
424--Generate a path from the top left to the lower right corners
425--spath = sln_path(maze, Point.new(1,1), Point.new(SIZE,SIZE))
426
427--Draw the maze
428draw_maze(maze, spath)
429
430wait()