How to draw a path and keep it out of pattern?

Hi sir,
I got a hard issue as attached file and figure below.
as this shown I want to draw a path by 13um , like the red-line I maked in picture.
This line start from left side of layer 71/0 , end at right side of layer 71/0 for the X-asix.
Path width is 13um and here is limitation:
1.keep it out of Mask pattern by 1um.
2.path "connections" can be "Diagonal" only.
3.Can been drawing run into the area of up-edge to down-edge by Y-asix.
as this case in GDS , we have around 1000um for the routing space.

this is a simple sample , in the real case we have so many Mask pattern and it is reason we can't make the path as a straight line.
Now , we make the path by manu manual , do you have any idea to make a scrpit for that?
in this case , we have so many path solution can be using , just make it keep the 3 rules.
I guess that I have to using xor or other function to find/define where the path routing area.
But I have no idea for the more detail .
Is it possible to make a script for that?

a.7z 143.2K


  • edited January 31

    Hi jiunnweiyeh

    Here's a example that sometimes works under certain senerio.

    Because this scrip is not clever enough to optimize to the pattern and path, you might need to fiddle around those magic numbers that hard coded in the script in order to make it even just show something if layout is changed.

    The script involves three main sections:

    genNodes :
    • Take RDL layer and defines region of intrest using a base layer
    • Convert layout to simple patterns to reduce DRC work load
    • Roughly split RDL pads and RDL routings
    • The spacing between RDL pads are the area for potential way points for routing
    • Generate nodes from those spacings, output to L(110, 0)
    • Take the results from genNodes L(110, 0)
    • Makes the nodes becomes on grid, main purpose is to classify nodes using their X valuse and put into nodeHash.
    • Sort nodeHash with X values, so now we get groups of node columns that is ready to be connected.
    • This returns the nodeHash for path routing
    • UsesnodeHash from genGridNodes, loop through each columns and find minium path for routing

    def genNodes(rdlLayer, roiLayer) rdlRoi = rdlLayer.inside(roiLayer) pix = # simplifying the RDL with a 2 * box dist = # usind layer.spacing(dist) to generate area for routing padSize = # threshold for pad, larger than this will be recognize as a obsticle pixVec = RBA::DVector::new(-pix, -pix) simplified = rdlRoi.collect_to_region{ |poly| bbox = poly.bbox center = (bbox.width < padSize) && (bbox.height < padSize) ? RBA::DBox::new(center + pixVec, center - pixVec) : bbox } padCenter = simplified.with_bbox_max( 0 .. + pix * 2) obsticles = simplified.without_bbox_max(0 .. + pix * 2) padSpace =, projection).polygons.raw.not_overlapping(padCenter).raw nodes1 = padSpace.merged(2) nodes2 = padSpace.not_interacting(nodes1).raw.not_overlapping(padCenter).raw.middle(as_boxes).sized(pix - dbu) nodes = (nodes1 + nodes2).not_interacting(simplified) padCenter.output(100, 0) # for visualization obsticles.output(100, 1) # for visualization padSpace .output(100, 2) # for visualization nodes1 .output(100, 3) # for visualization nodes2 .output(100, 4) # for visualization nodes .output(110, 0) # for visualization return nodes end def genGridNodes(nodesLayer) nodeHash = {} gridXsize = gridYsize = pix = pixVec = RBA::DVector::new(-pix, -pix) gridNodes = nodesLayer.collect_to_region{ |poly| center = gx = (center.x / gridXsize).to_int * gridXsize gy = (center.y / gridYsize).to_int * gridYsize gc = RBA::DPoint::new(gx, gy) if !nodeHash.key?(gx) then nodeHash[gx] = [] end nodeHash[gx].append(gy) RBA::DBox::new(gc - pixVec, gc + pixVec) } gridNodes.output(110, 1) # for visualization return nodeHash.sort.to_h end def genNodePath(nodeHash) nodePath = [] pathWidth = threshold = pathLayer = make_layer nodeHash.each{ |x, vys| nextNodes ={|y| RBA::DPoint::new(x, y)} if nodePath.empty? then nodePath << nextNodes[rand(nextNodes.length)] else closeDist = Float::INFINITY prevNode = nodePath[-1] closeNode = nextNodes[0] nextNodes.each{ |node| distance = node.distance(prevNode) if distance < closeDist then closeDist = distance closeNode = node end } if closeDist < threshold then nodePath << closeNode end end } pathLayer.insert(RBA::DPath::new(nodePath, pathWidth)) pathLayer.output(120, 0) # for visualization return pathLayer end rdlLayer = input( 3, 0) roiLayer = input(71, 0) nodesLayer = genNodes(rdlLayer, roiLayer) nodeHash = genGridNodes(nodesLayer) genNodePath(nodeHash)
  • edited January 31

    (1) genNodes simplify the patterns into orange boxes, later use layer space to extract spaced region.

    (2) genNodes space extracted by, however if the pads are not exactly aligned othogonally, or the pitch change between sections than this part will not work correctly.

    (3) genNodes simplify the space into nodes, again, if the pitch diviates alot from each other, this part also will not work.

    (4) after genGridNodes, the nodes is being grouped by column, iterate throuth each column and find nodes that is close to previous one.

    You probably can tell by now, this method cannot provide perfect 45 deg routing, and is not capable of doing tight routing, basically a run-and-prey type of algorithm.

  • Hi RawrRanger ,
    Thanks for your code , I will check it and try to make it into what my code if it is fine.

  • Holy cow!

    @jiunnweiyeh You like these kind of puzzles do you? :)

    From the academic viewpoint that looks like a variant of the path finding problem (see "A*" is an algorithm often used in routers for manhattan paths, so maybe this applies here. For any-angle paths algorithms are more complex though (see

    I wonder if there is a generic library for that case. As there is a Python module for everything, maybe someone published a useful implementation already?


  • Hi @Matthias
    Let me explain this request...
    This function , we called "stitching" .
    cause the (customer's design) DIE size is large than our exposure machine limitation.
    we have to cut our DIE as 2 part for photo Mask design.
    but we have some process issue and request for this line ... that must to make it keep out IO/line and other something pattern.
    I can't provided full GDS and rule in here , but the guildline would be what I means.
    in the real case, IO/Bump/line will more than the sample GDS I provided.
    so our designer has make the path as my first post by manual .
    when I using RawRanger 's code , I found some of issue and I am tring to fix it or list down the condination.
    Thanks very much for all of your help.

  • Hi jiunnweiyeh,

    Here's a revised version, the major differences are:
    1) Can route multiple path in predefined regions, the script will perform auto route if routing is not successful
    2) Now it can route mostly at 45 deg
    3) Reduces huge swing during routing, will propagate using small zig-zag when ever possible

    To make it route multiple paths, a guiding layer is required, in this case the layer in teal "L(72, 0) in code" is drawn for thsi purpose.

    def genNodes(rdlRoi) pix = # simplifying the RDL with a 2 * box dist = # usind layer.spacing(dist) to generate area for routing padSize = # threshold for pad, larger than this will be recognize as a obsticle gridXsize = gridYsize = pixVec = RBA::DVector::new(-pix, -pix) simplified = rdlRoi.collect_to_region{ |poly| bbox = poly.bbox center = gx = (center.x / gridXsize).to_int * gridXsize gy = (center.y / gridYsize).to_int * gridYsize gc = RBA::DPoint::new(gx, gy) (bbox.width < padSize) && (bbox.height < padSize) ? RBA::DBox::new(gc + pixVec, gc - pixVec) : bbox } padCenter = simplified.with_bbox_max( 0 .. + pix * 2) obsticles = simplified.without_bbox_max(0 .. + pix * 2) padSpace =, projection).polygons.raw.not_interacting(obsticles) crossPoint = padSpace.merged(2) node = padSpace.raw.sized( - dbu) node = node.not_interacting(simplified) #padCenter.output(100, 0) # for visualization #obsticles.output(100, 1) # for visualization #padSpace .output(100, 2) # for visualization node .output(100, 3) # for visualization return node end def genGridNodes(nodesLayer) nodeHash = {} gridNodes = nodesLayer.collect_to_region{ |poly| center = if !nodeHash.key?(center.x) then nodeHash[center.x] = [] end nodeHash[center.x].append(center.y) } return nodeHash.sort.to_h end def tidyGridNodes(nodeHash) # tidyup each column by x value again, groups columns # with x direction distance < threshold # this reduce the chance of path routing at a wierd angle threshold = newNodeHash = {} nodeHash.each{ |key, v| if newNodeHash.empty? then newNodeHash[key] = v else preKey = newNodeHash.keys[-1] delta = key - preKey if (delta < threshold) then newNodeHash[preKey] += v else newNodeHash[key] = v end end } return newNodeHash end def genNodePath(nodeHash, startPoint = 0) nodePath = [] nodeHash.each{ |x, vys| nextNodes ={|y| RBA::DPoint::new(x, y)} if nodePath.empty? then startPoint = [startPoint, nextNodes.length].min nodePath << nextNodes[startPoint] else prevNode = nodePath[-1] nextNodes = nextNodes.sort_by{ |node| node.distance(prevNode)} closeNode = nextNodes[0] # this part makes the routing tends to go in a zig-zag pattern # instead of sway in particular direction # pick two candidate that is close to previous point, compares the angle vector # choose the one that is vertical to previous path if (nextNodes.length > 1 ) && (nodePath.length > 1) then candidate1 = nextNodes[0] candidate2 = nextNodes[1] cadiDist1 = candidate1.distance(prevNode) cadiDist2 = candidate2.distance(prevNode) if (cadiDist1/cadiDist2).between?(0.6, 1.4)then preVec = prevNode - nodePath[-2] candiVec1 = candidate1 - prevNode candiVec2 = candidate2 - prevNode closeNode = (candiVec1.y * preVec.y) < 0 ? candidate1 : candidate2 end end # after point is choosen, tried to rectify the path to be at 45 deg angle # if path is at a angle that is too large or too small, tried to insert addition # point and make it connect two points in 45 deg # if the angle is almost at 45 deg, we'll just modify next point coordinate slightly # to make it at exact 45 deg angleVec = closeNode - prevNode if !(angleVec.y / angleVec.x).abs.between?(0.4, 1.6) then e1a = RBA::DEdge::new(prevNode, prevNode + RBA::DVector::new( 1, 1)) e1b = RBA::DEdge::new(prevNode, prevNode + RBA::DVector::new( 1, -1)) e2a = RBA::DEdge::new(closeNode, closeNode + RBA::DVector::new(-1, 1)) e2b = RBA::DEdge::new(closeNode, closeNode + RBA::DVector::new(-1, -1)) cutPt1 = e1a.cut_point( (e1a.is_parallel?(e2a)) ? e2b : e2a) cutPt2 = e1b.cut_point( (e1b.is_parallel?(e2a)) ? e2b : e2a) cutDst1 = cutPt1.distance(prevNode) + cutPt1.distance(closeNode) cutDst2 = cutPt2.distance(prevNode) + cutPt2.distance(closeNode) cutPt = (cutDst1 > cutDst2) ? cutPt1 : cutPt2 nodePath << cutPt nodePath << closeNode else dir = (angleVec.y / angleVec.y.abs) nodePath << prevNode + RBA::DVector::new(angleVec.x, dir * angleVec.x) end end } return nodePath end def routePath(rdlLayer, roiLayer, pathWidth = goodPaths = [] badPaths = [] roiLayer.collect{ |p| eachROI = make_layer eachROI.insert(p) rdlRoi = rdlLayer.interacting(eachROI) nodesLayer = genNodes(rdlRoi) nodeHash = genGridNodes(nodesLayer) nodeHash = tidyGridNodes(nodeHash) maxRetry = nodeHash[nodeHash.keys[0]].length # auto perform retry if the inserted path interfers with RDL pattern # retry by changing the entery point of first node (0..maxRetry).each{ |i| pathLayer = make_layer nodePath = genNodePath(nodeHash, startPoint = i) pathObj = RBA::DPath::new(nodePath, pathWidth) pathLayer.insert(pathObj) noInterfere = rdlRoi.interacting(pathLayer).count == 0 if noInterfere then goodPaths.append(pathObj) break elsif i == (maxRetry-1) badPaths.append(pathObj) end } } return goodPaths, badPaths end cellView = RBA::CellView::active layout = cellView.layout cell = cellView.cell rdlLayer = input( 2, 0) roiLayer = input(72, 0) goodPaths, badPaths = routePath(rdlLayer, roiLayer) # insert using path instead of drc layer, due to drc layer converts everything into polygons # which makes it difficult to be edited manually. goodPaths.each{ |path| cell.shapes(layout.layer(120, 0)).insert(path)} badPaths .each{ |path| cell.shapes(layout.layer(120, 1)).insert(path)}
  • edited February 2

    And for optimizing the route, implementing an A* or other type of path finding algorithms will be neccessary if the layout becomes complicated, without this type of optimization, the path might no always get all the way through to another side.

    Due to the example shown here got a quite distinct characteristic, that is the each obsticles is small enough, and in most cases thay don't populated at a way that makes dead ends, so brute forcing this becomes a quick and somewhat feasible method.

Sign In or Register to comment.