* This article contains the following executables: NEVIN.ZIP
Randy holds a BS in computer science from Oregon State University and an MS in computer science from the University of Washington. He has worked for Microsoft since 1983 on various programming languages and networking products. He can be reached at 1731 211th PL NE, Redmond, WA 98053.
A few years ago, a friend of mine designed an adapter board for the IBM PC. The tools he used were blue and red strips of tape, a sharp knife, large sheets of clear plastic, and a generous amount of patience. It took him several weeks, and after the first board was tested he discovered that some of the traces were incorrect and had to be cut with the knife and rerouted with a solder and wires. This caused me to start thinking about ways to use the power of the computer to simplify this tedious, error-prone job.
The design of a printed circuit board implements an electronic circuit. First you create a schematic. From this you derive a list of chips and other components that perform the required functions, and a list of the pins that need to be connected. Together, these lists are referred to as the "net-list." As long as the connections are made correctly, you usually don't care where the traces (the wires embedded in the board) are placed.
As you can imagine (or may already know), designing a PC board is a complex search problem with a seemingly infinite number of possible solutions. Luckily, there are algorithms from the field of artificial intelligence that we can use to design computer programs called "autorouters" that do this searching for you. In this article, I'll look at two algorithms: The breadth-first and A* (pronounced as "A Star") search algorithms. This article is actually based on an application I wrote to layout, view, and laser-print circuit board designs. Because of the length of that application (nearly 2500 lines of C code), I'll focus my discussion here on the pseudocode that implements the two algorithms mentioned and the source code that implements the A* algorithm. The entire C source code that implements the printed circuit board layout system is available on DDJ's Forum on CompuServe, DDJ's on-line service, and on the disks mentioned at the end of this article.
Autorouting is one of a class of global optimization problems that are difficult to solve. A good circuit board layout, for example, minimizes things like:
Autorouting can also be viewed as a collection of search problems. The individual problems deal with finding a route and laying down a trace between two locations. There are many algorithms for solving search problems, each with different running time characteristics and data space requirements.
Autorouting search algorithms typically operate in two phases{1}, treating the board as a matrix of cells. The first phase starts at the source cell and searches for the target cell, usually by going in several directions at the same time. The algorithm builds an auxiliary data structure to keep track of how each cell was reached (this is referred to as "Pred" in the algorithms in Figure 1 and Figure 2 ). The first phase ends when the target cell has been found, and the second phase begins. If the first phase exhausts all possibilities without reaching the target cell, then no route exists between them, and there is no reason to do the second phase.
BFS Algorithm (* breadth-first search *)
(* Search a graph or state space, depending on the problem
definition. *)
(* S is the start node, T is the goal node. *)
(* Open is an ordered list of nodes (ordered by arrival time;
nodes enter at the tail and leave at the head), also called a
queue. Closed is a set of nodes (order doesn't matter). In
general, nodes that need to be searched are put on Open. As they
are searched, they are removed from Open and put in Closed. *)
(* Pred is defined for each node, and is a list of "came from"
indications, so when we finally reach T, we traverse Pred to
construct a path to S. *)
1 Open <- {S} (* a list of one element *)
Closed <- {} (* the empty set *)
Pred [S] <- NULL, found <- FALSE
WHILE Open <> {} and not found DO
5 x <- the first node on Open
Open <- Open - {x} (* remove x from Open *)
Closed <- Closed + {x} (* put x in Closed *)
IF x = T THEN found <- TRUE (* we're done *)
ELSE (* continue search through node x *)
10 let R be the set of neighboring nodes of x
FOR each y in R DO
IF y is not on Open or in Closed THEN
Pred[y] <- x (* remember where we came from *)
Open <- Open + {y} (* put y on Open (at the tail) *)
15 IF found THEN
use Pred[T] to find Pred[Pred[T]] and so on until S is reached
(* this traces out the solution path in reverse *)
ELSE T cannot be reached from S
The second phase uses the auxiliary data structure to trace the route from the target cell back to the source cell, actually laying down the electrical connections. The second phase is identical for the breadth-first and A* search algorithms. But the first phase is different, and it is this phase that gives these algorithms different behaviors.
The main data structures used in the first phase are the Open queue and the Closed set, which hold cell coordinates. Because a cell's coordinates uniquely identify it, we'll say that the Open queue and Closed set contain cells. Cell coordinates will be represented as r2c3s1 for the cell at row 2, column 3, side 1, or as r2c3 when it is understood that all cells are on the same side of the board. To remind ourselves that Open is a queue and Closed is a set, when we talk about adding cells to them, we will put the cells "on" the queue and "in" the set. Initially, the Open queue contains the source cell and the Closed set is empty.
The first phase is a loop, which removes an element from the head of the Open queue, puts it in the Closed set (which indicates that it has been searched), and checks to see if it is the target cell. If so, the first phase is done. Otherwise, the neighbors of the cell (those adjacent to it) are placed on the Open queue, and the loop continues. As we'll see later, the essential difference in the breadth-first and A* search algorithms is the order in which the neighbors are placed on the Open queue.
Figure 1 contains pseudocode for the breadth-first search algorithm. This algorithm works by processing a first in/first out (FIFO) queue of open cells; that is, cells that have been reached, but not yet searched. Initially, the open queue contains only the source cell. A cell is removed from the head of the open queue, placed in the set of closed cells (cells that have been searched), and checked to see if it is the target cell. If not, its neighbors are placed at the tail of the open queue. Neighboring cells that have already been reached are ignored. (If a cell's coordinates are on the open queue or in the closed set, then it has been reached, otherwise, it has not.) This continues until one of two things happens:
Figure 2 shows the behavior of Lee's algorithm while searching for a path between the source cell S (r5c5) and the target cell T (r8c8). Lee's algorithm does not specify the order in which neighboring cells are placed on the open queue, but we'll use the compass directions north, east, south, and west, followed by northeast, southeast, southwest, and northwest. This order tends to produce traces with a minimal number of turns.
In Figure 2a, the source cell (r5c5) has been searched, and its eight neighbors have been placed on the open queue. The arrows indicate the direction from which each cell was reached, and correspond to the Pred data structure. After the first eight cells on the open queue have been reached and moved to the closed set, the algorithm searches the configuration in Figure 2b, where there are sixteen cells on the open queue. Once these sixteen cells have been searched, the configuration in Figure 2c is reached. Now the target cell (r8c8) is fourth from the end on the open queue, and a solution is imminent. Searching r8c8, the algorithm recognizes it as the target cell, and uses the Pred data structure to construct a trace back to the source cell.
You can see that the search progresses outward from the source cell in all directions, like ripples when you throw a pebble into the water. If we double the size of the problem so that S and T are six cells apart, the number of cells searched and therefore the processing time will be about four times as great. If we triple the size of the problem, the number of cells searched will be roughly nine times more. Thus, the behavior of Lee's algorithm is quadratic in the size of the problem, which makes it infeasible for large problems.
Figure 3 gives pseudocode for the A* search algorithm, while Listing One shows it implemented in C. This method also works by processing a queue of open cells, which initially contains only the source cell. But this is a priority queue, which means cells are inserted according to the estimated distance to the target{3}, not just at the end. Cells that are on the shortest estimated path from source to target go to the head of the queue. The A* algorithm removes the cell from the head of the open queue and checks to see if it's the target. If not, the neighboring cells are put on the open queue at the proper position. The algorithm checks neighboring cells that have already been searched to see if the new path between them and the source is shorter than the previous one. If it is, they are repositioned on the open queue according to the new estimated path length from source to target. As in breadth-first search, this continues until the target cell has been found or the open queue is empty.
A* Algorithm (* heuristic search *)
(* Search a graph or state space, depending on the problem
definition. *)
(* S is the start node, T is the goal node. *)
(* Open is an ordered list of nodes (ordered by lowest F value;
see below), also called a priority queue. Closed is a set of
nodes (order doesn't matter). In general, nodes that need to be
searched are put on Open (at the proper position). As they are
searched, they are removed from Open and put in Closed.
Occasionally a newer, better route will be found to a node after
it has already been searched, in which case we remove it from
Closed and put it back on Open to be reconsidered. *)
(* G[x] is the distance already traveled to get from S to node x,
and is known exactly. H(x) is a function (heuristic) which
returns an estimate of the distance from node x to T. F[x] is
the estimated distance from S to T by going through node x, and
is computed by F[x] = G[x] + H(x). H(x) can be calculated for
any node, but F[x] and G[x] only become defined when node x is
visited. *)
(* Pred is defined for each node, and is a list of "came from"
indications, so when we finally reach T, we traverse Pred to
construct a path to S. *)
(* Distance (x,y) is a function for calculating the distance
between two neighboring nodes. *)
1 Open <- {S} (* a list of one element *)
Closed <- {} (* the empty set *)
G[S] <- 0, F[S] <- 0, Pred[S] <- NULL, found <- FALSE
WHILE Open <> {} and not found DO
5 x <- the first node on Open (* node with smallest F value *)
Open <- Open - {x} (* remove x from Open *)
Closed <- Closed + {x} (* put x in Closed *)
IF x = T THEN found <- TRUE (* we're done *)
ELSE (* continue search through node x *)
10 let R be the set of neighboring nodes of x
FOR each y in R DO
IF y is not on Open or in Closed THEN
G[y] <- G[x] + Distance (x,y)
F[y] <- G[y] + H(y) (* estimate solution path
length *)
15 Pred[y] <- x (* remember where we came from *)
Open <- Open + {y} (* put y on Open *)
ELSE (* y is on Open or in Closed *)
IF (G[x] + Distance (x,y)) < G[y] THEN
(* we've found a better route to y *)
20 G[y] <- G[x] + Distance (x,y)
F[y] <- G[y] + H(y)
Pred[y] <- x (* remember where we came from *)
IF y is on Open THEN
reposition y according to F[y]
25 ELSE (* y is in Closed *)
Closed <- Closed - {y} (* remove y from Closed *)
Open <- Open + {y} (* put y on Open *)
IF found THEN
use Pred[T] to find Pred[Pred[T]] and so on until S is reached
30 (* this traces out the solution path in reverse *)
ELSE T cannot be reached from S
A* depends on being able to estimate the distance between a cell and the target cell. In the case of autorouting, a simple measure of this distance is available, and this helps A* to concentrate the search in the direction most likely to succeed. The more accurate the estimate, the faster the search.
In practice, A* does not suffer from the quadratic behavior of Lee's algorithm, it solves similar problems faster and can be applied to larger problems where Lee's algorithm performs poorly. As the distance between the source and target cells increases, the number of cells processed by A* increases, but not as dramatically as with Lee's algorithm.
Figure 4 shows the behavior of the A* search algorithm. A* does not specify whether new cells go in front of or behind cells already on the open queue that evaluate to identical estimated path lengths. We use the convention that they are placed in front. This minimizes the time to insert a cell on the open queue.
In Figure 4a, the source cell (r3c3) has been searched, and its eight neighbors are on the open queue. Each cell on the open queue also includes the estimated length of the shortest path from S to T that goes through that cell. After the first cell (r4c4) has been searched and moved to the closed set, the configuration in Figure 4b is reached, where there are 12 cells on the open queue. After searching the next cell (r5c5), the algorithm reaches the configuration in Figure 4c. Now the target cell (r6c6) is at the head of the open queue, and a solution will be found on the next iteration of the loop. Searching r6c6, A* recognizes it as the target and uses the Pred data structure to construct a trace back to the source cell.
You can see that the search progresses more directly toward the target cell. The target draws the search much as the earth's gravity pulls objects toward the center of mass. If we double the size of the problem, the search will process about twice as many cells, and if we triple its size, the search will run through three times as many. This linear behavior makes A* more attractive for autorouting than the quadratic Lee's algorithm. With the incorporation of the heuristic -- the rule, that guides the search in the direction most likely to succeed -- it is difficult to estimate worst case behavior. However, A* will never take more time than Lee's algorithm, and it will never search any cells that Lee's algorithm could avoid.
The algorithms in Figures 1 and 3 solve the general search problem. When these algorithms are implemented and customized to a particular application, there are ways to speed them up.
The A* algorithm in Figure 3 recomputes the heuristic H(y) when it discovers a better way to reach a cell. Depending on how difficult this heuristic is to compute, you can probably save some work at the expense of complicating the algorithm. When lines 20 and 21 of Figure 3 are executed, the previous values of G[y] and F[y] are destroyed. But F[y] = G[y] + H(y), so you could save F[y] - G[y] (which is H(y)) in a temporary variable, and use that variable instead of recomputing H(y) on line 21. Also, the common sub-expression G[x] + Distance(x,y) should be placed in a temporary variable, instead of being computed twice (lines 18 and 20).
Often, rather than searching for a path between two individual cells, what is really desired is a path between one of a set of source cells and one of a set of target cells (as when connecting power and ground pins). Both algorithms can be modified by adding the entire set of source cells to the initial open queue, and checking for a member of the set of target cells on each iteration. When this is done, the heuristic used by the A* algorithm becomes more complicated. It must estimate the minimum distance from the current cell to any one of the target cells.
For breadth-first search, once the target cell is placed on the open queue, it is pointless to add any more cells to the open queue because when this happens, the problem is solved. An appropriate shortcut would be to insert a check before line 13 in Figure 1 to see if y is the target cell. If it is, use Pred[y] to construct the trace back to the source cell, and return.
Both search algorithms use quite a bit of memory to solve problems of non-trivial size. The breadth-first search algorithm needs memory to represent the board, the predecessor structure, and the closed set. The A* search algorithm needs these also, plus structures for F[x] and G[x] (see Figure 3). In addition, both algorithms dynamically allocate memory for the open cell queue.
The board is represented as a pair of two-dimensional arrays -- one for the front side, the other for the back -- in which the dimensions are the number of rows and columns of cells. Not counting holes and traces relating to holes (Figure 5, groups A, B, and C), there are 30 possible cell contents, which can be represented with 5 bits per cell.
The hole-related cells are more difficult to enumerate; they can be combined in many ways. If we simply assign 1 bit to each of the eight traces in groups B and C, and add one more bit to indicate a hole, 14 bits will be sufficient to represent any cell. On a board of N rows and M columns, we'll need N*M*28 bits total.
The predecessor structure is also a pair of two-dimensional arrays, where an entry must be able to represent one of the eight compass directions or an indication for the opposite side of the board. This takes 4 bits per cell, or N*M*8 bits total.
The closed set can be represented by a pair of two-dimensional, single-bit arrays, where a bit is one if the corresponding cell has been searched, and zero otherwise. This will take N*M*2 bits total.
F[x] and G[x] will be similar to the board arrays, but they must contain a 16-bit integer for each cell, requiring N*M*64 bits total. Note that if memory usage needs to be minimized at the cost of increased processing time, we could omit the F[x] arrays, and calculate the F values as they are needed from the G[x] arrays and the heuristic function, H(x).
Breadth-first search thus requires N*M*38 bits, and A* needs N*M*102 bits of static memory. For a printed circuit board 4 x 13 inches (80 cells x 260 cells), breadth-first search will need 98,800 bytes and A* will need 265,200 bytes. Different algorithms that solve the same problem often trade off memory against processing time to achieve better performance. This is the case with A* versus the breadth-first search.</entry>
Despite the fact that A* requires more memory than breadth-first search, A* exhibits better memory usage patterns. This is because it shows better locality of reference than breadth-first search. Locality of reference deals with the sequence in which memory locations are used, and consists of two rules of thumb: 1. The memory location currently being referenced is likely to be referenced again in the near future, and 2. Memory locations near the one currently being referenced are likely to be referenced in the near future.
When the first rule holds true for a given program, that program can probably benefit from a memory cache. When the second rule holds true, the program can probably benefit from a virtual memory environment with a least-recently-used page preemption policy. Most computer systems with virtual memory and caches apply them to both code and data, so programs that exhibit good locality of reference should benefit from both rules.
This becomes a factor when solving large problems (say, routing a printed circuit board that is 10 inches in both dimensions). In a virtual memory environment, improved locality of reference can minimize swapping. In an environment with cache memory, improved locality of reference can increase the cache hit rate. Both of these tend to decrease the total running time.
The memory references in the breadth-first search algorithm go around and around in circles of constantly increasing size, and do not reflect a common locality of reference. Thus, the breadth-first search algorithm is not able to take good advantage of virtual memory or a memory cache. The memory references of A* tend to be from the same area of the printed circuit board for extended periods of time, taking better advantage of these mechanisms. In a large problem, this helps to offset the extra memory that A* requires by adding speed beyond that provided by the basic algorithm. Improved locality of reference by itself may not be a sufficient reason to select A* over breadth-first search, but it is icing on the cake.
The A* search algorithm uses a heuristic to estimate the distance between the current cell and the target cell. As implemented in the autorouting program, the heuristic is a simple geometric distance approximation. Figure 5 illustrates all the possible cell types used to construct a trace, grouped by type. For each group, the distance of that cell type is also given. These distances are calculated based on a cell size of 50 x 50 mils. (A mil is 1/1000 inch, so the autorouter uses 20 cells/inch. A typical full-length adapter board for an IBM PC is 4-inches high and 13-inches long, or 80-cell rows x 260-cell columns.)
The group B and C traces can coexist in the same cell, so a hole can have up to 16 traces connecting it with other cells (eight on each side of the board). Also, the parallel traces of group F can coexist in the same cell (on the same side of the board), as shown by group J. This allows the routing of two traces through the same cell, providing the higher density required by some circuits (memory arrays, for example). Aside from these exceptions, cells can only contain one trace type (on each side of the board).
To determine the approximate distance of a trace that will connect two holes, view the board as a matrix, the differences in cell coordinates are three rows and five columns. The shortest path between them will use a diagonal trace across three cells and a horizontal trace across two cells. Using the cell types in Figure 5, the length of the trace will be 23 + (2 * 71) + 60 + 50 + 12 = 287 mils. A trace that uses a routing hole to go from one side of the board to the other covers a greater distance than one that goes diagonally across a cell (group E in Figure 5) and stays on the same side of the board because part of its path goes around the edge of a circle.
A typical hole is 25 mils in diameter, and is at the center of a cell. To calculate the distance of a trace through a routing hole, measure the section of the hole between the two connecting traces. For instance, an entering trace can connect to a hole at a point A, and possible exiting traces on the opposite side of the board at points B, C, D, and E. The distances between A and each of these points are 10, 20, 29, and 39 mils, respectively. To calculate these, use the geometric formula Circumference = PI * Diameter (approximately 78.5 mils) and divide by 8 (a 1/8 section of a hole is approximately 9.8 mils), add 1, 2, 3, and 4 of these sections, then round off to an integer.
The heuristic in the autorouting program includes a penalty when a trace takes a turn or switches to the other side of the board through a routing hole because turns are often the weak points in a circuit, and traces are more likely to break at a turn than in a straight part. The penalty encourages A* to use straight lines, and even allows a slightly longer trace to be selected over one with too many turns. The amount of penalty depends on the kind of turn; sharper turns are assessed a larger penalty. Routing holes incur a significant penalty, since overusing them early in the routing process can make later traces more difficult or even impossible to construct because a routing hole dedicates a cell exclusively to a single trace, for both sides of the board. Such a cell is not available to later routing, thus reducing the total number of cells that can be used. -- R.N.
_AUTOROUTING WITH THE A* ALGORITHM_
by Randy Nevin
* PC BOARD LAYOUT SYSTEM TO ACCOMPANY _AUTOROUTING WITH THE A* ALGORITHM_ BY RANDY NEVIN IS
ATTACHED TO THE END OF THE FOLLOWING LISTINGS
[LISTING ONE]
BFS Algorithm (* breadth-first search *)
(* Search a graph or state space, depending on the problem definition. *)
(* S is the start node, T is the goal node. *)
(* Open is an ordered list of nodes (ordered by arrival time; nodes enter
at the tail and leave at the head), also called a queue. Closed is a set
of nodes (order doesn't matter). In general, nodes that need to be
searched are put on Open. As they are searched, they are removed from
Open and put in Closed. *)
(* Pred is defined for each node, and is a list of "came from" indications,
so when we finally reach T, we traverse Pred to construct a path to S. *)
1 Open <- {S} (* a list of one element *)
Closed <- {} (* the empty set *)
Pred[S] <- NULL, found <- FALSE
WHILE Open <> {} and not found DO
5 x <- the first node on Open
Open <- Open - {x} (* remove x from Open *)
Closed <- Closed + {x} (* put x in Closed *)
IF x = T THEN found <- TRUE (* we're done *)
ELSE (* continue search through node x *)
10 let R be the set of neighboring nodes of x
FOR each y in R DO
IF y is not on Open or in Closed THEN
Pred[y] <- x (* remember where we came from *)
Open <- Open + {y} (* put y on Open (at the tail) *)
15 IF found THEN
use Pred[T] to find Pred[Pred[T]] and so on until S is reached
(* this traces out the solution path in reverse *)
ELSE T cannot be reached from S
Figure 3: Pseudo-code for the A* algorithm
A* Algorithm (* heuristic search *)
(* Search a graph or state space, depending on the problem definition. *)
(* S is the start node, T is the goal node. *)
(* Open is an ordered list of nodes (ordered by lowest F value; see below),
also called a priority queue. Closed is a set of nodes (order doesn't
matter). In general, nodes that need to be searched are put on Open (at
the proper position). As they are searched, they are removed from Open
and put in Closed. Occasionally a newer, better route will be found to a
node after it has already been searched, in which case we remove it from
Closed and put it back on Open to be reconsidered. *)
(* G[x] is the distance already traveled to get from S to node x, and is
known exactly. H(x) is a function (heuristic) which returns an estimate
of the distance from node x to T. F[x] is the estimated distance from S
to T by going through node x, and is computed by F[x] = G[x] + H(x).
H(x) can be calculated for any node, but F[x] and G[x] only become
defined when node x is visited. *)
(* Pred is defined for each node, and is a list of "came from" indications,
so when we finally reach T, we traverse Pred to construct a path to
S. *)
(* Distance(x,y) is a function for calculating the distance between two
neighboring nodes. *)
1 Open <- {S} (* a list of one element *)
Closed <- {} (* the empty set *)
G[S] <- 0, F[S] <- 0, Pred[S] <- NULL, found <- FALSE
WHILE Open <> {} and not found DO
5 x <- the first node on Open (* node with smallest F value *)
Open <- Open - {x} (* remove x from Open *)
Closed <- Closed + {x} (* put x in Closed *)
IF x = T THEN found <- TRUE (* we're done *)
ELSE (* continue search through node x *)
10 let R be the set of neighboring nodes of x
FOR each y in R DO
IF y is not on Open or in Closed THEN
G[y] <- G[x] + Distance(x,y)
F[y] <- G[y] + H(y) (* estimate solution path length *)
15 Pred[y] <- x (* remember where we came from *)
Open <- Open + {y} (* put y on Open *)
ELSE (* y is on Open or in Closed *)
IF (G[x] + Distance(x,y)) < G[y] THEN
(* we've found a better route to y *)
20 G[y] <- G[x] + Distance(x,y)
F[y] <- G[y] + H(y)
Pred[y] <- x (* remember where we came from *)
IF y is on Open THEN
reposition y according to F[y]
25 ELSE (* y is in Closed *)
Closed <- Closed - {y} (* remove y from Closed *)
Open <- Open + {y} (* put y on Open *)
IF found THEN
use Pred[T] to find Pred[Pred[T]] and so on until S is reached
30 (* this traces out the solution path in reverse *)
ELSE T cannot be reached from S
Copyright © 1989, Dr. Dobb's Journal
/*
** printed circuit board autorouter, Copyright (C) Randy Nevin 1989.
** you may give this software to anyone, make as many copies as you
** like, and post it on public computer bulletin boards and file
** servers. you may not sell it or charge any fee for distribution
** (except for media and postage), remove this comment or the
** copyright notice from the code, or claim that you wrote this code
** or anything derived from it.
** the author's address is: Randy Nevin, 1731 211th PL NE, Redmond,
** WA 98053. this code is available directly from the author; just
** send a floppy and a self-addressed floppy mailer with sufficient
** postage. however, you should first attempt to get a copy of this
** software package from the Dr. Dobb's Journal BBS.
*/
/* the low-order bit indicates a hole */
#define HOLE 0x00000001L /* a conducting hole */
/* traces radiating outward from a hole to a side or corner */
#define HOLE_NORTH 0x00000002L /* upward */
#define HOLE_NORTHEAST 0x00000004L /* upward and right */
#define HOLE_EAST 0x00000008L /* to the right */
#define HOLE_SOUTHEAST 0x00000010L /* downward and right */
#define HOLE_SOUTH 0x00000020L /* downward */
#define HOLE_SOUTHWEST 0x00000040L /* downward and left */
#define HOLE_WEST 0x00000080L /* to the left */
#define HOLE_NORTHWEST 0x00000100L /* upward and left */
/* straight lines through the center */
#define LINE_HORIZONTAL 0x00000002L /* left-to-right line */
#define LINE_VERTICAL 0x00000004L /* top-to-bottom line */
/* lines cutting across a corner, connecting adjacent sides */
#define CORNER_NORTHEAST 0x00000008L /* upper right corner */
#define CORNER_SOUTHEAST 0x00000010L /* lower right corner */
#define CORNER_SOUTHWEST 0x00000020L /* lower left corner */
#define CORNER_NORTHWEST 0x00000040L /* upper left corner */
/* diagonal lines through the center */
#define DIAG_NEtoSW 0x00000080L /* northeast to southwest */
#define DIAG_SEtoNW 0x00000100L /* southeast to northwest */
/* 135 degree angle side-to-far-corner lines */
#define BENT_NtoSE 0x00000200L /* north to southeast */
#define BENT_NtoSW 0x00000400L /* north to southwest */
#define BENT_EtoSW 0x00000800L /* east to southwest */
#define BENT_EtoNW 0x00001000L /* east to northwest */
#define BENT_StoNW 0x00002000L /* south to northwest */
#define BENT_StoNE 0x00004000L /* south to northeast */
#define BENT_WtoNE 0x00008000L /* west to northeast */
#define BENT_WtoSE 0x00010000L /* west to southeast */
/* 90 degree corner-to-adjacent-corner lines */
#define ANGLE_NEtoSE 0x00020000L /* northeast to southeast */
#define ANGLE_SEtoSW 0x00040000L /* southeast to southwest */
#define ANGLE_SWtoNW 0x00080000L /* southwest to northwest */
#define ANGLE_NWtoNE 0x00100000L /* northwest to northeast */
/* 45 degree angle side-to-near-corner lines */
#define SHARP_NtoNE 0x00200000L /* north to northeast */
#define SHARP_EtoNE 0x00400000L /* east to northeast */
#define SHARP_EtoSE 0x00800000L /* east to southeast */
#define SHARP_StoSE 0x01000000L /* south to southeast */
#define SHARP_StoSW 0x02000000L /* south to southwest */
#define SHARP_WtoSW 0x04000000L /* west to southwest */
#define SHARP_WtoNW 0x08000000L /* west to northwest */
#define SHARP_NtoNW 0x10000000L /* north to northwest */
/* directions the cell can be reached from (point to previous cell) */
#define FROM_NORTH 1
#define FROM_NORTHEAST 2
#define FROM_EAST 3
#define FROM_SOUTHEAST 4
#define FROM_SOUTH 5
#define FROM_SOUTHWEST 6
#define FROM_WEST 7
#define FROM_NORTHWEST 8
#define FROM_OTHERSIDE 9
#define TOP 0
#define BOTTOM 1
#define EMPTY 0
#define ILLEGAL -1
/* visit neighboring cells in this order
** (where [9] is on the other side):
** +---+---+---+
** | 1 | 2 | 3 |
** +---+---+---+
** | 4 |[9]| 5 |
** +---+---+---+
** | 6 | 7 | 8 |
** +---+---+---+
*/
static int delta[8][2] = { /* for visiting neighbors on the same side */
{ 1, -1 }, /* northwest */
{ 1, 0 }, /* north */
{ 1, 1 }, /* northeast */
{ 0, -1 }, /* west */
{ 0, 1 }, /* east */
{ -1, -1 }, /* southwest */
{ -1, 0 }, /* south */
{ -1, 1 } /* southeast */
};
static int ndir[8] = { /* for building paths back to source */
FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
FROM_EAST, FROM_WEST,
FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
};
/* blocking masks for neighboring cells */
#define BLOCK_NORTHEAST ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
| ANGLE_NEtoSE | ANGLE_NWtoNE \
| SHARP_NtoNE | SHARP_EtoNE )
#define BLOCK_SOUTHEAST ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
| ANGLE_NEtoSE | ANGLE_SEtoSW \
| SHARP_EtoSE | SHARP_StoSE )
#define BLOCK_SOUTHWEST ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
| ANGLE_SEtoSW | ANGLE_SWtoNW \
| SHARP_StoSW | SHARP_WtoSW )
#define BLOCK_NORTHWEST ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
| ANGLE_SWtoNW | ANGLE_NWtoNE \
| SHARP_WtoNW | SHARP_NtoNW )
struct block {
int r1, c1; long b1, h1;
int r2, c2; long b2, h2;
};
static struct block blocking[8] = { /* blocking masks */
{ 0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
1, 0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
0, 1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
-1, 0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ -1, 0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
0, 1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
};
static int selfok[5][8] = { /* mask for self-blocking corner effects */
{ 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0, 0, 0 }
};
static long newmask[5][8] = { /* patterns to mask in neighbor cells */
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
{ 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
{ 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
{ 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
};
/* board dimensions */
extern int Nrows;
extern int Ncols;
void Solve () { /* route all traces */
int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
register int i;
char far *n1;
char far *n2;
long curcell, newcell, buddy;
int newdist, olddir, success, self;
/* go until no more work to do */
for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
if (r1 == r2 && c1 == c2) /* already routed */
continue;
success = 0;
InitQueue(); /* initialize the search queue */
/* get rough estimate of trace distance */
a = GetApxDist( r1, c1, r2, c2 );
SetQueue( r1, c1, TOP, 0, a, r2, c2 );
SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
/* search until success or we exhaust all possibilities */
for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
GetQueue( &r, &c, &s, &d, &a )) {
if (r == r2 && c == c2) { /* success! */
/* lay traces */
Retrace( r1, c1, r2, c2, s );
success++;
break;
}
curcell = GetCell( r, c, s );
if (curcell & CORNER_NORTHWEST)
self = 1;
else if (curcell & CORNER_NORTHEAST)
self = 2;
else if (curcell & CORNER_SOUTHWEST)
self = 3;
else if (curcell & CORNER_SOUTHEAST)
self = 4;
else
self = 0;
/* consider neighbors */
for (i = 0; i < 8; i++) {
/* check self-block */
if (!selfok[self][i])
continue;
if ((nr = r+delta[i][0]) < 0
|| nr >= Nrows
|| (nc = c+delta[i][1]) < 0
|| nc >= Ncols)
/* off the edge */
continue;
newcell = GetCell( nr, nc, s );
/* check for non-target hole */
if (newcell & HOLE) {
if (nr != r2 || nc != c2)
continue;
}
else {
newcell &= ~(newmask[self][i]);
/* check for traces */
if (newcell)
continue;
}
/* check blocking on corner neighbors */
if (delta[i][0] && delta[i][1]) {
/* check first buddy */
buddy = GetCell( r+blocking[i].r1,
c+blocking[i].c1, s );
if (buddy & HOLE) {
if (buddy & (blocking[i].h1))
continue;
}
else if (buddy & (blocking[i].b1))
continue;
/* check second buddy */
buddy = GetCell( r+blocking[i].r2,
c+blocking[i].c2, s );
if (buddy & HOLE) {
if (buddy & (blocking[i].h2))
continue;
}
else if (buddy & (blocking[i].b2))
continue;
}
olddir = GetDir( r, c, s );
newdist = d+CalcDist( ndir[i], olddir,
(olddir == FROM_OTHERSIDE)
? GetDir( r, c, 1-s ) : 0 );
/* if not visited yet, add it to queue */
if (!GetDir( nr, nc, s )) {
SetDir( nr, nc, s, ndir[i] );
SetDist( nr, nc, s, newdist );
SetQueue( nr, nc, s, newdist,
GetApxDist( nr, nc, r2, c2 ),
r2, c2 );
}
/* we might have found a better path */
else if (newdist < GetDist( nr, nc, s )) {
SetDir( nr, nc, s, ndir[i] );
SetDist( nr, nc, s, newdist );
ReSetQueue( nr, nc, s, newdist,
GetApxDist( nr, nc, r2, c2 ),
r2, c2 );
}
}
/* consider other side of board */
/* check for holes or traces on other side */
if (newcell = GetCell( r, c, 1-s ))
continue;
skip = 0;
/* check for nearby holes */
for (i = 0; i < 8; i++) {
if ((nr = r+delta[i][0]) < 0
|| nr >= Nrows
|| (nc = c+delta[i][1]) < 0
|| nc >= Ncols)
/* off the edge */
continue;
if (GetCell( nr, nc, s ) & HOLE) {
/* neighboring hole */
skip = 1;
break;
}
}
if (skip) /* neighboring hole? */
continue; /* yes, can't drill one here */
olddir = GetDir( r, c, s );
newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
(olddir == FROM_OTHERSIDE)
? GetDir( r, c, 1-s ) : 0 );
/* if not visited yet, add it to queue */
if (!GetDir( r, c, 1-s )) {
SetDir( r, c, 1-s, FROM_OTHERSIDE );
SetDist( r, c, 1-s, newdist );
SetQueue( r, c, 1-s, newdist,
a, r2, c2 );
}
/* we might have found a better path */
else if (newdist < GetDist( r, c, 1-s )) {
SetDir( r, c, 1-s, FROM_OTHERSIDE );
SetDist( r, c, 1-s, newdist );
ReSetQueue( r, c, 1-s, newdist,
a, r2, c2 );
}
}
if (!success)
printf( "\t*!* UNSUCCESSFUL *!*\n" );
/* clear direction flags */
for (r = 0; r < Nrows; r++) {
for (c = 0; c < Ncols; c++) {
SetDir( r, c, TOP, EMPTY );
SetDir( r, c, BOTTOM, EMPTY );
}
}
}
}
/* this table drives the retracing phase */
static long bit[8][9] = { /* OT=Otherside */
/* N, NE, E, SE, S, SW, W, NW, OT */
/* N */ { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE,
0, SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW,
(HOLE | HOLE_SOUTH) },
/* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW,
SHARP_StoSW, 0, SHARP_WtoSW, ANGLE_SWtoNW,
(HOLE | HOLE_SOUTHWEST) },
/* E */ { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW,
(HOLE | HOLE_WEST) },
/* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW,
BENT_StoNW, ANGLE_SWtoNW, SHARP_WtoNW, 0,
(HOLE | HOLE_NORTHWEST) },
/* S */ { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE,
LINE_VERTICAL, BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW,
(HOLE | HOLE_NORTH) },
/* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE,
DIAG_NEtoSW, BENT_WtoNE, ANGLE_NWtoNE,
(HOLE | HOLE_NORTHEAST) },
/* W */ { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE,
CORNER_SOUTHEAST, BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW,
(HOLE | HOLE_EAST) },
/* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW,
(HOLE | HOLE_SOUTHEAST) }
};
void Retrace ( rr1, cc1, rr2, cc2, s )
/* work from target back to source, laying down the trace */
int rr1, cc1, rr2, cc2, s; /* start on side s */
{
int r0, c0, s0, r1, c1, s1, r2, c2, s2;
register int x, y;
long b;
r1 = rr2;
c1 = cc2;
s1 = s;
r0 = c0 = s0 = ILLEGAL;
do {
/* find where we came from to get here */
switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
case FROM_NORTH: r2++; break;
case FROM_EAST: c2++; break;
case FROM_SOUTH: r2--; break;
case FROM_WEST: c2--; break;
case FROM_NORTHEAST: r2++; c2++; break;
case FROM_SOUTHEAST: r2--; c2++; break;
case FROM_SOUTHWEST: r2--; c2--; break;
case FROM_NORTHWEST: r2++; c2--; break;
case FROM_OTHERSIDE: s2 = 1-s2; break;
default:
fprintf( stderr, "internal error\n" );
exit( -1 );
break;
}
if (r0 != ILLEGAL)
y = GetDir( r0, c0, s0 );
/* see if target or hole */
if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
switch (x) {
case FROM_NORTH:
OrCell( r1, c1, s1, HOLE_NORTH ); break;
case FROM_EAST:
OrCell( r1, c1, s1, HOLE_EAST ); break;
case FROM_SOUTH:
OrCell( r1, c1, s1, HOLE_SOUTH ); break;
case FROM_WEST:
OrCell( r1, c1, s1, HOLE_WEST ); break;
case FROM_NORTHEAST:
OrCell( r1, c1, s1, HOLE_NORTHEAST ); break;
case FROM_SOUTHEAST:
OrCell( r1, c1, s1, HOLE_SOUTHEAST ); break;
case FROM_SOUTHWEST:
OrCell( r1, c1, s1, HOLE_SOUTHWEST ); break;
case FROM_NORTHWEST:
OrCell( r1, c1, s1, HOLE_NORTHWEST ); break;
case FROM_OTHERSIDE:
default:
fprintf( stderr, "internal error\n" );
exit( -1 );
break;
}
}
else {
if ((y == FROM_NORTH
|| y == FROM_NORTHEAST
|| y == FROM_EAST
|| y == FROM_SOUTHEAST
|| y == FROM_SOUTH
|| y == FROM_SOUTHWEST
|| y == FROM_WEST
|| y == FROM_NORTHWEST)
&& (x == FROM_NORTH
|| x == FROM_NORTHEAST
|| x == FROM_EAST
|| x == FROM_SOUTHEAST
|| x == FROM_SOUTH
|| x == FROM_SOUTHWEST
|| x == FROM_WEST
|| x == FROM_NORTHWEST
|| x == FROM_OTHERSIDE)
&& (b = bit[y-1][x-1])) {
OrCell( r1, c1, s1, b );
if (b & HOLE)
OrCell( r2, c2, s2, HOLE );
}
else {
fprintf( stderr, "internal error\n" );
exit( -1 );
}
}
if (r2 == rr1 && c2 == cc1) { /* see if source */
switch (x) {
case FROM_NORTH:
OrCell( r2, c2, s2, HOLE_SOUTH ); break;
case FROM_EAST:
OrCell( r2, c2, s2, HOLE_WEST ); break;
case FROM_SOUTH:
OrCell( r2, c2, s2, HOLE_NORTH ); break;
case FROM_WEST:
OrCell( r2, c2, s2, HOLE_EAST ); break;
case FROM_NORTHEAST:
OrCell( r2, c2, s2, HOLE_SOUTHWEST ); break;
case FROM_SOUTHEAST:
OrCell( r2, c2, s2, HOLE_NORTHWEST ); break;
case FROM_SOUTHWEST:
OrCell( r2, c2, s2, HOLE_NORTHEAST ); break;
case FROM_NORTHWEST:
OrCell( r2, c2, s2, HOLE_SOUTHEAST ); break;
case FROM_OTHERSIDE:
default:
fprintf( stderr, "internal error\n" );
exit( -1 );
break;
}
}
/* move to next cell */
r0 = r1; c0 = c1; s0 = s1;
r1 = r2; c1 = c2; s1 = s2;
} while (!(r2 == rr1 && c2 == cc1));
}
int GetApxDist ( r1, c1, r2, c2 ) /* calculate approximate distance */
int r1, c1, r2, c2;
{
register int d1, d2; /* row and column deltas */
int d0; /* temporary variable for swapping d1 and d2 */
/* NOTE: the -25 used below is because we are not going */
/* from the center of (r1,c1) to the center of (r2,c2), */
/* we are going from the edge of a hole at (r1,c1) to */
/* the edge of a hole at (r2,c2). holes are 25 mils in */
/* diameter (12.5 mils in radius), so we back off by 2 */
/* radii. */
if ((d1 = r1-r2) < 0) /* get absolute row delta */
d1 = -d1;
if ((d2 = c1-c2) < 0) /* get absolute column delta */
d2 = -d2;
if (!d1) /* in same row? */
return( (d2*50)-25 ); /* 50 mils per cell */
if (!d2) /* in same column? */
return( (d1*50)-25 ); /* 50 mils per cell */
if (d1 > d2) { /* get smaller into d1 */
d0 = d1;
d1 = d2;
d2 = d0;
}
d2 -= d1; /* get non-diagonal part of approximate route */
return( (d1*71)+(d2*50)-25 ); /* 71 mils diagonally per cell */
}
/* distance to go through a cell */
static int dist[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
/* N, NE, E, SE, S, SW, W, NW, OT, OR */
/* N */ { 50, 60, 35, 60, 99, 60, 35, 60, 12, 12 },
/* NE */ { 60, 71, 60, 71, 60, 99, 60, 71, 23, 23 },
/* E */ { 35, 60, 50, 60, 35, 60, 99, 60, 12, 12 },
/* SE */ { 60, 71, 60, 71, 60, 71, 60, 99, 23, 23 },
/* S */ { 99, 60, 35, 60, 50, 60, 35, 60, 12, 12 },
/* SW */ { 60, 99, 60, 71, 60, 71, 60, 71, 23, 23 },
/* W */ { 35, 60, 99, 60, 35, 60, 50, 60, 12, 12 },
/* NW */ { 60, 71, 60, 99, 60, 71, 60, 71, 23, 23 },
/* OT */ { 12, 23, 12, 23, 12, 23, 12, 23, 99, 99 },
/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 }
};
/* distance around (circular) segment of hole */
static int circ[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
/* N, NE, E, SE, S, SW, W, NW, OT, OR */
/* N */ { 39, 29, 20, 10, 0, 10, 20, 29, 99, 0 },
/* NE */ { 29, 39, 29, 20, 10, 0, 10, 20, 99, 0 },
/* E */ { 20, 29, 39, 29, 20, 10, 0, 10, 99, 0 },
/* SE */ { 10, 20, 29, 39, 29, 20, 10, 0, 99, 0 },
/* S */ { 0, 10, 20, 29, 39, 29, 20, 10, 99, 0 },
/* SW */ { 10, 0, 10, 20, 29, 39, 29, 20, 99, 0 },
/* W */ { 20, 10, 0, 10, 20, 29, 39, 29, 99, 0 },
/* NW */ { 29, 20, 10, 0, 10, 20, 29, 39, 99, 0 },
/* OT */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 0 },
/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 0 }
};
/* penalty for routing holes and turns, scaled by sharpness of turn */
static int penalty[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
/* N, NE, E, SE, S, SW, W, NW, OT, OR */
/* N */ { 0, 5, 10, 15, 20, 15, 10, 5, 50, 0 },
/* NE */ { 5, 0, 5, 10, 15, 20, 15, 10, 50, 0 },
/* E */ { 10, 5, 0, 5, 10, 15, 20, 15, 50, 0 },
/* SE */ { 15, 10, 5, 0, 5, 10, 15, 20, 50, 0 },
/* S */ { 20, 15, 10, 5, 0, 5, 10, 15, 50, 0 },
/* SW */ { 15, 20, 15, 10, 5, 0, 5, 10, 50, 0 },
/* W */ { 10, 15, 20, 15, 10, 5, 0, 5, 50, 0 },
/* NW */ { 5, 10, 15, 20, 15, 10, 5, 0, 50, 0 },
/* OT */ { 50, 50, 50, 50, 50, 50, 50, 50, 100, 0 },
/* OR */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
/*
** x is the direction to enter the cell of interest.
** y is the direction to exit the cell of interest.
** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
** return the distance of the trace through the cell of interest.
** the calculation is driven by the tables above.
*/
int CalcDist ( x, y, z )
/* calculate distance of a trace through a cell */
int x, y, z;
{
int adjust;
adjust = 0; /* set if hole is encountered */
if (x == EMPTY)
x = 10;
if (y == EMPTY)
y = 10;
else if (y == FROM_OTHERSIDE) {
if (z == EMPTY)
z = 10;
adjust = circ[x-1][z-1] + penalty[x-1][z-1];
}
return( dist[x-1][y-1] + penalty[x-1][y-1] + adjust );
}
Figure 1: Pseudo-code for the breadth-first search algorith