daily pastebin goal
80%
SHARE
TWEET

Untitled

a guest Jul 18th, 2018 86 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
  49.   add_frontier(x-1, y, grid, frontier)
  50.   add_frontier(x+1, y, grid, frontier)
  51.   add_frontier(x, y-1, grid, frontier)
  52.   add_frontier(x, y+1, grid, frontier)
  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. OK, I Understand
 
Top