From 5059950c50b407c7fdedcbf2113df8f9dafd59eb Mon Sep 17 00:00:00 2001 From: jaseg Date: Fri, 14 Aug 2020 18:23:31 +0200 Subject: randomized maze generation works --- plugin/main_dialog.fbp | 2 +- plugin/mesh_dialog.py | 190 ++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 167 insertions(+), 25 deletions(-) diff --git a/plugin/main_dialog.fbp b/plugin/main_dialog.fbp index 6c389c0..ac7e900 100644 --- a/plugin/main_dialog.fbp +++ b/plugin/main_dialog.fbp @@ -45,7 +45,7 @@ MainDialog - 588,356 + 751,480 wxCLOSE_BOX|wxDEFAULT_DIALOG_STYLE|wxMINIMIZE_BOX|wxRESIZE_BORDER|wxSTAY_ON_TOP ; ; forward_declare Security Mesh Generator Plugin diff --git a/plugin/mesh_dialog.py b/plugin/mesh_dialog.py index 3b4e91a..94edf0c 100644 --- a/plugin/mesh_dialog.py +++ b/plugin/mesh_dialog.py @@ -1,11 +1,16 @@ from collections import defaultdict from dataclasses import dataclass +from contextlib import contextmanager +import textwrap +import random import wx import pcbnew +import matplotlib.cm import shapely +from shapely import geometry from shapely.geometry import polygon from shapely import affinity @@ -146,7 +151,7 @@ class MeshPluginMainDialog(mesh_plugin_dialog.MainDialog): if self.tearup_confirm_dialog.ShowModal() == wx.ID_YES: raise AbortError() - self.generate_mesh_backend(zone, anchors, warn=warn) + self.generate_mesh_backend(zone, anchors, warn=warn, settings=settings) except GeneratorError as e: return wx.MessageDialog(self, str(e), "Mesh Generation Error").ShowModal() @@ -161,7 +166,7 @@ class MeshPluginMainDialog(mesh_plugin_dialog.MainDialog): for j in range(outline.PointCount()): point = outline.CPoint(j) outline_points.append((pcbnew.ToMM(point.x), pcbnew.ToMM(point.y))) - yield polygon.LinearRing(outline_points) + yield polygon.Polygon(outline_points) def generate_mesh_backend(self, zone, anchors, warn=lambda s: None, settings=GeneratorSettings()): anchor, = anchors @@ -179,11 +184,10 @@ class MeshPluginMainDialog(mesh_plugin_dialog.MainDialog): raise GeneratorError('Mesh zone has too many outlines (has {}, should have one).'.format(len(zone_outlines))) zone_outline, *_rest = zone_outlines - mesh_origin = zone_outline.centroid width_per_trace = settings.trace_width + settings.space_width grid_cell_width = width_per_trace * settings.num_traces - zone_outline_rotated = affinity.rotate(zone_outline, -settings.mesh_angle, origin=mesh_origin) + zone_outline_rotated = affinity.rotate(zone_outline, -settings.mesh_angle, origin=zone_outline.centroid) bbox = zone_outline_rotated.bounds grid_origin = (bbox[0] + settings.offset_x - grid_cell_width, bbox[1] + settings.offset_y - grid_cell_width) @@ -195,29 +199,100 @@ class MeshPluginMainDialog(mesh_plugin_dialog.MainDialog): for y in range(grid_rows): row = [] for x in range(grid_cols): - cell = polygon.LinearRing([(0, 0), (0, 1), (1, 1), (1, 0)]) + cell = polygon.Polygon([(0, 0), (0, 1), (1, 1), (1, 0)]) cell = affinity.scale(cell, grid_cell_width, grid_cell_width, origin=(0, 0)) - cell = affinity.translate(cell, mesh_origin.x + x*grid_cell_width, mesh_origin.y + y*grid_cell_width) - cell = affinity.rotate(cell, settings.mesh_angle, origin=mesh_origin) + cell = affinity.translate(cell, grid_origin[0] + x*grid_cell_width, grid_origin[1] + y*grid_cell_width) + cell = affinity.rotate(cell, settings.mesh_angle, origin=zone_outline.centroid) row.append(cell) grid.append(row) - break - - for row in grid: - for cell in row: - poly = pcbnew.DRAWSEGMENT() - poly.SetLayer(self.board.GetLayerID('Eco2.User')) - poly.SetShape(pcbnew.S_POLYGON) - poly.SetWidth(0) - self.board.Add(poly) - s = poly.GetPolyShape() - s.NewOutline() - for x, y in zip(*cell.xy): - s.Append(pcbnew.FromMM(x), pcbnew.FromMM(y)) - print('OUTLINE POINT', x, y) - break - - pcbnew.Refresh() + + exit_line = affinity.rotate(geometry.LineString([(0,0), (0,-100000)]), settings.anchor_exit, origin=(0, 0)) + exit_line = affinity.translate(exit_line, anchor_outlines[0].centroid.x, anchor_outlines[0].centroid.y) + possible_exits = [] + for y, row in enumerate(grid): + for x, cell in enumerate(row): + if any(ol.overlaps(cell) for ol in anchor_outlines): # cell lies on outline + if exit_line.crosses(cell): # cell lies on exit line + possible_exits.append((cell, (x, y))) + if len(possible_exits) == 0: + raise GeneratorError('Cannot find an exit. This is a bug, please report.') + exit_cell = possible_exits[0] # might overlap multiple if not orthogonal + + num_valid = 0 + with DebugOutput('/mnt/c/Users/jaseg/shared/test.svg') as dbg: + dbg.add(zone_outline, color='#00000020') + + for y, row in enumerate(grid): + for x, cell in enumerate(row): + if zone_outline.contains(cell): + if cell == exit_cell[0]: + color = '#ff00ff80' + elif any(ol.overlaps(cell) for ol in anchor_outlines): + color = '#ffff0080' + elif any(ol.contains(cell) for ol in anchor_outlines): + color = '#ff000080' + else: + num_valid += 1 + color = '#00ff0080' + elif zone_outline.overlaps(cell): + color = '#ffff0080' + else: + color = '#ff000080' + dbg.add(cell, color=color) + + for foo in anchor_outlines: + dbg.add(foo, color='#0000ff00', stroke_width=0.05, stroke_color='#000000ff') + + def is_valid(cell): + if not zone_outline.contains(cell): + return False + if any(ol.overlaps(cell) for ol in anchor_outlines): + return False + if any(ol.contains(cell) for ol in anchor_outlines): + return False + return True + + def iter_neighbors(x, y): + if x > 0: + yield x-1, y + if x < grid_cols: + yield x+1, y + if y > 0: + yield x, y-1 + if y < grid_rows: + yield x, y+1 + + def random_iter(it): + l = list(it) + random.shuffle(l) + yield from l + + not_visited = { (x, y) for x in range(grid_cols) for y in range(grid_rows) if is_valid(grid[y][x]) } + num_to_visit = len(not_visited) + with DebugOutput('/mnt/c/Users/jaseg/shared/test2.svg') as dbg: + dbg.add(zone_outline, color='#00000020') + + x, y = exit_cell[1] + visited = 0 + stack = [] + while not_visited: + for n_x, n_y in random_iter(iter_neighbors(x, y)): + if (n_x, n_y) in not_visited: + dbg.add(grid[n_y][n_x], color=virihex(visited, max=num_to_visit)) + stack.append((x, y)) + not_visited.remove((n_x, n_y)) + visited += 1 + x, y = n_x, n_y + break + else: + *stack, (x, y) = stack + + for foo in anchor_outlines: + dbg.add(foo, color='#0000ff00', stroke_width=0.05, stroke_color='#000000ff') + + + + #pcbnew.Refresh() #self.tearup_mesh() # TODO generate @@ -227,6 +302,73 @@ class MeshPluginMainDialog(mesh_plugin_dialog.MainDialog): def quit(self, evt): self.Destroy() +def virihex(val, max=1.0, alpha=1.0): + r, g, b, _a = matplotlib.cm.viridis(val/max) + r, g, b, a = [ int(round(0xff*c)) for c in [r, g, b, alpha] ] + return f'#{r:02x}{g:02x}{b:02x}{a:02x}' + +@contextmanager +def DebugOutput(filename): + with open(filename, 'w') as f: + wrapper = DebugOutputWrapper(f) + yield wrapper + wrapper.save() + +class DebugOutputWrapper: + def __init__(self, f): + self.f = f + self.objs = [] + + def add(self, obj, color=None, stroke_width=0, stroke_color=None): + self.objs.append((obj, (color, stroke_color, stroke_width))) + + def gen_svg(self, obj, fill_color=None, stroke_color=None, stroke_width=None): + fill_color = fill_color or '#ff0000aa' + stroke_color = stroke_color or '#000000ff' + stroke_width = 0 if stroke_width is None else stroke_width + + exterior_coords = [ ["{},{}".format(*c) for c in obj.exterior.coords] ] + interior_coords = [ ["{},{}".format(*c) for c in interior.coords] for interior in obj.interiors ] + path = " ".join([ + "M {0} L {1} z".format(coords[0], " L ".join(coords[1:])) + for coords in exterior_coords + interior_coords]) + return (f'') + + def save(self, margin:'unit'=5, scale:'px/unit'=10): + #specify margin in coordinate units + margin = 5 + + bboxes = [ list(obj.bounds) for obj, _style in self.objs ] + min_x = min( bbox[0] for bbox in bboxes ) - margin + min_y = min( bbox[1] for bbox in bboxes ) - margin + max_x = max( bbox[2] for bbox in bboxes ) + margin + max_y = max( bbox[3] for bbox in bboxes ) + margin + + width = max_x - min_x + height = max_y - min_y + + props = { + 'version': '1.1', + 'baseProfile': 'full', + 'width': '{width:.0f}px'.format(width = width*scale), + 'height': '{height:.0f}px'.format(height = height*scale), + 'viewBox': '%.1f,%.1f,%.1f,%.1f' % (min_x, min_y, width, height), + 'xmlns': 'http://www.w3.org/2000/svg', + 'xmlns:ev': 'http://www.w3.org/2001/xml-events', + 'xmlns:xlink': 'http://www.w3.org/1999/xlink' + } + + self.f.write(textwrap.dedent(r''' + + + {data} + + ''').format( + attrs = ' '.join(['{key:s}="{val:s}"'.format(key = key, val = props[key]) for key in props]), + data = '\n'.join(self.gen_svg(obj, *style) for obj, style in self.objs) + ).strip()) + def show_dialog(board): dialog = MeshPluginMainDialog(board) dialog.ShowModal() -- cgit