_AUTOROUTING WITH THE A* ALGORITHM_
by Randy Nevin
[LISTING ONE]
/*
** 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
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