• API
• FAQ
• Tools
• Archive
daily pastebin goal
9%
SHARE
TWEET

# Untitled

a guest Jul 18th, 2018 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # --------------------------------------------------------------------
2. # An implementation of Prim's algorithm for generating mazes.
3. # This is a pretty fast algorithm, when implemented well, since it
4. # only needs random access to the list of frontier cells. It does
5. # require space proportional to the size of the maze, but even worse-
6. # case, it won't be but a fraction of the size of the maze itself.
7. # As with Kruskal's, this algorithm tends to generate mazes with many
8. # short cul-de-sacs.
9. # --------------------------------------------------------------------
10. # NOTE: the display routine used in this script requires a terminal
11. # that supports ANSI escape sequences. Windows users, sorry. :(
12. # --------------------------------------------------------------------
13.
14. # --------------------------------------------------------------------
15. # 1. Allow the maze to be customized via command-line parameters
16. # --------------------------------------------------------------------
17.
18. width  = (ARGV[0] || 10).to_i
19. height = (ARGV[1] || width).to_i
20. seed   = (ARGV[2] || rand(0xFFFF_FFFF)).to_i
21.
22. srand(seed)
23.
24. # --------------------------------------------------------------------
25. # 2. Set up constants to aid with describing the passage directions
26. # --------------------------------------------------------------------
27.
28. N, S, E, W = 1, 2, 4, 8
29. IN         = 0x10
30. FRONTIER   = 0x20
31. OPPOSITE   = { E => W, W =>  E, N =>  S, S => N }
32.
33. # --------------------------------------------------------------------
34. # 3. Data structures and methods to assist the algorithm
35. # --------------------------------------------------------------------
36.
37. grid = Array.new(height) { Array.new(width, 0) }
38. frontier = []
39.
40. def add_frontier(x, y, grid, frontier)
41.   if x >= 0 && y >= 0 && y < grid.length && x < grid[y].length && grid[y][x] == 0
42.     grid[y][x] |= FRONTIER
43.     frontier << [x,y]
44.   end
45. end
46.
47. def mark(x, y, grid, frontier)
48.   grid[y][x] |= IN
53. end
54.
55. def neighbors(x, y, grid)
56.   n = []
57.
58.   n << [x-1, y] if x > 0 && grid[y][x-1] & IN != 0
59.   n << [x+1, y] if x+1 < grid[y].length && grid[y][x+1] & IN != 0
60.   n << [x, y-1] if y > 0 && grid[y-1][x] & IN != 0
61.   n << [x, y+1] if y+1 < grid.length && grid[y+1][x] & IN != 0
62.
63.   n
64. end
65.
66. def direction(fx, fy, tx, ty)
67.   return E if fx < tx
68.   return W if fx > tx
69.   return S if fy < ty
70.   return N if fy > ty
71. end
72.
73. # --------------------------------------------------------------------
74. # 4. Routines for displaying the maze
75. # --------------------------------------------------------------------
76.
77. def empty?(cell)
78.   cell == 0 || cell == FRONTIER
79. end
80.
81. def display_maze(grid)
82.   print "\e[H" # move to upper-left
83.   puts " " + "_" * (grid[0].length * 2 - 1)
84.   grid.each_with_index do |row, y|
85.     print "|"
86.     row.each_with_index do |cell, x|
87.       print "\e[41m" if cell == FRONTIER
88.       if empty?(cell) && y+1 < grid.length && empty?(grid[y+1][x])
89.         print " "
90.       else
91.         print((cell & S != 0) ? " " : "_")
92.       end
93.       print "\e[m" if cell == FRONTIER
94.
95.       if empty?(cell) && x+1 < row.length && empty?(row[x+1])
96.         print((y+1 < grid.length && (empty?(grid[y+1][x]) || empty?(grid[y+1][x+1]))) ? " " : "_")
97.       elsif cell & E != 0
98.         print(((cell | row[x+1]) & S != 0) ? " " : "_")
99.       else
100.         print "|"
101.       end
102.     end
103.     puts
104.   end
105. end
106.
107. # --------------------------------------------------------------------
108. # 5. Prim's algorithm
109. # --------------------------------------------------------------------
110.
111. print "\e[2J" # clear the screen
112.
113. mark(rand(width), rand(height), grid, frontier)
114. until frontier.empty?
115.   x, y = frontier.delete_at(rand(frontier.length))
116.   n = neighbors(x, y, grid)
117.   nx, ny = n[rand(n.length)]
118.
119.   dir = direction(x, y, nx, ny)
120.   grid[y][x] |= dir
121.   grid[ny][nx] |= OPPOSITE[dir]
122.
123.   mark(x, y, grid, frontier)
124.
125.   display_maze(grid)
126.   sleep 0.01
127. end
128.
129. display_maze(grid)
130.
131. # --------------------------------------------------------------------
132. # 6. Show the parameters used to build this maze, for repeatability
133. # --------------------------------------------------------------------
134.
135. puts "#{\$0} #{width} #{height} #{seed}"
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top