#!/usr/bin/env python3 # Draw a cylindrical maze suitable for plotting with the Eggbot # The maze itself is generated using a depth first search (DFS) # Written by Daniel C. Newman for the Eggbot Project # Improvements and suggestions by W. Craig Trader # 20 September 2010 # Update 26 April 2011 by Daniel C. Newman # # 1. Address Issue #40 # The extension now draws the maze by columns, going down # one column of cells and then up the next column. By using # this technique, the impact of slippage is largely limited # the the West and East ends of the maze not meeting. Otherwise, # the maze will still look quite well aligned both locally and # globally. Only very gross slippage will impact the local # appearance of the maze. # # Note that this new drawing technique is nearly as fast as # the prior method. The prior method has been preserved and # can be selected by setting self.hpp = True. ("hpp" intended # to mean "high plotting precision".) # # 2. Changed the page dimensions to use a height of 800 rather # than 1000 pixels. # # 3. When drawing the solution layer, draw the ending cell last. # Previously, the starting and ending cells were first drawn, # and then the solution path itself. That caused the pen to # move to the beginning, the end, and then back to the beginning # again to start the solution path. Alternatively, the solution # path might have been drawn from the end to the start. However, # just drawing the ending cell last was easier code-wise. # # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA import sys import array import math import random import inkex from lxml import etree # Initialize the pseudo random number generator random.seed() PLOT_WIDTH = 3200 # Eggbot plot width in pixels PLOT_HEIGHT = 800 # Eggbot plot height in pixels TARGET_WIDTH = 3200 # Desired plot width in pixels TARGET_HEIGHT = 600 # Desired plot height in pixels def draw_SVG_path(pts, c, t, parent): """ Add a SVG path element to the document We could do this just as easily as a polyline """ if not pts: # Nothing to draw return if isinstance(pts, list): assert len(pts) % 3 == 0, "len(pts) must be a multiple of three" d = "{0} {1:d},{2:d}".format(pts[0], pts[1], pts[2]) for i in range(3, len(pts), 3): d += " {0} {1:d},{2:d}".format(pts[i], pts[i + 1], pts[i + 2]) elif isinstance(pts, str): d = pts else: return style = {'stroke': c, 'stroke-width': str(t), 'fill': 'none'} line_attribs = {'style': str(inkex.Style(style)), 'd': d} etree.SubElement(parent, inkex.addNS('path', 'svg'), line_attribs) def draw_SVG_rect(x, y, w, h, c, t, fill, parent): """ Add a SVG rect element to the document """ style = {'stroke': c, 'stroke-width': str(t), 'fill': fill} rect_attribs = {'style': str(inkex.Style(style)), 'x': str(x), 'y': str(y), 'width': str(w), 'height': str(h)} etree.SubElement(parent, inkex.addNS('rect', 'svg'), rect_attribs) class Eggmazing(inkex.EffectExtension): """ Each cell in the maze is represented using 9 bits: Visited -- When set, indicates that this cell has been visited during construction of the maze Border -- Four bits indicating which if any of this cell's walls are part of the maze's boundary (i.e., are unremovable walls) Walls -- Four bits indicating which if any of this cell's walls are still standing Visited Border Walls x x x x x x x x x W S E N W S E N """ _VISITED = 0x0100 _NORTH = 0x0001 _EAST = 0x0002 _SOUTH = 0x0004 _WEST = 0x0008 def __init__(self): inkex.Effect.__init__(self) self.arg_parser.add_argument("--tab", default="controls", help="The active tab when Apply was pressed") self.arg_parser.add_argument("--mazeSize", default="MEDIUM", help="Difficulty of maze to build") self.hpp = False self.w = 0 self.h = 0 self.solved = 0 self.start_x = 0 self.start_y = 0 self.finish_x = 0 self.finish_y = 0 self.solution_x = None self.solution_y = None self.cells = None # Drawing information self.scale = 25.0 self.last_point = None self.path = '' def effect(self): # These dimensions are chosen so as to maintain integral dimensions # with a ratio of width to height of TARGET_WIDTH to TARGET_HEIGHT. # Presently that's 3200 to 600 which leads to a ratio of 5 and 1/3. if self.options.mazeSize == 'SMALL': self.w = 32 self.h = 6 elif self.options.mazeSize == 'MEDIUM': self.w = 64 self.h = 12 elif self.options.mazeSize == 'LARGE': self.w = 96 self.h = 18 else: self.w = 128 self.h = 24 # The large mazes tend to hit the recursion limit limit = sys.getrecursionlimit() if limit < (4 + self.w * self.h): sys.setrecursionlimit(4 + self.w * self.h) maze_size = self.w * self.h self.finish_x = self.w - 1 self.finish_y = self.h - 1 self.solution_x = array.array('i', range(maze_size)) self.solution_y = array.array('i', range(maze_size)) self.cells = array.array('H', range(maze_size)) # Remove any old maze for node in self.document.xpath('//svg:g[@inkscape:label="1 - Maze"]', namespaces=inkex.NSS): parent = node.getparent() parent.remove(node) # Remove any old solution for node in self.document.xpath('//svg:g[@inkscape:label="2 - Solution"]', namespaces=inkex.NSS): parent = node.getparent() parent.remove(node) # Remove any empty, default "Layer 1" for node in self.document.xpath('//svg:g[@id="layer1"]', namespaces=inkex.NSS): if not node.getchildren(): parent = node.getparent() parent.remove(node) # Start a new maze self.solved = 0 self.start_x = random.randint(0, self.w - 1) self.finish_x = random.randint(0, self.w - 1) # Initialize every cell with all four walls up for i in range(maze_size): self.cells[i] = Eggmazing._NORTH | Eggmazing._EAST | Eggmazing._SOUTH | Eggmazing._WEST # Now set our borders -- borders being walls which cannot be removed. # Since we are a maze on the surface of a cylinder we only have two # edges and hence only two borders. We consider our two edges to run # from WEST to EAST and to be at the NORTH and SOUTH. z = (self.h - 1) * self.w for x in range(self.w): self.cells[x] |= Eggmazing._NORTH << 4 self.cells[x + z] |= Eggmazing._SOUTH << 4 # Build the maze self.handle_cell(0, self.start_x, self.start_y) # Now that the maze has been built, remove the appropriate walls # associated with the start and finish points of the maze # Note: we have to remove these after building the maze. If we # remove them first, then the lack of a border at the start (or # finish) cell will allow the handle_cell() routine to wander # outside of the maze. I.e., handle_cell() doesn't do boundary # checking on the cell cell coordinates it generates. Instead, it # relies upon the presence of borders to prevent it wandering # outside the confines of the maze. self.remove_border(self.start_x, self.start_y, Eggmazing._NORTH) self.remove_wall(self.start_x, self.start_y, Eggmazing._NORTH) self.remove_border(self.finish_x, self.finish_y, Eggmazing._SOUTH) self.remove_wall(self.finish_x, self.finish_y, Eggmazing._SOUTH) # Now draw the maze # The following scaling and translations scale the maze's # (width, height) to (TARGET_WIDTH, TARGET_HEIGHT), and translates # the maze so that it centered within a document of dimensions # (width, height) = (PLOT_WIDTH, PLOT_HEIGHT) # Note that each cell in the maze is drawn 2 x units wide by # 2 y units high. A width and height of 2 was chosen for # convenience and for allowing easy identification (as the integer 1) # of the centerline along which to draw solution paths. It is the # abstract units which are then mapped to the TARGET_WIDTH eggbot x # pixels by TARGET_HEIGHT eggbot y pixels rectangle. scale_x = float(TARGET_WIDTH) / float(2 * self.w) scale_y = float(TARGET_HEIGHT) / float(2 * self.h) translate_x = float(PLOT_WIDTH - TARGET_WIDTH) / 2.0 translate_y = float(PLOT_HEIGHT - TARGET_HEIGHT) / 2.0 # And the SVG transform is thus t = 'translate({0:f},{1:f}) scale({2:f},{3:f})'.format(translate_x, translate_y, scale_x, scale_y) # For scaling line thicknesses. We'll typically draw a line of # thickness 1 but will need to make the SVG path have a thickness # of 1 / scale so that after our transforms are applied, the # resulting thickness is the 1 we wanted in the first place. if scale_x > scale_y: self.scale = scale_x else: self.scale = scale_y self.last_point = None self.path = '' if not self.hpp: # To draw the walls, we start at the left-most column of cells, draw down drawing # the WEST and NORTH walls and then draw up drawing the EAST and SOUTH walls. # By drawing in this back and forth fashion, we minimize the effect of slippage. for x in range(0, self.w, 2): self.draw_vertical(x) else: # The drawing style of the "high plotting precision" / "faster plotting" mode # is such that it minimizes the number of pen up / pen down operations # but at the expense of requiring higher drawing precision. It's style # of drawing works best when there is very minimal slippage of the egg # Draw the horizontal walls self.draw_horizontal_hpp(0, Eggmazing._NORTH) for y in range(self.h - 1): self.draw_horizontal_hpp(y, Eggmazing._SOUTH) self.draw_horizontal_hpp(self.h - 1, Eggmazing._SOUTH) # Draw the vertical walls # Since this is a maze on the surface of a cylinder, we don't need # to draw the vertical walls at the outer edges (x = 0 & x = w - 1) for x in range(self.w): self.draw_vertical_hpp(x, Eggmazing._EAST) # Maze in layer "1 - Maze" attribs = { inkex.addNS('label', 'inkscape'): '1 - Maze', inkex.addNS('groupmode', 'inkscape'): 'layer', 'transform': t} maze_layer = etree.SubElement(self.document.getroot(), 'g', attribs) draw_SVG_path(self.path, "#000000", float(1 / self.scale), maze_layer) # Now draw the solution in red in layer "2 - Solution" attribs = { inkex.addNS('label', 'inkscape'): '2 - Solution', inkex.addNS('groupmode', 'inkscape'): 'layer', 'transform': t} maze_layer = etree.SubElement(self.document.getroot(), 'g', attribs) # Mark the starting cell draw_SVG_rect(0.25 + 2 * self.start_x, 0.25 + 2 * self.start_y, 1.5, 1.5, "#ff0000", 0, "#ff0000", maze_layer) # And now generate the solution path itself # To minimize the number of plotted paths (and hence pen up / pen # down operations), we generate as few SVG paths as possible. # However, for aesthetic reasons we stop the path and start a new # one when it runs off the edge of the document. We could keep on # drawing as the eggbot will handle that just fine. However, it # doesn't look as good in Inkscape. So, we end the path and start # a new one which is wrapped to the other edge of the document. pts = [] end_path = False i = 0 while i < self.solved: x1 = self.solution_x[i] y1 = self.solution_y[i] i += 1 x2 = self.solution_x[i] y2 = self.solution_y[i] if math.fabs(x1 - x2) > 1: # We wrapped horizontally... if x1 > x2: x2 = x1 + 1 else: x2 = x1 - 1 end_path = True if i == 1: pts.extend(['M', 2 * x1 + 1, 2 * y1 + 1]) pts.extend(['L', 2 * x2 + 1, 2 * y2 + 1]) if not end_path: continue x2 = self.solution_x[i] y2 = self.solution_y[i] pts.extend(['M', 2 * x2 + 1, 2 * y2 + 1]) end_path = False # Put the solution path into the drawing draw_SVG_path(pts, '#ff0000', float(8 / self.scale), maze_layer) # Now mark the ending cell draw_SVG_rect(0.25 + 2 * self.finish_x, 0.25 + 2 * self.finish_y, 1.5, 1.5, "#ff0000", 0, "#ff0000", maze_layer) # Restore the recursion limit sys.setrecursionlimit(limit) # Set some document properties node = self.document.getroot() node.set('width', '3200') node.set('height', '800') # The following end up being ignored by Inkscape.... node = self.svg.namedview node.set('showborder', 'false') node.set(inkex.addNS('cx', u'inkscape'), '1600') node.set(inkex.addNS('cy', u'inkscape'), '500') node.set(inkex.addNS('showpageshadow', u'inkscape'), 'false') # Mark the cell at (x, y) as "visited" def visit(self, x, y): self.cells[y * self.w + x] |= Eggmazing._VISITED # Return a non-zero value if the cell at (x, y) has been visited def is_visited(self, x, y): if self.cells[y * self.w + x] & Eggmazing._VISITED: return -1 else: return 0 # Return a non-zero value if the cell at (x, y) has a wall # in the direction d def is_wall(self, x, y, d): if self.cells[y * self.w + x] & d: return -1 else: return 0 # Remove the wall in the direction d from the cell at (x, y) def remove_wall(self, x, y, d): self.cells[y * self.w + x] &= ~d # Return a non-zero value if the cell at (x, y) has a border wall # in the direction d def is_border(self, x, y, d): if self.cells[y * self.w + x] & (d << 4): return -1 else: return 0 # Remove the border in the direction d from the cell at (x, y) def remove_border(self, x, y, d): self.cells[y * self.w + x] &= ~(d << 4) # This is the DFS algorithm which builds the maze. We start at depth 0 # at the starting cell (self.start_x, self.start_y). We then walk to a # randomly selected neighboring cell which has not yet been visited (i.e., # previously walked into). Each step of the walk is a recursive descent # in depth. The solution to the maze comes about when we walk into the # finish cell at (self.finish_x, self.finish_y). # # Each recursive descent finishes when the currently visited cell has no # unvisited neighboring cells. # # Since we don't revisit previously visited cells, each cell is visited # no more than once. As it turns out, each cell is visited, but that's a # little harder to show. Net, net, each cell is visited exactly once. def handle_cell(self, depth, x, y): # Mark the current cell as visited self.visit(x, y) # Save this cell's location in our solution trail / backtrace if not self.solved: self.solution_x[depth] = x self.solution_y[depth] = y if (x == self.finish_x) and (y == self.finish_y): # Maze has been solved self.solved = depth # Shuffle the four compass directions: this is the primary source # of "randomness" in the generated maze. We need to visit each # neighboring cell which has not yet been visited. If we always # did that in the same order, then our mazes would look very regular. # So, we shuffle the list of directions we try in order to find an # unvisited neighbor. # HINT: TRY COMMENTING OUT THE shuffle() BELOW AND SEE FOR YOURSELF directions = [Eggmazing._NORTH, Eggmazing._SOUTH, Eggmazing._EAST, Eggmazing._WEST] random.shuffle(directions) # Now from the cell at (x, y), look to each of the four # directions for unvisited neighboring cells for each_direction in directions: # If there is a border in direction[i], then don't try # looking for a neighboring cell in that direction. We # Use this check and borders to prevent generating invalid # cell coordinates. if self.is_border(x, y, each_direction): continue # Determine the cell coordinates of a neighboring cell # NOTE: we trust the use of maze borders to prevent us # from generating invalid cell coordinates if each_direction == Eggmazing._NORTH: nx = x ny = y - 1 opposite_direction = Eggmazing._SOUTH elif each_direction == Eggmazing._SOUTH: nx = x ny = y + 1 opposite_direction = Eggmazing._NORTH elif each_direction == Eggmazing._EAST: nx = x + 1 ny = y opposite_direction = Eggmazing._WEST else: nx = x - 1 ny = y opposite_direction = Eggmazing._EAST # Wrap in the horizontal dimension if nx < 0: nx += self.w elif nx >= self.w: nx -= self.w # See if this neighboring cell has been visited if self.is_visited(nx, ny): # Neighbor has been visited already continue # The neighboring cell has not been visited: remove the wall in # the current cell leading to the neighbor. And, from the # neighbor remove its wall leading to the current cell. self.remove_wall(x, y, each_direction) self.remove_wall(nx, ny, opposite_direction) # Now recur by "moving" to this unvisited neighboring cell self.handle_cell(depth + 1, nx, ny) def draw_line(self, x1, y1, x2, y2): if self.last_point is not None: if (self.last_point[0] == x1) and (self.last_point[1] == y1): self.path += ' L {0:d},{1:d}'.format(x2, y2) self.last_point = [x2, y2] elif (self.last_point[0] == x2) and (self.last_point[1] == y2): self.path += ' L {0:d},{1:d} L {2:d},{3:d}'.format(x1, y1, x2, y2) # self.last_point unchanged else: self.path += ' M {0:d},{1:d} L {2:d},{3:d}'.format(x1, y1, x2, y2) self.last_point = [x2, y2] else: self.path = 'M {0:d},{1:d} L {2:d},{3:d}'.format(x1, y1, x2, y2) self.last_point = [x2, y2] def draw_wall(self, x, y, d, dir_): if dir_ > 0: if d == Eggmazing._NORTH: self.draw_line(2 * (x + 1), 2 * y, 2 * x, 2 * y) elif d == Eggmazing._WEST: self.draw_line(2 * x, 2 * y, 2 * x, 2 * (y + 1)) elif d == Eggmazing._SOUTH: self.draw_line(2 * (x + 1), 2 * (y + 1), 2 * x, 2 * (y + 1)) else: # Eggmazing._EAST self.draw_line(2 * (x + 1), 2 * y, 2 * (x + 1), 2 * (y + 1)) else: if d == Eggmazing._NORTH: self.draw_line(2 * x, 2 * y, 2 * (x + 1), 2 * y) elif d == Eggmazing._WEST: self.draw_line(2 * x, 2 * (y + 1), 2 * x, 2 * y) elif d == Eggmazing._SOUTH: self.draw_line(2 * x, 2 * (y + 1), 2 * (x + 1), 2 * (y + 1)) else: # Eggmazing._EAST self.draw_line(2 * (x + 1), 2 * (y + 1), 2 * (x + 1), 2 * y) # Draw the vertical walls of the maze along the column of cells at # horizontal positions def draw_vertical(self, x): # Drawing moving downwards from north to south if self.is_wall(x, 0, Eggmazing._NORTH): self.draw_wall(x, 0, Eggmazing._NORTH, +1) for y in range(self.h): if self.is_wall(x, y, Eggmazing._WEST): self.draw_wall(x, y, Eggmazing._WEST, +1) if self.is_wall(x, y, Eggmazing._SOUTH): self.draw_wall(x, y, Eggmazing._SOUTH, +1) # Now, return drawing upwards moving from south to north x += 1 if x >= self.w: return for y in range(self.h - 1, -1, -1): if self.is_wall(x, y, Eggmazing._SOUTH): self.draw_wall(x, y, Eggmazing._SOUTH, -1) if self.is_wall(x, y, Eggmazing._WEST): self.draw_wall(x, y, Eggmazing._WEST, -1) if self.is_wall(x, 0, Eggmazing._NORTH): self.draw_wall(x, 0, Eggmazing._NORTH, -1) # Draw the horizontal walls of the maze along the row of # cells at "height" y: "high plotting precision" version def draw_horizontal_hpp(self, y, wall): # Cater to Python 2.4 and earlier # dy = 0 if wall == Eggmazing._NORTH else 1 if wall == Eggmazing._NORTH: dy = 0 else: dy = 1 tracing = False segment = 0 for x in range(self.w): if self.is_wall(x, y, wall): if not tracing: # Starting a new segment segment = x tracing = True else: if tracing: # Reached the end of a segment self.draw_line(2 * segment, 2 * (y + dy), 2 * x, 2 * (y + dy)) tracing = False if tracing: # Draw the last wall segment self.draw_line(2 * segment, 2 * (y + dy), 2 * self.w, 2 * (y + dy)) # Draw the vertical walls of the maze along the column of cells at # horizontal position x: "high plotting precision" version def draw_vertical_hpp(self, x, wall): dx = 0 if wall == Eggmazing._WEST else 1 # We alternate the direction in which we draw each vertical wall. # First, from North to South and then from South to North. This # reduces pen travel on the Eggbot if x % 2 == 0: # North-South y_start, y_finis, dy, offset = 0, self.h, 1, 0 else: # South-North y_start, y_finis, dy, offset = self.h - 1, -1, -1, 2 tracing = False segment = y_start for y in range(y_start, y_finis, dy): assert 0 <= y < self.h, "y ({0:d}) is out of range".format(y) if self.is_wall(x, y, wall): if not tracing: # Starting a new segment segment = y tracing = True else: if tracing: # Hit the end of a segment self.draw_line(2 * (x + dx), 2 * segment + offset, 2 * (x + dx), 2 * y + offset) tracing = False if tracing: # complete the last wall segment self.draw_line(2 * (x + dx), 2 * segment + offset, 2 * (x + dx), 2 * y_finis + offset) if __name__ == '__main__': Eggmazing().run()