JPH0390965A - Ｃａｄシステム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　要〕 ＣＡＤシステムにおけるプリント基板上の配線経路の最
短ルートを決定する最短ルート抽出方式出発点から目的
点迄の最短ルートの探索を高速化することを目的とし、 ＣＡＤシステムにおけるプリント基板上の配線経路の最
短ルートを探索し決定する最短ルート抽出方式であって
、出発点から目的点までが１直線であるときの第１の配
線経路決定パターンと、出発点から目的点までが２直線
であるときの第２の配線経路決定パターンと、前記第１
及び第２の配線経路決定パターンでは結線できないとき
に方向を検索する検索パターンと、出発点からの出発方
向を決定するパターンを格納する第１のテーブルと、出
発後の方向変更を決定・するパターンを格納する第２の
テーブルと、途中で障害物に突き当たった場合に方向変
更を決定するパターンを格納する第３のテーブルとを備
え、最初に前記第１及び第２の配線経路決定パターンに
より配線経路を決定し、前記第１及び第２の配線経路決
定パターンでは配線経路が決定できないときに、前記検
索パターンを参照しつつ前記第１のテーブルにより出発
方向を決定し、出発方向の決定後、前記第２のテーブル
を参照して変更方向を決定し、さらに、変更方向におけ
る障害物の有無により第３のテーブルを参照して変更方
向を決定し、以降、第２及び第３のテーブルを繰返し参
照して出発点から目的点までの配線経路を決定するよう
に構成する。

〔産業上の利用分野〕

本発明は、ＣＡＤシステムにおけるプリント基板上の配
線経路の最短ルートを探索し決定する最短ルート抽出方
式に関する。

近年、半導体デバイスが高密度化、大規模化するにつれ
て、これを用いた回路設計も複雑になっている。そこで
、設計の途中過程をコンピュータ・シミュレーションに
より確認しながら設計作業を進めるＣＡＤ　（ｃｏｍｐ
ｕｔｅｒ　ａｉｄｅｄ　ｄｅｓｉｇｎ）システムが進展
している。

ＣＡＤシステムで重要な点はプリント基板上の配線経路
の決定である。即ち、素子間を接続する配線経路を所定
の規則に従って処理するが、配線区間の決定と配線経路
の決定が重要な過程であり、このため、配線経路の決定
には種々の配線アルゴリズムが提案されている。代表的
な配線アルゴリズムは後述する“しｅｅ”のアルゴリズ
ムである。

〔従来の技術〕

第８図は“Ｌｅｅ”のアルゴリズムによる配線経路の決
定方法である。

図中、Ｓは出発点、Ｔは目的点、斜線部分は障害物であ
る。この方法では配線経路の探索は次のように行う。即
ち、出発点Ｓに隣接する格子で「空」の格子すべてに「
１」を記入する。次に、「１」に隣接する「空」の格子
すべてに「２」を書き込む。このようにして、順次、「
３」、「４」「５」　・・・と埋め、目的点Ｔに到達す
ればＳ−Ｔ間に経路を見出すことができる。そして、記
入された数字を逆にたどればＳ−Ｔ間の最短ルートを決
定することができる。

〔発明が解決しようとする課題〕

第９．■０図は従来の問題点を説明する図である。

上述の方法では隣接するすべての「空」の格子に数字を
埋めて行くため、目的点とは全く逆の方向の格子にも数
字を記入することになる。また、数字を記入できる「空
」の格子がなくなった段階でしか最終結果の判断ができ
ない。

従って、第９図のように、明らかに経路が分かっている
場合でも出発点Ｓから目的点Ｔに向かって一直線とはい
かず、図示のように出発点から順次、「空」の格子に埋
め、目的点に隣接する「空」の格子に数字が記入される
まで、全く逆方向の格子にまで数字を埋めなければなら
ない。

また、第１０図のように、配線経路の無い場合でも全て
の「空」の格子に数字を記入しないと判断できない。

このように、従来方法では配線経路の決定の処理に膨大
な時間を要する。

本発明の目的は、出発点から目的点上の最短ルートの探
索および決定を高速化することが可能な最短ルート抽出
方式を提供することにある。

〔課題を解決するための手段〕

第１図は本発明の原理構成図である。

本発明は、ＣＡＤシステムにおけるプリント基板上の配
線経路の最短ルートを探索し決定する最短ルート抽出方
式であって、出発点から目的点までが１直線であるとき
の第１の配線経路決定パターン（１）と、出発点から目
的点までが２直線であるときの第２の配線経路決定パタ
ーン（１）と、前記第１及び第２の配線経路決定パター
ンでは結線できないときに方向を検索する検索パターン
（２）と、出発点からの出発方向を決定するパターンを
格納する第１のテーブル（３）と、出発後の方向変更を
決定するパターンを格納する第２のテーブル（４）と、
途中で障害物に突き当たった場合に方向変更を決定する
パターンを格納する第３のテーブル（５）により構成す
る。

〔作　用〕

本発明では、最初に前記第１及び第２の配線経路決定パ
ターンにより配線経路を決定し、前記前記第１及び第２
の配線経路決定パターンでは配線経路が決定できないと
きに、前記検索パターンを参照しつつ前記第１のテーブ
ルにより出発方向を決定し、出発方向の決定後、前記第
２のテーブルを参照して変更方向を決定し、さらに、変
更方向における障害物の有無により第３のテーブルを参
照して変更方向を決定し、以降、第２及び第３のテーブ
ルを繰返し参照して出発点から目的点までの配線経路を
決定する。

〔実施例〕

第２．３図は、本発明の基本的な配線経路の決定パター
ンである。これらの基本配線経路決定パターンで決定で
きる場合は最も単純な場合である。

第２図は第１の配線経路決定パターンであり、出発点Ｓ
に対し目的点Ｔが一直線で示される場合で、８方向が存
在し、２点で格子座標のＸ成分の小さいものを出発点、
大きいものを目的点とし、２点間のＸ方向の格子数（Δ
Ｘ）とＹ方向の格子数（ΔＹ）を求める。

この場合、ΔＸ＝Ｏ又はΔＹ＝Ｏ又は ΔＸ　＝　ΔＹ が本図のルートを使用する基本であり、ΔＸ＝０又はΔ
Ｙ＝０であれば、第２図の上下左右方向を示し、１Δｘ
１＝１ΔＹ１であれば４５度の斜め４方向を示すことに
なる。途中に障害物が無いかぎり出発点から目的点まで
１本線となる。

第３図は第２の配線経路決定パターンであり、縦方向又
は漢方向＋４５度（ルート１）、若しくは４５度十縦方
向又は横方向（ルート２〉で示される場合である。

上述のような基本配線経路決定パターンでは決定できな
いときは、以下の第４図を基本検索方向として、後述す
る方向決定パターンで配線経路を決定することになる。

第４図は方向検索の基本パターンであり、上記の第２．
３図では決定できない場合に、配線経路の検索方向を１
〜８の番号で表し、後述する方向決定パターンで方向を
決定する。即ち、上記の８つの方向を下記の基本パター
ンに適用する。

出発点からの出発方向の決定パターン ■ΔＸ＝Ｏ１Δｙ＞ｏ　　の時、 ２→４→３→１→５　の順序で探索 ■ΔＸ＝Ｏ１ΔＹ＜Ｏの時、 ８→６→７→１→５　の順序で探索 ■ΔＹ＝０　　の時、 ２→８→１→３→７　の順序で探索 ■Δｘ≧１ΔＹ１、ΔＹ〉０　の時、 ２→３→ｌ→８→４　の順序で探索 ■△Ｘ≧１ΔＹｌ、Δｙ＜ｏ　　の時、８→７→１→６
→２　の順序で探索 ■ΔＸ≦１ΔＹｌ、ΔＹ＞０　　の時、２→ｌ→３→８
→４　の順序で探索 ■ΔＸ≦１ΔＹ１、ΔＹ〈０　の時、 ８→１→７→６→２　の順序で探索 これらの７パターンを第１のテーブルに格納する。

次に、出発後の方向変更を下記の基本パターンで行う。

出発後の変更方向の決定パターン ■１△ｘ　　＞ｌΔＹ１、ＡＸ＞０ 変更方向＝１、 移動量＝ΔＸ−１△Ｙ ■１ΔＸ１）１ΔＹｌ、ＡＸ＜Ｏ 変更方向＝５、 移動量＝−１ΔＸ　＝　ΔＹ ■１△ＹＩ〉１ΔＸ１、ΔＹ＞０ 変更方向＝３、 移動量＝ΔＹ−ＡＸ ■１ΔＹｌ＞　　ΔＸＩ、ΔＹ＜０ 変更方向＝７、 移動量＝−１ΔＹｌ＝　　ＡＸ ■１ΔＸ１＝ｌΔＹｌ、ＡＸ〉０゜ の時、 変更方向＝２、 移動量＝ΔＸ の時、 の時、 の時、 の時、 ΔＹ＞０ ■　△Ｘｌ＝　　△Ｙｌ、ＡＸ＞０、ΔＹ＜０の時、 変更方向＝８、 移動量＝ΔＸ ■　Δｘｌ＝　△Ｙ　１ΔＸく０、ΔＹ＜０の時、 変更方向＝６、 移動量＝ΔＸ ■１Δｘ　＝　ΔＹ１、ＡＸ＜Ｏ，△Ｙ＞０の時、 変更方向＝４、 移動量＝ΔＸ これらの８パターンを第２のテーブルに格納する。

次に障害物に突き当たった場合の方向変更の基本パター
ンを示す。

障害物に突き当たった場合の変更方向の決定パターン ■方向＝１、ΔＹ〉０　の時、 変更方向＝現在方向＋（１→２→−１）の順■方向＝１
、ΔＹ＜Ｏの時、 変更方向＝現在方向＋（−１→−２→１）の順■方向＝
２、ｌΔＸＬ？：ｌΔＹｌ　　ノ時、変更方向＝現在方
向＋（−１→−２→１）の順■方向＝２．１Δｘ１く１
ΔＹ１　の時、変更方向＝現在方向＋（１→２→−ｌ）
の順■方向＝３、ΔＸ≧０　の時、 変更方向＝現在方向＋（−１→−２→１）の順■方向＝
３、ＡＸ＜Ｏの時、 変更方向＝現在方向＋（１→２→−１）の順■方向＝４
．１ΔＸＩ≧１ΔＹ　　の時、変更方向＝現在方向＋（
１→２→−１）の順■方向＝４．１ΔＸ１〈１ΔＹ１　
の時、変更方向＝現在方向＋（−１→−２→１）の順■
方向＝５、ΔＹ≧０　の時、 変更方向＝現在方向＋（−１→−２→１）の順Ｏ方向＝
５、ΔＹ〈０　の時、 変更方向＝現在方向＋（１→２→−１）の順０方向−６
，１△Ｘ１≧１ΔＹ１　の時、変更方向＝現在方向＋（
−１→−２→１）の順■方向＝６、ｌ　ＡＸ　ｌ　＜　
ｌΔＹｌ　　ノ時、変更方向＝現在方向＋（１→２→−
１）の順［相］方向＝７、ΔＸ≧０　の時、 変更方向＝現在方向＋（１→２→−１）の順■方向＝７
、ＡＸ＜Ｏの時、 変更方向＝現在方向＋（−１→−２→１）の順■方向＝
８．１ΔＸ１≧１ΔＹｌ　　の時、変更方向＝現在方向
＋（１→２→−１）の順［相］方向＝８．１ΔＸ１く１
ΔＹ１　の時、変更方向＝現在方向＋（−１→２→Ｐ）
の順但し、方向−〇の時、方向＝８ 方向＝−１の時、方向−７ 方向＝９の時、方向＝１ 方向＝１０の時、方向＝２ そして、３方向全て移動できない場合は経路が無いと判
断する。

これらの１６のパターンを第３のテーブルに格納する。

出発方向を決定後、格子上の現在位置と目的点間のΔＸ
、△Ｙから探索方向と移動量を求め探索方向の格子を調
べながら移動する。移動中に障害物に突き当たった場合
、最適な方向に方向変更し、方向変更後回びその地点と
目的点間の△Ｘ、ΔＹから探索方向と移動量を求める。

この処理を続けることにより目的点に到達することが可
能である。

第５図は本発明の一実施例フローチャートである。また
、第６図は本発明の他の実施例フローチャートである。

第５図は第２，３図の基本配線経路決定パターンに合致
する場合である。

第５図において、先ず、出発点と目的点の格子座標を求
める（１）。出発点のＸ座標と目的点のＸ座標を比較す
る（２）。ここでは処理の方向を左から右に向かって進
めるとする。出発点のＸ座標が目的点のＸ座標より大き
いときは出発点と目的点を入れ換えることになる（３）
。出発点のＸ座標が目的点のＸ座標より小さいときは、
出発点のＸ座標と目的点のＸ座標の差（Δχ）と出発点
のＹ座標と目的点のＹ座標の差（ΔＹ）を求めるく４）
。その結果、ΔＸ＝０又はΔＹ＝０又はΔＸ１−１△Ｙ
１か否かを判断する（５）。これらのいずれかを満足す
る場合は、上下左右方向か斜め４方向を示し第２図のパ
ターンに合致することになり、出発点と目的点は１本線
で結ばれる（６）。

これらのいずれにも合致しない場合は、つぎに第３図の
パターンに合致するか否かであり、先ず、ルート１のケ
ースとして縦又は横＋斜めの２本線で結べるか否か判断
しく７）、そうでなければ斜め十縦又は横の２本線で結
べるか否か判断する（８）。上述のステップ６．７．８
でない場合は次の第６図のフローチャートに移る。そし
てステップ６．７．８にて１本線で結べる場合、２本線
で結べる場合は第２．３図で探索できることになり（９
）、探索を行う。

第６図は他の実施例フローチャートであり、第２．３図
では探索できない場合に第１．２．３のテーブルを参照
して配線経路を決定する処理フローチャートである。第
７図は第６図の処理の一例である。

先ず、出発方向を決定する第１のテーブルを参照して、
既に求めた、ΔＸ、ΔＹから出発方向を決定する（１）
。次に決定した方向に「ＩＪ　　（１格子）進む（２）
。そして、その位置、即ち、現在位置と目的点との△Ｘ
、ΔＹを、変更方向を示す第２のテーブルを参照して求
め変更方向と、移動量を求め（３）、方向変更できるか
否か判断しく４）、方向変更できる場合は変更した方向
に移動量分だけ１つづつ進む（５）。この移動を進め目
的点に到達したか否か判断しく６）、到達していない場
合には次に障害物に突き当たったか否か判断しく７）、
障害物に突き当たった場合には、障害物に突き当たった
場合の第３のテーブルを参照し、障害物に突き当たる１
つ前の位置と目的点とのΔＸ、ΔＹより方向変更を行う
（８〉。そして、方向変更できるか否か判断しく９〉、
できる場合には変更した方向に「１」進む（１０）。

以下、ステップ３からこの手順を繰り返して行い目的点
までの配線経路を決定する。尚、ステップ６にて目的点
に到達した場合は探索が終了するが（１１）　、ステッ
プ１，４．９にて出発方向が決定できない場合、方向変
更出来ない場合等は探索できず（１２）　、終了する。

第７図は配線経路の決定の一例である。図示のように（
ａ）図から出発しくｄ）図で配線径路が決定する。図中
、Ｓは出発点、Ｔは目的点、斜線部分は障害物、散点部
分は障害物ではない共有格子である。

（ａ）において、 ■△Ｘ＝５　（目的点のＸ座標７−出発点のＸ座標２）
、ΔＹ＝４（目的点のＹ座標５−出発点のＹ座標ｌ）よ
り、第１テーブルの■を参照して出発方向は２→３→１
→８→４となる。第４図を参照して、座標（３・２）の
方向２は障害物が有るため進めない。評（２，２）の方
向３は障害物が有るためやはり進めない。座標（３・１
）の方向１は障害物がないため進めることができ、この
方向に出発方向が決定する。

■現在位置は上記■であり、この座標はΔＸ＝４、ΔＹ
＝４であるから変更方向を格納する第２のテーブルの■
を参照して、方向は２、移動量はΔＸ（＝４）となる。

しかし、第４図の「２」の方向の座標（４，２）は障害
物があるため進めず、障害物のある場合の方向変更を第
３のテーブルにより行う。

■現在方向は２、△Ｘ＝４、Δｙ＝４より変更方向は、
第３のテーブルの■を参照して現在方向＋（−１又は−
２又は１）の順で探索する。方向２−１は障害物がない
から変換方向が決定され座標（４，１）となる。

（ｂ）において、 ■現在位置■ではΔＸ＝３、ΔＹ＝４であるから、第２
のテーブルの■から進む方向は１であり、移動量はΔＹ
−１Δｘ１より１となる。しかし、座標（４，２）には
障害物があるため進めず、方向変更を行う。

■現在方向は３、ΔＸ＝３、△Ｙ＝４より第３のテーブ
ルの■より変更方向は現在方向＋（−１又は−２又は１
）で探索する。そして、方向３−１は障害物があるため
進めない。方向３−２は障害物がないため進めることが
でき変更方向は座標（５，１）に決定される。

■現在位置■ではΔＸ＝２、ΔＹ＝４より、第２のテー
ブルより方向は３、移動量は２、しかし座標（５，３）
に障害物ではないが共有格子があるため方向変更を行う
（座標（５・２））に移動する。

（Ｃ）において、 ■現在方向は３であり、ΔＸ＝２、ΔＹ＝３であるから
、第３のテーブルの■より変更方向は、現在方向＋（−
１又は−２又は１）である。

方向３−１は障害物がないため変更方向を座標（６・３
〉に決定する。

■現在位置■は座標（６，３）であるから、△Ｘ＝１、
ΔＹ＝２より第２のテーブルの■を参照して方向は３、
移動量は１、しかし、座標（６゜４）に共有格子がある
ため方向変更を行う。

■現在方向は２、ΔＸ＝１、ΔＹ＝２より、第３のテー
ブルの■を参照して変更方向は現在方向＋（１又は２又
は−１）。方向２＋１は共有格子があるため進めない。

方向２＋２は共有格子があるため進めない。そして、方
向２−１は障害物がないため変更方向を座標（７，３）
に決定する。

（ｄ）において、 ■現在位置■は座標（０，２＞であるから、ΔＸ＝０、
△Ｙ＝２より第２のテーブルを参照して方向は２、移動
量は２である。しかし、座標（７・４）には共有格子が
あるため方向変更を行う。

■現在方向は３であり、Δｘ＝０、Δｙ＝２より変更方
向は現在方向＋（−１又は−２又はｌ〉。

方向３−１は障害物がないため変更方向を座標（８，４
＞に決定する。

そして、Δｘ＝−１、ΔＹ＝１であるから、第２のテー
ブル■より方向は４、移動量は１となり目的点Ｔに到達
する。

〔発明の効果〕

以上説明したように、本発明ではチエツクの対象となる
格子は探索方向の格子のみであり、出発方向、変更方向
は予め出発点を持っているため判断が速く、変更できる
方向がない時点で「経路がない」と判断するため処理時
間が大幅に削減できる。さらに、経路変更方向は常に目
的点までの距離を詰めるようになっているため最短ルー
トで探索できる。

【図面の簡単な説明】

第１図は本発明の原理構成図、 第２図は第１の配線経路決定パターン、第３図は第２の
配線経路決定パターン、第４図は方向検索パターン、 第５図は第１及び第２の配線経路決定パターンに基づ〈
実施例フローチャート、 第６図は第１．２．３のテーブルに基づく配線経路決定
の実施例フローチャート、 第７図（ａ）〜（ｄ）は第６図フローチャートに基づく
出発点から目的点までの手順の一例、第８図は“Ｌｅｅ
”のアルゴリズムの説明図、及び 第９．１０図は従来の問題点の説明図である。 （符号の説明） １・・・配線経路決定パターン、 ２・・・検索テーブル、 ３・・・第１のテーブル、 ４・・・第２のテーブル、 ５・・・第３のテーブル。

Claims (1)

【特許請求の範囲】
1. １．ＣＡＤシステムにおけるプリント基板上の配線経路
   の最短ルートを探索し決定する最短ルート抽出方式であ
   って、 出発点から目的点までが１直線であるときの第１の配線
   経路決定パターン（１）と、 出発点から目的点までが２直線であるときの第２の配線
   経路決定パターン（１）と、 前記第１及び第２の配線経路決定パターンでは結線でき
   ないときに方向を検索する検索パターン（２）と、 出発点からの出発方向を決定するパターンを格納する第
   １のテーブル（３）と、 出発後の方向変更を決定するパターンを格納する第２の
   テーブル（４）と、 途中で障害物に突き当たった場合に方向変更を決定する
   パターンを格納する第３のテーブル（５）とを備え、 最初に前記第１及び第２の配線経路決定パターンにより
   配線経路を決定し、 前記第１及び第２の配線経路決定パターンでは配線経路
   が決定できないときに、前記検索パターンを参照しつつ
   前記第１のテーブルにより出発方向を決定し、出発方向
   の決定後、前記第２のテーブルを参照して変更方向を決
   定し、さらに、変更方向における障害物の有無により第
   ３のテーブルを参照して変更方向を決定し、以降、第２
   及び第３のテーブルを繰返し参照して出発点から目的点
   までの配線経路を決定するようにしたことを特徴とする
   最短ルート抽出方式。