# 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)`
###### genGridNodes:
• 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
###### genNodePath:
• Uses`nodeHash` from `genGridNodes`, loop through each columns and find minium path for routing
``````def genNodes(rdlLayer, roiLayer)
rdlRoi  = rdlLayer.inside(roiLayer)
pix     =   5.um         # simplifying the RDL with a 2 * pix.um box
dist    = 180.um         # usind layer.spacing(dist) to generate area for routing
padSize =  50.um         # 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.center
(bbox.width < padSize) && (bbox.height < padSize) ? RBA::DBox::new(center + pixVec, center - pixVec) : bbox
}

padCenter  = simplified.with_bbox_max(   0 .. 1.0.um + pix * 2)
obsticles  = simplified.without_bbox_max(0 .. 1.0.um + pix * 2)
nodes      = (nodes1 + nodes2).not_interacting(simplified)

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  =  5.um
gridYsize  =  5.um
pix        =  5.um
pixVec     = RBA::DVector::new(-pix, -pix)

gridNodes = nodesLayer.collect_to_region{ |poly|
center = poly.bbox.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 = 13.um
threshold = 300.um
pathLayer = make_layer

nodeHash.each{ |x, vys|
nextNodes = vys.sort.map{|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 layer.space, 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.
Thanks.

• 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 https://en.wikipedia.org/wiki/Pathfinding). "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 https://en.wikipedia.org/wiki/Any-angle_path_planning).

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?

Matthias

• 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       =   5.um         # simplifying the RDL with a 2 * pix.um box
dist      = 180.um         # usind layer.spacing(dist) to generate area for routing
padSize   =  50.um         # threshold for pad, larger than this will be recognize as a obsticle
gridXsize =   5.um
gridYsize =   5.um
pixVec    = RBA::DVector::new(-pix, -pix)

simplified = rdlRoi.collect_to_region{ |poly|
bbox   = poly.bbox
center = 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 .. 1.0.um + pix * 2)
obsticles  = simplified.without_bbox_max(0 .. 1.0.um + pix * 2)
node       = node.not_interacting(simplified)

#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 = poly.bbox.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   = 35.um
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 = vys.sort.map{|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]

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 = 13.um)
goodPaths  = []

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)
end
}
}
end

cellView = RBA::CellView::active
layout   = cellView.layout
cell     = cellView.cell
rdlLayer = input( 2, 0)
roiLayer = input(72, 0)

# 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)}