src/hid/lesstif/menu.c: Added doxygen comments for GetXY().

[geda-pcb/pcjc2.git] / src / autoroute.c

/*!
 * \file src/autoroute.c
 *
 * \brief Functions used to autoroute nets.
 *
 * this file, autoroute.c, was written and is
 *
 * Copyright (c) 2001 C. Scott Ananian
 *
 * Copyright (c) 2006 harry eaton
 *
 * Copyright (c) 2009 harry eaton
 *
 * This file implements a rectangle-expansion router, based on
 * "A Method for Gridless Routing of Printed Circuit Boards" by
 * A. C. Finch, K. J. Mackenzie, G. J. Balsdon, and G. Symonds in the
 * 1985 Proceedings of the 22nd ACM/IEEE Design Automation Conference.
 *
 * This reference is available from the ACM Digital Library at
 * http://www.acm.org/dl for those with institutional or personal
 * access to it.  It's also available from your local engineering
 * library.
 *
 * The code is much closer to what is described in the paper now,
 * in that expansion areas can grow from corners and in all directions
 * at once. Previously, these were emulated with discrete boxes moving
 * in the cardinal directions. With the new method, there are fewer but
 * larger expansion boxes that one might do a better job of routing in.
 *
 * <hr>
 *
 * <h1><b>Copyright.</b></h1>\n
 *
 * PCB, interactive printed circuit board design
 *
 * Copyright (C) 1994,1995,1996 Thomas Nau
 *
 * Copyright (C) 1998,1999,2000,2001 harry eaton
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * Contact addresses for paper mail and Email:
 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
 * haceaton@aplcomm.jhuapl.edu
 *
 */

#define NET_HEAP 1
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "global.h"

#include <assert.h>
#include <setjmp.h>

#include "data.h"
#include "macro.h"
#include "autoroute.h"
#include "box.h"
#include "create.h"
#include "draw.h"
#include "error.h"
#include "find.h"
#include "heap.h"
#include "rtree.h"
#include "misc.h"
#include "mtspace.h"
#include "mymem.h"
#include "polygon.h"
#include "rats.h"
#include "remove.h"
#include "thermal.h"
#include "undo.h"
#include "vector.h"
#include "pcb-printf.h"
#include "hid_draw.h"

#ifdef HAVE_LIBDMALLOC
#include <dmalloc.h>
#endif

/* #defines to enable some debugging output */
/*
#define ROUTE_VERBOSE
*/

/*
#define ROUTE_DEBUG
//#define DEBUG_SHOW_ROUTE_BOXES
#define DEBUG_SHOW_EXPANSION_BOXES
//#define DEBUG_SHOW_EDGES
//#define DEBUG_SHOW_VIA_BOXES
#define DEBUG_SHOW_TARGETS
#define DEBUG_SHOW_SOURCES
//#define DEBUG_SHOW_ZIGZAG
*/

static direction_t
directionIncrement(direction_t dir)
{
  switch(dir)
  {
  case NORTH:
    dir = EAST;
    break;
  case EAST:
    dir = SOUTH;
    break;
  case SOUTH:
    dir = WEST;
    break;
  case WEST:
    dir = NE;
    break;
  case NE:
    dir = SE;
    break;
  case SE:
    dir = SW;
    break;
  case SW:
    dir = NW;
    break;
  case NW:
    dir = ALL;
    break;
  case ALL:
    dir = NORTH;
    break;
  }
return dir;
}

#ifdef ROUTE_DEBUG
HID_DRAW *ddraw = NULL;
static hidGC ar_gc = 0;
#endif

#define EXPENSIVE 3e28
/* round up "half" thicknesses */
#define HALF_THICK(x) (((x)+1)/2)
/* a styles maximum bloat is its keepaway plus the larger of its via radius
 * or line half-thickness. */
#define BLOAT(style)\
        ((style)->Keepaway + HALF_THICK((style)->Thick))
/* conflict penalty is less for traces laid down during previous pass than
 * it is for traces already laid down in this pass. */
#define CONFLICT_LEVEL(rb)\
        (((rb)->flags.is_odd==AutoRouteParameters.is_odd) ?\
         HI_CONFLICT : LO_CONFLICT )
#define CONFLICT_PENALTY(rb)\
        ((CONFLICT_LEVEL(rb)==HI_CONFLICT ? \
         AutoRouteParameters.ConflictPenalty : \
         CONFLICT_LEVEL(rb)==LO_CONFLICT ? \
         AutoRouteParameters.LastConflictPenalty : 1) * (rb)->pass)

#define _NORTH 1
#define _EAST 2
#define _SOUTH 4
#define _WEST 8

#define LIST_LOOP(init, which, x) do {\
     routebox_t *__next_one__ = (init);\
   x = NULL;\
   if (!__next_one__)\
     assert(__next_one__);\
   else\
   while (!x  || __next_one__ != (init)) {\
     x = __next_one__;\
     /* save next one first in case the command modifies or frees it */\
     __next_one__ = x->which.next
#define FOREACH_SUBNET(net, p) do {\
  routebox_t *_pp_;\
  /* fail-fast: check subnet_processed flags */\
  LIST_LOOP(net, same_net, p); \
  assert(!p->flags.subnet_processed);\
  END_LOOP;\
  /* iterate through *distinct* subnets */\
  LIST_LOOP(net, same_net, p); \
  if (!p->flags.subnet_processed) {\
    LIST_LOOP(p, same_subnet, _pp_);\
    _pp_->flags.subnet_processed=1;\
    END_LOOP
#define END_FOREACH(net, p) \
  }; \
  END_LOOP;\
  /* reset subnet_processed flags */\
  LIST_LOOP(net, same_net, p); \
  p->flags.subnet_processed=0;\
  END_LOOP;\
} while (0)
#define SWAP(t, f, s) do { t a=s; s=f; f=a; } while (0)
/* notes:
 * all rectangles are assumed to be closed on the top and left and
 * open on the bottom and right.   That is, they include their top-left
 * corner but don't include their bottom and right edges.
 *
 * expansion regions are always half-closed.  This means that when
 * tracing paths, you must steer clear of the bottom and right edges.,
 * because these are not actually in the allowed box.
 *
 * All routeboxes *except* EXPANSION_AREAS now have their "box" bloated by
 * their particular required keepaway. This simplifies the tree searching.
 * the "sbox" contains the unbloated box.
 */
/* ---------------------------------------------------------------------------
 * some local types
 */

/* enumerated type for conflict levels */
typedef enum
{ NO_CONFLICT = 0, LO_CONFLICT = 1, HI_CONFLICT = 2 }
conflict_t;

typedef struct routebox_list
{
  struct routebox *next, *prev;
}routebox_list;

typedef enum etype
  { PAD, PIN, VIA, VIA_SHADOW, LINE, OTHER, EXPANSION_AREA, PLANE, THERMAL }
  etype;

typedef struct routebox
{
  BoxType box, sbox;
  union
  {
    PadType *pad;
    PinType *pin;
    PinType *via;
    struct routebox *via_shadow;        /* points to the via in r-tree which
                                         * points to the PinType in the PCB. */
    LineType *line;
    void *generic;              /* 'other' is polygon, arc, text */
    struct routebox *expansion_area;    /* previous expansion area in search */
  }
  parent;
  unsigned short group;
  unsigned short layer;
  etype type;
  struct
  {
    unsigned nonstraight:1;
    unsigned fixed:1;
    /* for searches */
    unsigned source:1;
    unsigned target:1;
    /* rects on same net as source and target don't need clearance areas */
    unsigned nobloat:1;
    /* mark circular pins, so that we be sure to connect them up properly */
    unsigned circular:1;
    /* we sometimes create routeboxen that don't actually belong to a
     * r-tree yet -- make sure refcount of homelesss is set properly */
    unsigned homeless:1;
    /* was this nonfixed obstacle generated on an odd or even pass? */
    unsigned is_odd:1;
    /* fixed route boxes that have already been "routed through" in this
     * search have their "touched" flag set. */
    unsigned touched:1;
    /* this is a status bit for iterating through *different* subnets */
    unsigned subnet_processed:1;
    /* some expansion_areas represent via candidates */
    unsigned is_via:1;
    /* mark non-straight lines which go from bottom-left to upper-right,
     * instead of from upper-left to bottom-right. */
    unsigned bl_to_ur:1;
    /* mark polygons which are "transparent" for via-placement; that is,
     * vias through the polygon will automatically be given a keepaway
     * and will not electrically connect to the polygon. */
    unsigned clear_poly:1;
    /* this marks "conflicting" routes that must be torn up to obtain
     * a correct routing.  This flag allows us to return a correct routing
     * even if the user cancels auto-route after a non-final pass. */
    unsigned is_bad:1;
    /* for assertion that 'box' is never changed after creation */
    unsigned inited:1;
    /* indicate this expansion ares is a thermal between the pin and plane */
    unsigned is_thermal;
  }
  flags;
  /* indicate the direction an expansion box came from */
  cost_t cost;
  CheapPointType cost_point;
  /* reference count for homeless routeboxes; free when refcount==0 */
  int refcount;
  /* when routing with conflicts, we keep a record of what we're
   * conflicting with.
   */
  vector_t *conflicts_with;
  /* route style of the net associated with this routebox */
  RouteStyleType *style;
  /* congestion values for the edges of an expansion box */
  unsigned char n, e, s, w;
  /* what pass this this track was laid down on */
  unsigned char pass;
  /* the direction this came from, if any */
  direction_t came_from;
  /* circular lists with connectivity information. */
  routebox_list same_net, same_subnet, original_subnet, different_net;
  union {
    PinType *via;
    LineType *line;
  } livedraw_obj;
}
routebox_t;

typedef struct routedata
{
  /* one rtree per layer *group */
  rtree_t *layergrouptree[MAX_GROUP];   /* no silkscreen layers here =) */
  /* root pointer into connectivity information */
  routebox_t *first_net;
  /* default routing style */
  RouteStyleType defaultstyle;
  /* style structures */
  RouteStyleType *styles[NUM_STYLES + 1];
  /* what is the maximum bloat (keepaway+line half-width or
   * keepaway+via_radius) for any style we've seen? */
  Coord max_bloat;
  Coord max_keep;
  mtspace_t *mtspace;
}
routedata_t;

typedef struct edge_struct
{
  routebox_t *rb;               /* path expansion edges are real routeboxen. */
  CheapPointType cost_point;
  cost_t cost_to_point;         /* from source */
  cost_t cost;                  /* cached edge cost */
  routebox_t *mincost_target;   /* minimum cost from cost_point to any target */
  vetting_t *work;              /* for via search edges */
  direction_t expand_dir;
  struct
  {
    /* this indicates that this 'edge' is a via candidate. */
    unsigned is_via:1;
    /* record "conflict level" of via candidates, in case we need to split
     * them later. */
    conflict_t via_conflict_level:2;
    /* when "routing with conflicts", sometimes edge is interior. */
    unsigned is_interior:1;
    /* this is a fake edge used to defer searching for via spaces */
    unsigned via_search:1;
    /* this is a via edge in a plane where the cost point moves for free */
    unsigned in_plane:1;
  }
  flags;
}
edge_t;

static struct
{
  /* net style parameters */
  RouteStyleType *style;
  /* the present bloat */
  Coord bloat;
  /* cost parameters */
  cost_t ViaCost,               /* additional "length" cost for using a via */
    LastConflictPenalty,        /* length mult. for routing over last pass' trace */
    ConflictPenalty,            /* length multiplier for routing over another trace */
    JogPenalty,                 /* additional "length" cost for changing direction */
    CongestionPenalty,          /* (rational) length multiplier for routing in */
    NewLayerPenalty,            /* penalty for routing on a previously unused layer */
    MinPenalty;                 /* smallest Direction Penalty */
  /* maximum conflict incidence before calling it "no path found" */
  int hi_conflict;
  /* are vias allowed? */
  bool use_vias;
  /* is this an odd or even pass? */
  bool is_odd;
  /* permit conflicts? */
  bool with_conflicts;
  /* is this a final "smoothing" pass? */
  bool is_smoothing;
  /* rip up nets regardless of conflicts? */
  bool rip_always;
  bool last_smooth;
  unsigned char pass;
}
AutoRouteParameters;

struct routeone_state
{
  /* heap of all candidate expansion edges */
  heap_t *workheap;
  /* information about the best path found so far. */
  routebox_t *best_path, *best_target;
  cost_t best_cost;
};


/* ---------------------------------------------------------------------------
 * some local prototypes
 */
static routebox_t *CreateExpansionArea (const BoxType * area, Cardinal group,
                                        routebox_t * parent,
                                        bool relax_edge_requirements,
                                        edge_t * edge);

static cost_t edge_cost (const edge_t * e, const cost_t too_big);
static void best_path_candidate (struct routeone_state *s,
                                 edge_t * e, routebox_t * best_target);

static BoxType edge_to_box (const routebox_t * rb, direction_t expand_dir);

static void add_or_destroy_edge (struct routeone_state *s, edge_t * e);

static void
RD_DrawThermal (routedata_t * rd, Coord X, Coord Y,
                Cardinal group, Cardinal layer, routebox_t * subnet,
                bool is_bad);
static void ResetSubnet (routebox_t * net);
#ifdef ROUTE_DEBUG
static int showboxen = -2;
static int aabort = 0;
static void showroutebox (routebox_t * rb);
#endif

/* ---------------------------------------------------------------------------
 * some local identifiers
 */
/* group number of groups that hold surface mount pads */
static Cardinal front, back;
static bool usedGroup[MAX_GROUP];
static int x_cost[MAX_GROUP], y_cost[MAX_GROUP];
static bool is_layer_group_active[MAX_GROUP];
static int ro = 0;
static int smoothes = 1;
static int passes = 12;
static int routing_layers = 0;
static float total_wire_length = 0;
static int total_via_count = 0;

/* assertion helper for routeboxen */
#ifndef NDEBUG
static int
__routebox_is_good (routebox_t * rb)
{
  assert (rb && (rb->group < max_group) &&
          (rb->box.X1 <= rb->box.X2) && (rb->box.Y1 <= rb->box.Y2) &&
          (rb->flags.homeless ?
           (rb->box.X1 != rb->box.X2) || (rb->box.Y1 != rb->box.Y2) :
           (rb->box.X1 != rb->box.X2) && (rb->box.Y1 != rb->box.Y2)));
  assert ((rb->flags.source ? rb->flags.nobloat : 1) &&
          (rb->flags.target ? rb->flags.nobloat : 1) &&
          (rb->flags.homeless ? !rb->flags.touched : rb->refcount == 0) &&
          (rb->flags.touched ? rb->type != EXPANSION_AREA : 1));
  assert ((rb->flags.is_odd ? (!rb->flags.fixed) &&
           (rb->type == VIA || rb->type == VIA_SHADOW || rb->type == LINE
            || rb->type == PLANE) : 1));
  assert (rb->flags.clear_poly ?
          ((rb->type == OTHER || rb->type == PLANE) && rb->flags.fixed
           && !rb->flags.homeless) : 1);
  assert (rb->flags.inited);
/* run through conflict list showing none are homeless, targets or sources */
  if (rb->conflicts_with)
    {
      int i;
      for (i = 0; i < vector_size (rb->conflicts_with); i++)
        {
          routebox_t *c = vector_element (rb->conflicts_with, i);
          assert (!c->flags.homeless && !c->flags.source && !c->flags.target
                  && !c->flags.fixed);
        }
    }
  assert (rb->style != NULL && rb->style != NULL);
  assert (rb->type == EXPANSION_AREA
          || (rb->same_net.next && rb->same_net.prev && rb->same_subnet.next
              && rb->same_subnet.prev && rb->original_subnet.next
              && rb->original_subnet.prev && rb->different_net.next
              && rb->different_net.prev));
  return 1;
}
static int
__edge_is_good (edge_t * e)
{
  assert (e && e->rb && __routebox_is_good (e->rb));
  assert ((e->rb->flags.homeless ? e->rb->refcount > 0 : 1));
  assert ((0 <= e->expand_dir) && (e->expand_dir < 9)
          && (e->flags.
              is_interior ? (e->expand_dir == ALL
                             && e->rb->conflicts_with) : 1));
  assert ((e->flags.is_via ? e->rb->flags.is_via : 1)
          && (e->flags.via_conflict_level >= 0
              && e->flags.via_conflict_level <= 2)
          && (e->flags.via_conflict_level != 0 ? e->flags.is_via : 1));
  assert ((e->cost_to_point >= 0) && e->cost >= 0);
  return 1;
}

int
no_planes (const BoxType * b, void *cl)
{
  routebox_t *rb = (routebox_t *) b;
  if (rb->type == PLANE)
    return 0;
  return 1;
}
#endif /* !NDEBUG */

/*---------------------------------------------------------------------
 * route utility functions.
 */

enum boxlist
{ NET, SUBNET, ORIGINAL, DIFFERENT_NET };
static struct routebox_list *
__select_list (routebox_t * r, enum boxlist which)
{
  assert (r);
  switch (which)
    {
    default:
      assert (0);
    case NET:
      return &(r->same_net);
    case SUBNET:
      return &(r->same_subnet);
    case ORIGINAL:
      return &(r->original_subnet);
    case DIFFERENT_NET:
      return &(r->different_net);
    }
}
static void
InitLists (routebox_t * r)
{
  static enum boxlist all[] =
  { NET, SUBNET, ORIGINAL, DIFFERENT_NET }
  , *p;
  for (p = all; p < all + (sizeof (all) / sizeof (*p)); p++)
    {
      struct routebox_list *rl = __select_list (r, *p);
      rl->prev = rl->next = r;
    }
}

static void
MergeNets (routebox_t * a, routebox_t * b, enum boxlist which)
{
  struct routebox_list *al, *bl, *anl, *bnl;
  routebox_t *an, *bn;
  assert (a && b);
  assert (a != b);
  assert (a->type != EXPANSION_AREA);
  assert (b->type != EXPANSION_AREA);
  al = __select_list (a, which);
  bl = __select_list (b, which);
  assert (al && bl);
  an = al->next;
  bn = bl->next;
  assert (an && bn);
  anl = __select_list (an, which);
  bnl = __select_list (bn, which);
  assert (anl && bnl);
  bl->next = an;
  anl->prev = b;
  al->next = bn;
  bnl->prev = a;
}

static void
RemoveFromNet (routebox_t * a, enum boxlist which)
{
  struct routebox_list *al, *anl, *apl;
  routebox_t *an, *ap;
  assert (a);
  al = __select_list (a, which);
  assert (al);
  an = al->next;
  ap = al->prev;
  if (an == a || ap == a)
    return;                     /* not on any list */
  assert (an && ap);
  anl = __select_list (an, which);
  apl = __select_list (ap, which);
  assert (anl && apl);
  anl->prev = ap;
  apl->next = an;
  al->next = al->prev = a;
  return;
}

static void
init_const_box (routebox_t * rb,
                Coord X1, Coord Y1, Coord X2,
                Coord Y2, Coord keepaway)
{
  BoxType *bp = (BoxType *) & rb->box;  /* note discarding const! */
  assert (!rb->flags.inited);
  assert (X1 <= X2 && Y1 <= Y2);
  bp->X1 = X1 - keepaway;
  bp->Y1 = Y1 - keepaway;
  bp->X2 = X2 + keepaway;
  bp->Y2 = Y2 + keepaway;
  bp = (BoxType *) & rb->sbox;
  bp->X1 = X1;
  bp->Y1 = Y1;
  bp->X2 = X2;
  bp->Y2 = Y2;
  rb->flags.inited = 1;
}

static inline BoxType
shrink_routebox (const routebox_t * rb)
{
  return rb->sbox;
}

static inline cost_t
box_area (const BoxType b)
{
  cost_t ans = b.X2 - b.X1;
  return ans * (b.Y2 - b.Y1);
}

static inline CheapPointType
closest_point_in_routebox (const CheapPointType * from, const routebox_t * rb)
{
  return closest_point_in_box (from, &rb->sbox);
}

static inline bool
point_in_shrunk_box (const routebox_t * box, Coord X, Coord Y)
{
  BoxType b = shrink_routebox (box);
  return point_in_box (&b, X, Y);
}

/*---------------------------------------------------------------------
 * routedata initialization functions.
 */

static routebox_t *
AddPin (PointerListType layergroupboxes[], PinType *pin, bool is_via,
        RouteStyleType * style)
{
  routebox_t **rbpp, *lastrb = NULL;
  int i, ht;
  /* a pin cuts through every layer group */
  for (i = 0; i < max_group; i++)
    {
      rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[i]);
      *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
      memset ((void *) *rbpp, 0, sizeof (**rbpp));
      (*rbpp)->group = i;
      ht = HALF_THICK (MAX (pin->Thickness, pin->DrillingHole));
      init_const_box (*rbpp,
                      /*X1 */ pin->X - ht,
                      /*Y1 */ pin->Y - ht,
                      /*X2 */ pin->X + ht,
                      /*Y2 */ pin->Y + ht, style->Keepaway);
      /* set aux. properties */
      if (is_via)
        {
          (*rbpp)->type = VIA;
          (*rbpp)->parent.via = pin;
        }
      else
        {
          (*rbpp)->type = PIN;
          (*rbpp)->parent.pin = pin;
        }
      (*rbpp)->flags.fixed = 1;
      (*rbpp)->came_from = ALL;
      (*rbpp)->style = style;
      (*rbpp)->flags.circular = !TEST_FLAG (SQUAREFLAG, pin);
      /* circular lists */
      InitLists (*rbpp);
      /* link together */
      if (lastrb)
        {
          MergeNets (*rbpp, lastrb, NET);
          MergeNets (*rbpp, lastrb, SUBNET);
          MergeNets (*rbpp, lastrb, ORIGINAL);
        }
      lastrb = *rbpp;
    }
  return lastrb;
}
static routebox_t *
AddPad (PointerListType layergroupboxes[],
        ElementType *element, PadType *pad, RouteStyleType * style)
{
  Coord halfthick;
  routebox_t **rbpp;
  int layergroup = (TEST_FLAG (ONSOLDERFLAG, pad) ? back : front);
  assert (0 <= layergroup && layergroup < max_group);
  assert (PCB->LayerGroups.Number[layergroup] > 0);
  rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
  assert (rbpp);
  *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
  assert (*rbpp);
  memset (*rbpp, 0, sizeof (**rbpp));
  (*rbpp)->group = layergroup;
  halfthick = HALF_THICK (pad->Thickness);
  init_const_box (*rbpp,
                  /*X1 */ MIN (pad->Point1.X, pad->Point2.X) - halfthick,
                  /*Y1 */ MIN (pad->Point1.Y, pad->Point2.Y) - halfthick,
                  /*X2 */ MAX (pad->Point1.X, pad->Point2.X) + halfthick,
                  /*Y2 */ MAX (pad->Point1.Y, pad->Point2.Y) + halfthick,
                  style->Keepaway);
  /* kludge for non-manhattan pads (which are not allowed at present) */
  if (pad->Point1.X != pad->Point2.X && pad->Point1.Y != pad->Point2.Y)
    (*rbpp)->flags.nonstraight = 1;
  /* set aux. properties */
  (*rbpp)->type = PAD;
  (*rbpp)->parent.pad = pad;
  (*rbpp)->flags.fixed = 1;
  (*rbpp)->came_from = ALL;
  (*rbpp)->style = style;
  /* circular lists */
  InitLists (*rbpp);
  return *rbpp;
}
static routebox_t *
AddLine (PointerListType layergroupboxes[], int layergroup, LineType *line,
         LineType *ptr, RouteStyleType * style)
{
  routebox_t **rbpp;
  assert (layergroupboxes && line);
  assert (0 <= layergroup && layergroup < max_group);
  assert (PCB->LayerGroups.Number[layergroup] > 0);

  rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
  *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
  memset (*rbpp, 0, sizeof (**rbpp));
  (*rbpp)->group = layergroup;
  init_const_box (*rbpp,
                  /*X1 */ MIN (line->Point1.X,
                               line->Point2.X) - HALF_THICK (line->Thickness),
                  /*Y1 */ MIN (line->Point1.Y,
                               line->Point2.Y) - HALF_THICK (line->Thickness),
                  /*X2 */ MAX (line->Point1.X,
                               line->Point2.X) + HALF_THICK (line->Thickness),
                  /*Y2 */ MAX (line->Point1.Y,
                               line->Point2.Y) +
                  HALF_THICK (line->Thickness), style->Keepaway);
  /* kludge for non-manhattan lines */
  if (line->Point1.X != line->Point2.X && line->Point1.Y != line->Point2.Y)
    {
      (*rbpp)->flags.nonstraight = 1;
      (*rbpp)->flags.bl_to_ur =
        (MIN (line->Point1.X, line->Point2.X) == line->Point1.X) !=
        (MIN (line->Point1.Y, line->Point2.Y) == line->Point1.Y);
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ZIGZAG)
      showroutebox (*rbpp);
#endif
    }
  /* set aux. properties */
  (*rbpp)->type = LINE;
  (*rbpp)->parent.line = ptr;
  (*rbpp)->flags.fixed = 1;
  (*rbpp)->came_from = ALL;
  (*rbpp)->style = style;
  /* circular lists */
  InitLists (*rbpp);
  return *rbpp;
}
static routebox_t *
AddIrregularObstacle (PointerListType layergroupboxes[],
                      Coord X1, Coord Y1,
                      Coord X2, Coord Y2, Cardinal layergroup,
                      void *parent, RouteStyleType * style)
{
  routebox_t **rbpp;
  Coord keep = style->Keepaway;
  assert (layergroupboxes && parent);
  assert (X1 <= X2 && Y1 <= Y2);
  assert (0 <= layergroup && layergroup < max_group);
  assert (PCB->LayerGroups.Number[layergroup] > 0);

  rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
  *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
  memset (*rbpp, 0, sizeof (**rbpp));
  (*rbpp)->group = layergroup;
  init_const_box (*rbpp, X1, Y1, X2, Y2, keep);
  (*rbpp)->flags.nonstraight = 1;
  (*rbpp)->type = OTHER;
  (*rbpp)->parent.generic = parent;
  (*rbpp)->flags.fixed = 1;
  (*rbpp)->style = style;
  /* circular lists */
  InitLists (*rbpp);
  return *rbpp;
}

static routebox_t *
AddPolygon (PointerListType layergroupboxes[], Cardinal layer,
            PolygonType *polygon, RouteStyleType * style)
{
  int is_not_rectangle = 1;
  int layergroup = GetLayerGroupNumberByNumber (layer);
  routebox_t *rb;
  assert (0 <= layergroup && layergroup < max_group);
  rb = AddIrregularObstacle (layergroupboxes,
                             polygon->BoundingBox.X1,
                             polygon->BoundingBox.Y1,
                             polygon->BoundingBox.X2,
                             polygon->BoundingBox.Y2,
                             layergroup, polygon, style);
  if (polygon->PointN == 4 &&
      polygon->HoleIndexN == 0 &&
      (polygon->Points[0].X == polygon->Points[1].X ||
       polygon->Points[0].Y == polygon->Points[1].Y) &&
      (polygon->Points[1].X == polygon->Points[2].X ||
       polygon->Points[1].Y == polygon->Points[2].Y) &&
      (polygon->Points[2].X == polygon->Points[3].X ||
       polygon->Points[2].Y == polygon->Points[3].Y) &&
      (polygon->Points[3].X == polygon->Points[0].X ||
       polygon->Points[3].Y == polygon->Points[0].Y))
    is_not_rectangle = 0;
  rb->flags.nonstraight = is_not_rectangle;
  rb->layer = layer;
  rb->came_from = ALL;
  if (TEST_FLAG (CLEARPOLYFLAG, polygon))
    {
      rb->flags.clear_poly = 1;
      if (!is_not_rectangle)
        rb->type = PLANE;
    }
  return rb;
}
static void
AddText (PointerListType layergroupboxes[], Cardinal layergroup,
         TextType *text, RouteStyleType * style)
{
  AddIrregularObstacle (layergroupboxes,
                        text->BoundingBox.X1, text->BoundingBox.Y1,
                        text->BoundingBox.X2, text->BoundingBox.Y2,
                        layergroup, text, style);
}
static routebox_t *
AddArc (PointerListType layergroupboxes[], Cardinal layergroup,
        ArcType *arc, RouteStyleType * style)
{
  return AddIrregularObstacle (layergroupboxes,
                               arc->BoundingBox.X1, arc->BoundingBox.Y1,
                               arc->BoundingBox.X2, arc->BoundingBox.Y2,
                               layergroup, arc, style);
}

struct rb_info
{
  BoxType query;
  routebox_t *winner;
  jmp_buf env;
};

static int
__found_one_on_lg (const BoxType * box, void *cl)
{
  struct rb_info *inf = (struct rb_info *) cl;
  routebox_t *rb = (routebox_t *) box;
  BoxType sb;

  if (rb->flags.nonstraight)
    return 0;
  sb = shrink_box (&rb->box, rb->style->Keepaway);
  if (inf->query.X1 >= sb.X2 || inf->query.X2 <= sb.X1 ||
      inf->query.Y1 >= sb.Y2 || inf->query.Y2 <= sb.Y1)
    return 0;
  inf->winner = rb;
  if (rb->type == PLANE)
    return 1;                   /* keep looking for something smaller if a plane was found */
  longjmp (inf->env, 1);
  return 0;
}
static routebox_t *
FindRouteBoxOnLayerGroup (routedata_t * rd,
                          Coord X, Coord Y, Cardinal layergroup)
{
  struct rb_info info;
  info.winner = NULL;
  info.query = point_box (X, Y);
  if (setjmp (info.env) == 0)
    r_search (rd->layergrouptree[layergroup], &info.query, NULL,
              __found_one_on_lg, &info);
  return info.winner;
}

#ifdef ROUTE_DEBUG_VERBOSE
static void
DumpRouteBox (routebox_t * rb)
{
  pcb_printf ("RB: %#mD-%#mD l%d; ",
          rb->box.X1, rb->box.Y1, rb->box.X2, rb->box.Y2, (int) rb->group);
  switch (rb->type)
    {
    case PAD:
      printf ("PAD[%s %s] ", rb->parent.pad->Name, rb->parent.pad->Number);
      break;
    case PIN:
      printf ("PIN[%s %s] ", rb->parent.pin->Name, rb->parent.pin->Number);
      break;
    case VIA:
      if (!rb->parent.via)
        break;
      printf ("VIA[%s %s] ", rb->parent.via->Name, rb->parent.via->Number);
      break;
    case LINE:
      printf ("LINE ");
      break;
    case OTHER:
      printf ("OTHER ");
      break;
    case EXPANSION_AREA:
      printf ("EXPAREA ");
      break;
    default:
      printf ("UNKNOWN ");
      break;
    }
  if (rb->flags.nonstraight)
    printf ("(nonstraight) ");
  if (rb->flags.fixed)
    printf ("(fixed) ");
  if (rb->flags.source)
    printf ("(source) ");
  if (rb->flags.target)
    printf ("(target) ");
  if (rb->flags.homeless)
    printf ("(homeless) ");
  printf ("\n");
}
#endif

static routedata_t *
CreateRouteData ()
{
  NetListListType Nets;
  PointerListType layergroupboxes[MAX_GROUP];
  BoxType bbox;
  routedata_t *rd;
  int group, i;

  /* check which layers are active first */
  routing_layers = 0;
  for (group = 0; group < max_group; group++)
    {
      for (i = 0; i < PCB->LayerGroups.Number[group]; i++)
        /* layer must be 1) not silk (ie, < max_copper_layer) and 2) on */
        if ((PCB->LayerGroups.Entries[group][i] < max_copper_layer) &&
            PCB->Data->Layer[PCB->LayerGroups.Entries[group][i]].On)
          {
            routing_layers++;
            is_layer_group_active[group] = true;
            break;
          }
        else
          is_layer_group_active[group] = false;
    }
  /* if via visibility is turned off, don't use them */
  AutoRouteParameters.use_vias = routing_layers > 1 && PCB->ViaOn;
  front = GetLayerGroupNumberBySide (TOP_SIDE);
  back = GetLayerGroupNumberBySide (BOTTOM_SIDE);
  /* determine preferred routing direction on each group */
  for (i = 0; i < max_group; i++)
    {
      if (i != back && i != front)
        {
          x_cost[i] = (i & 1) ? 2 : 1;
          y_cost[i] = (i & 1) ? 1 : 2;
        }
      else if (i == back)
        {
          x_cost[i] = 4;
          y_cost[i] = 2;
        }
      else
        {
          x_cost[i] = 2;
          y_cost[i] = 2;
        }
    }
  /* create routedata */
  rd = (routedata_t *)malloc (sizeof (*rd));
  memset ((void *) rd, 0, sizeof (*rd));
  /* create default style */
  rd->defaultstyle.Thick = Settings.LineThickness;
  rd->defaultstyle.Diameter = Settings.ViaThickness;
  rd->defaultstyle.Hole = Settings.ViaDrillingHole;
  rd->defaultstyle.Keepaway = Settings.Keepaway;
  rd->max_bloat = BLOAT (&rd->defaultstyle);
  rd->max_keep = Settings.Keepaway;
  /* create styles structures */
  bbox.X1 = bbox.Y1 = 0;
  bbox.X2 = PCB->MaxWidth;
  bbox.Y2 = PCB->MaxHeight;
  for (i = 0; i < NUM_STYLES + 1; i++)
    {
      RouteStyleType *style =
        (i < NUM_STYLES) ? &PCB->RouteStyle[i] : &rd->defaultstyle;
      rd->styles[i] = style;
    }

  /* initialize pointerlisttype */
  for (i = 0; i < max_group; i++)
    {
      layergroupboxes[i].Ptr = NULL;
      layergroupboxes[i].PtrN = 0;
      layergroupboxes[i].PtrMax = 0;
      GROUP_LOOP (PCB->Data, i);
      {
        if (layer->LineN || layer->ArcN)
          usedGroup[i] = true;
        else
          usedGroup[i] = false;
      }
      END_LOOP;
    }
  usedGroup[front] = true;
  usedGroup[back] = true;
  /* add the objects in the netlist first.
   * then go and add all other objects that weren't already added
   *
   * this saves on searching the trees to find the nets
   */
  /* use the DRCFLAG to mark objects as they are entered */
  Nets = CollectSubnets (false);
  {
    routebox_t *last_net = NULL;
    NETLIST_LOOP (&Nets);
    {
      routebox_t *last_in_net = NULL;
      NET_LOOP (netlist);
      {
        routebox_t *last_in_subnet = NULL;
        int j;

        for (j = 0; j < NUM_STYLES; j++)
          if (net->Style == rd->styles[j])
            break;
        CONNECTION_LOOP (net);
        {
          routebox_t *rb = NULL;
          SET_FLAG (DRCFLAG, (PinType *) connection->ptr2);
          if (connection->type == LINE_TYPE)
            {
              LineType *line = (LineType *) connection->ptr2;

              /* lines are listed at each end, so skip one */
              /* this should probably by a macro named "BUMP_LOOP" */
              n--;

              /* dice up non-straight lines into many tiny obstacles */
              if (line->Point1.X != line->Point2.X
                  && line->Point1.Y != line->Point2.Y)
                {
                  LineType fake_line = *line;
                  Coord dx = (line->Point2.X - line->Point1.X);
                  Coord dy = (line->Point2.Y - line->Point1.Y);
                  int segs = MAX (ABS (dx),
                                  ABS (dy)) / (4 * BLOAT (rd->styles[j]) + 1);
                  int qq;
                  segs = CLAMP (segs, 1, 32);   /* don't go too crazy */
                  dx /= segs;
                  dy /= segs;
                  for (qq = 0; qq < segs - 1; qq++)
                    {
                      fake_line.Point2.X = fake_line.Point1.X + dx;
                      fake_line.Point2.Y = fake_line.Point1.Y + dy;
                      if (fake_line.Point2.X == line->Point2.X
                          && fake_line.Point2.Y == line->Point2.Y)
                        break;
                      rb =
                        AddLine (layergroupboxes, connection->group,
                                 &fake_line, line, rd->styles[j]);
                      if (last_in_subnet && rb != last_in_subnet)
                        MergeNets (last_in_subnet, rb, ORIGINAL);
                      if (last_in_net && rb != last_in_net)
                        MergeNets (last_in_net, rb, NET);
                      last_in_subnet = last_in_net = rb;
                      fake_line.Point1 = fake_line.Point2;
                    }
                  fake_line.Point2 = line->Point2;
                  rb =
                    AddLine (layergroupboxes, connection->group, &fake_line,
                             line, rd->styles[j]);
                }
              else
                {
                  rb =
                    AddLine (layergroupboxes, connection->group, line, line,
                             rd->styles[j]);
                }
            }
          else
            switch (connection->type)
              {
              case PAD_TYPE:
                rb =
                  AddPad (layergroupboxes, (ElementType *)connection->ptr1,
                          (PadType *)connection->ptr2, rd->styles[j]);
                break;
              case PIN_TYPE:
                rb =
                  AddPin (layergroupboxes, (PinType *)connection->ptr2, false,
                          rd->styles[j]);
                break;
              case VIA_TYPE:
                rb =
                  AddPin (layergroupboxes, (PinType *)connection->ptr2, true,
                          rd->styles[j]);
                break;
              case POLYGON_TYPE:
                rb =
                  AddPolygon (layergroupboxes,
                              GetLayerNumber (PCB->Data, (LayerType *)connection->ptr1),
                              (struct polygon_st *)connection->ptr2, rd->styles[j]);
                break;
              }
          assert (rb);
          /* update circular connectivity lists */
          if (last_in_subnet && rb != last_in_subnet)
            MergeNets (last_in_subnet, rb, ORIGINAL);
          if (last_in_net && rb != last_in_net)
            MergeNets (last_in_net, rb, NET);
          last_in_subnet = last_in_net = rb;
          rd->max_bloat = MAX (rd->max_bloat, BLOAT (rb->style));
          rd->max_keep = MAX (rd->max_keep, rb->style->Keepaway);
        }
        END_LOOP;
      }
      END_LOOP;
      if (last_net && last_in_net)
        MergeNets (last_net, last_in_net, DIFFERENT_NET);
      last_net = last_in_net;
    }
    END_LOOP;
    rd->first_net = last_net;
  }
  FreeNetListListMemory (&Nets);

  /* reset all nets to "original" connectivity (which we just set) */
  {
    routebox_t *net;
    LIST_LOOP (rd->first_net, different_net, net);
    ResetSubnet (net);
    END_LOOP;
  }

  /* add pins and pads of elements */
  ALLPIN_LOOP (PCB->Data);
  {
    if (TEST_FLAG (DRCFLAG, pin))
      CLEAR_FLAG (DRCFLAG, pin);
    else
      AddPin (layergroupboxes, pin, false, rd->styles[NUM_STYLES]);
  }
  ENDALL_LOOP;
  ALLPAD_LOOP (PCB->Data);
  {
    if (TEST_FLAG (DRCFLAG, pad))
      CLEAR_FLAG (DRCFLAG, pad);
    else
      AddPad (layergroupboxes, element, pad, rd->styles[NUM_STYLES]);
  }
  ENDALL_LOOP;
  /* add all vias */
  VIA_LOOP (PCB->Data);
  {
    if (TEST_FLAG (DRCFLAG, via))
      CLEAR_FLAG (DRCFLAG, via);
    else
      AddPin (layergroupboxes, via, true, rd->styles[NUM_STYLES]);
  }
  END_LOOP;

  for (i = 0; i < max_copper_layer; i++)
    {
      int layergroup = GetLayerGroupNumberByNumber (i);
      /* add all (non-rat) lines */
      LINE_LOOP (LAYER_PTR (i));
      {
        if (TEST_FLAG (DRCFLAG, line))
          {
            CLEAR_FLAG (DRCFLAG, line);
            continue;
          }
        /* dice up non-straight lines into many tiny obstacles */
        if (line->Point1.X != line->Point2.X
            && line->Point1.Y != line->Point2.Y)
          {
            LineType fake_line = *line;
            Coord dx = (line->Point2.X - line->Point1.X);
            Coord dy = (line->Point2.Y - line->Point1.Y);
            int segs = MAX (ABS (dx), ABS (dy)) / (4 * rd->max_bloat + 1);
            int qq;
            segs = CLAMP (segs, 1, 32); /* don't go too crazy */
            dx /= segs;
            dy /= segs;
            for (qq = 0; qq < segs - 1; qq++)
              {
                fake_line.Point2.X = fake_line.Point1.X + dx;
                fake_line.Point2.Y = fake_line.Point1.Y + dy;
                if (fake_line.Point2.X == line->Point2.X
                    && fake_line.Point2.Y == line->Point2.Y)
                  break;
                AddLine (layergroupboxes, layergroup, &fake_line, line,
                         rd->styles[NUM_STYLES]);
                fake_line.Point1 = fake_line.Point2;
              }
            fake_line.Point2 = line->Point2;
            AddLine (layergroupboxes, layergroup, &fake_line, line,
                     rd->styles[NUM_STYLES]);
          }
        else
          {
            AddLine (layergroupboxes, layergroup, line, line,
                     rd->styles[NUM_STYLES]);
          }
      }
      END_LOOP;
      /* add all polygons */
      POLYGON_LOOP (LAYER_PTR (i));
      {
        if (TEST_FLAG (DRCFLAG, polygon))
          CLEAR_FLAG (DRCFLAG, polygon);
        else
          AddPolygon (layergroupboxes, i, polygon, rd->styles[NUM_STYLES]);
      }
      END_LOOP;
      /* add all copper text */
      TEXT_LOOP (LAYER_PTR (i));
      {
        AddText (layergroupboxes, layergroup, text, rd->styles[NUM_STYLES]);
      }
      END_LOOP;
      /* add all arcs */
      ARC_LOOP (LAYER_PTR (i));
      {
        AddArc (layergroupboxes, layergroup, arc, rd->styles[NUM_STYLES]);
      }
      END_LOOP;
    }

  /* create r-trees from pointer lists */
  for (i = 0; i < max_group; i++)
    {
      /* create the r-tree */
      rd->layergrouptree[i] =
        r_create_tree ((const BoxType **) layergroupboxes[i].Ptr,
                       layergroupboxes[i].PtrN, 1);
    }

  if (AutoRouteParameters.use_vias)
    {
      rd->mtspace = mtspace_create ();

      /* create "empty-space" structures for via placement (now that we know
       * appropriate keepaways for all the fixed elements) */
      for (i = 0; i < max_group; i++)
        {
          POINTER_LOOP (&layergroupboxes[i]);
          {
            routebox_t *rb = (routebox_t *) * ptr;
            if (!rb->flags.clear_poly)
              mtspace_add (rd->mtspace, &rb->box, FIXED, rb->style->Keepaway);
          }
          END_LOOP;
        }
    }
  /* free pointer lists */
  for (i = 0; i < max_group; i++)
    FreePointerListMemory (&layergroupboxes[i]);
  /* done! */
  return rd;
}

void
DestroyRouteData (routedata_t ** rd)
{
  int i;
  for (i = 0; i < max_group; i++)
    r_destroy_tree (&(*rd)->layergrouptree[i]);
  if (AutoRouteParameters.use_vias)
    mtspace_destroy (&(*rd)->mtspace);
  free (*rd);
  *rd = NULL;
}

/*-----------------------------------------------------------------
 * routebox reference counting.
 */

/*!
 * \brief Increment the reference count on a routebox.
 */
static void
RB_up_count (routebox_t * rb)
{
  assert (rb->flags.homeless);
  rb->refcount++;
}

/*!
 * \brief Decrement the reference count on a routebox, freeing if this
 * box becomes unused.
 */
static void
RB_down_count (routebox_t * rb)
{
  assert (rb->type == EXPANSION_AREA);
  assert (rb->flags.homeless);
  assert (rb->refcount > 0);
  if (--rb->refcount == 0)
    {
      if (rb->parent.expansion_area->flags.homeless)
        RB_down_count (rb->parent.expansion_area);
      free (rb);
    }
}

/*-----------------------------------------------------------------
 * Rectangle-expansion routing code.
 */

static void
ResetSubnet (routebox_t * net)
{
  routebox_t *rb;
  /* reset connectivity of everything on this net */
  LIST_LOOP (net, same_net, rb);
  rb->same_subnet = rb->original_subnet;
  END_LOOP;
}

static inline cost_t
cost_to_point_on_layer (const CheapPointType * p1,
                        const CheapPointType * p2, Cardinal point_layer)
{
  cost_t x_dist = p1->X - p2->X, y_dist = p1->Y - p2->Y, r;
  x_dist *= x_cost[point_layer];
  y_dist *= y_cost[point_layer];
  /* cost is proportional to orthogonal distance. */
  r = ABS (x_dist) + ABS (y_dist);
  if (p1->X != p2->X && p1->Y != p2->Y)
    r += AutoRouteParameters.JogPenalty;
  return r;
}

static cost_t
cost_to_point (const CheapPointType * p1, Cardinal point_layer1,
               const CheapPointType * p2, Cardinal point_layer2)
{
  cost_t r = cost_to_point_on_layer (p1, p2, point_layer1);
  /* apply via cost penalty if layers differ */
  if (point_layer1 != point_layer2)
    r += AutoRouteParameters.ViaCost;
  return r;
}

/*!
 * \brief Return the minimum *cost* from a point to a box on any layer.
 *
 * It's safe to return a smaller than minimum cost.
 */
static cost_t
cost_to_layerless_box (const CheapPointType * p, Cardinal point_layer,
                       const BoxType * b)
{
  CheapPointType p2 = closest_point_in_box (p, b);
  register cost_t c1, c2;

  c1 = p2.X - p->X;
  c2 = p2.Y - p->Y;

  c1 = ABS (c1);
  c2 = ABS (c2);
  if (c1 < c2)
    return c1 * AutoRouteParameters.MinPenalty + c2;
  else
    return c2 * AutoRouteParameters.MinPenalty + c1;
}

/*!
 * \brief Get to actual pins/pad target coordinates.
 */
bool
TargetPoint (CheapPointType * nextpoint, const routebox_t * target)
{
  if (target->type == PIN)
    {
      nextpoint->X = target->parent.pin->X;
      nextpoint->Y = target->parent.pin->Y;
      return true;
    }
  else if (target->type == PAD)
    {
      if (abs (target->parent.pad->Point1.X - nextpoint->X) <
          abs (target->parent.pad->Point2.X - nextpoint->X))
        nextpoint->X = target->parent.pad->Point1.X;
      else
        nextpoint->X = target->parent.pad->Point2.X;
      if (abs (target->parent.pad->Point1.Y - nextpoint->Y) <
          abs (target->parent.pad->Point2.Y - nextpoint->Y))
        nextpoint->Y = target->parent.pad->Point1.Y;
      else
        nextpoint->Y = target->parent.pad->Point2.Y;
      return true;
    }
  else
    {
      nextpoint->X = CENTER_X (target->sbox);
      nextpoint->Y = CENTER_Y (target->sbox);
    }
  return false;
}

/*!
 * \brief Return the *minimum cost* from a point to a route box,
 * including possible via costs if the route box is on a different
 * layer.
 *
 * Assume routbox is bloated unless it is an expansion area.
 */
static cost_t
cost_to_routebox (const CheapPointType * p, Cardinal point_layer,
                  const routebox_t * rb)
{
  register cost_t trial = 0;
  CheapPointType p2 = closest_point_in_routebox (p, rb);
  if (!usedGroup[point_layer] || !usedGroup[rb->group])
    trial = AutoRouteParameters.NewLayerPenalty;
  if ((p2.X - p->X) * (p2.Y - p->Y) != 0)
    trial += AutoRouteParameters.JogPenalty;
  /* special case for defered via searching */
  if (point_layer > max_group || point_layer == rb->group)
    return trial + ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
  /* if this target is only a via away, then the via is cheaper than the congestion */
  if (p->X == p2.X && p->Y == p2.Y)
    return trial + 1;
  trial += AutoRouteParameters.ViaCost;
  trial += ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
  return trial;
}


static BoxType
bloat_routebox (routebox_t * rb)
{
  BoxType r;
  Coord keepaway;
  assert (__routebox_is_good (rb));

  if (rb->flags.nobloat)
    return rb->sbox;

  /* Obstacle exclusion zones get bloated by the larger of
   * the two required clearances plus half the track width.
   */
  keepaway = MAX (AutoRouteParameters.style->Keepaway, rb->style->Keepaway);
  r = bloat_box (&rb->sbox, keepaway +
                 HALF_THICK (AutoRouteParameters.style->Thick));
  return r;
}


#ifdef ROUTE_DEBUG              /* only for debugging expansion areas */

/*!
 * \brief Makes a line on the solder layer silk surrounding the box.
 */
void
showbox (BoxType b, Dimension thickness, int group)
{
  LineType *line;
  LayerType *SLayer = LAYER_PTR (group);
  if (showboxen < -1)
    return;
  if (showboxen != -1 && showboxen != group)
    return;

  if (ddraw != NULL)
    {
      ddraw->set_line_width (ar_gc, thickness);
      ddraw->set_line_cap (ar_gc, Trace_Cap);
      ddraw->set_color (ar_gc, SLayer->Color);

      ddraw->draw_line (ar_gc, b.X1, b.Y1, b.X2, b.Y1);
      ddraw->draw_line (ar_gc, b.X1, b.Y2, b.X2, b.Y2);
      ddraw->draw_line (ar_gc, b.X1, b.Y1, b.X1, b.Y2);
      ddraw->draw_line (ar_gc, b.X2, b.Y1, b.X2, b.Y2);
    }

#if 1
  if (b.Y1 == b.Y2 || b.X1 == b.X2)
    thickness = 5;
  line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
                               b.X1, b.Y1, b.X2, b.Y1, thickness, 0,
                               MakeFlags (0));
  AddObjectToCreateUndoList (LINE_TYPE,
                             LAYER_PTR (top_silk_layer), line,
                             line);
  if (b.Y1 != b.Y2)
    {
      line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
                                   b.X1, b.Y2, b.X2, b.Y2, thickness, 0,
                                   MakeFlags (0));
      AddObjectToCreateUndoList (LINE_TYPE,
                                 LAYER_PTR (bottom_silk_layer),
                                 line, line);
    }
  line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
                               b.X1, b.Y1, b.X1, b.Y2, thickness, 0,
                               MakeFlags (0));
  AddObjectToCreateUndoList (LINE_TYPE,
                             LAYER_PTR (top_silk_layer), line,
                             line);
  if (b.X1 != b.X2)
    {
      line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
                                   b.X2, b.Y1, b.X2, b.Y2, thickness, 0,
                                   MakeFlags (0));
      AddObjectToCreateUndoList (LINE_TYPE,
                                 LAYER_PTR (top_silk_layer),
                                 line, line);
    }
#endif
}
#endif

#if defined(ROUTE_DEBUG)
static void
showedge (edge_t * e)
{
  BoxType *b = (BoxType *) e->rb;

  if (ddraw == NULL)
    return;

  ddraw->set_line_cap (ar_gc, Trace_Cap);
  ddraw->set_line_width (ar_gc, 1);
  ddraw->set_color (ar_gc, Settings.MaskColor);

  switch (e->expand_dir)
    {
    case NORTH:
      ddraw->draw_line (ar_gc, b->X1, b->Y1, b->X2, b->Y1);
      break;
    case SOUTH:
      ddraw->draw_line (ar_gc, b->X1, b->Y2, b->X2, b->Y2);
      break;
    case WEST:
      ddraw->draw_line (ar_gc, b->X1, b->Y1, b->X1, b->Y2);
      break;
    case EAST:
      ddraw->draw_line (ar_gc, b->X2, b->Y1, b->X2, b->Y2);
      break;
    default:
      break;
    }
}
#endif

#if defined(ROUTE_DEBUG)
static void
showroutebox (routebox_t * rb)
{
  showbox (rb->sbox, rb->flags.source ? 20 : (rb->flags.target ? 10 : 1),
           rb->flags.is_via ? top_silk_layer : rb->group);
}
#endif

/*!
 * \brief Return a "parent" of this edge which immediately precedes it
 * in the route.
 */
static routebox_t *
route_parent (routebox_t * rb)
{
  while (rb->flags.homeless && !rb->flags.is_via && !rb->flags.is_thermal)
    {
      assert (rb->type == EXPANSION_AREA);
      rb = rb->parent.expansion_area;
      assert (rb);
    }
  return rb;
}

static vector_t *
path_conflicts (routebox_t * rb, routebox_t * conflictor, bool branch)
{
  if (branch)
    rb->conflicts_with = vector_duplicate (rb->conflicts_with);
  else if (!rb->conflicts_with)
    rb->conflicts_with = vector_create ();
  vector_append (rb->conflicts_with, conflictor);
  return rb->conflicts_with;
}

/*!
 * \brief Touch everything (except fixed) on each net found
 * in the conflicts vector. If the vector is different
 * from the last one touched, untouch the last batch
 * and touch the new one. Always call with touch=1
 * (except for recursive call). Call with NULL, 1 to
 * clear the last batch touched.
 *
 * Touched items become invisible to current path
 * so we don't encounter the same conflictor more
 * than once.
 */
static void
touch_conflicts (vector_t * conflicts, int touch)
{
  static vector_t *last = NULL;
  static int last_size = 0;
  int i, n;
  i = 0;
  if (touch)
    {
      if (last && conflicts != last)
        touch_conflicts (last, 0);
      if (!conflicts)
        return;
      last = conflicts;
      i = last_size;
    }
  n = vector_size (conflicts);
  for (; i < n; i++)
    {
      routebox_t *rb = (routebox_t *) vector_element (conflicts, i);
      routebox_t *p;
      LIST_LOOP (rb, same_net, p);
      if (!p->flags.fixed)
        p->flags.touched = touch;
      END_LOOP;
    }
  if (!touch)
    {
      last = NULL;
      last_size = 0;
    }
  else
    last_size = n;
}

/*!
 * \brief Return a "parent" of this edge which resides in a r-tree
 * somewhere.
 *
 * Actually, this "parent" *may* be a via box, which doesn't live in
 * a r-tree.
 */
static routebox_t *
nonhomeless_parent (routebox_t * rb)
{
  return route_parent (rb);
}

/*!
 * \brief Some routines to find the minimum *cost* from a cost point to
 * a target (any target).
 */
struct mincost_target_closure
{
  const CheapPointType *CostPoint;
  Cardinal CostPointLayer;
  routebox_t *nearest;
  cost_t nearest_cost;
};
static int
__region_within_guess (const BoxType * region, void *cl)
{
  struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl;
  cost_t cost_to_region;
  if (mtc->nearest == NULL)
    return 1;
  cost_to_region =
    cost_to_layerless_box (mtc->CostPoint, mtc->CostPointLayer, region);
  assert (cost_to_region >= 0);
  /* if no guess yet, all regions are "close enough" */
  /* note that cost is *strictly more* than minimum distance, so we'll
   * always search a region large enough. */
  return (cost_to_region < mtc->nearest_cost);
}
static int
__found_new_guess (const BoxType * box, void *cl)
{
  struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl;
  routebox_t *guess = (routebox_t *) box;
  cost_t cost_to_guess =
    cost_to_routebox (mtc->CostPoint, mtc->CostPointLayer, guess);
  assert (cost_to_guess >= 0);
  /* if this is cheaper than previous guess... */
  if (cost_to_guess < mtc->nearest_cost)
    {
      mtc->nearest = guess;
      mtc->nearest_cost = cost_to_guess;        /* this is our new guess! */
      return 1;
    }
  else
    return 0;                   /* not less expensive than our last guess */
}

/*!
 * \brief .
 *
 * \c target_guess is our guess at what the nearest target is, or
 * \c NULL if we just plum don't have a clue.
 */
static routebox_t *
mincost_target_to_point (const CheapPointType * CostPoint,
                         Cardinal CostPointLayer,
                         rtree_t * targets, routebox_t * target_guess)
{
  struct mincost_target_closure mtc;
  assert (target_guess == NULL || target_guess->flags.target);  /* this is a target, right? */
  mtc.CostPoint = CostPoint;
  mtc.CostPointLayer = CostPointLayer;
  mtc.nearest = target_guess;
  if (mtc.nearest)
    mtc.nearest_cost =
      cost_to_routebox (mtc.CostPoint, mtc.CostPointLayer, mtc.nearest);
  else
    mtc.nearest_cost = EXPENSIVE;
  r_search (targets, NULL, __region_within_guess, __found_new_guess, &mtc);
  assert (mtc.nearest != NULL && mtc.nearest_cost >= 0);
  assert (mtc.nearest->flags.target);   /* this is a target, right? */
  return mtc.nearest;
}

/*!
 * \brief Create edge from field values.
 *
 * mincost_target_guess can be \c NULL .
 */
static edge_t *
CreateEdge (routebox_t * rb,
            Coord CostPointX, Coord CostPointY,
            cost_t cost_to_point,
            routebox_t * mincost_target_guess,
            direction_t expand_dir, rtree_t * targets)
{
  edge_t *e;
  assert (__routebox_is_good (rb));
  e = (edge_t *)malloc (sizeof (*e));
  memset ((void *) e, 0, sizeof (*e));
  assert (e);
  e->rb = rb;
  if (rb->flags.homeless)
    RB_up_count (rb);
  e->cost_point.X = CostPointX;
  e->cost_point.Y = CostPointY;
  e->cost_to_point = cost_to_point;
  e->flags.via_search = 0;
  /* if this edge is created in response to a target, use it */
  if (targets)
    e->mincost_target =
      mincost_target_to_point (&e->cost_point, rb->group,
                               targets, mincost_target_guess);
  else
    e->mincost_target = mincost_target_guess;
  e->expand_dir = expand_dir;
  assert (e->rb && e->mincost_target);  /* valid edge? */
  assert (!e->flags.is_via || e->expand_dir == ALL);
  /* cost point should be on edge (unless this is a plane/via/conflict edge) */
#if 0
  assert (rb->type == PLANE || rb->conflicts_with != NULL || rb->flags.is_via
          || rb->flags.is_thermal
          || ((expand_dir == NORTH || expand_dir == SOUTH) ? rb->sbox.X1 <=
              CostPointX && CostPointX < rb->sbox.X2
              && CostPointY == (expand_dir ==
                                NORTH ? rb->sbox.Y1 : rb->sbox.Y2 - 1) :
              /* expand_dir==EAST || expand_dir==WEST */
              rb->sbox.Y1 <= CostPointY && CostPointY < rb->sbox.Y2 &&
              CostPointX == (expand_dir ==
                             EAST ? rb->sbox.X2 - 1 : rb->sbox.X1)));
#endif
  assert (__edge_is_good (e));
  /* done */
  return e;
}

/*!
 * \brief Create edge, using previous edge to fill in defaults.
 *
 * Most of the work here is in determining a new cost point.
 */
static edge_t *
CreateEdge2 (routebox_t * rb, direction_t expand_dir,
             edge_t * previous_edge, rtree_t * targets, routebox_t * guess)
{
  BoxType thisbox;
  CheapPointType thiscost, prevcost;
  cost_t d;

  assert (rb && previous_edge);
  /* okay, find cheapest costpoint to costpoint of previous edge */
  thisbox = edge_to_box (rb, expand_dir);
  prevcost = previous_edge->cost_point;
  /* find point closest to target */
  thiscost = closest_point_in_box (&prevcost, &thisbox);
  /* compute cost-to-point */
  d = cost_to_point_on_layer (&prevcost, &thiscost, rb->group);
  /* add in jog penalty */
  if (previous_edge->expand_dir != expand_dir)
    d += AutoRouteParameters.JogPenalty;
  /* okay, new edge! */
  return CreateEdge (rb, thiscost.X, thiscost.Y,
                     previous_edge->cost_to_point + d,
                     guess ? guess : previous_edge->mincost_target,
                     expand_dir, targets);
}

/*!
 * \brief Create via edge, using previous edge to fill in defaults.
 */
static edge_t *
CreateViaEdge (const BoxType * area, Cardinal group,
               routebox_t * parent, edge_t * previous_edge,
               conflict_t to_site_conflict,
               conflict_t through_site_conflict, rtree_t * targets)
{
  routebox_t *rb;
  CheapPointType costpoint;
  cost_t d;
  edge_t *ne;
  cost_t scale[3];

  scale[0] = 1;
  scale[1] = AutoRouteParameters.LastConflictPenalty;
  scale[2] = AutoRouteParameters.ConflictPenalty;

  assert (box_is_good (area));
  assert (AutoRouteParameters.with_conflicts ||
          (to_site_conflict == NO_CONFLICT &&
           through_site_conflict == NO_CONFLICT));
  rb = CreateExpansionArea (area, group, parent, true, previous_edge);
  rb->flags.is_via = 1;
  rb->came_from = ALL;
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_VIA_BOXES)
  showroutebox (rb);
#endif /* ROUTE_DEBUG && DEBUG_SHOW_VIA_BOXES */
  /* for planes, choose a point near the target */
  if (previous_edge->flags.in_plane)
    {
      routebox_t *target;
      CheapPointType pnt;
      /* find a target near this via box */
      pnt.X = CENTER_X (*area);
      pnt.Y = CENTER_Y (*area);
      target = mincost_target_to_point (&pnt, rb->group,
                                        targets,
                                        previous_edge->mincost_target);
      /* now find point near the target */
      pnt.X = CENTER_X (target->box);
      pnt.Y = CENTER_Y (target->box);
      costpoint = closest_point_in_routebox (&pnt, rb);
      /* we moved from the previous cost point through the plane which is free travel */
      d =
        (scale[through_site_conflict] *
         cost_to_point (&costpoint, group, &costpoint,
                        previous_edge->rb->group));
      ne =
        CreateEdge (rb, costpoint.X, costpoint.Y,
                    previous_edge->cost_to_point + d, target, ALL, NULL);
      ne->mincost_target = target;
    }
  else
    {
      routebox_t *target;
      target = previous_edge->mincost_target;
      costpoint = closest_point_in_routebox (&previous_edge->cost_point, rb);
      d =
        (scale[to_site_conflict] *
         cost_to_point_on_layer (&costpoint, &previous_edge->cost_point,
                                 previous_edge->rb->group)) +
        (scale[through_site_conflict] *
         cost_to_point (&costpoint, group, &costpoint,
                        previous_edge->rb->group));
      /* if the target is just this via away, then this via is cheaper */
      if (target->group == group &&
          point_in_shrunk_box (target, costpoint.X, costpoint.Y))
        d -= AutoRouteParameters.ViaCost / 2;
      ne =
        CreateEdge (rb, costpoint.X, costpoint.Y,
                    previous_edge->cost_to_point + d,
                    previous_edge->mincost_target, ALL, targets);
    }
  ne->flags.is_via = 1;
  ne->flags.via_conflict_level = to_site_conflict;
  assert (__edge_is_good (ne));
  return ne;
}

/*!
 * \brief Create "interior" edge for routing with conflicts.
 *
 * Presently once we "jump inside" the conflicting object
 * we consider it a routing highway to travel inside since
 * it will become available if the conflict is elliminated.
 * That is why we ignore the interior_edge argument.
 */
static edge_t *
CreateEdgeWithConflicts (const BoxType * interior_edge,
                         routebox_t * container, edge_t * previous_edge,
                         cost_t cost_penalty_to_box, rtree_t * targets)
{
  routebox_t *rb;
  CheapPointType costpoint;
  cost_t d;
  edge_t *ne;
  assert (interior_edge && container && previous_edge && targets);
  assert (!container->flags.homeless);
  assert (AutoRouteParameters.with_conflicts);
  assert (container->flags.touched == 0);
  assert (previous_edge->rb->group == container->group);
  /* use the caller's idea of what this box should be */
  rb =
    CreateExpansionArea (interior_edge, previous_edge->rb->group,
                         previous_edge->rb, true, previous_edge);
  path_conflicts (rb, container, true); /* crucial! */
  costpoint =
    closest_point_in_box (&previous_edge->cost_point, interior_edge);
  d =
    cost_to_point_on_layer (&costpoint, &previous_edge->cost_point,
                            previous_edge->rb->group);
  d *= cost_penalty_to_box;
  d += previous_edge->cost_to_point;
  ne = CreateEdge (rb, costpoint.X, costpoint.Y, d, NULL, ALL, targets);
  ne->flags.is_interior = 1;
  assert (__edge_is_good (ne));
  return ne;
}

static void
KillEdge (void *edge)
{
  edge_t *e = (edge_t *) edge;
  assert (e);
  if (e->rb->flags.homeless)
    RB_down_count (e->rb);
  if (e->flags.via_search)
    mtsFreeWork (&e->work);
  free (e);
}

static void
DestroyEdge (edge_t ** e)
{
  assert (e && *e);
  KillEdge (*e);
  *e = NULL;
}

/*!
 * \brief Cost function for an edge.
 */
static cost_t
edge_cost (const edge_t * e, const cost_t too_big)
{
  cost_t penalty = e->cost_to_point;
  if (e->rb->flags.is_thermal || e->rb->type == PLANE)
    return penalty;             /* thermals are cheap */
  if (penalty > too_big)
    return penalty;

  /* cost_to_routebox adds in our via correction, too. */
  return penalty +
    cost_to_routebox (&e->cost_point, e->rb->group, e->mincost_target);
}

/*!
 * \brief Given an edge of a box, return a box containing exactly the
 * points on that edge.
 *
 * Note that the return box is treated as closed; that is, the bottom
 * and right "edges" consist of points (just barely) not in the
 * (half-open) box.
 */
static BoxType
edge_to_box (const routebox_t * rb, direction_t expand_dir)
{
  BoxType b = shrink_routebox (rb);
  /* narrow box down to just the appropriate edge */
  switch (expand_dir)
    {
    case NORTH:
      b.Y2 = b.Y1 + 1;
      break;
    case EAST:
      b.X1 = b.X2 - 1;
      break;
    case SOUTH:
      b.Y1 = b.Y2 - 1;
      break;
    case WEST:
      b.X2 = b.X1 + 1;
      break;
    default:
      assert (0);
    }
  /* done! */
  return b;
}

struct broken_boxes
{
  BoxType left, center, right;
  bool is_valid_left, is_valid_center, is_valid_right;
};

static struct broken_boxes
break_box_edge (const BoxType * original, direction_t which_edge,
                routebox_t * breaker)
{
  BoxType origbox, breakbox;
  struct broken_boxes result;

  assert (original && breaker);

  origbox = *original;
  breakbox = bloat_routebox (breaker);
  ROTATEBOX_TO_NORTH (origbox, which_edge);
  ROTATEBOX_TO_NORTH (breakbox, which_edge);
  result.right.Y1 = result.center.Y1 = result.left.Y1 = origbox.Y1;
  result.right.Y2 = result.center.Y2 = result.left.Y2 = origbox.Y1 + 1;
  /* validity of breaker is not important because the boxes are marked invalid */
  //assert (breakbox.X1 <= origbox.X2 && breakbox.X2 >= origbox.X1);
  /* left edge piece */
  result.left.X1 = origbox.X1;
  result.left.X2 = breakbox.X1;
  /* center (ie blocked) edge piece */
  result.center.X1 = MAX (breakbox.X1, origbox.X1);
  result.center.X2 = MIN (breakbox.X2, origbox.X2);
  /* right edge piece */
  result.right.X1 = breakbox.X2;
  result.right.X2 = origbox.X2;
  /* validity: */
  result.is_valid_left = (result.left.X1 < result.left.X2);
  result.is_valid_center = (result.center.X1 < result.center.X2);
  result.is_valid_right = (result.right.X1 < result.right.X2);
  /* rotate back */
  ROTATEBOX_FROM_NORTH (result.left, which_edge);
  ROTATEBOX_FROM_NORTH (result.center, which_edge);
  ROTATEBOX_FROM_NORTH (result.right, which_edge);
  /* done */
  return result;
}

#ifndef NDEBUG
static int
share_edge (const BoxType * child, const BoxType * parent)
{
  return
    (child->X1 == parent->X2 || child->X2 == parent->X1 ||
     child->Y1 == parent->Y2 || child->Y2 == parent->Y1) &&
    ((parent->X1 <= child->X1 && child->X2 <= parent->X2) ||
     (parent->Y1 <= child->Y1 && child->Y2 <= parent->Y2));
}
static int
edge_intersect (const BoxType * child, const BoxType * parent)
{
  return
    (child->X1 <= parent->X2) && (child->X2 >= parent->X1) &&
    (child->Y1 <= parent->Y2) && (child->Y2 >= parent->Y1);
}
#endif

/*!
 * \brief Area is the expansion area, on layer group 'group'.
 *
 * 'parent' is the immediately preceding expansion area, for backtracing.
 * 'lastarea' is the last expansion area created, we string these
 * together in a loop so we can remove them all easily at the end.
 */
static routebox_t *
CreateExpansionArea (const BoxType * area, Cardinal group,
                     routebox_t * parent,
                     bool relax_edge_requirements, edge_t * src_edge)
{
  routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
  memset ((void *) rb, 0, sizeof (*rb));
  assert (area && parent);
  init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
  rb->group = group;
  rb->type = EXPANSION_AREA;
  /* should always share edge or overlap with parent */
  assert (relax_edge_requirements ? box_intersect (&rb->sbox, &parent->sbox)
          : share_edge (&rb->sbox, &parent->sbox));
  rb->parent.expansion_area = route_parent (parent);
  rb->cost_point =
    closest_point_in_box (&rb->parent.expansion_area->cost_point, area);
  rb->cost =
    rb->parent.expansion_area->cost +
    cost_to_point_on_layer (&rb->parent.expansion_area->cost_point,
                            &rb->cost_point, rb->group);
  assert (relax_edge_requirements ? edge_intersect (&rb->sbox, &parent->sbox)
          : share_edge (&rb->sbox, &parent->sbox));
  if (rb->parent.expansion_area->flags.homeless)
    RB_up_count (rb->parent.expansion_area);
  rb->flags.homeless = 1;
  rb->flags.nobloat = 1;
  rb->style = AutoRouteParameters.style;
  rb->conflicts_with = parent->conflicts_with;
/* we will never link an EXPANSION_AREA into the nets because they
 * are *ONLY* used for path searching. No need to call  InitLists ()
 */
  rb->came_from = src_edge->expand_dir;
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
  showroutebox (rb);
#endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */
  return rb;
}

/*------ Expand ------*/
struct E_result
{
  routebox_t *parent;
  routebox_t *n, *e, *s, *w;
  Coord keep, bloat;
  BoxType inflated, orig;
  int done;
};

/*!
 * \brief Test method for Expand().
 *
 * This routebox potentially is a blocker limiting expansion
 * if this is so, we limit the inflate box so another exactly
 * like it wouldn't be seen. We do this while keep the inflated
 * box as large as possible.
 */
static int
__Expand_this_rect (const BoxType * box, void *cl)
{
  struct E_result *res = (struct E_result *) cl;
  routebox_t *rb = (routebox_t *) box;
  BoxType rbox;
  Coord dn, de, ds, dw, bloat;

  /* we don't see conflicts already encountered */
  if (rb->flags.touched)
    return 0;

  /* The inflated box outer edges include its own 
   * track width plus its own keepaway.
   *
   * To check for intersection, we need to expand
   * anything with greater keepaway by its excess
   * keepaway.
   *
   * If something has nobloat then we need to shrink
   * the inflated box back and see if it still touches.
   */

  if (rb->flags.nobloat)
    {
      rbox = rb->sbox;
      bloat = res->bloat;
      if (rbox.X2 <= res->inflated.X1 + bloat ||
          rbox.X1 >= res->inflated.X2 - bloat ||
          rbox.Y1 >= res->inflated.Y2 - bloat ||
          rbox.Y2 <= res->inflated.Y1 + bloat)
        return 0;               /* doesn't touch */
    }
  else
    {
      if (rb->style->Keepaway > res->keep)
        rbox = bloat_box (&rb->sbox, rb->style->Keepaway - res->keep);
      else
        rbox = rb->sbox;

      if (rbox.X2 <= res->inflated.X1 || rbox.X1 >= res->inflated.X2
          || rbox.Y1 >= res->inflated.Y2 || rbox.Y2 <= res->inflated.Y1)
        return 0;               /* doesn't touch */
      bloat = 0;
    }

  /* this is an intersecting box; it has to jump through a few more hoops */
  if (rb == res->parent || rb->parent.expansion_area == res->parent)
    return 0;                   /* don't see what we came from */

  /* if we are expanding a source edge, don't let other sources
   * or their expansions stop us.
   */
#if 1
  if (res->parent->flags.source)
    if (rb->flags.source
        || (rb->type == EXPANSION_AREA
            && rb->parent.expansion_area->flags.source))
      return 0;
#endif

  /* we ignore via expansion boxes because maybe its
   * cheaper to get there without the via through
   * the path we're exploring  now.
   */
  if (rb->flags.is_via && rb->type == EXPANSION_AREA)
    return 0;

  if (rb->type == PLANE)        /* expanding inside a plane is not good */
    {
      if (rbox.X1 < res->orig.X1 && rbox.X2 > res->orig.X2 &&
          rbox.Y1 < res->orig.Y1 && rbox.Y2 > res->orig.Y2)
        {
          res->inflated = bloat_box (&res->orig, res->bloat);
          return 1;
        }
    }
  /* calculate the distances from original box to this blocker */
  dn = de = ds = dw = 0;
  if (!(res->done & _NORTH) && rbox.Y1 <= res->orig.Y1
      && rbox.Y2 > res->inflated.Y1)
    dn = res->orig.Y1 - rbox.Y2;
  if (!(res->done & _EAST) && rbox.X2 >= res->orig.X2
      && rbox.X1 < res->inflated.X2)
    de = rbox.X1 - res->orig.X2;
  if (!(res->done & _SOUTH) && rbox.Y2 >= res->orig.Y2
      && rbox.Y1 < res->inflated.Y2)
    ds = rbox.Y1 - res->orig.Y2;
  if (!(res->done & _WEST) && rbox.X1 <= res->orig.X1
      && rbox.X2 > res->inflated.X1)
    dw = res->orig.X1 - rbox.X2;
  if (dn <= 0 && de <= 0 && ds <= 0 && dw <= 0)
    return 1;
  /* now shrink the inflated box to the largest blocking direction */
  if (dn >= de && dn >= ds && dn >= dw)
    {
      res->inflated.Y1 = rbox.Y2 - bloat;
      res->n = rb;
    }
  else if (de >= ds && de >= dw)
    {
      res->inflated.X2 = rbox.X1 + bloat;
      res->e = rb;
    }
  else if (ds >= dw)
    {
      res->inflated.Y2 = rbox.Y1 + bloat;
      res->s = rb;
    }
  else
    {
      res->inflated.X1 = rbox.X2 - bloat;
      res->w = rb;
    }
  return 1;
}

static bool
boink_box (routebox_t * rb, struct E_result *res, direction_t dir)
{
  Coord bloat;
  if (rb->style->Keepaway > res->keep)
    bloat = res->keep - rb->style->Keepaway;
  else
    bloat = 0;
  if (rb->flags.nobloat)
    bloat = res->bloat;
  switch (dir)
    {
    case NORTH:
    case SOUTH:
      if (rb->sbox.X2 <= res->inflated.X1 + bloat
          || rb->sbox.X1 >= res->inflated.X2 - bloat)
        return false;
      return true;
    case EAST:
    case WEST:
      if (rb->sbox.Y1 >= res->inflated.Y2 - bloat
          || rb->sbox.Y2 <= res->inflated.Y1 + bloat)
        return false;
      return true;
      break;
    default:
      assert (0);
    }
  return false;
}

/*!
 * \brief Main Expand routine.
 *
 * The expansion probe edge includes the keepaway and half thickness
 * as the search is performed in order to see everything relevant.
 * The result is backed off by this amount before being returned.
 * Targets (and other no-bloat routeboxes) go all the way to touching.
 * This is accomplished by backing off the probe edge when checking
 * for touch against such an object. Usually the expanding edge
 * bumps into neighboring pins on the same device that require a
 * keepaway, preventing seeing a target immediately. Rather than await
 * another expansion to actually touch the target, the edge breaker code 
 * looks past the keepaway to see these targets even though they 
 * weren't actually touched in the expansion.
 */
struct E_result *
Expand (rtree_t * rtree, edge_t * e, const BoxType * box)
{
  static struct E_result ans;
  int noshrink;                 /* bit field of which edges to not shrink */

  ans.bloat = AutoRouteParameters.bloat;
  ans.orig = *box;
  ans.n = ans.e = ans.s = ans.w = NULL;

  /* the inflated box must be bloated in all directions that it might
   * hit something in order to guarantee that we see object in the
   * tree it might hit. The tree holds objects bloated by their own
   * keepaway so we are guaranteed to honor that.
   */
  switch (e->expand_dir)
    {
    case ALL:
      ans.inflated.X1 = (e->rb->came_from == EAST ? ans.orig.X1 : 0);
      ans.inflated.Y1 = (e->rb->came_from == SOUTH ? ans.orig.Y1 : 0);
      ans.inflated.X2 =
        (e->rb->came_from == WEST ? ans.orig.X2 : PCB->MaxWidth);
      ans.inflated.Y2 =
        (e->rb->came_from == NORTH ? ans.orig.Y2 : PCB->MaxHeight);
      if (e->rb->came_from == NORTH)
        ans.done = noshrink = _SOUTH;
      else if (e->rb->came_from == EAST)
        ans.done = noshrink = _WEST;
      else if (e->rb->came_from == SOUTH)
        ans.done = noshrink = _NORTH;
      else if (e->rb->came_from == WEST)
        ans.done = noshrink = _EAST;
      else
        ans.done = noshrink = 0;
      break;
    case NORTH:
      ans.done = _SOUTH + _EAST + _WEST;
      noshrink = _SOUTH;
      ans.inflated.X1 = box->X1 - ans.bloat;
      ans.inflated.X2 = box->X2 + ans.bloat;
      ans.inflated.Y2 = box->Y2;
      ans.inflated.Y1 = 0;      /* far north */
      break;
    case NE:
      ans.done = _SOUTH + _WEST;
      noshrink = 0;
      ans.inflated.X1 = box->X1 - ans.bloat;
      ans.inflated.X2 = PCB->MaxWidth;
      ans.inflated.Y2 = box->Y2 + ans.bloat;
      ans.inflated.Y1 = 0;
      break;
    case EAST:
      ans.done = _NORTH + _SOUTH + _WEST;
      noshrink = _WEST;
      ans.inflated.Y1 = box->Y1 - ans.bloat;
      ans.inflated.Y2 = box->Y2 + ans.bloat;
      ans.inflated.X1 = box->X1;
      ans.inflated.X2 = PCB->MaxWidth;
      break;
    case SE:
      ans.done = _NORTH + _WEST;
      noshrink = 0;
      ans.inflated.X1 = box->X1 - ans.bloat;
      ans.inflated.X2 = PCB->MaxWidth;
      ans.inflated.Y2 = PCB->MaxHeight;
      ans.inflated.Y1 = box->Y1 - ans.bloat;
      break;
    case SOUTH:
      ans.done = _NORTH + _EAST + _WEST;
      noshrink = _NORTH;
      ans.inflated.X1 = box->X1 - ans.bloat;
      ans.inflated.X2 = box->X2 + ans.bloat;
      ans.inflated.Y1 = box->Y1;
      ans.inflated.Y2 = PCB->MaxHeight;
      break;
    case SW:
      ans.done = _NORTH + _EAST;
      noshrink = 0;
      ans.inflated.X1 = 0;
      ans.inflated.X2 = box->X2 + ans.bloat;
      ans.inflated.Y2 = PCB->MaxHeight;
      ans.inflated.Y1 = box->Y1 - ans.bloat;
      break;
    case WEST:
      ans.done = _NORTH + _SOUTH + _EAST;
      noshrink = _EAST;
      ans.inflated.Y1 = box->Y1 - ans.bloat;
      ans.inflated.Y2 = box->Y2 + ans.bloat;
      ans.inflated.X1 = 0;
      ans.inflated.X2 = box->X2;
      break;
    case NW:
      ans.done = _SOUTH + _EAST;
      noshrink = 0;
      ans.inflated.X1 = 0;
      ans.inflated.X2 = box->X2 + ans.bloat;
      ans.inflated.Y2 = box->Y2 + ans.bloat;
      ans.inflated.Y1 = 0;
      break;
    default:
      noshrink = ans.done = 0;
      assert (0);
    }
  ans.keep = e->rb->style->Keepaway;
  ans.parent = nonhomeless_parent (e->rb);
  r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
/* because the overlaping boxes are found in random order, some blockers
 * may have limited edges prematurely, so we check if the blockers realy
 * are blocking, and make another try if not
 */
  if (ans.n && !boink_box (ans.n, &ans, NORTH))
    ans.inflated.Y1 = 0;
  else
    ans.done |= _NORTH;
  if (ans.e && !boink_box (ans.e, &ans, EAST))
    ans.inflated.X2 = PCB->MaxWidth;
  else
    ans.done |= _EAST;
  if (ans.s && !boink_box (ans.s, &ans, SOUTH))
    ans.inflated.Y2 = PCB->MaxHeight;
  else
    ans.done |= _SOUTH;
  if (ans.w && !boink_box (ans.w, &ans, WEST))
    ans.inflated.X1 = 0;
  else
    ans.done |= _WEST;
  if (ans.done != _NORTH + _EAST + _SOUTH + _WEST)
    {
      r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
    }
  if ((noshrink & _NORTH) == 0)
    ans.inflated.Y1 += ans.bloat;
  if ((noshrink & _EAST) == 0)
    ans.inflated.X2 -= ans.bloat;
  if ((noshrink & _SOUTH) == 0)
    ans.inflated.Y2 -= ans.bloat;
  if ((noshrink & _WEST) == 0)
    ans.inflated.X1 += ans.bloat;
  return &ans;
}

/*!
 * \brief \c blocker_to_heap puts the blockers into a heap so they
 * can be retrieved in clockwise order. If a blocker
 * is also a target, it gets put into the vector too.
 * It returns 1 for any fixed blocker that is not part 
 * of this net and zero otherwise. 
 */
static int
blocker_to_heap (heap_t * heap, routebox_t * rb,
                 BoxType * box, direction_t dir)
{
  BoxType b = rb->sbox;
  if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
    b =
      bloat_box (&b,
                 rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
  b = clip_box (&b, box);
  assert (box_is_good (&b));
  /* we want to look at the blockers clockwise around the box */
  switch (dir)
    {
      /* we need to use the other coordinate fraction to resolve
       * ties since we want the shorter of the furthest
       * first.
       */
    case NORTH:
      heap_insert (heap, b.X1 - b.X1 / (b.X2 + 1.0), rb);
      break;
    case EAST:
      heap_insert (heap, b.Y1 - b.Y1 / (b.Y2 + 1.0), rb);
      break;
    case SOUTH:
      heap_insert (heap, -(b.X2 + b.X1 / (b.X2 + 1.0)), rb);
      break;
    case WEST:
      heap_insert (heap, -(b.Y2 + b.Y1 / (b.Y2 + 1.0)), rb);
      break;
    default:
      assert (0);
    }
  if (rb->flags.fixed && !rb->flags.target && !rb->flags.source)
    return 1;
  return 0;
}

/*!
 * \brief This creates an EXPANSION_AREA to bridge small gaps or,
 * (more commonly) create a supper-thin box to provide a
 * home for an expansion edge.
 */
static routebox_t *
CreateBridge (const BoxType * area, routebox_t * parent, direction_t dir)
{
  routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
  memset ((void *) rb, 0, sizeof (*rb));
  assert (area && parent);
  init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
  rb->group = parent->group;
  rb->type = EXPANSION_AREA;
  rb->came_from = dir;
  rb->cost_point = closest_point_in_box (&parent->cost_point, area);
  rb->cost = parent->cost + cost_to_point_on_layer (&parent->cost_point,
                                                    &rb->cost_point,
                                                    rb->group);
  rb->parent.expansion_area = route_parent (parent);
  if (rb->parent.expansion_area->flags.homeless)
    RB_up_count (rb->parent.expansion_area);
  rb->flags.homeless = 1;
  rb->flags.nobloat = 1;
  rb->style = parent->style;
  rb->conflicts_with = parent->conflicts_with;
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGES)
  showroutebox (rb);
#endif
  return rb;
}

/*!
 * \brief \c moveable_edge prepares the new search edges based on the
 * starting box, direction and blocker if any.
 */
void
moveable_edge (vector_t * result, const BoxType * box, direction_t dir,
               routebox_t * rb,
               routebox_t * blocker, edge_t * e, rtree_t * targets,
               struct routeone_state *s, rtree_t * tree, vector_t * area_vec)
{
  BoxType b;
  assert (box_is_good (box));
  b = *box;
  /* for the cardinal directions, move the box to overlap the
   * the parent by 1 unit. Corner expansions overlap more
   * and their starting boxes are pre-prepared.
   * Check if anything is headed off the board edges
   */
  switch (dir)
    {
    default:
      break;
    case NORTH:
      b.Y2 = b.Y1;
      b.Y1--;
      if (b.Y1 <= AutoRouteParameters.bloat)
        return;                 /* off board edge */
      break;
    case EAST:
      b.X1 = b.X2;
      b.X2++;
      if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat)
        return;                 /* off board edge */
      break;
    case SOUTH:
      b.Y1 = b.Y2;
      b.Y2++;
      if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat)
        return;                 /* off board edge */
      break;
    case WEST:
      b.X2 = b.X1;
      b.X1--;
      if (b.X1 <= AutoRouteParameters.bloat)
        return;                 /* off board edge */
      break;
    case NE:
      if (b.Y1 <= AutoRouteParameters.bloat + 1
          && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
        return;                 /* off board edge */
      if (b.Y1 <= AutoRouteParameters.bloat + 1)
        dir = EAST;             /* north off board edge */
      if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
        dir = NORTH;            /* east off board edge */
      break;
    case SE:
      if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
          && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
        return;                 /* off board edge */
      if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
        dir = EAST;             /* south off board edge */
      if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
        dir = SOUTH;            /* east off board edge */
      break;
    case SW:
      if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
          && b.X1 <= AutoRouteParameters.bloat + 1)
        return;                 /* off board edge */
      if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
        dir = WEST;             /* south off board edge */
      if (b.X1 <= AutoRouteParameters.bloat + 1)
        dir = SOUTH;            /* west off board edge */
      break;
    case NW:
      if (b.Y1 <= AutoRouteParameters.bloat + 1
          && b.X1 <= AutoRouteParameters.bloat + 1)
        return;                 /* off board edge */
      if (b.Y1 <= AutoRouteParameters.bloat + 1)
        dir = WEST;             /* north off board edge */
      if (b.X1 <= AutoRouteParameters.bloat + 1)
        dir = NORTH;            /* west off board edge */
      break;
    }

  if (!blocker)
    {
      edge_t *ne;
      routebox_t *nrb = CreateBridge (&b, rb, dir);
      /* move the cost point in corner expansions
       * these boxes are bigger, so move close to the target
       */
      if (dir == NE || dir == SE || dir == SW || dir == NW)
        {
          CheapPointType p;
          p =
            closest_point_in_box (&nrb->cost_point, &e->mincost_target->sbox);
          p = closest_point_in_box (&p, &b);
          nrb->cost += cost_to_point_on_layer (&p, &nrb->cost_point,
                                               nrb->group);
          nrb->cost_point = p;
        }
      ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
                       nrb->cost, NULL, dir, targets);
      vector_append (result, ne);
    }
  else if (AutoRouteParameters.with_conflicts && !blocker->flags.target
           && !blocker->flags.fixed && !blocker->flags.touched &&
           !blocker->flags.source && blocker->type != EXPANSION_AREA)
    {
      edge_t *ne;
      routebox_t *nrb;
      /* make a bridge to the edge of the blocker
       * in all directions from there
       */
      switch (dir)
        {
        case NORTH:
          b.Y1 = blocker->sbox.Y2 - 1;
          break;
        case EAST:
          b.X2 = blocker->sbox.X1 + 1;
          break;
        case SOUTH:
          b.Y2 = blocker->sbox.Y1 + 1;
          break;
        case WEST:
          b.X1 = blocker->sbox.X2 - 1;
          break;
        default:
          assert (0);
        }
      if (!box_is_good (&b))
        return;                 /* how did this happen ? */
      nrb = CreateBridge (&b, rb, dir);
      r_insert_entry (tree, &nrb->box, 1);
      vector_append (area_vec, nrb);
      nrb->flags.homeless = 0;  /* not homeless any more */
      /* mark this one as conflicted */
      path_conflicts (nrb, blocker, true);
      /* and make an expansion edge */
      nrb->cost_point =
        closest_point_in_box (&nrb->cost_point, &blocker->sbox);
      nrb->cost +=
        cost_to_point_on_layer (&nrb->parent.expansion_area->cost_point,
                                &nrb->cost_point,
                                nrb->group) * CONFLICT_PENALTY (blocker);

      ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y, nrb->cost,
                       NULL, ALL, targets);
      ne->flags.is_interior = 1;
      vector_append (result, ne);
    }
#if 1
  else if (blocker->type == EXPANSION_AREA)
    {
      if (blocker->cost < rb->cost || blocker->cost <= rb->cost +
          cost_to_point_on_layer (&blocker->cost_point, &rb->cost_point,
                                  rb->group))
        return;
      if (blocker->conflicts_with || rb->conflicts_with)
        return;
      /* does the blocker overlap this routebox ?? */
      /* does this re-parenting operation leave a memory leak? */
      if (blocker->parent.expansion_area->flags.homeless)
        RB_down_count (blocker->parent.expansion_area);
      blocker->parent.expansion_area = rb;
      return;
    }
#endif
  else if (blocker->flags.target)
    {
      routebox_t *nrb;
      edge_t *ne;
      b = bloat_box (&b, 1);
      if (!box_intersect (&b, &blocker->sbox))
        {
          /* if the expansion edge stopped before touching, expand the bridge */
          switch (dir)
            {
            case NORTH:
              b.Y1 -= AutoRouteParameters.bloat + 1;
              break;
            case EAST:
              b.X2 += AutoRouteParameters.bloat + 1;
              break;
            case SOUTH:
              b.Y2 += AutoRouteParameters.bloat + 1;
              break;
            case WEST:
              b.X1 -= AutoRouteParameters.bloat + 1;
              break;
            default:
              assert (0);
            }
        }
      assert (box_intersect (&b, &blocker->sbox));
      b = shrink_box (&b, 1);
      nrb = CreateBridge (&b, rb, dir);
      r_insert_entry (tree, &nrb->box, 1);
      vector_append (area_vec, nrb);
      nrb->flags.homeless = 0;  /* not homeless any more */
      ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
                       nrb->cost, blocker, dir, NULL);
      best_path_candidate (s, ne, blocker);
      DestroyEdge (&ne);
    }
}

struct break_info
{
  heap_t *heap;
  routebox_t *parent;
  BoxType box;
  direction_t dir;
  bool ignore_source;
};

static int
__GatherBlockers (const BoxType * box, void *cl)
{
  routebox_t *rb = (routebox_t *) box;
  struct break_info *bi = (struct break_info *) cl;
  BoxType b;

  if (bi->parent == rb || rb->flags.touched ||
      bi->parent->parent.expansion_area == rb)
    return 0;
  if (rb->flags.source && bi->ignore_source)
    return 0;
  b = rb->sbox;
  if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
    b =
      bloat_box (&b,
                 rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
  if (b.X2 <= bi->box.X1 || b.X1 >= bi->box.X2
      || b.Y1 >= bi->box.Y2 || b.Y2 <= bi->box.Y1)
    return 0;
  return blocker_to_heap (bi->heap, rb, &bi->box, bi->dir);
}

/*!
 * \brief Shrink the box to the last limit for the previous direction,
 * i.e. if dir is SOUTH, then this means fixing up an EAST leftover
 * edge, which would be the southern most edge for that example.
 */
static inline BoxType
previous_edge (Coord last, direction_t i, const BoxType * b)
{
  BoxType db = *b;
  switch (i)
    {
    case EAST:
      db.X1 = last;
      break;
    case SOUTH:
      db.Y1 = last;
      break;
    case WEST:
      db.X2 = last;
      break;
    default:
      Message ("previous edge bogus direction!");
      assert (0);
    }
  return db;
}

/*!
 * \brief Break all the edges of the box that need breaking, handling
 * targets as they are found, and putting any moveable edges
 * in the return vector.
 */
vector_t *
BreakManyEdges (struct routeone_state * s, rtree_t * targets, rtree_t * tree,
                vector_t * area_vec, struct E_result * ans, routebox_t * rb,
                edge_t * e)
{
  struct break_info bi;
  vector_t *edges;
  heap_t *heap[4];
  Coord first, last;
  Coord bloat;
  direction_t dir;
  routebox_t fake;

  edges = vector_create ();
  bi.ignore_source = rb->parent.expansion_area->flags.source;
  bi.parent = rb;
  /* we add 2 to the bloat.
   * 1 will get us to the actual blocker that Expand() hit
   * but 1 more is needed because the new expansion edges
   * move out by 1 so they don't overlap their parents
   * this extra expansion could "trap" the edge if
   * there is a blocker 2 units from the original rb,
   * it is 1 unit from the new expansion edge which
   * would prevent expansion. So we want to break the
   * edge on it now to avoid the trap.
   */

  bloat = AutoRouteParameters.bloat + 2;
  /* for corner expansion, we need to have a fake blocker
   * to prevent expansion back where we came from since
   * we still need to break portions of all 4 edges
   */
  if (e->expand_dir == NE || e->expand_dir == SE ||
      e->expand_dir == SW || e->expand_dir == NW)
    {
      BoxType *fb = (BoxType *) &fake.sbox;
      memset (&fake, 0, sizeof (fake));
      *fb = e->rb->sbox;
      fake.flags.fixed = 1;     /* this stops expansion there */
      fake.type = LINE;
      fake.style = AutoRouteParameters.style;
#ifndef NDEBUG
      /* the routbox_is_good checker wants a lot more! */
      fake.flags.inited = 1;
      fb = (BoxType *) &fake.box;
      *fb = e->rb->sbox;
      fake.same_net.next = fake.same_net.prev = &fake;
      fake.same_subnet.next = fake.same_subnet.prev = &fake;
      fake.original_subnet.next = fake.original_subnet.prev = &fake;
      fake.different_net.next = fake.different_net.prev = &fake;
#endif
    }
  /* gather all of the blockers in heaps so they can be accessed
   * in clockwise order, which allows finding corners that can
   * be expanded.
   */
  for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
    {
      /* don't break the edge we came from */
      if (e->expand_dir != ((dir + 2) % 4))
        {
          heap[dir] = heap_create ();
          bi.box = bloat_box (&rb->sbox, bloat);
          bi.heap = heap[dir];
          bi.dir = dir;
          /* convert to edge */
          switch (dir)
            {
            case NORTH:
              bi.box.Y2 = bi.box.Y1 + bloat + 1;
              /* for corner expansion, block the start edges and
               * limit the blocker search to only the new edge segment
               */
              if (e->expand_dir == SE || e->expand_dir == SW)
                blocker_to_heap (heap[dir], &fake, &bi.box, dir);
              if (e->expand_dir == SE)
                bi.box.X1 = e->rb->sbox.X2;
              if (e->expand_dir == SW)
                bi.box.X2 = e->rb->sbox.X1;
              rb->n = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
              break;
            case EAST:
              bi.box.X1 = bi.box.X2 - bloat - 1;
              /* corner, same as above */
              if (e->expand_dir == SW || e->expand_dir == NW)
                blocker_to_heap (heap[dir], &fake, &bi.box, dir);
              if (e->expand_dir == SW)
                bi.box.Y1 = e->rb->sbox.Y2;
              if (e->expand_dir == NW)
                bi.box.Y2 = e->rb->sbox.Y1;
              rb->e = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
              break;
            case SOUTH:
              bi.box.Y1 = bi.box.Y2 - bloat - 1;
              /* corner, same as above */
              if (e->expand_dir == NE || e->expand_dir == NW)
                blocker_to_heap (heap[dir], &fake, &bi.box, dir);
              if (e->expand_dir == NE)
                bi.box.X1 = e->rb->sbox.X2;
              if (e->expand_dir == NW)
                bi.box.X2 = e->rb->sbox.X1;
              rb->s = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
              break;
            case WEST:
              bi.box.X2 = bi.box.X1 + bloat + 1;
              /* corner, same as above */
              if (e->expand_dir == NE || e->expand_dir == SE)
                blocker_to_heap (heap[dir], &fake, &bi.box, dir);
              if (e->expand_dir == SE)
                bi.box.Y1 = e->rb->sbox.Y2;
              if (e->expand_dir == NE)
                bi.box.Y2 = e->rb->sbox.Y1;
              rb->w = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
              break;
            default:
              assert (0);
            }
        }
      else
        heap[dir] = NULL;
    }
#if 1
  rb->cost +=
    (rb->n + rb->e + rb->s +
     rb->w) * AutoRouteParameters.CongestionPenalty / box_area (rb->sbox);
#endif
/* now handle the blockers:
 * Go around the expansion area clockwise (North->East->South->West)
 * pulling blockers from the heap (which makes them come out in the right
 * order). Break the edges on the blocker and make the segments and corners
 * moveable as possible.
 */
  first = last = -1;
  for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
    {
      if (heap[dir] && !heap_is_empty (heap[dir]))
        {
          /* pull the very first one out of the heap outside of the
           * heap loop because it is special; it can be part of a corner
           */
          routebox_t *blk = (routebox_t *) heap_remove_smallest (heap[dir]);
          BoxType b = rb->sbox;
          struct broken_boxes broke = break_box_edge (&b, dir, blk);
          if (broke.is_valid_left)
            {
              /* if last > 0, then the previous edge had a segment
               * joining this one, so it forms a valid corner expansion
               */
              if (last > 0)
                {
                  /* make a corner expansion */
                  BoxType db = b;
                  switch (dir)
                    {
                    case EAST:
                      /* possible NE expansion */
                      db.X1 = last;
                      db.Y2 = MIN (db.Y2, broke.left.Y2);
                      break;
                    case SOUTH:
                      /* possible SE expansion */
                      db.Y1 = last;
                      db.X1 = MAX (db.X1, broke.left.X1);
                      break;
                    case WEST:
                      /* possible SW expansion */
                      db.X2 = last;
                      db.Y1 = MAX (db.Y1, broke.left.Y1);
                      break;
                    default:
                      assert (0);
                      break;
                    }
                  moveable_edge (edges, &db, (direction_t)(dir + 3), rb, NULL, e, targets,
                                 s, NULL, NULL);
                }
              else if (dir == NORTH)    /* north is start, so nothing "before" it */
                {
                  /* save for a possible corner once we've
                   * finished circling the box
                   */
                  first = MAX (b.X1, broke.left.X2);
                }
              else
                {
                  /* this is just a boring straight expansion
                   * since the orthogonal segment was blocked
                   */
                  moveable_edge (edges, &broke.left, dir, rb, NULL, e,
                                 targets, s, NULL, NULL);
                }
            }                   /* broke.is_valid_left */
          else if (last > 0)
            {
              /* if the last one didn't become a corner,
               * we still want to expand it straight out
               * in the direction of the previous edge,
               * which it belongs to. 
               */
              BoxType db = previous_edge (last, dir, &rb->sbox);
              moveable_edge (edges, &db, (direction_t)(dir - 1), rb, NULL, e, targets, s,
                             NULL, NULL);
            }
          if (broke.is_valid_center && !blk->flags.source)
            moveable_edge (edges, &broke.center, dir, rb, blk, e, targets, s,
                           tree, area_vec);
          /* this is the heap extraction loop. We break out
           * if there's nothing left in the heap, but if we * are blocked all the way to the far edge, we can
           * just leave stuff in the heap when it is destroyed
           */
          while (broke.is_valid_right)
            {
              /* move the box edge to the next potential free point */
              switch (dir)
                {
                case NORTH:
                  last = b.X1 = MAX (broke.right.X1, b.X1);
                  break;
                case EAST:
                  last = b.Y1 = MAX (broke.right.Y1, b.Y1);
                  break;
                case SOUTH:
                  last = b.X2 = MIN (broke.right.X2, b.X2);
                  break;
                case WEST:
                  last = b.Y2 = MIN (broke.right.Y2, b.Y2);
                  break;
                default:
                  assert (0);
                }
              if (heap_is_empty (heap[dir]))
                break;
              blk = (routebox_t *)heap_remove_smallest (heap[dir]);
              broke = break_box_edge (&b, dir, blk);
              if (broke.is_valid_left)
                moveable_edge (edges, &broke.left, dir, rb, NULL, e, targets,
                               s, NULL, NULL);
              if (broke.is_valid_center && !blk->flags.source)
                moveable_edge (edges, &broke.center, dir, rb, blk, e, targets,
                               s, tree, area_vec);
            }
          if (!broke.is_valid_right)
            last = -1;
        }
      else                      /* if (heap[dir]) */
        {
          /* nothing touched this edge! Expand the whole edge unless
           * (1) it hit the board edge or (2) was the source of our expansion
           *
           * for this case (of hitting nothing) we give up trying for corner
           * expansions because it is likely that they're not possible anyway 
           */
          if ((e->expand_dir == ALL ? e->rb->came_from : e->expand_dir) !=
              ((dir + 2) % 4))
            {
              /* ok, we are not going back on ourselves, and the whole edge seems free */
              moveable_edge (edges, &rb->sbox, dir, rb, NULL, e, targets, s,
                             NULL, NULL);
            }

          if (last > 0)
            {
              /* expand the leftover from the prior direction */
              BoxType db = previous_edge (last, dir, &rb->sbox);
              moveable_edge (edges, &db, (direction_t)(dir - 1), rb, NULL, e, targets, s,
                             NULL, NULL);
            }
          last = -1;
        }
    }                           /* for loop */
  /* finally, check for the NW corner now that we've come full circle */
  if (first > 0 && last > 0)
    {
      BoxType db = rb->sbox;
      db.X2 = first;
      db.Y2 = last;
      moveable_edge (edges, &db, NW, rb, NULL, e, targets, s, NULL, NULL);
    }
  else
    {
      if (first > 0)
        {
          BoxType db = rb->sbox;
          db.X2 = first;
          moveable_edge (edges, &db, NORTH, rb, NULL, e, targets, s, NULL,
                         NULL);
        }
      else if (last > 0)
        {
          BoxType db = rb->sbox;
          db.Y2 = last;
          moveable_edge (edges, &db, WEST, rb, NULL, e, targets, s, NULL,
                         NULL);
        }
    }
  /* done with all expansion edges of this box */
  for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
    {
      if (heap[dir])
        heap_destroy (&heap[dir]);
    }
  return edges;
}

static routebox_t *
rb_source (routebox_t * rb)
{
  while (rb && !rb->flags.source)
    {
      assert (rb->type == EXPANSION_AREA);
      rb = rb->parent.expansion_area;
    }
  assert (rb);
  return rb;
}

/* ------------ */

struct foib_info
{
  const BoxType *box;
  routebox_t *intersect;
  jmp_buf env;
};

static int
foib_rect_in_reg (const BoxType * box, void *cl)
{
  struct foib_info *foib = (struct foib_info *) cl;
  BoxType rbox;
  routebox_t *rb = (routebox_t *) box;
  if (rb->flags.touched)
    return 0;
//  if (rb->type == EXPANSION_AREA && !rb->flags.is_via)
  //   return 0;
  rbox = bloat_routebox (rb);
  if (!box_intersect (&rbox, foib->box))
    return 0;
  /* this is an intersector! */
  foib->intersect = (routebox_t *) box;
  longjmp (foib->env, 1);       /* skip to the end! */
  return 1;
}
static routebox_t *
FindOneInBox (rtree_t * rtree, routebox_t * rb)
{
  struct foib_info foib;
  BoxType r;

  r = rb->sbox;
  foib.box = &r;
  foib.intersect = NULL;

  if (setjmp (foib.env) == 0)
    r_search (rtree, &r, NULL, foib_rect_in_reg, &foib);
  return foib.intersect;
}

struct therm_info
{
  routebox_t *plane;
  BoxType query;
  jmp_buf env;
};
static int
ftherm_rect_in_reg (const BoxType * box, void *cl)
{
  routebox_t *rbox = (routebox_t *) box;
  struct therm_info *ti = (struct therm_info *) cl;
  BoxType sq, sb;

  if (rbox->type != PIN && rbox->type != VIA && rbox->type != VIA_SHADOW)
    return 0;
  if (rbox->group != ti->plane->group)
    return 0;

  sb = shrink_routebox (rbox);
  switch (rbox->type)
    {
    case PIN:
      sq = shrink_box (&ti->query, rbox->parent.pin->Thickness);
      if (!box_intersect (&sb, &sq))
        return 0;
      sb.X1 = rbox->parent.pin->X;
      sb.Y1 = rbox->parent.pin->Y;
      break;
    case VIA:
      if (rbox->flags.fixed)
        {
          sq = shrink_box (&ti->query, rbox->parent.via->Thickness);
          sb.X1 = rbox->parent.pin->X;
          sb.Y1 = rbox->parent.pin->Y;
        }
      else
        {
          sq = shrink_box (&ti->query, rbox->style->Diameter);
          sb.X1 = CENTER_X (sb);
          sb.Y1 = CENTER_Y (sb);
        }
      if (!box_intersect (&sb, &sq))
        return 0;
      break;
    case VIA_SHADOW:
      sq = shrink_box (&ti->query, rbox->style->Diameter);
      if (!box_intersect (&sb, &sq))
        return 0;
      sb.X1 = CENTER_X (sb);
      sb.Y1 = CENTER_Y (sb);
      break;
    default:
      assert (0);
    }
  ti->plane = rbox;
  longjmp (ti->env, 1);
  return 1;
}

/*!
 * \brief Check for a pin or via target that a polygon can just use a
 * thermal to connect to.
 */
routebox_t *
FindThermable (rtree_t * rtree, routebox_t * rb)
{
  struct therm_info info;

  info.plane = rb;
  info.query = shrink_routebox (rb);

  if (setjmp (info.env) == 0)
    {
      r_search (rtree, &info.query, NULL, ftherm_rect_in_reg, &info);
      return NULL;
    }
  return info.plane;
}

/*!
 * \brief Route-tracing code: once we've got a path of expansion boxes,
 * trace a line through them to actually create the connection.
 */
static void
RD_DrawThermal (routedata_t * rd, Coord X, Coord Y,
                Cardinal group, Cardinal layer, routebox_t * subnet,
                bool is_bad)
{
  routebox_t *rb;
  rb = (routebox_t *) malloc (sizeof (*rb));
  memset ((void *) rb, 0, sizeof (*rb));
  init_const_box (rb, X, Y, X + 1, Y + 1, 0);
  rb->group = group;
  rb->layer = layer;
  rb->flags.fixed = 0;
  rb->flags.is_bad = is_bad;
  rb->flags.is_odd = AutoRouteParameters.is_odd;
  rb->flags.circular = 0;
  rb->style = AutoRouteParameters.style;
  rb->type = THERMAL;
  InitLists (rb);
  MergeNets (rb, subnet, NET);
  MergeNets (rb, subnet, SUBNET);
  /* add it to the r-tree, this may be the whole route! */
  r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
  rb->flags.homeless = 0;
}

static void
RD_DrawVia (routedata_t * rd, Coord X, Coord Y,
            Coord radius, routebox_t * subnet, bool is_bad)
{
  routebox_t *rb, *first_via = NULL;
  int i;
  int ka = AutoRouteParameters.style->Keepaway;
  PinType *live_via = NULL;

  if (TEST_FLAG (LIVEROUTEFLAG, PCB))
    {
       live_via = CreateNewVia (PCB->Data, X, Y, radius * 2,
                                2 * AutoRouteParameters.style->Keepaway, 0,
                                AutoRouteParameters.style->Hole, NULL,
                                MakeFlags (0));
       if (live_via != NULL)
         DrawVia (live_via);
    }

  /* a via cuts through every layer group */
  for (i = 0; i < max_group; i++)
    {
      if (!is_layer_group_active[i])
        continue;
      rb = (routebox_t *) malloc (sizeof (*rb));
      memset ((void *) rb, 0, sizeof (*rb));
      init_const_box (rb,
                      /*X1 */ X - radius, /*Y1 */ Y - radius,
                      /*X2 */ X + radius + 1, /*Y2 */ Y + radius + 1, ka);
      rb->group = i;
      rb->flags.fixed = 0;      /* indicates that not on PCB yet */
      rb->flags.is_odd = AutoRouteParameters.is_odd;
      rb->flags.is_bad = is_bad;
      rb->came_from = ALL;
      rb->flags.circular = true;
      rb->style = AutoRouteParameters.style;
      rb->pass = AutoRouteParameters.pass;
      if (first_via == NULL)
        {
          rb->type = VIA;
          rb->parent.via = NULL;        /* indicates that not on PCB yet */
          first_via = rb;
          /* only add the first via to mtspace, not the shadows too */
          mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
                       rb->style->Keepaway);
        }
      else
        {
          rb->type = VIA_SHADOW;
          rb->parent.via_shadow = first_via;
        }
      InitLists (rb);
      /* add these to proper subnet. */
      MergeNets (rb, subnet, NET);
      MergeNets (rb, subnet, SUBNET);
      assert (__routebox_is_good (rb));
      /* and add it to the r-tree! */
      r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
      rb->flags.homeless = 0;   /* not homeless anymore */
      rb->livedraw_obj.via = live_via;
    }
}
static void
RD_DrawLine (routedata_t * rd,
             Coord X1, Coord Y1, Coord X2,
             Coord Y2, Coord halfthick, Cardinal group,
             routebox_t * subnet, bool is_bad, bool is_45)
{
  /* we hold the line in a queue to concatenate segments that
   * ajoin one another. That reduces the number of things in
   * the trees and allows conflict boxes to be larger, both of
   * which are really useful.
   */
  static Coord qX1 = -1, qY1, qX2, qY2;
  static Coord qhthick;
  static Cardinal qgroup;
  static bool qis_45, qis_bad;
  static routebox_t *qsn;

  routebox_t *rb;
  Coord ka = AutoRouteParameters.style->Keepaway;

  /* don't draw zero-length segments. */
  if (X1 == X2 && Y1 == Y2)
    return;
  if (qX1 == -1)                /* first ever */
    {
      qX1 = X1;
      qY1 = Y1;
      qX2 = X2;
      qY2 = Y2;
      qhthick = halfthick;
      qgroup = group;
      qis_45 = is_45;
      qis_bad = is_bad;
      qsn = subnet;
      return;
    }
  /* Check if the lines concatenat. We only check the
   * normal expected nextpoint=lastpoint condition 
   */
  if (X1 == qX2 && Y1 == qY2 && qhthick == halfthick && qgroup == group)
    {
      if (qX1 == qX2 && X1 == X2)       /* everybody on the same X here */
        {
          qY2 = Y2;
          return;
        }
      if (qY1 == qY2 && Y1 == Y2)       /* same Y all around */
        {
          qX2 = X2;
          return;
        }
    }
  /* dump the queue, no match here */
  if (qX1 == -1)
    return;                     /* but not this! */
  rb = (routebox_t *) malloc (sizeof (*rb));
  memset ((void *) rb, 0, sizeof (*rb));
  assert (is_45 ? (ABS (qX2 - qX1) == ABS (qY2 - qY1))  /* line must be 45-degrees */
          : (qX1 == qX2 || qY1 == qY2) /* line must be ortho */ );
  init_const_box (rb,
                  /*X1 */ MIN (qX1, qX2) - qhthick,
                  /*Y1 */ MIN (qY1, qY2) - qhthick,
                  /*X2 */ MAX (qX1, qX2) + qhthick + 1,
                  /*Y2 */ MAX (qY1, qY2) + qhthick + 1, ka);
  rb->group = qgroup;
  rb->type = LINE;
  rb->parent.line = NULL;       /* indicates that not on PCB yet */
  rb->flags.fixed = 0;          /* indicates that not on PCB yet */
  rb->flags.is_odd = AutoRouteParameters.is_odd;
  rb->flags.is_bad = qis_bad;
  rb->came_from = ALL;
  rb->flags.homeless = 0;       /* we're putting this in the tree */
  rb->flags.nonstraight = qis_45;
  rb->flags.bl_to_ur = ((qX2 >= qX1 && qY2 <= qY1)
                        || (qX2 <= qX1 && qY2 >= qY1));
  rb->style = AutoRouteParameters.style;
  rb->pass = AutoRouteParameters.pass;
  InitLists (rb);
  /* add these to proper subnet. */
  MergeNets (rb, qsn, NET);
  MergeNets (rb, qsn, SUBNET);
  assert (__routebox_is_good (rb));
  /* and add it to the r-tree! */
  r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);

  if (TEST_FLAG (LIVEROUTEFLAG, PCB))
    {
      LayerType *layer = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
      LineType *line = CreateNewLineOnLayer (layer, qX1, qY1, qX2, qY2,
                                             2 * qhthick, 0, MakeFlags (0));
      rb->livedraw_obj.line = line;
      if (line != NULL)
        DrawLine (layer, line);
    }

  /* and to the via space structures */
  if (AutoRouteParameters.use_vias)
    mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
                 rb->style->Keepaway);
  usedGroup[rb->group] = true;
  /* and queue this one */
  qX1 = X1;
  qY1 = Y1;
  qX2 = X2;
  qY2 = Y2;
  qhthick = halfthick;
  qgroup = group;
  qis_45 = is_45;
  qis_bad = is_bad;
  qsn = subnet;
}

static bool
RD_DrawManhattanLine (routedata_t * rd,
                      const BoxType * box1, const BoxType * box2,
                      CheapPointType start, CheapPointType end,
                      Coord halfthick, Cardinal group,
                      routebox_t * subnet, bool is_bad, bool last_was_x)
{
  CheapPointType knee = start;
  if (end.X == start.X)
    {
      RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
                   subnet, is_bad, false);
      return false;
    }
  else if (end.Y == start.Y)
    {
      RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
                   subnet, is_bad, false);
      return true;
    }
  /* find where knee belongs */
  if (point_in_box (box1, end.X, start.Y)
      || point_in_box (box2, end.X, start.Y))
    {
      knee.X = end.X;
      knee.Y = start.Y;
    }
  else
    {
      knee.X = start.X;
      knee.Y = end.Y;
    }
  if ((knee.X == end.X && !last_was_x) &&
      (point_in_box (box1, start.X, end.Y)
       || point_in_box (box2, start.X, end.Y)))
    {
      knee.X = start.X;
      knee.Y = end.Y;
    }
  assert (AutoRouteParameters.is_smoothing
          || point_in_closed_box (box1, knee.X, knee.Y)
          || point_in_closed_box (box2, knee.X, knee.Y));

  if (1 || !AutoRouteParameters.is_smoothing)
    {
      /* draw standard manhattan paths */
      RD_DrawLine (rd, start.X, start.Y, knee.X, knee.Y, halfthick, group,
                   subnet, is_bad, false);
      RD_DrawLine (rd, knee.X, knee.Y, end.X, end.Y, halfthick, group,
                   subnet, is_bad, false);
    }
  else
    {
      /* draw 45-degree path across knee */
      Coord len45 = MIN (ABS (start.X - end.X), ABS (start.Y - end.Y));
      CheapPointType kneestart = knee, kneeend = knee;
      if (kneestart.X == start.X)
        kneestart.Y += (kneestart.Y > start.Y) ? -len45 : len45;
      else
        kneestart.X += (kneestart.X > start.X) ? -len45 : len45;
      if (kneeend.X == end.X)
        kneeend.Y += (kneeend.Y > end.Y) ? -len45 : len45;
      else
        kneeend.X += (kneeend.X > end.X) ? -len45 : len45;
      RD_DrawLine (rd, start.X, start.Y, kneestart.X, kneestart.Y, halfthick,
                   group, subnet, is_bad, false);
      RD_DrawLine (rd, kneestart.X, kneestart.Y, kneeend.X, kneeend.Y,
                   halfthick, group, subnet, is_bad, true);
      RD_DrawLine (rd, kneeend.X, kneeend.Y, end.X, end.Y, halfthick, group,
                   subnet, is_bad, false);
    }
  return (knee.X != end.X);
}

/* for smoothing, don't pack traces to min clearance gratuitously */
#if 0
static void
add_clearance (CheapPointType * nextpoint, const BoxType * b)
{
  if (nextpoint->X == b->X1)
    {
      if (nextpoint->X +
          AutoRouteParameters.style->Keepaway < (b->X1 + b->X2) / 2)
        nextpoint->X += AutoRouteParameters.style->Keepaway;
      else
        nextpoint->X = (b->X1 + b->X2) / 2;
    }
  else if (nextpoint->X == b->X2)
    {
      if (nextpoint->X -
          AutoRouteParameters.style->Keepaway > (b->X1 + b->X2) / 2)
        nextpoint->X -= AutoRouteParameters.style->Keepaway;
      else
        nextpoint->X = (b->X1 + b->X2) / 2;
    }
  else if (nextpoint->Y == b->Y1)
    {
      if (nextpoint->Y +
          AutoRouteParameters.style->Keepaway < (b->Y1 + b->Y2) / 2)
        nextpoint->Y += AutoRouteParameters.style->Keepaway;
      else
        nextpoint->Y = (b->Y1 + b->Y2) / 2;
    }
  else if (nextpoint->Y == b->Y2)
    {
      if (nextpoint->Y -
          AutoRouteParameters.style->Keepaway > (b->Y1 + b->Y2) / 2)
        nextpoint->Y -= AutoRouteParameters.style->Keepaway;
      else
        nextpoint->Y = (b->Y1 + b->Y2) / 2;
    }
}
#endif

/*!
 * \brief This back-traces the expansion boxes along the best path
 * it draws the lines that will make the actual path.
 *
 * During refinement passes, it should try to maximize the area
 * for other tracks so routing completion is easier.
 *
 * During smoothing passes, it should try to make a better path,
 * possibly using diagonals, etc. The path boxes are larger on
 * average now so there is more possiblity to decide on a nice
 * path. Any combination of lines and arcs is possible, so long
 * as they don't poke more than half thick outside the path box.
 */

static void
TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
           routebox_t * subnet, bool is_bad)
{
  bool last_x = false;
  Coord halfwidth = HALF_THICK (AutoRouteParameters.style->Thick);
  Coord radius = HALF_THICK (AutoRouteParameters.style->Diameter);
  CheapPointType lastpoint, nextpoint;
  routebox_t *lastpath;
  BoxType b;

  assert (subnet->style == AutoRouteParameters.style);
  /*XXX: because we round up odd thicknesses, there's the possibility that
   * a connecting line end-point might be 0.005 mil off the "real" edge.
   * don't worry about this because line *thicknesses* are always >= 0.01 mil. */

  /* if we start with a thermal the target was a plane
   * or the target was a pin and the source a plane
   * in which case this thermal is the whole path
   */
  if (path->flags.is_thermal)
    {
      /* the target was a plane, so we need to find a good spot for the via
       * now. It's logical to place it close to the source box which
       * is where we're utlimately headed on this path. However, it
       * must reside in the plane as well as the via area too. 
       */
      nextpoint.X = CENTER_X (path->sbox);
      nextpoint.Y = CENTER_Y (path->sbox);
      if (path->parent.expansion_area->flags.is_via)
        {
          TargetPoint (&nextpoint, rb_source (path));
          /* nextpoint is the middle of the source terminal now */
          b = clip_box (&path->sbox, &path->parent.expansion_area->sbox);
          nextpoint = closest_point_in_box (&nextpoint, &b);
          /* now it's in the via and plane near the source */
        }
      else                      /* no via coming, target must have been a pin */
        {
          assert (target->type == PIN);
          TargetPoint (&nextpoint, target);
        }
      assert (point_in_box (&path->sbox, nextpoint.X, nextpoint.Y));
      RD_DrawThermal (rd, nextpoint.X, nextpoint.Y, path->group,
                      path->layer, subnet, is_bad);
    }
  else
    {
      /* start from best place of target box */
      lastpoint.X = CENTER_X (target->sbox);
      lastpoint.Y = CENTER_Y (target->sbox);
      TargetPoint (&lastpoint, target);
      if (AutoRouteParameters.last_smooth
          && box_in_box (&path->sbox, &target->sbox))
        path = path->parent.expansion_area;
      b = path->sbox;
      if (path->flags.circular)
        b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
      nextpoint = closest_point_in_box (&lastpoint, &b);
      if (AutoRouteParameters.last_smooth)
        RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
                     halfwidth, path->group, subnet, is_bad, TRUE);
      else
        last_x = RD_DrawManhattanLine (rd, &target->sbox, &path->sbox,
                                       lastpoint, nextpoint, halfwidth,
                                       path->group, subnet, is_bad, last_x);
    }
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
  showroutebox (path);
#if defined(ROUTE_VERBOSE)
  pcb_printf ("TRACEPOINT start %#mD\n", nextpoint.X, nextpoint.Y);
#endif
#endif

  do
    {
      lastpoint = nextpoint;
      lastpath = path;
      assert (path->type == EXPANSION_AREA);
      path = path->parent.expansion_area;
      b = path->sbox;
      if (path->flags.circular)
        b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
      assert (b.X1 != b.X2 && b.Y1 != b.Y2);    /* need someplace to put line! */
      /* find point on path perimeter closest to last point */
      /* if source terminal, try to hit a good place */
      nextpoint = closest_point_in_box (&lastpoint, &b);
#if 0
      /* leave more clearance if this is a smoothing pass */
      if (AutoRouteParameters.is_smoothing &&
          (nextpoint.X != lastpoint.X || nextpoint.Y != lastpoint.Y))
        add_clearance (&nextpoint, &b);
#endif
      if (path->flags.source && path->type != PLANE)
        TargetPoint (&nextpoint, path);
      assert (point_in_box (&lastpath->box, lastpoint.X, lastpoint.Y));
      assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
#if defined(ROUTE_DEBUG_VERBOSE)
      printf ("TRACEPATH: ");
      DumpRouteBox (path);
      pcb_printf ("TRACEPATH: point %#mD to point %#mD layer %d\n",
              lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
              path->group);
#endif

      /* draw orthogonal lines from lastpoint to nextpoint */
      /* knee is placed in lastpath box */
      /* should never cause line to leave union of lastpath/path boxes */
      if (AutoRouteParameters.last_smooth)
        RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
                     halfwidth, path->group, subnet, is_bad, TRUE);
      else
        last_x = RD_DrawManhattanLine (rd, &lastpath->sbox, &path->sbox,
                                       lastpoint, nextpoint, halfwidth,
                                       path->group, subnet, is_bad, last_x);
      if (path->flags.is_via)
        {                       /* if via, then add via */
#ifdef ROUTE_VERBOSE
          printf (" (vias)");
#endif
          assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
          RD_DrawVia (rd, nextpoint.X, nextpoint.Y, radius, subnet, is_bad);
        }

      assert (lastpath->flags.is_via || path->group == lastpath->group);

#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
      showroutebox (path);
#endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
      /* if this is connected to a plane, draw the thermal */
      if (path->flags.is_thermal || path->type == PLANE)
        RD_DrawThermal (rd, lastpoint.X, lastpoint.Y, path->group,
                        path->layer, subnet, is_bad);
      /* when one hop from the source, make an extra path in *this* box */
      if (path->type == EXPANSION_AREA
          && path->parent.expansion_area->flags.source
          && path->parent.expansion_area->type != PLANE)
        {
          /* find special point on source (if it exists) */
          if (TargetPoint (&lastpoint, path->parent.expansion_area))
            {
              lastpoint = closest_point_in_routebox (&lastpoint, path);
              b = shrink_routebox (path);
#if 0
              if (AutoRouteParameters.is_smoothing)
                add_clearance (&lastpoint, &b);
#else
              if (AutoRouteParameters.last_smooth)
                RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X,
                             nextpoint.Y, halfwidth, path->group, subnet,
                             is_bad, TRUE);
              else
#endif
                last_x = RD_DrawManhattanLine (rd, &b, &b,
                                               nextpoint, lastpoint,
                                               halfwidth, path->group, subnet,
                                               is_bad, last_x);
#if defined(ROUTE_DEBUG_VERBOSE)
              printf ("TRACEPATH: ");
              DumpRouteBox (path);
              pcb_printf
                ("TRACEPATH: (to source) point %#mD to point %#mD layer %d\n",
                 nextpoint.X, nextpoint.Y, lastpoint.X, lastpoint.Y,
                 path->group);
#endif

              nextpoint = lastpoint;
            }
        }
    }
  while (!path->flags.source);
  /* flush the line queue */
  RD_DrawLine (rd, -1, 0, 0, 0, 0, 0, NULL, false, false);

  if (TEST_FLAG (LIVEROUTEFLAG, PCB))
    Draw ();

#ifdef ROUTE_DEBUG
  if (ddraw != NULL)
    gui->flush_debug_draw ();
#endif
}

/*!
 * \brief Create a fake "edge" used to defer via site searching.
 */
static void
CreateSearchEdge (struct routeone_state *s, vetting_t * work, edge_t * parent,
                  routebox_t * rb, conflict_t conflict, rtree_t * targets,
                  bool in_plane)
{
  routebox_t *target;
  BoxType b;
  cost_t cost;
  assert (__routebox_is_good (rb));
  /* find the cheapest target */
#if 0
  target =
    mincost_target_to_point (&parent->cost_point, max_group + 1, targets,
                             parent->mincost_target);
#else
  target = parent->mincost_target;
#endif
  b = shrink_routebox (target);
  cost =
    parent->cost_to_point + AutoRouteParameters.ViaCost +
    cost_to_layerless_box (&rb->cost_point, 0, &b);
  if (cost < s->best_cost)
    {
      edge_t *ne;
      ne = (edge_t *)malloc (sizeof (*ne));
      memset ((void *) ne, 0, sizeof (*ne));
      assert (ne);
      ne->flags.via_search = 1;
      ne->flags.in_plane = in_plane;
      ne->rb = rb;
      if (rb->flags.homeless)
        RB_up_count (rb);
      ne->work = work;
      ne->mincost_target = target;
      ne->flags.via_conflict_level = conflict;
      ne->cost_to_point = parent->cost_to_point;
      ne->cost_point = parent->cost_point;
      ne->cost = cost;
      heap_insert (s->workheap, ne->cost, ne);
    }
  else
    {
      mtsFreeWork (&work);
    }
}

static void
add_or_destroy_edge (struct routeone_state *s, edge_t * e)
{
  e->cost = edge_cost (e, s->best_cost);
  assert (__edge_is_good (e));
  assert (is_layer_group_active[e->rb->group]);
  if (e->cost < s->best_cost)
    heap_insert (s->workheap, e->cost, e);
  else
    DestroyEdge (&e);
}

static void
best_path_candidate (struct routeone_state *s,
                     edge_t * e, routebox_t * best_target)
{
  e->cost = edge_cost (e, EXPENSIVE);
  if (s->best_path == NULL || e->cost < s->best_cost)
    {
#if defined(ROUTE_DEBUG) && defined (ROUTE_VERBOSE)
      printf ("New best path seen! cost = %f\n", e->cost);
#endif
      /* new best path! */
      if (s->best_path && s->best_path->flags.homeless)
        RB_down_count (s->best_path);
      s->best_path = e->rb;
      s->best_target = best_target;
      s->best_cost = e->cost;
      assert (s->best_cost >= 0);
      /* don't free this when we destroy edge! */
      if (s->best_path->flags.homeless)
        RB_up_count (s->best_path);
    }
}


/*!
 * \brief Vectors for via site candidates (see mtspace.h).
 */
struct routeone_via_site_state
{
  vector_t *free_space_vec;
  vector_t *lo_conflict_space_vec;
  vector_t *hi_conflict_space_vec;
};

void
add_via_sites (struct routeone_state *s,
               struct routeone_via_site_state *vss,
               mtspace_t * mtspace, routebox_t * within,
               conflict_t within_conflict_level, edge_t * parent_edge,
               rtree_t * targets, Coord shrink, bool in_plane)
{
  Coord radius, keepaway;
  vetting_t *work;
  BoxType region = shrink_routebox (within);
  shrink_box (&region, shrink);

  radius = HALF_THICK (AutoRouteParameters.style->Diameter);
  keepaway = AutoRouteParameters.style->Keepaway;
  assert (AutoRouteParameters.use_vias);
  /* XXX: need to clip 'within' to shrunk_pcb_bounds, because when
     XXX: routing with conflicts may poke over edge. */

  /* ask for a via box near our cost_point first */
  work = mtspace_query_rect (mtspace, &region, radius, keepaway,
                             NULL, vss->free_space_vec,
                             vss->lo_conflict_space_vec,
                             vss->hi_conflict_space_vec,
                             AutoRouteParameters.is_odd,
                             AutoRouteParameters.with_conflicts,
                             &parent_edge->cost_point);
  if (!work)
    return;
  CreateSearchEdge (s, work, parent_edge, within, within_conflict_level,
                    targets, in_plane);
}

void
do_via_search (edge_t * search, struct routeone_state *s,
               struct routeone_via_site_state *vss, mtspace_t * mtspace,
               rtree_t * targets)
{
  int i, j, count = 0;
  Coord radius, keepaway;
  vetting_t *work;
  routebox_t *within;
  conflict_t within_conflict_level;

  radius = HALF_THICK (AutoRouteParameters.style->Diameter);
  keepaway = AutoRouteParameters.style->Keepaway;
  work = mtspace_query_rect (mtspace, NULL, 0, 0,
                             search->work, vss->free_space_vec,
                             vss->lo_conflict_space_vec,
                             vss->hi_conflict_space_vec,
                             AutoRouteParameters.is_odd,
                             AutoRouteParameters.with_conflicts, NULL);
  within = search->rb;
  within_conflict_level = search->flags.via_conflict_level;
  for (i = 0; i < 3; i++)
    {
      vector_t *v =
        (i == NO_CONFLICT ? vss->free_space_vec :
         i == LO_CONFLICT ? vss->lo_conflict_space_vec :
         i == HI_CONFLICT ? vss->hi_conflict_space_vec : NULL);
      assert (v);
      while (!vector_is_empty (v))
        {
          BoxType cliparea;
          BoxType *area = (BoxType *)vector_remove_last (v);
          if (!(i == NO_CONFLICT || AutoRouteParameters.with_conflicts))
            {
              free (area);
              continue;
            }
          /* answers are bloated by radius + keepaway */
          cliparea = shrink_box (area, radius + keepaway);
          close_box (&cliparea);
          free (area);
          assert (box_is_good (&cliparea));
          count++;
          for (j = 0; j < max_group; j++)
            {
              edge_t *ne;
              if (j == within->group || !is_layer_group_active[j])
                continue;
              ne = CreateViaEdge (&cliparea, j, within, search,
                                  within_conflict_level, (conflict_t)i, targets);
              add_or_destroy_edge (s, ne);
            }
        }
    }
  /* prevent freeing of work when this edge is destroyed */
  search->flags.via_search = 0;
  if (!work)
    return;
  CreateSearchEdge (s, work, search, within, within_conflict_level, targets,
                    search->flags.in_plane);
  assert (vector_is_empty (vss->free_space_vec));
  assert (vector_is_empty (vss->lo_conflict_space_vec));
  assert (vector_is_empty (vss->hi_conflict_space_vec));
}

/* vector of expansion areas to be eventually removed from r-tree
 * this is a global for troubleshooting
 */
vector_t *area_vec;

/* some routines for use in gdb while debugging */
#if defined(ROUTE_DEBUG)
static void
list_conflicts (routebox_t * rb)
{
  int i, n;
  if (!rb->conflicts_with)
    return;
  n = vector_size (rb->conflicts_with);
  for (i = 0; i < n; i++)
    printf ("%p, ", vector_element (rb->conflicts_with, i));
}

static void
show_area_vec (int lay)
{
  int n, save;

  if (!area_vec)
    return;
  save = showboxen;
  showboxen = lay;
  for (n = 0; n < vector_size (area_vec); n++)
    {
      routebox_t *rb = (routebox_t *) vector_element (area_vec, n);
      showroutebox (rb);
    }
  showboxen = save;
}

static bool
net_id (routebox_t * rb, long int id)
{
  routebox_t *p;
  LIST_LOOP (rb, same_net, p);
  if (p->flags.source && p->parent.pad->ID == id)
    return true;
  END_LOOP;
  return false;
}

static void
trace_parents (routebox_t * rb)
{
  while (rb && rb->type == EXPANSION_AREA)
    {
      printf (" %p ->", rb);
      rb = rb->parent.expansion_area;
    }
  if (rb)
    printf (" %p is source\n", rb);
  else
    printf ("NULL!\n");
}

static void
show_one (routebox_t * rb)
{
  int save = showboxen;
  showboxen = -1;
  showroutebox (rb);
  showboxen = save;
}

static void
show_path (routebox_t * rb)
{
  while (rb && rb->type == EXPANSION_AREA)
    {
      show_one (rb);
      rb = rb->parent.expansion_area;
    }
  show_one (rb);
}

static void
show_sources (routebox_t * rb)
{
  routebox_t *p;
  if (!rb->flags.source && !rb->flags.target)
    {
      printf ("start with a source or target please\n");
      return;
    }
  LIST_LOOP (rb, same_net, p);
  if (p->flags.source)
    show_one (p);
  END_LOOP;
}

#endif

static int
__conflict_source (const BoxType * box, void *cl)
{
  routebox_t *rb = (routebox_t *) box;
  if (rb->flags.touched || rb->flags.fixed)
    return 0;
  else
    {
      routebox_t *dis = (routebox_t *) cl;
      path_conflicts (dis, rb, false);
      touch_conflicts (dis->conflicts_with, 1);
    }
  return 1;
}

static void
source_conflicts (rtree_t * tree, routebox_t * rb)
{
  if (!AutoRouteParameters.with_conflicts)
    return;
  r_search (tree, &rb->sbox, NULL, __conflict_source, rb);
  touch_conflicts (NULL, 1);
}

struct routeone_status
{
  bool found_route;
  int route_had_conflicts;
  cost_t best_route_cost;
  bool net_completely_routed;
};


static struct routeone_status
RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
{
  struct routeone_status result;
  routebox_t *p;
  int seen, i;
  const BoxType **target_list;
  int num_targets;
  rtree_t *targets;
  /* vector of source edges for filtering */
  vector_t *source_vec;
  /* working vector */
  vector_t *edge_vec;

  struct routeone_state s;
  struct routeone_via_site_state vss;

  assert (rd && from);
  result.route_had_conflicts = 0;
  /* no targets on to/from net need keepaway areas */
  LIST_LOOP (from, same_net, p);
  p->flags.nobloat = 1;
  END_LOOP;
  /* set 'source' flags */
  LIST_LOOP (from, same_subnet, p);
  if (!p->flags.nonstraight)
    p->flags.source = 1;
  END_LOOP;

  /* count up the targets */
  num_targets = 0;
  seen = 0;
  /* remove source/target flags from non-straight obstacles, because they
   * don't fill their bounding boxes and so connecting to them
   * after we've routed is problematic.  Better solution? */
  if (to)
    {                           /* if we're routing to a specific target */
      if (!to->flags.source)
        {                       /* not already connected */
          /* check that 'to' and 'from' are on the same net */
          seen = 0;
#ifndef NDEBUG
          LIST_LOOP (from, same_net, p);
          if (p == to)
            seen = 1;
          END_LOOP;
#endif
          assert (seen);        /* otherwise from and to are on different nets! */
          /* set target flags only on 'to's subnet */
          LIST_LOOP (to, same_subnet, p);
          if (!p->flags.nonstraight && is_layer_group_active[p->group])
            {
              p->flags.target = 1;
              num_targets++;
            }
          END_LOOP;
        }
    }
  else
    {
      /* all nodes on the net but not connected to from are targets */
      LIST_LOOP (from, same_net, p);
      if (!p->flags.source && is_layer_group_active[p->group]
          && !p->flags.nonstraight)
        {
          p->flags.target = 1;
          num_targets++;
        }
      END_LOOP;
    }

  /* if no targets, then net is done!  reset flags and return. */
  if (num_targets == 0)
    {
      LIST_LOOP (from, same_net, p);
      p->flags.source = p->flags.target = p->flags.nobloat = 0;
      END_LOOP;
      result.found_route = false;
      result.net_completely_routed = true;
      result.best_route_cost = 0;
      result.route_had_conflicts = 0;

      return result;
    }
  result.net_completely_routed = false;

  /* okay, there's stuff to route */
  assert (!from->flags.target);
  assert (num_targets > 0);
  /* create list of target pointers and from that a r-tree of targets */
  target_list = (const BoxType **)malloc (num_targets * sizeof (*target_list));
  i = 0;
  LIST_LOOP (from, same_net, p);
  if (p->flags.target)
    {
      target_list[i++] = &p->box;
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_TARGETS)
      showroutebox (p);
#endif
    }
  END_LOOP;
  targets = r_create_tree ((const BoxType **)target_list, i, 0);
  assert (i <= num_targets);
  free (target_list);

  source_vec = vector_create ();
  /* touch the source subnet to prepare check for conflictors */
  LIST_LOOP (from, same_subnet, p);
  p->flags.touched = 1;
  END_LOOP;
  LIST_LOOP (from, same_subnet, p);
  {
    /* we need the test for 'source' because this box may be nonstraight */
    if (p->flags.source && is_layer_group_active[p->group])
      {
        CheapPointType cp;
        edge_t *e;
        BoxType b = shrink_routebox (p);

#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_SOURCES)
        showroutebox (p);
#endif
        /* may expand in all directions from source; center edge cost point. */
        /* note that planes shouldn't really expand, but we need an edge */

        cp.X = CENTER_X (b);
        cp.Y = CENTER_Y (b);
        e = CreateEdge (p, cp.X, cp.Y, 0, NULL, ALL, targets);
        cp = closest_point_in_box (&cp, &e->mincost_target->sbox);
        cp = closest_point_in_box (&cp, &b);
        e->cost_point = cp;
        p->cost_point = cp;
        source_conflicts (rd->layergrouptree[p->group], p);
        vector_append (source_vec, e);
      }
  }
  END_LOOP;
  LIST_LOOP (from, same_subnet, p);
  p->flags.touched = 0;
  END_LOOP;
  /* break source edges; some edges may be too near obstacles to be able
   * to exit from. */

  /* okay, main expansion-search routing loop. */
  /* set up the initial activity heap */
  s.workheap = heap_create ();
  assert (s.workheap);
  while (!vector_is_empty (source_vec))
    {
      edge_t *e = (edge_t *)vector_remove_last (source_vec);
      assert (is_layer_group_active[e->rb->group]);
      e->cost = edge_cost (e, EXPENSIVE);
      heap_insert (s.workheap, e->cost, e);
    }
  vector_destroy (&source_vec);
  /* okay, process items from heap until it is empty! */
  s.best_path = NULL;
  s.best_cost = EXPENSIVE;
  area_vec = vector_create ();
  edge_vec = vector_create ();
  vss.free_space_vec = vector_create ();
  vss.lo_conflict_space_vec = vector_create ();
  vss.hi_conflict_space_vec = vector_create ();
  while (!heap_is_empty (s.workheap))
    {
      edge_t *e = (edge_t *)heap_remove_smallest (s.workheap);
#ifdef ROUTE_DEBUG
      if (aabort)
        goto dontexpand;
#endif
      /* don't bother expanding this edge if the minimum possible edge cost
       * is already larger than the best edge cost we've found. */
      if (s.best_path && e->cost >= s.best_cost)
        {
          heap_free (s.workheap, KillEdge);
          goto dontexpand;      /* skip this edge */
        }
      /* surprisingly it helps to give up and not try too hard to find
       * a route! This is not only faster, but results in better routing.
       * who would have guessed?
       */
      if (seen++ > max_edges)
        goto dontexpand;
      assert (__edge_is_good (e));
      /* mark or unmark conflictors as needed */
      touch_conflicts (e->rb->conflicts_with, 1);
      if (e->flags.via_search)
        {
          do_via_search (e, &s, &vss, rd->mtspace, targets);
          goto dontexpand;
        }
      /* we should never add edges on inactive layer groups to the heap. */
      assert (is_layer_group_active[e->rb->group]);
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
      //showedge (e);
#endif
      if (e->rb->flags.is_thermal)
        {
          best_path_candidate (&s, e, e->mincost_target);
          goto dontexpand;
        }
      /* for a plane, look for quick connections with thermals or vias */
      if (e->rb->type == PLANE)
        {
          routebox_t *pin = FindThermable (targets, e->rb);
          if (pin)
            {
              BoxType b = shrink_routebox (pin);
              edge_t *ne;
              routebox_t *nrb;
              assert (pin->flags.target);
              nrb = CreateExpansionArea (&b, e->rb->group, e->rb, true, e);
              nrb->flags.is_thermal = 1;
              /* moving through the plane is free */
              e->cost_point.X = b.X1;
              e->cost_point.Y = b.Y1;
              ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, pin);
              best_path_candidate (&s, ne, pin);
              DestroyEdge (&ne);
            }
          else
            {
              /* add in possible via sites in plane */
              if (AutoRouteParameters.use_vias &&
                  e->cost + AutoRouteParameters.ViaCost < s.best_cost)
                {
                  /* we need a giant thermal */
                  routebox_t *nrb =
                    CreateExpansionArea (&e->rb->sbox, e->rb->group, e->rb,
                                         true, e);
                  edge_t *ne = CreateEdge2 (nrb, e->expand_dir, e, NULL,
                                            e->mincost_target);
                  nrb->flags.is_thermal = 1;
                  add_via_sites (&s, &vss, rd->mtspace, nrb, NO_CONFLICT, ne,
                                 targets, e->rb->style->Diameter, true);
                }
            }
          goto dontexpand;      /* planes only connect via thermals */
        }
      if (e->flags.is_via)
        {                       /* special case via */
          routebox_t *intersecting;
          assert (AutoRouteParameters.use_vias);
          assert (e->expand_dir == ALL);
          assert (vector_is_empty (edge_vec));
          /* if there is already something here on this layer (like an
           * EXPANSION_AREA), then we don't want to expand from here
           * at least not inside the expansion area. A PLANE on the
           * other hand may be a target, or not. 
           */
          intersecting =
            FindOneInBox (rd->layergrouptree[e->rb->group], e->rb);

          if (intersecting && intersecting->flags.target
              && intersecting->type == PLANE)
            {
              /* we have hit a plane */
              edge_t *ne;
              routebox_t *nrb;
              BoxType b = shrink_routebox (e->rb);
              /* limit via region to that inside the plane */
              clip_box (&b, &intersecting->sbox);
              nrb = CreateExpansionArea (&b, e->rb->group, e->rb, true, e);
              nrb->flags.is_thermal = 1;
              ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, intersecting);
              best_path_candidate (&s, ne, intersecting);
              DestroyEdge (&ne);
              goto dontexpand;
            }
          else if (intersecting == NULL)
            {
              /* this via candidate is in an open area; add it to r-tree as
               * an expansion area */
              assert (e->rb->type == EXPANSION_AREA && e->rb->flags.is_via);
              /*assert (!r_search (rd->layergrouptree[e->rb->group],
                 &e->rb->box, NULL, no_planes,0));
               */
              r_insert_entry (rd->layergrouptree[e->rb->group], &e->rb->box,
                              1);
              e->rb->flags.homeless = 0;        /* not homeless any more */
              /* add to vector of all expansion areas in r-tree */
              vector_append (area_vec, e->rb);
              /* mark reset refcount to 0, since this is not homeless any more. */
              e->rb->refcount = 0;
              /* go ahead and expand this edge! */
            }
          else if (1)
            goto dontexpand;
          else if (0)
            {                   /* XXX: disabling this causes no via
                                   collisions. */
              BoxType a = bloat_routebox (intersecting), b;
              edge_t *ne;
              int i, j;
              /* something intersects this via candidate.  split via candidate
               * into pieces and add these pieces to the workheap. */
              for (i = 0; i < 3; i++)
                {
                  for (j = 0; j < 3; j++)
                    {
                      b = shrink_routebox (e->rb);
                      switch (i)
                        {
                        case 0:
                          b.X2 = MIN (b.X2, a.X1);
                          break;        /* left */
                        case 1:
                          b.X1 = MAX (b.X1, a.X1);
                          b.X2 = MIN (b.X2, a.X2);
                          break;        /*c */
                        case 2:
                          b.X1 = MAX (b.X1, a.X2);
                          break;        /* right */
                        default:
                          assert (0);
                        }
                      switch (j)
                        {
                        case 0:
                          b.Y2 = MIN (b.Y2, a.Y1);
                          break;        /* top */
                        case 1:
                          b.Y1 = MAX (b.Y1, a.Y1);
                          b.Y2 = MIN (b.Y2, a.Y2);
                          break;        /*c */
                        case 2:
                          b.Y1 = MAX (b.Y1, a.Y2);
                          break;        /* bottom */
                        default:
                          assert (0);
                        }
                      /* skip if this box is not valid */
                      if (!(b.X1 < b.X2 && b.Y1 < b.Y2))
                        continue;
                      if (i == 1 && j == 1)
                        {
                          /* this bit of the via space is obstructed. */
                          if (intersecting->type == EXPANSION_AREA
                              || intersecting->flags.fixed)
                            continue;   /* skip this bit, it's already been done. */
                          /* create an edge with conflicts, if enabled */
                          if (!AutoRouteParameters.with_conflicts)
                            continue;
                          ne = CreateEdgeWithConflicts (&b, intersecting, e, 1
                                                        /*cost penalty to box */
                                                        , targets);
                          add_or_destroy_edge (&s, ne);
                        }
                      else
                        {
                          /* if this is not the intersecting piece, create a new
                           * (hopefully unobstructed) via edge and add it back to the
                           * workheap. */
                          ne =
                            CreateViaEdge (&b, e->rb->group,
                                           e->rb->parent.expansion_area, e,
                                           e->flags.via_conflict_level,
                                           NO_CONFLICT
                                           /* value here doesn't matter */
                                           , targets);
                          add_or_destroy_edge (&s, ne);
                        }
                    }
                }
              goto dontexpand;
            }
          /* between the time these edges are inserted and the
           * time they are processed, new expansion boxes (which
           * conflict with these edges) may be added to the graph!
           * w.o vias this isn't a problem because the broken box
           * is not homeless. */
        }
      if (1)
        {
          routebox_t *nrb;
          struct E_result *ans;
          BoxType b;
          vector_t *broken;
          if (e->flags.is_interior)
            {
              assert (AutoRouteParameters.with_conflicts);      /* no interior edges unless
                                                                   routing with conflicts! */
              assert (e->rb->conflicts_with);
              b = e->rb->sbox;
              switch (e->rb->came_from)
                {
                case NORTH:
                  b.Y2 = b.Y1 + 1;
                  b.X1 = CENTER_X (b);
                  b.X2 = b.X1 + 1;
                  break;
                case EAST:
                  b.X1 = b.X2 - 1;
                  b.Y1 = CENTER_Y (b);
                  b.Y2 = b.Y1 + 1;
                  break;
                case SOUTH:
                  b.Y1 = b.Y2 - 1;
                  b.X1 = CENTER_X (b);
                  b.X2 = b.X1 + 1;
                  break;
                case WEST:
                  b.X2 = b.X1 + 1;
                  b.Y1 = CENTER_Y (b);
                  b.Y2 = b.Y1 + 1;
                  break;
                default:
                  assert (0);
                }
            }
          /* sources may not expand to their own edges because of
           * adjacent blockers.
           */
          else if (e->rb->flags.source)
            b = box_center (&e->rb->sbox);
          else
            b = e->rb->sbox;
          ans = Expand (rd->layergrouptree[e->rb->group], e, &b);
          if (!box_intersect (&ans->inflated, &ans->orig))
            goto dontexpand;
#if 0
          /* skip if it didn't actually expand */
          if (ans->inflated.X1 >= e->rb->sbox.X1 &&
              ans->inflated.X2 <= e->rb->sbox.X2 &&
              ans->inflated.Y1 >= e->rb->sbox.Y1 &&
              ans->inflated.Y2 <= e->rb->sbox.Y2)
            goto dontexpand;
#endif

          if (!box_is_good (&ans->inflated))
            goto dontexpand;
          nrb = CreateExpansionArea (&ans->inflated, e->rb->group, e->rb,
                                     true, e);
          r_insert_entry (rd->layergrouptree[nrb->group], &nrb->box, 1);
          vector_append (area_vec, nrb);
          nrb->flags.homeless = 0;      /* not homeless any more */
          broken =
            BreakManyEdges (&s, targets, rd->layergrouptree[nrb->group],
                            area_vec, ans, nrb, e);
          while (!vector_is_empty (broken))
            {
              edge_t *ne = (edge_t *)vector_remove_last (broken);
              add_or_destroy_edge (&s, ne);
            }
          vector_destroy (&broken);

          /* add in possible via sites in nrb */
          if (AutoRouteParameters.use_vias && !e->rb->flags.is_via &&
              e->cost + AutoRouteParameters.ViaCost < s.best_cost)
            add_via_sites (&s, &vss,
                           rd->mtspace, nrb, NO_CONFLICT, e, targets, 0,
                           false);
          goto dontexpand;
        }
    dontexpand:
      DestroyEdge (&e);
    }
  touch_conflicts (NULL, 1);
  heap_destroy (&s.workheap);
  r_destroy_tree (&targets);
  assert (vector_is_empty (edge_vec));
  vector_destroy (&edge_vec);

  /* we should have a path in best_path now */
  if (s.best_path)
    {
      routebox_t *rb;
#ifdef ROUTE_VERBOSE
      printf ("%d:%d RC %.0f", ro++, seen, s.best_cost);
#endif
      result.found_route = true;
      result.best_route_cost = s.best_cost;
      /* determine if the best path had conflicts */
      result.route_had_conflicts = 0;
      if (AutoRouteParameters.with_conflicts && s.best_path->conflicts_with)
        {
          while (!vector_is_empty (s.best_path->conflicts_with))
            {
              rb = (routebox_t *)vector_remove_last (s.best_path->conflicts_with);
              rb->flags.is_bad = 1;
              result.route_had_conflicts++;
            }
        }
#ifdef ROUTE_VERBOSE
      if (result.route_had_conflicts)
        printf (" (%d conflicts)", result.route_had_conflicts);
#endif
      if (result.route_had_conflicts < AutoRouteParameters.hi_conflict)
        {
          /* back-trace the path and add lines/vias to r-tree */
          TracePath (rd, s.best_path, s.best_target, from,
                     result.route_had_conflicts);
          MergeNets (from, s.best_target, SUBNET);
        }
      else
        {
#ifdef ROUTE_VERBOSE
          printf (" (too many in fact)");
#endif
          result.found_route = false;
        }
#ifdef ROUTE_VERBOSE
      printf ("\n");
#endif
    }
  else
    {
#ifdef ROUTE_VERBOSE
      printf ("%d:%d NO PATH FOUND.\n", ro++, seen);
#endif
      result.best_route_cost = s.best_cost;
      result.found_route = false;
    }
  /* now remove all expansion areas from the r-tree. */
  while (!vector_is_empty (area_vec))
    {
      routebox_t *rb = (routebox_t *)vector_remove_last (area_vec);
      assert (!rb->flags.homeless);
      if (rb->conflicts_with
          && rb->parent.expansion_area->conflicts_with != rb->conflicts_with)
        vector_destroy (&rb->conflicts_with);
      r_delete_entry (rd->layergrouptree[rb->group], &rb->box);
    }
  vector_destroy (&area_vec);
  /* clean up; remove all 'source', 'target', and 'nobloat' flags */
  LIST_LOOP (from, same_net, p);
  if (p->flags.source && p->conflicts_with)
    vector_destroy (&p->conflicts_with);
  p->flags.touched = p->flags.source = p->flags.target = p->flags.nobloat = 0;
  END_LOOP;

  vector_destroy (&vss.free_space_vec);
  vector_destroy (&vss.lo_conflict_space_vec);
  vector_destroy (&vss.hi_conflict_space_vec);

  return result;
}

static void
InitAutoRouteParameters (int pass,
                         RouteStyleType * style,
                         bool with_conflicts, bool is_smoothing,
                         bool lastpass)
{
  int i;
  /* routing style */
  AutoRouteParameters.style = style;
  AutoRouteParameters.bloat = style->Keepaway + HALF_THICK (style->Thick);
  /* costs */
  AutoRouteParameters.ViaCost =
    INCH_TO_COORD (3.5) + style->Diameter * (is_smoothing ? 80 : 30);
  AutoRouteParameters.LastConflictPenalty =
    (400 * pass / passes + 2) / (pass + 1);
  AutoRouteParameters.ConflictPenalty =
    4 * AutoRouteParameters.LastConflictPenalty;
  AutoRouteParameters.JogPenalty = 1000 * (is_smoothing ? 20 : 4);
  AutoRouteParameters.CongestionPenalty = 1e6;
  AutoRouteParameters.MinPenalty = EXPENSIVE;
  for (i = 0; i < max_group; i++)
    {
      if (is_layer_group_active[i])
        {
          AutoRouteParameters.MinPenalty = MIN (x_cost[i],
                                                AutoRouteParameters.
                                                MinPenalty);
          AutoRouteParameters.MinPenalty =
            MIN (y_cost[i], AutoRouteParameters.MinPenalty);
        }
    }
  AutoRouteParameters.NewLayerPenalty = is_smoothing ?
    0.5 * EXPENSIVE : 10 * AutoRouteParameters.ViaCost;
  /* other */
  AutoRouteParameters.hi_conflict = MAX (8 * (passes - pass + 1), 6);
  AutoRouteParameters.is_odd = (pass & 1);
  AutoRouteParameters.with_conflicts = with_conflicts;
  AutoRouteParameters.is_smoothing = is_smoothing;
  AutoRouteParameters.rip_always = is_smoothing;
  AutoRouteParameters.last_smooth = 0;  //lastpass;
  AutoRouteParameters.pass = pass + 1;
}

#ifndef NDEBUG
int
bad_boy (const BoxType * b, void *cl)
{
  routebox_t *box = (routebox_t *) b;
  if (box->type == EXPANSION_AREA)
    return 1;
  return 0;
}

bool
no_expansion_boxes (routedata_t * rd)
{
  int i;
  BoxType big;
  big.X1 = 0;
  big.X2 = MAX_COORD;
  big.Y1 = 0;
  big.Y2 = MAX_COORD;
  for (i = 0; i < max_group; i++)
    {
      if (r_search (rd->layergrouptree[i], &big, NULL, bad_boy, NULL))
        return false;
    }
  return true;
}
#endif

static void
ripout_livedraw_obj (routebox_t *rb)
{
  if (rb->type == LINE && rb->livedraw_obj.line)
    {
      LayerType *layer = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
      EraseLine (rb->livedraw_obj.line);
      DestroyObject (PCB->Data, LINE_TYPE, layer, rb->livedraw_obj.line, NULL);
      rb->livedraw_obj.line = NULL;
    }
  if (rb->type == VIA && rb->livedraw_obj.via)
    {
      EraseVia (rb->livedraw_obj.via);
      DestroyObject (PCB->Data, VIA_TYPE, rb->livedraw_obj.via, NULL, NULL);
      rb->livedraw_obj.via = NULL;
    }
}

static int
ripout_livedraw_obj_cb (const BoxType * b, void *cl)
{
  routebox_t *box = (routebox_t *) b;
  ripout_livedraw_obj (box);
  return 0;
}

struct routeall_status
{
  /* --- for completion rate statistics ---- */
  int total_subnets;
  /* total subnets routed without conflicts */
  int routed_subnets;
  /* total subnets routed with conflicts */
  int conflict_subnets;
  /* net failted entirely */
  int failed;
  /* net was ripped */
  int ripped;
  int total_nets_routed;
};

static double
calculate_progress (double this_heap_item, double this_heap_size,
                    struct routeall_status *ras)
{
  double total_passes = passes + smoothes + 1;      /* + 1 is the refinement pass */
  double this_pass = AutoRouteParameters.pass - 1; /* Number passes from zero */
  double heap_fraction = (double)(ras->routed_subnets + ras->conflict_subnets + ras->failed) /
                         (double)ras->total_subnets;
  double pass_fraction = (this_heap_item + heap_fraction ) / this_heap_size;
  double process_fraction = (this_pass + pass_fraction) / total_passes;

  return process_fraction;
}

struct routeall_status
RouteAll (routedata_t * rd)
{
  struct routeall_status ras;
  struct routeone_status ros;
  bool rip;
  int request_cancel;
#ifdef NET_HEAP
  heap_t *net_heap;
#endif
  heap_t *this_pass, *next_pass, *tmp;
  routebox_t *net, *p, *pp;
  cost_t total_net_cost, last_cost = 0, this_cost = 0;
  int i;
  int this_heap_size;
  int this_heap_item;

  /* initialize heap for first pass; 
   * do smallest area first; that makes
   * the subsequent costs more representative */
  this_pass = heap_create ();
  next_pass = heap_create ();
#ifdef NET_HEAP
  net_heap = heap_create ();
#endif
  LIST_LOOP (rd->first_net, different_net, net);
  {
    double area;
    BoxType bb = shrink_routebox (net);
    LIST_LOOP (net, same_net, p);
    {
      MAKEMIN (bb.X1, p->sbox.X1);
      MAKEMIN (bb.Y1, p->sbox.Y1);
      MAKEMAX (bb.X2, p->sbox.X2);
      MAKEMAX (bb.Y2, p->sbox.Y2);
    }
    END_LOOP;
    area = (double) (bb.X2 - bb.X1) * (bb.Y2 - bb.Y1);
    heap_insert (this_pass, area, net);
  }
  END_LOOP;

  ras.total_nets_routed = 0;
  /* refinement/finishing passes */
  for (i = 0; i <= passes + smoothes; i++)
    {
#ifdef ROUTE_VERBOSE
      if (i > 0 && i <= passes)
        printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i);
      else if (i > passes)
        printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
                i - passes);
#endif
      ras.total_subnets = ras.routed_subnets = ras.conflict_subnets =
        ras.failed = ras.ripped = 0;
      assert (heap_is_empty (next_pass));

      this_heap_size = heap_size (this_pass);
      for (this_heap_item = 0; !heap_is_empty (this_pass); this_heap_item++)
        {
#ifdef ROUTE_DEBUG
          if (aabort)
            break;
#endif
          net = (routebox_t *) heap_remove_smallest (this_pass);
          InitAutoRouteParameters (i, net->style, i < passes, i > passes,
                                   i == passes + smoothes);
          if (i > 0)
            {
              /* rip up all unfixed traces in this net ? */
              if (AutoRouteParameters.rip_always)
                rip = true;
              else
                {
                  rip = false;
                  LIST_LOOP (net, same_net, p);
                  if (p->flags.is_bad)
                    {
                      rip = true;
                      break;
                    }
                  END_LOOP;
                }

              LIST_LOOP (net, same_net, p);
              p->flags.is_bad = 0;
              if (!p->flags.fixed)
                {
#ifndef NDEBUG
                  bool del;
#endif
                  assert (!p->flags.homeless);
                  if (rip)
                    {
                      RemoveFromNet (p, NET);
                      RemoveFromNet (p, SUBNET);
                    }
                  if (AutoRouteParameters.use_vias && p->type != VIA_SHADOW
                      && p->type != PLANE)
                    {
                      mtspace_remove (rd->mtspace, &p->box,
                                      p->flags.is_odd ? ODD : EVEN,
                                      p->style->Keepaway);
                      if (!rip)
                        mtspace_add (rd->mtspace, &p->box,
                                     p->flags.is_odd ? EVEN : ODD,
                                     p->style->Keepaway);
                    }
                  if (rip)
                    {
                      if (TEST_FLAG (LIVEROUTEFLAG, PCB))
                        ripout_livedraw_obj (p);
#ifndef NDEBUG
                      del =
#endif
                        r_delete_entry (rd->layergrouptree[p->group],
                                        &p->box);
#ifndef NDEBUG
                      assert (del);
#endif
                    }
                  else
                    {
                      p->flags.is_odd = AutoRouteParameters.is_odd;
                    }
                }
              END_LOOP;
              if (TEST_FLAG (LIVEROUTEFLAG, PCB))
                Draw ();
              /* reset to original connectivity */
              if (rip)
                {
                  ras.ripped++;
                  ResetSubnet (net);
                }
              else
                {
                  heap_insert (next_pass, 0, net);
                  continue;
                }
            }
          /* count number of subnets */
          FOREACH_SUBNET (net, p);
          ras.total_subnets++;
          END_FOREACH (net, p);
          /* the first subnet doesn't require routing. */
          ras.total_subnets--;
          /* and re-route! */
          total_net_cost = 0;
          /* only route that which isn't fully routed */
#ifdef ROUTE_DEBUG
          if (ras.total_subnets == 0 || aabort)
#else
          if (ras.total_subnets == 0)
#endif
            {
              heap_insert (next_pass, 0, net);
              continue;
            }

          /* the loop here ensures that we get to all subnets even if
           * some of them are unreachable from the first subnet. */
          LIST_LOOP (net, same_net, p);
          {
#ifdef NET_HEAP
            BoxType b = shrink_routebox (p);
            /* using a heap allows us to start from smaller objects and
             * end at bigger ones. also prefer to start at planes, then pads */
            heap_insert (net_heap, (float) (b.X2 - b.X1) *
#if defined(ROUTE_RANDOMIZED)
                         (0.3 + rand () / (RAND_MAX + 1.0)) *
#endif
                         (b.Y2 - b.Y1) * (p->type == PLANE ?
                                          -1 : (p->type ==
                                                PAD ? 1 : 10)), p);
          }
          END_LOOP;
          ros.net_completely_routed = 0;
          while (!heap_is_empty (net_heap))
            {
              p = (routebox_t *) heap_remove_smallest (net_heap);
#endif
              if (!p->flags.fixed || p->flags.subnet_processed ||
                  p->type == OTHER)
                continue;

              while (!ros.net_completely_routed)
                {
                  double percent;

                  assert (no_expansion_boxes (rd));
                  /* FIX ME: the number of edges to examine should be in autoroute parameters
                   * i.e. the 2000 and 800 hard-coded below should be controllable by the user
                   */
                  ros =
                    RouteOne (rd, p, NULL,
                              ((AutoRouteParameters.
                                is_smoothing ? 2000 : 800) * (i +
                                                              1)) *
                              routing_layers);
                  total_net_cost += ros.best_route_cost;
                  if (ros.found_route)
                    {
                      if (ros.route_had_conflicts)
                        ras.conflict_subnets++;
                      else
                        {
                          ras.routed_subnets++;
                          ras.total_nets_routed++;
                        }
                    }
                  else
                    {
                      if (!ros.net_completely_routed)
                        ras.failed++;
                      /* don't bother trying any other source in this subnet */
                      LIST_LOOP (p, same_subnet, pp);
                      pp->flags.subnet_processed = 1;
                      END_LOOP;
                      break;
                    }
                  /* note that we can infer nothing about ras.total_subnets based
                   * on the number of calls to RouteOne, because we may be unable
                   * to route a net from a particular starting point, but perfectly
                   * able to route it from some other. */
                  percent = calculate_progress (this_heap_item, this_heap_size, &ras);
                  request_cancel = gui->progress (percent * 100., 100,
                                                  _("Autorouting tracks"));
                  if (request_cancel)
                    {
                      ras.total_nets_routed = 0;
                      ras.conflict_subnets = 0;
                      Message ("Autorouting cancelled\n");
                      goto out;
                    }
                }
            }
#ifndef NET_HEAP
          END_LOOP;
#endif
          if (!ros.net_completely_routed)
            net->flags.is_bad = 1;      /* don't skip this the next round */

          /* Route easiest nets from this pass first on next pass.
           * This works best because it's likely that the hardest
           * is the last one routed (since it has the most obstacles)
           * but it will do no good to rip it up and try it again
           * without first changing any of the other routes
           */
          heap_insert (next_pass, total_net_cost, net);
          if (total_net_cost < EXPENSIVE)
            this_cost += total_net_cost;
          /* reset subnet_processed flags */
          LIST_LOOP (net, same_net, p);
          {
            p->flags.subnet_processed = 0;
          }
          END_LOOP;
        }
      /* swap this_pass and next_pass and do it all over again! */
      ro = 0;
      assert (heap_is_empty (this_pass));
      tmp = this_pass;
      this_pass = next_pass;
      next_pass = tmp;
#if defined(ROUTE_DEBUG) || defined (ROUTE_VERBOSE)
      printf
        ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f, %d conflicts, %d failed %d ripped\n",
         i, ras.routed_subnets, ras.total_subnets, this_cost,
         ras.conflict_subnets, ras.failed, ras.ripped);
#endif
#ifdef ROUTE_DEBUG
      if (aabort)
        break;
#endif
      /* if no conflicts found, skip directly to smoothing pass! */
      if (ras.conflict_subnets == 0 && ras.routed_subnets == ras.total_subnets
          && i <= passes)
        i = passes - (smoothes ? 0 : 1);
      /* if no changes in a smoothing round, then we're done */
      if (this_cost == last_cost && i > passes && i < passes + smoothes)
        i = passes + smoothes - 1;
      last_cost = this_cost;
      this_cost = 0;
    }

  Message ("%d of %d nets successfully routed.\n",
           ras.routed_subnets, ras.total_subnets);

out:
  heap_destroy (&this_pass);
  heap_destroy (&next_pass);
#ifdef NET_HEAP
  heap_destroy (&net_heap);
#endif

  /* no conflicts should be left at the end of the process. */
  assert (ras.conflict_subnets == 0);

  return ras;
}

struct fpin_info
{
  PinType *pin;
  Coord X, Y;
  jmp_buf env;
};

static int
fpin_rect (const BoxType * b, void *cl)
{
  PinType *pin = (PinType *) b;
  struct fpin_info *info = (struct fpin_info *) cl;
  if (pin->X == info->X && pin->Y == info->Y)
    {
      info->pin = (PinType *) b;
      longjmp (info->env, 1);
    }
  return 0;
}

static int
FindPin (const BoxType * box, PinType ** pin)
{
  struct fpin_info info;

  info.pin = NULL;
  info.X = box->X1;
  info.Y = box->Y1;
  if (setjmp (info.env) == 0)
    r_search (PCB->Data->pin_tree, box, NULL, fpin_rect, &info);
  else
    {
      *pin = info.pin;
      return PIN_TYPE;
    }
  if (setjmp (info.env) == 0)
    r_search (PCB->Data->via_tree, box, NULL, fpin_rect, &info);
  else
    {
      *pin = info.pin;
      return VIA_TYPE;
    }
  *pin = NULL;
  return NO_TYPE;
}


/*!
 * \brief Paths go on first 'on' layer in group.
 *
 * Returns 'true' if any paths were added.
 */
bool
IronDownAllUnfixedPaths (routedata_t * rd)
{
  bool changed = false;
  LayerType *layer;
  routebox_t *net, *p;
  int i;
  LIST_LOOP (rd->first_net, different_net, net);
  {
    LIST_LOOP (net, same_net, p);
    {
      if (!p->flags.fixed)
        {
          /* find first on layer in this group */
          assert (PCB->LayerGroups.Number[p->group] > 0);
          assert (is_layer_group_active[p->group]);
          for (i = 0, layer = NULL; i < PCB->LayerGroups.Number[p->group];
               i++)
            {
              layer = LAYER_PTR (PCB->LayerGroups.Entries[p->group][i]);
              if (layer->On)
                break;
            }
          assert (layer && layer->On);  /*at least one layer must be on in this group! */
          assert (p->type != EXPANSION_AREA);
          if (p->type == LINE)
            {
              Coord halfwidth = HALF_THICK (p->style->Thick);
              double th = halfwidth * 2 + 1;
              BoxType b;
              assert (p->parent.line == NULL);
              /* orthogonal; thickness is 2*halfwidth */
              /* flip coordinates, if bl_to_ur */
              b = p->sbox;
              total_wire_length +=
                sqrt ((b.X2 - b.X1 - th) * (b.X2 - b.X1 - th) +
                      (b.Y2 - b.Y1 - th) * (b.Y2 - b.Y1 - th));
              b = shrink_box (&b, halfwidth);
              if (b.X2 == b.X1 + 1)
                b.X2 = b.X1;
              if (b.Y2 == b.Y1 + 1)
                b.Y2 = b.Y1;
              if (p->flags.bl_to_ur)
                {
                  Coord t;
                  t = b.X1;
                  b.X1 = b.X2;
                  b.X2 = t;
                }
              /* using CreateDrawn instead of CreateNew concatenates sequential lines */
              p->parent.line = CreateDrawnLineOnLayer
                (layer, b.X1, b.Y1, b.X2, b.Y2,
                 p->style->Thick,
                 p->style->Keepaway * 2,
                 MakeFlags (AUTOFLAG |
                            (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG :
                             0)));

              if (p->parent.line)
                {
                  AddObjectToCreateUndoList (LINE_TYPE, layer,
                                             p->parent.line, p->parent.line);
                  changed = true;
                }
            }
          else if (p->type == VIA || p->type == VIA_SHADOW)
            {
              routebox_t *pp =
                (p->type == VIA_SHADOW) ? p->parent.via_shadow : p;
              Coord radius = HALF_THICK (pp->style->Diameter);
              BoxType b = shrink_routebox (p);
              total_via_count++;
              assert (pp->type == VIA);
              if (pp->parent.via == NULL)
                {
                  assert (b.X1 + radius == b.X2 - radius);
                  assert (b.Y1 + radius == b.Y2 - radius);
                  pp->parent.via =
                    CreateNewVia (PCB->Data, b.X1 + radius,
                                  b.Y1 + radius,
                                  pp->style->Diameter,
                                  2 * pp->style->Keepaway,
                                  0, pp->style->Hole, NULL,
                                  MakeFlags (AUTOFLAG));
                  assert (pp->parent.via);
                  if (pp->parent.via)
                    {
                      AddObjectToCreateUndoList (VIA_TYPE,
                                                 pp->parent.via,
                                                 pp->parent.via,
                                                 pp->parent.via);
                      changed = true;
                    }
                }
              assert (pp->parent.via);
              if (p->type == VIA_SHADOW)
                {
                  p->type = VIA;
                  p->parent.via = pp->parent.via;
                }
            }
          else if (p->type == THERMAL)
            /* nothing to do because, the via might not be there yet */ ;
          else
            assert (0);
        }
    }
    END_LOOP;
    /* loop again to place all the thermals now that the vias are down */
    LIST_LOOP (net, same_net, p);
    {
      if (p->type == THERMAL)
        {
          PinType *pin = NULL;
          /* thermals are alread a single point search, no need to shrink */
          int type = FindPin (&p->box, &pin);
          if (pin)
            {
              AddObjectToClearPolyUndoList (type,
                                            pin->Element ? pin->Element : pin,
                                            pin, pin, false);
              RestoreToPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
                                pin);
              AddObjectToFlagUndoList (type,
                                       pin->Element ? pin->Element : pin, pin,
                                       pin);
              ASSIGN_THERM (p->layer, PCB->ThermStyle, pin);
              AddObjectToClearPolyUndoList (type,
                                            pin->Element ? pin->Element : pin,
                                            pin, pin, true);
              ClearFromPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
                                pin);
              changed = true;
            }
        }
    }
    END_LOOP;
  }
  END_LOOP;
  return changed;
}

bool
AutoRoute (bool selected)
{
  bool changed = false;
  routedata_t *rd;
  int i;

  total_wire_length = 0;
  total_via_count = 0;

#ifdef ROUTE_DEBUG
  ddraw = gui->request_debug_draw ();
  if (ddraw != NULL)
    {
      ar_gc = ddraw->make_gc ();
      ddraw->set_line_cap (ar_gc, Round_Cap);
    }
#endif

  for (i = 0; i < NUM_STYLES; i++)
    {
      if (PCB->RouteStyle[i].Thick == 0 ||
          PCB->RouteStyle[1].Diameter == 0 ||
          PCB->RouteStyle[1].Hole == 0 || PCB->RouteStyle[i].Keepaway == 0)
        {
          Message ("You must define proper routing styles\n"
                   "before auto-routing.\n");
          return (false);
        }
    }
  if (PCB->Data->RatN == 0)
    return (false);
  rd = CreateRouteData ();

  if (1)
    {
      routebox_t *net, *rb, *last;
      int i = 0;
      /* count number of rats selected */
      RAT_LOOP (PCB->Data);
      {
        if (!selected || TEST_FLAG (SELECTEDFLAG, line))
          i++;
      }
      END_LOOP;
#ifdef ROUTE_VERBOSE
      printf ("%d nets!\n", i);
#endif
      if (i == 0)
        goto donerouting;       /* nothing to do here */
      /* if only one rat selected, do things the quick way. =) */
      if (i == 1)
        {
          RAT_LOOP (PCB->Data);
          if (!selected || TEST_FLAG (SELECTEDFLAG, line))
            {
              /* look up the end points of this rat line */
              routebox_t *a =
                FindRouteBoxOnLayerGroup (rd, line->Point1.X,
                                          line->Point1.Y, line->group1);
              routebox_t *b =
                FindRouteBoxOnLayerGroup (rd, line->Point2.X,
                                          line->Point2.Y, line->group2);

              /* If the rat starts or ends at a non-straight pad (i.e., at a
               * rotated SMD), a or b will be NULL since the autorouter can't
               * handle these.
               */
              if (a != NULL && b != NULL)
                {
                  assert (a->style == b->style);
                  /* route exactly one net, without allowing conflicts */
                  InitAutoRouteParameters (0, a->style, false, true, true);
                  /* hace planes work better as sources than targets */
                  changed = RouteOne (rd, a, b, 150000).found_route || changed;
                  goto donerouting;
                }
            }
          END_LOOP;
        }
      /* otherwise, munge the netlists so that only the selected rats
       * get connected. */
      /* first, separate all sub nets into separate nets */
      /* note that this code works because LIST_LOOP is clever enough not to
       * be fooled when the list is changing out from under it. */
      last = NULL;
      LIST_LOOP (rd->first_net, different_net, net);
      {
        FOREACH_SUBNET (net, rb);
        {
          if (last)
            {
              last->different_net.next = rb;
              rb->different_net.prev = last;
            }
          last = rb;
        }
        END_FOREACH (net, rb);
        LIST_LOOP (net, same_net, rb);
        {
          rb->same_net = rb->same_subnet;
        }
        END_LOOP;
        /* at this point all nets are equal to their subnets */
      }
      END_LOOP;
      if (last)
        {
          last->different_net.next = rd->first_net;
          rd->first_net->different_net.prev = last;
        }

      /* now merge only those subnets connected by a rat line */
      RAT_LOOP (PCB->Data);
      if (!selected || TEST_FLAG (SELECTEDFLAG, line))
        {
          /* look up the end points of this rat line */
          routebox_t *a;
          routebox_t *b;
          a =
            FindRouteBoxOnLayerGroup (rd, line->Point1.X,
                                      line->Point1.Y, line->group1);
          b =
            FindRouteBoxOnLayerGroup (rd, line->Point2.X,
                                      line->Point2.Y, line->group2);
          if (!a || !b)
            {
#ifdef DEBUG_STALE_RATS
              AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
              ASSIGN_FLAG (SELECTEDFLAG, true, line);
              DrawRat (line, 0);
#endif /* DEBUG_STALE_RATS */
              Message ("The rats nest is stale! Aborting autoroute...\n");
              goto donerouting;
            }
          /* merge subnets into a net! */
          MergeNets (a, b, NET);
        }
      END_LOOP;
      /* now 'different_net' may point to too many different nets.  Reset. */
      LIST_LOOP (rd->first_net, different_net, net);
      {
        if (!net->flags.touched)
          {
            LIST_LOOP (net, same_net, rb);
            rb->flags.touched = 1;
            END_LOOP;
          }
        else                    /* this is not a "different net"! */
          RemoveFromNet (net, DIFFERENT_NET);
      }
      END_LOOP;
      /* reset "touched" flag */
      LIST_LOOP (rd->first_net, different_net, net);
      {
        LIST_LOOP (net, same_net, rb);
        {
          assert (rb->flags.touched);
          rb->flags.touched = 0;
        }
        END_LOOP;
      }
      END_LOOP;
    }
  /* okay, rd's idea of netlist now corresponds to what we want routed */
  /* auto-route all nets */
  changed = (RouteAll (rd).total_nets_routed > 0) || changed;
donerouting:
  gui->progress (0, 0, NULL);
  if (TEST_FLAG (LIVEROUTEFLAG, PCB))
    {
      int i;
      BoxType big = {0, 0, MAX_COORD, MAX_COORD};
      for (i = 0; i < max_group; i++)
        {
          r_search (rd->layergrouptree[i], &big, NULL, ripout_livedraw_obj_cb, NULL);
        }
    }
#ifdef ROUTE_DEBUG
  if (ddraw != NULL)
    {
      ddraw->destroy_gc (ar_gc);
      gui->finish_debug_draw ();
    }
#endif

  if (changed)
    changed = IronDownAllUnfixedPaths (rd);
  Message ("Total added wire length = %$mS, %d vias added\n",
           (Coord) total_wire_length, total_via_count);
  DestroyRouteData (&rd);
  if (changed)
    {
      SaveUndoSerialNumber ();

      /* optimize rats, we've changed connectivity a lot. */
      DeleteRats (false /*all rats */ );
      RestoreUndoSerialNumber ();
      AddAllRats (false /*all rats */ , NULL);
      RestoreUndoSerialNumber ();

      IncrementUndoSerialNumber ();

      Redraw ();
    }
#if defined (ROUTE_DEBUG)
  aabort = 0;
#endif
  return (changed);
}