KiCad PCB EDA Suite
solve.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  *
7  * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
8  *
9  * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 /* see "Autorouting With the A* Algorithm" (Dr.Dobbs journal)
30 */
31 
36 #include <fctsys.h>
37 #include <class_drawpanel.h>
38 #include <confirm.h>
39 #include <wxPcbStruct.h>
40 #include <gr_basic.h>
41 #include <macros.h>
42 
43 #include <class_board.h>
44 #include <class_track.h>
45 
46 #include <pcbnew.h>
47 #include <protos.h>
48 #include <autorout.h>
49 #include <cell.h>
50 
52  int two_sides,
53  int row_source,
54  int col_source,
55  int row_target,
56  int col_target,
57  RATSNEST_ITEM* pt_rat );
58 
59 static int Retrace( AUTOROUTER_CONTEXT& ctx,
60  int,
61  int,
62  int,
63  int,
64  int,
65  int net_code );
66 
67 static void OrCell_Trace( AUTOROUTER_CONTEXT& ctx,
68  int col,
69  int row,
70  int side,
71  int orient,
72  int current_net_code );
73 
74 static void AddNewTrace( AUTOROUTER_CONTEXT& ctx );
75 
76 
77 static int segm_oX, segm_oY;
78 static int segm_fX, segm_fY; /* Origin and position of the current
79  * trace segment. */
81 static int s_Clearance; // Clearance value used in autorouter
82 
84 
85 int OpenNodes; // total number of nodes opened
86 int ClosNodes; // total number of nodes closed
87 int MoveNodes; // total number of nodes moved
88 int MaxNodes; // maximum number of nodes opened at one time
89 
90 #define NOSUCCESS 0
91 #define STOP_FROM_ESC -1
92 #define ERR_MEMORY -2
93 #define SUCCESS 1
94 #define TRIVIAL_SUCCESS 2
95 
96 /*
97 ** visit neighboring cells like this (where [9] is on the other side):
98 **
99 ** +---+---+---+
100 ** | 1 | 2 | 3 |
101 ** +---+---+---+
102 ** | 4 |[9]| 5 |
103 ** +---+---+---+
104 ** | 6 | 7 | 8 |
105 ** +---+---+---+
106 */
107 
108 /* for visiting neighbors on the same side: increments/decrements coord of
109  * [] [0] = row [] (1] = col was added to the coord of the midpoint for
110  * Get the coord of the 8 neighboring points.
111  */
112 static const int delta[8][2] =
113 {
114  { 1, -1 }, // northwest
115  { 1, 0 }, // north
116  { 1, 1 }, // northeast
117  { 0, -1 }, // west
118  { 0, 1 }, // east
119  { -1, -1 }, // southwest
120  { -1, 0 }, // south
121  { -1, 1 } // southeast
122 };
123 
124 static const int ndir[8] =
125 {
126  // for building paths back to source
130 };
131 
132 // blocking masks for neighboring cells
133 #define BLOCK_NORTHEAST ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
134  | ANGLE_NEtoSE | ANGLE_NWtoNE \
135  | SHARP_NtoNE | SHARP_EtoNE | HOLE )
136 #define BLOCK_SOUTHEAST ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
137  | ANGLE_NEtoSE | ANGLE_SEtoSW \
138  | SHARP_EtoSE | SHARP_StoSE | HOLE )
139 #define BLOCK_SOUTHWEST ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
140  | ANGLE_SEtoSW | ANGLE_SWtoNW \
141  | SHARP_StoSW | SHARP_WtoSW | HOLE )
142 #define BLOCK_NORTHWEST ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
143  | ANGLE_SWtoNW | ANGLE_NWtoNE \
144  | SHARP_WtoNW | SHARP_NtoNW | HOLE )
145 #define BLOCK_NORTH ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW \
146  | BENT_EtoNW | BENT_WtoNE \
147  | BENT_StoNE | BENT_StoNW \
148  | CORNER_NORTHEAST | CORNER_NORTHWEST \
149  | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \
150  | DIAG_NEtoSW | DIAG_SEtoNW \
151  | SHARP_NtoNE | SHARP_NtoNW \
152  | SHARP_EtoNE | SHARP_WtoNW | HOLE )
153 #define BLOCK_EAST ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW \
154  | BENT_NtoSE | BENT_StoNE \
155  | BENT_WtoNE | BENT_WtoSE \
156  | CORNER_NORTHEAST | CORNER_SOUTHEAST \
157  | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \
158  | DIAG_NEtoSW | DIAG_SEtoNW \
159  | SHARP_EtoNE | SHARP_EtoSE \
160  | SHARP_NtoNE | SHARP_StoSE | HOLE )
161 #define BLOCK_SOUTH ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW \
162  | BENT_EtoSW | BENT_WtoSE \
163  | BENT_NtoSE | BENT_NtoSW \
164  | CORNER_SOUTHEAST | CORNER_SOUTHWEST \
165  | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \
166  | DIAG_NEtoSW | DIAG_SEtoNW \
167  | SHARP_StoSE | SHARP_StoSW \
168  | SHARP_EtoSE | SHARP_WtoSW | HOLE )
169 #define BLOCK_WEST ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE \
170  | BENT_NtoSW | BENT_StoNW \
171  | BENT_EtoSW | BENT_EtoNW \
172  | CORNER_SOUTHWEST | CORNER_NORTHWEST \
173  | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \
174  | DIAG_NEtoSW | DIAG_SEtoNW \
175  | SHARP_WtoSW | SHARP_WtoNW \
176  | SHARP_NtoNW | SHARP_StoSW | HOLE )
177 
178 struct block
179 {
180  int r1, c1;
181  long b1;
182  int r2, c2;
183  long b2;
184 };
185 
186 // blocking masks for diagonal traces
187 static struct block blocking[8] =
188 { {
189  0, -1,
191  1, 0,
193  },
194  {
195  0, 0, 0,
196  0, 0, 0
197  },
198  {
199  1, 0,
201  0, 1,
203  },
204  {
205  0, 0, 0,
206  0, 0, 0
207  },
208  {
209  0, 0, 0,
210  0, 0, 0
211  },
212  {
213  0, -1,
215  -1, 0,
217  },
218  {
219  0, 0, 0,
220  0, 0, 0
221  },
222  {
223  -1, 0,
225  0, 1,
227  } };
228 
229 // mask for hole-related blocking effects
230 static struct
231 {
232  long trace;
233  int present;
234 } selfok2[8] =
235 {
236  { HOLE_NORTHWEST, 0 },
237  { HOLE_NORTH, 0 },
238  { HOLE_NORTHEAST, 0 },
239  { HOLE_WEST, 0 },
240  { HOLE_EAST, 0 },
241  { HOLE_SOUTHWEST, 0 },
242  { HOLE_SOUTH, 0 },
243  { HOLE_SOUTHEAST, 0 }
244 };
245 
246 static long newmask[8] =
247 {
248  // patterns to mask out in neighbor cells
249  0,
251  0,
254  0,
256  0
257 };
258 
259 
260 /* Route all traces
261  * :
262  * 1 if OK
263  * -1 if escape (stop being routed) request
264  * -2 if default memory allocation
265  */
266 int PCB_EDIT_FRAME::Solve( AUTOROUTER_CONTEXT& aCtx, int aLayersCount )
267 {
268  int current_net_code;
269  int row_source, col_source, row_target, col_target;
270  int success, nbsucces = 0, nbunsucces = 0;
271  NETINFO_ITEM* net;
272  bool stop = false;
273  wxString msg;
274  int routedCount = 0; // routed ratsnest count
275  bool two_sides = aLayersCount == 2;
276 
277  m_canvas->SetAbortRequest( false );
278 
279  s_Clearance = aCtx.board->GetDesignSettings().GetDefault()->GetClearance();
280 
281  // Prepare the undo command info
282  s_ItemsListPicker.ClearListAndDeleteItems(); // Should not be necessary, but...
283 
284  // go until no more work to do
285  GetWork( &row_source, &col_source, &current_net_code,
286  &row_target, &col_target, &pt_cur_ch ); // First net to route.
287 
288  for( ; row_source != ILLEGAL; GetWork( &row_source, &col_source,
289  &current_net_code, &row_target,
290  &col_target,
291  &pt_cur_ch ) )
292  {
293  // Test to stop routing ( escape key pressed )
294  wxYield();
295 
296  if( m_canvas->GetAbortRequest() )
297  {
298  if( IsOK( this, _( "Abort routing?" ) ) )
299  {
300  success = STOP_FROM_ESC;
301  stop = true;
302  break;
303  }
304  else
305  {
306  m_canvas->SetAbortRequest( false );
307  }
308  }
309 
310  EraseMsgBox();
311 
312  routedCount++;
313  net = aCtx.board->FindNet( current_net_code );
314 
315  if( net )
316  {
317  msg.Printf( wxT( "[%8.8s]" ), GetChars( net->GetNetname() ) );
318  AppendMsgPanel( wxT( "Net route" ), msg, BROWN );
319  msg.Printf( wxT( "%d / %d" ), routedCount, RoutingMatrix.m_RouteCount );
320  AppendMsgPanel( wxT( "Activity" ), msg, BROWN );
321  }
322 
323  segm_oX = aCtx.bbox.GetX() + ( RoutingMatrix.m_GridRouting * col_source );
324  segm_oY = aCtx.bbox.GetY() + ( RoutingMatrix.m_GridRouting * row_source );
325  segm_fX = aCtx.bbox.GetX() + ( RoutingMatrix.m_GridRouting * col_target );
326  segm_fY = aCtx.bbox.GetY() + ( RoutingMatrix.m_GridRouting * row_target );
327 
328  // Draw segment.
329  GRLine( m_canvas->GetClipBox(), aCtx.dc,
331  0, WHITE );
332  pt_cur_ch->m_PadStart->Draw( m_canvas, aCtx.dc, GR_OR | GR_HIGHLIGHT );
333  pt_cur_ch->m_PadEnd->Draw( m_canvas, aCtx.dc, GR_OR | GR_HIGHLIGHT );
334 
335  success = Autoroute_One_Track( aCtx, two_sides, row_source, col_source,
336  row_target, col_target, pt_cur_ch );
337 
338  switch( success )
339  {
340  case NOSUCCESS:
341  pt_cur_ch->m_Status |= CH_UNROUTABLE;
342  nbunsucces++;
343  break;
344 
345  case STOP_FROM_ESC:
346  stop = true;
347  break;
348 
349  case ERR_MEMORY:
350  stop = true;
351  break;
352 
353  default:
354  nbsucces++;
355  break;
356  }
357 
358  msg.Printf( wxT( "%d" ), nbsucces );
359  AppendMsgPanel( wxT( "OK" ), msg, GREEN );
360  msg.Printf( wxT( "%d" ), nbunsucces );
361  AppendMsgPanel( wxT( "Fail" ), msg, RED );
362  msg.Printf( wxT( " %d" ), aCtx.board->GetUnconnectedNetCount() );
363  AppendMsgPanel( wxT( "Not Connected" ), msg, CYAN );
364 
365  // Delete routing from display.
366  pt_cur_ch->m_PadStart->Draw( m_canvas, aCtx.dc, GR_AND );
367  pt_cur_ch->m_PadEnd->Draw( m_canvas, aCtx.dc, GR_AND );
368 
369  if( stop )
370  break;
371  }
372 
373  SaveCopyInUndoList( s_ItemsListPicker, UR_UNSPECIFIED );
374  s_ItemsListPicker.ClearItemsList(); // s_ItemsListPicker is no more owner of picked items
375 
376  return SUCCESS;
377 }
378 
379 
380 /* Route a trace on the BOARD.
381  * Parameters:
382  * 1 side / 2 sides (0 / 1)
383  * Coord source (row, col)
384  * Coord destination (row, col)
385  * Net_code
386  * Pointer to the ratsnest reference
387  *
388  * Returns:
389  * SUCCESS if routed
390  * TRIVIAL_SUCCESS if pads are connected by overlay (no track needed)
391  * If failure NOSUCCESS
392  * Escape STOP_FROM_ESC if demand
393  * ERR_MEMORY if memory allocation failed.
394  */
396  int two_sides,
397  int row_source,
398  int col_source,
399  int row_target,
400  int col_target,
401  RATSNEST_ITEM* pt_rat )
402 {
403  int r, c, side, d, apx_dist, nr, nc;
404  int result, skip;
405  int i;
406  long curcell, newcell, buddy, lastopen, lastclos, lastmove;
407  int newdist, olddir, _self;
408  int current_net_code;
409  int marge;
410  LSET padLayerMaskStart; // Mask layers belonging to the starting pad.
411  LSET padLayerMaskEnd; // Mask layers belonging to the ending pad.
412 
413  LSET topLayerMask( g_Route_Layer_TOP );
414 
415  LSET bottomLayerMask( g_Route_Layer_BOTTOM );
416 
417  LSET routeLayerMask; // Mask two layers for routing.
418 
419  LSET tab_mask[2]; // Enables the calculation of the mask layer being
420  // tested. (side = TOP or BOTTOM)
421  int start_mask_layer = 0;
422  wxString msg;
423 
424  // @todo this could be a bottle neck
425  LSET all_cu = LSET::AllCuMask( ctx.board->GetCopperLayerCount() );
426 
427  wxBusyCursor dummy_cursor; // Set an hourglass cursor while routing a
428  // track
429 
430  result = NOSUCCESS;
431 
432  marge = s_Clearance + ( ctx.pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
433 
434  // clear direction flags
436 
437  if( two_sides )
438  memset( RoutingMatrix.m_DirSide[TOP], FROM_NOWHERE, i );
440 
441  lastopen = lastclos = lastmove = 0;
442 
443  // Set tab_masque[side] for final test of routing.
444  if( two_sides )
445  tab_mask[TOP] = topLayerMask;
446  tab_mask[BOTTOM] = bottomLayerMask;
447 
448  // Set active layers mask.
449  routeLayerMask = topLayerMask | bottomLayerMask;
450 
451  pt_cur_ch = pt_rat;
452 
453  current_net_code = pt_rat->GetNet();
454  padLayerMaskStart = pt_cur_ch->m_PadStart->GetLayerSet();
455 
456  padLayerMaskEnd = pt_cur_ch->m_PadEnd->GetLayerSet();
457 
458 
459  /* First Test if routing possible ie if the pads are accessible
460  * on the routing layers.
461  */
462  if( ( routeLayerMask & padLayerMaskStart ) == 0 )
463  goto end_of_route;
464 
465  if( ( routeLayerMask & padLayerMaskEnd ) == 0 )
466  goto end_of_route;
467 
468  /* Then test if routing possible ie if the pads are accessible
469  * On the routing grid (1 grid point must be in the pad)
470  */
471  {
472  int cX = ( RoutingMatrix.m_GridRouting * col_source ) + ctx.bbox.GetX();
473  int cY = ( RoutingMatrix.m_GridRouting * row_source ) + ctx.bbox.GetY();
474  int dx = pt_cur_ch->m_PadStart->GetSize().x / 2;
475  int dy = pt_cur_ch->m_PadStart->GetSize().y / 2;
476  int px = pt_cur_ch->m_PadStart->GetPosition().x;
477  int py = pt_cur_ch->m_PadStart->GetPosition().y;
478 
479  if( ( ( int( pt_cur_ch->m_PadStart->GetOrientation() ) / 900 ) & 1 ) != 0 )
480  std::swap( dx, dy );
481 
482  if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
483  goto end_of_route;
484 
485  cX = ( RoutingMatrix.m_GridRouting * col_target ) + ctx.bbox.GetX();
486  cY = ( RoutingMatrix.m_GridRouting * row_target ) + ctx.bbox.GetY();
487  dx = pt_cur_ch->m_PadEnd->GetSize().x / 2;
488  dy = pt_cur_ch->m_PadEnd->GetSize().y / 2;
489  px = pt_cur_ch->m_PadEnd->GetPosition().x;
490  py = pt_cur_ch->m_PadEnd->GetPosition().y;
491 
492  if( ( ( int( pt_cur_ch->m_PadEnd->GetOrientation() ) / 900) & 1 ) != 0 )
493  std::swap( dx, dy );
494 
495  if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
496  goto end_of_route;
497  }
498 
499  // Test the trivial case: direct connection overlay pads.
500  if( row_source == row_target && col_source == col_target &&
501  ( padLayerMaskEnd & padLayerMaskStart & all_cu ).any() )
502  {
503  result = TRIVIAL_SUCCESS;
504  goto end_of_route;
505  }
506 
507  // Placing the bit to remove obstacles on 2 pads to a link.
508  ctx.pcbframe->SetStatusText( wxT( "Gen Cells" ) );
509 
510  PlacePad( pt_cur_ch->m_PadStart, CURRENT_PAD, marge, WRITE_OR_CELL );
511  PlacePad( pt_cur_ch->m_PadEnd, CURRENT_PAD, marge, WRITE_OR_CELL );
512 
513  // Regenerates the remaining barriers (which may encroach on the
514  // placement bits precedent)
515  i = ctx.board->GetPadCount();
516 
517  for( unsigned ii = 0; ii < ctx.board->GetPadCount(); ii++ )
518  {
519  D_PAD* ptr = ctx.board->GetPad( ii );
520 
521  if( ( pt_cur_ch->m_PadStart != ptr ) && ( pt_cur_ch->m_PadEnd != ptr ) )
522  {
523  PlacePad( ptr, ~CURRENT_PAD, marge, WRITE_AND_CELL );
524  }
525  }
526 
527  InitQueue(); // initialize the search queue
528  apx_dist = RoutingMatrix.GetApxDist( row_source, col_source, row_target, col_target );
529 
530  // Initialize first search.
531  if( two_sides ) // Preferred orientation.
532  {
533  if( abs( row_target - row_source ) > abs( col_target - col_source ) )
534  {
535  if( ( padLayerMaskStart & topLayerMask ).any() )
536  {
537  start_mask_layer = 2;
538 
539  if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
540  row_target, col_target ) == 0 )
541  {
542  return ERR_MEMORY;
543  }
544  }
545 
546  if( ( padLayerMaskStart & bottomLayerMask ).any() )
547  {
548  start_mask_layer |= 1;
549 
550  if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
551  row_target, col_target ) == 0 )
552  {
553  return ERR_MEMORY;
554  }
555  }
556  }
557  else
558  {
559  if( ( padLayerMaskStart & bottomLayerMask ).any() )
560  {
561  start_mask_layer = 1;
562 
563  if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
564  row_target, col_target ) == 0 )
565  {
566  return ERR_MEMORY;
567  }
568  }
569 
570  if( ( padLayerMaskStart & topLayerMask ).any() )
571  {
572  start_mask_layer |= 2;
573 
574  if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
575  row_target, col_target ) == 0 )
576  {
577  return ERR_MEMORY;
578  }
579  }
580  }
581  }
582  else if( ( padLayerMaskStart & bottomLayerMask ).any() )
583  {
584  start_mask_layer = 1;
585 
586  if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, row_target, col_target ) == 0 )
587  {
588  return ERR_MEMORY;
589  }
590  }
591 
592  // search until success or we exhaust all possibilities
593  GetQueue( &r, &c, &side, &d, &apx_dist );
594 
595  for( ; r != ILLEGAL; GetQueue( &r, &c, &side, &d, &apx_dist ) )
596  {
597  curcell = RoutingMatrix.GetCell( r, c, side );
598 
599  if( curcell & CURRENT_PAD )
600  curcell &= ~HOLE;
601 
602  if( (r == row_target) && (c == col_target) // success if layer OK
603  && (tab_mask[side] & padLayerMaskEnd).any() )
604  {
605  // Remove link.
606  GRSetDrawMode( ctx.dc, GR_XOR );
607  GRLine( ctx.pcbframe->GetCanvas()->GetClipBox(),
608  ctx.dc,
609  segm_oX, segm_oY,
610  segm_fX, segm_fY,
611  0,
612  WHITE );
613 
614  // Generate trace.
615  if( Retrace( ctx, row_source, col_source,
616  row_target, col_target, side, current_net_code ) )
617  {
618  result = SUCCESS; // Success : Route OK
619  }
620 
621  break; // Routing complete.
622  }
623 
624  if( ctx.pcbframe->GetCanvas()->GetAbortRequest() )
625  {
626  result = STOP_FROM_ESC;
627  break;
628  }
629 
630  // report every COUNT new nodes or so
631  #define COUNT 20000
632 
633  if( ( OpenNodes - lastopen > COUNT )
634  || ( ClosNodes - lastclos > COUNT )
635  || ( MoveNodes - lastmove > COUNT ) )
636  {
637  lastopen = OpenNodes;
638  lastclos = ClosNodes;
639  lastmove = MoveNodes;
640  msg.Printf( wxT( "Activity: Open %d Closed %d Moved %d" ),
642  ctx.pcbframe->SetStatusText( msg );
643  }
644 
645  _self = 0;
646 
647  if( curcell & HOLE )
648  {
649  _self = 5;
650 
651  // set 'present' bits
652  for( i = 0; i < 8; i++ )
653  {
654  selfok2[i].present = 0;
655 
656  if( curcell & selfok2[i].trace )
657  selfok2[i].present = 1;
658  }
659  }
660 
661  for( i = 0; i < 8; i++ ) // consider neighbors
662  {
663  nr = r + delta[i][0];
664  nc = c + delta[i][1];
665 
666  // off the edge?
667  if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
668  nc < 0 || nc >= RoutingMatrix.m_Ncols )
669  continue; // off the edge
670 
671  if( _self == 5 && selfok2[i].present )
672  continue;
673 
674  newcell = RoutingMatrix.GetCell( nr, nc, side );
675 
676  if( newcell & CURRENT_PAD )
677  newcell &= ~HOLE;
678 
679  // check for non-target hole
680  if( newcell & HOLE )
681  {
682  if( nr != row_target || nc != col_target )
683  continue;
684  }
685  // check for traces
686  else if( newcell & HOLE & ~(newmask[i]) )
687  {
688  continue;
689  }
690 
691  // check blocking on corner neighbors
692  if( delta[i][0] && delta[i][1] )
693  {
694  // check first buddy
695  buddy = RoutingMatrix.GetCell( r + blocking[i].r1, c + blocking[i].c1, side );
696 
697  if( buddy & CURRENT_PAD )
698  buddy &= ~HOLE;
699 
700  if( buddy & HOLE )
701  continue;
702 
703 // if (buddy & (blocking[i].b1)) continue;
704  // check second buddy
705  buddy = RoutingMatrix.GetCell( r + blocking[i].r2, c + blocking[i].c2, side );
706 
707  if( buddy & CURRENT_PAD )
708  buddy &= ~HOLE;
709 
710  if( buddy & HOLE )
711  continue;
712 
713 // if (buddy & (blocking[i].b2)) continue;
714  }
715 
716  olddir = RoutingMatrix.GetDir( r, c, side );
717  newdist = d + RoutingMatrix.CalcDist( ndir[i], olddir,
718  ( olddir == FROM_OTHERSIDE ) ?
719  RoutingMatrix.GetDir( r, c, 1 - side ) : 0, side );
720 
721  // if (a) not visited yet, or (b) we have
722  // found a better path, add it to queue
723  if( !RoutingMatrix.GetDir( nr, nc, side ) )
724  {
725  RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
726  RoutingMatrix.SetDist( nr, nc, side, newdist );
727 
728  if( SetQueue( nr, nc, side, newdist,
729  RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
730  row_target, col_target ) == 0 )
731  {
732  return ERR_MEMORY;
733  }
734  }
735  else if( newdist < RoutingMatrix.GetDist( nr, nc, side ) )
736  {
737  RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
738  RoutingMatrix.SetDist( nr, nc, side, newdist );
739  ReSetQueue( nr, nc, side, newdist,
740  RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
741  row_target, col_target );
742  }
743  }
744 
745  //* Test the other layer. *
746  if( two_sides )
747  {
748  olddir = RoutingMatrix.GetDir( r, c, side );
749 
750  if( olddir == FROM_OTHERSIDE )
751  continue; // useless move, so don't bother
752 
753  if( curcell ) // can't drill via if anything here
754  continue;
755 
756  // check for holes or traces on other side
757  if( ( newcell = RoutingMatrix.GetCell( r, c, 1 - side ) ) != 0 )
758  continue;
759 
760  // check for nearby holes or traces on both sides
761  for( skip = 0, i = 0; i < 8; i++ )
762  {
763  nr = r + delta[i][0]; nc = c + delta[i][1];
764 
765  if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
766  nc < 0 || nc >= RoutingMatrix.m_Ncols )
767  continue; // off the edge !!
768 
769  if( RoutingMatrix.GetCell( nr, nc, side ) /* & blocking2[i] */ )
770  {
771  skip = 1; // can't drill via here
772  break;
773  }
774 
775  if( RoutingMatrix.GetCell( nr, nc, 1 - side ) /* & blocking2[i] */ )
776  {
777  skip = 1; // can't drill via here
778  break;
779  }
780  }
781 
782  if( skip ) // neighboring hole or trace?
783  continue; // yes, can't drill via here
784 
785  newdist = d + RoutingMatrix.CalcDist( FROM_OTHERSIDE, olddir, 0, side );
786 
787  /* if (a) not visited yet,
788  * or (b) we have found a better path,
789  * add it to queue */
790  if( !RoutingMatrix.GetDir( r, c, 1 - side ) )
791  {
792  RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
793  RoutingMatrix.SetDist( r, c, 1 - side, newdist );
794 
795  if( SetQueue( r, c, 1 - side, newdist, apx_dist, row_target, col_target ) == 0 )
796  {
797  return ERR_MEMORY;
798  }
799  }
800  else if( newdist < RoutingMatrix.GetDist( r, c, 1 - side ) )
801  {
802  RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
803  RoutingMatrix.SetDist( r, c, 1 - side, newdist );
804  ReSetQueue( r, c,
805  1 - side,
806  newdist,
807  apx_dist,
808  row_target,
809  col_target );
810  }
811  } // Finished attempt to route on other layer.
812  }
813 
814 end_of_route:
815  PlacePad( pt_cur_ch->m_PadStart, ~CURRENT_PAD, marge, WRITE_AND_CELL );
816  PlacePad( pt_cur_ch->m_PadEnd, ~CURRENT_PAD, marge, WRITE_AND_CELL );
817 
818  msg.Printf( wxT( "Activity: Open %d Closed %d Moved %d"),
820  ctx.pcbframe->SetStatusText( msg );
821 
822  return result;
823 }
824 
825 
826 static long bit[8][9] =
827 {
828  // OT=Otherside
829  // N, NE, E, SE, S, SW, W, NW, OT
830 // N
831  { LINE_VERTICAL,
832  BENT_StoNE,
834  SHARP_StoSE,
835  0,
836  SHARP_StoSW,
838  BENT_StoNW,
839  ( HOLE | HOLE_SOUTH )
840  },
841 // NE
842  {
843  BENT_NtoSW,
844  DIAG_NEtoSW,
845  BENT_EtoSW,
846  ANGLE_SEtoSW,
847  SHARP_StoSW,
848  0,
849  SHARP_WtoSW,
850  ANGLE_SWtoNW,
851  ( HOLE | HOLE_SOUTHWEST )
852  },
853 // E
854  {
856  BENT_WtoNE,
858  BENT_WtoSE,
860  SHARP_WtoSW,
861  0,
862  SHARP_WtoNW,
863  ( HOLE | HOLE_WEST )
864  },
865 // SE
866  {
867  SHARP_NtoNW,
868  ANGLE_NWtoNE,
869  BENT_EtoNW,
870  DIAG_SEtoNW,
871  BENT_StoNW,
872  ANGLE_SWtoNW,
873  SHARP_WtoNW,
874  0,
875  ( HOLE | HOLE_NORTHWEST )
876  },
877 // S
878  {
879  0,
880  SHARP_NtoNE,
882  BENT_NtoSE,
884  BENT_NtoSW,
886  SHARP_NtoNW,
887  ( HOLE | HOLE_NORTH )
888  },
889 // SW
890  {
891  SHARP_NtoNE,
892  0,
893  SHARP_EtoNE,
894  ANGLE_NEtoSE,
895  BENT_StoNE,
896  DIAG_NEtoSW,
897  BENT_WtoNE,
898  ANGLE_NWtoNE,
899  ( HOLE | HOLE_NORTHEAST )
900  },
901 // W
902  {
904  SHARP_EtoNE,
905  0,
906  SHARP_EtoSE,
908  BENT_EtoSW,
910  BENT_EtoNW,
911  ( HOLE | HOLE_EAST )
912  },
913 // NW
914  {
915  BENT_NtoSE,
916  ANGLE_NEtoSE,
917  SHARP_EtoSE,
918  0,
919  SHARP_StoSE,
920  ANGLE_SEtoSW,
921  BENT_WtoSE,
922  DIAG_SEtoNW,
923  ( HOLE | HOLE_SOUTHEAST )
924  }
925 };
926 
927 
928 /* work from target back to source, actually laying the traces
929  * Parameters:
930  * start on side target_side, of coordinates row_target, col_target.
931  * arrive on side masque_layer_start, coordinate row_source, col_source
932  * The search is done in reverse routing, the point of arrival (target) to
933  * the starting point (source)
934  * The router.
935  *
936  * Target_side = symbol (TOP / BOTTOM) of departure
937  * = Mask_layer_source mask layers Arrival
938  *
939  * Returns:
940  * 0 if error
941  * > 0 if Ok
942  */
943 static int Retrace( AUTOROUTER_CONTEXT& ctx,
944  int row_source, int col_source,
945  int row_target, int col_target, int target_side,
946  int current_net_code )
947 {
948  int r0, c0, s0;
949  int r1, c1, s1; // row, col, starting side.
950  int r2, c2, s2; // row, col, ending side.
951  int x, y = -1;
952  long b;
953 
954  r1 = row_target;
955  c1 = col_target; // start point is target ( end point is source )
956  s1 = target_side;
957  r0 = c0 = s0 = ILLEGAL;
958 
959  wxASSERT( g_CurrentTrackList.GetCount() == 0 );
960 
961  do
962  {
963  // find where we came from to get here
964  r2 = r1; c2 = c1; s2 = s1;
965  x = RoutingMatrix.GetDir( r1, c1, s1 );
966 
967  switch( x )
968  {
969  case FROM_NORTH:
970  r2++;
971  break;
972 
973  case FROM_EAST:
974  c2++;
975  break;
976 
977  case FROM_SOUTH:
978  r2--;
979  break;
980 
981  case FROM_WEST:
982  c2--;
983  break;
984 
985  case FROM_NORTHEAST:
986  r2++;
987  c2++;
988  break;
989 
990  case FROM_SOUTHEAST:
991  r2--;
992  c2++;
993  break;
994 
995  case FROM_SOUTHWEST:
996  r2--;
997  c2--;
998  break;
999 
1000  case FROM_NORTHWEST:
1001  r2++;
1002  c2--;
1003  break;
1004 
1005  case FROM_OTHERSIDE:
1006  s2 = 1 - s2;
1007  break;
1008 
1009  default:
1010  wxMessageBox( wxT( "Retrace: internal error: no way back" ) );
1011  return 0;
1012  }
1013 
1014  if( r0 != ILLEGAL )
1015  y = RoutingMatrix.GetDir( r0, c0, s0 );
1016 
1017  // see if target or hole
1018  if( ( ( r1 == row_target ) && ( c1 == col_target ) ) || ( s1 != s0 ) )
1019  {
1020  int p_dir;
1021 
1022  switch( x )
1023  {
1024  case FROM_NORTH:
1025  p_dir = HOLE_NORTH;
1026  break;
1027 
1028  case FROM_EAST:
1029  p_dir = HOLE_EAST;
1030  break;
1031 
1032  case FROM_SOUTH:
1033  p_dir = HOLE_SOUTH;
1034  break;
1035 
1036  case FROM_WEST:
1037  p_dir = HOLE_WEST;
1038  break;
1039 
1040  case FROM_NORTHEAST:
1041  p_dir = HOLE_NORTHEAST;
1042  break;
1043 
1044  case FROM_SOUTHEAST:
1045  p_dir = HOLE_SOUTHEAST;
1046  break;
1047 
1048  case FROM_SOUTHWEST:
1049  p_dir = HOLE_SOUTHWEST;
1050  break;
1051 
1052  case FROM_NORTHWEST:
1053  p_dir = HOLE_NORTHWEST;
1054  break;
1055 
1056  case FROM_OTHERSIDE:
1057  default:
1058  DisplayError( ctx.pcbframe, wxT( "Retrace: error 1" ) );
1059  return 0;
1060  }
1061 
1062  OrCell_Trace( ctx, r1, c1, s1, p_dir, current_net_code );
1063  }
1064  else
1065  {
1066  if( ( y == FROM_NORTH || y == FROM_NORTHEAST
1067  || y == FROM_EAST || y == FROM_SOUTHEAST
1068  || y == FROM_SOUTH || y == FROM_SOUTHWEST
1069  || y == FROM_WEST || y == FROM_NORTHWEST )
1070  && ( x == FROM_NORTH || x == FROM_NORTHEAST
1071  || x == FROM_EAST || x == FROM_SOUTHEAST
1072  || x == FROM_SOUTH || x == FROM_SOUTHWEST
1073  || x == FROM_WEST || x == FROM_NORTHWEST
1074  || x == FROM_OTHERSIDE )
1075  && ( ( b = bit[y - 1][x - 1] ) != 0 ) )
1076  {
1077  OrCell_Trace( ctx, r1, c1, s1, b, current_net_code );
1078 
1079  if( b & HOLE )
1080  OrCell_Trace( ctx, r2, c2, s2, HOLE, current_net_code );
1081  }
1082  else
1083  {
1084  wxMessageBox( wxT( "Retrace: error 2" ) );
1085  return 0;
1086  }
1087  }
1088 
1089  if( ( r2 == row_source ) && ( c2 == col_source ) ) // see if source
1090  {
1091  int p_dir;
1092 
1093  switch( x )
1094  {
1095  case FROM_NORTH:
1096  p_dir = HOLE_SOUTH;
1097  break;
1098 
1099  case FROM_EAST:
1100  p_dir = HOLE_WEST;
1101  break;
1102 
1103  case FROM_SOUTH:
1104  p_dir = HOLE_NORTH;
1105  break;
1106 
1107  case FROM_WEST:
1108  p_dir = HOLE_EAST;
1109  break;
1110 
1111  case FROM_NORTHEAST:
1112  p_dir = HOLE_SOUTHWEST;
1113  break;
1114 
1115  case FROM_SOUTHEAST:
1116  p_dir = HOLE_NORTHWEST;
1117  break;
1118 
1119  case FROM_SOUTHWEST:
1120  p_dir = HOLE_NORTHEAST;
1121  break;
1122 
1123  case FROM_NORTHWEST:
1124  p_dir = HOLE_SOUTHEAST;
1125  break;
1126 
1127  case FROM_OTHERSIDE:
1128  default:
1129  wxMessageBox( wxT( "Retrace: error 3" ) );
1130  return 0;
1131  }
1132 
1133  OrCell_Trace( ctx, r2, c2, s2, p_dir, current_net_code );
1134  }
1135 
1136  // move to next cell
1137  r0 = r1;
1138  c0 = c1;
1139  s0 = s1;
1140  r1 = r2;
1141  c1 = c2;
1142  s1 = s2;
1143  } while( !( ( r2 == row_source ) && ( c2 == col_source ) ) );
1144 
1145  AddNewTrace( ctx );
1146  return 1;
1147 }
1148 
1149 
1150 /* This function is used by Retrace and read the autorouting matrix data cells to create
1151  * the real track on the physical board
1152  */
1153 static void OrCell_Trace( AUTOROUTER_CONTEXT& ctx, int col, int row,
1154  int side, int orient, int current_net_code )
1155 {
1156  if( orient == HOLE ) // placement of a via
1157  {
1158  VIA* newVia = new VIA( ctx.board );
1159 
1160  g_CurrentTrackList.PushBack( newVia );
1161 
1162  g_CurrentTrackSegment->SetState( TRACK_AR, true );
1163  g_CurrentTrackSegment->SetLayer( F_Cu );
1164 
1166  ctx.bbox.GetY() + RoutingMatrix.m_GridRouting * col ) );
1167  g_CurrentTrackSegment->SetEnd( g_CurrentTrackSegment->GetStart() );
1168 
1171 
1172  g_CurrentTrackSegment->SetNetCode( current_net_code );
1173  }
1174  else // placement of a standard segment
1175  {
1176  TRACK* newTrack = new TRACK( ctx.board );
1177  int dx0, dy0, dx1, dy1;
1178 
1179  g_CurrentTrackList.PushBack( newTrack );
1180 
1182 
1183  if( side == TOP )
1185 
1186  g_CurrentTrackSegment->SetState( TRACK_AR, true );
1188  ctx.bbox.GetY() + RoutingMatrix.m_GridRouting * col ) );
1189  g_CurrentTrackSegment->SetNetCode( current_net_code );
1190 
1191  if( g_CurrentTrackSegment->Back() == NULL ) // Start trace.
1192  {
1193  g_CurrentTrackSegment->SetStart( wxPoint( segm_fX, segm_fY ) );
1194 
1195  // Placement on the center of the pad if outside grid.
1196  dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
1197  dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1198 
1199  dx0 = pt_cur_ch->m_PadEnd->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
1200  dy0 = pt_cur_ch->m_PadEnd->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1201 
1202  // If aligned, change the origin point.
1203  if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1204  {
1205  g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
1206  }
1207  else // Creation of a supplemental segment
1208  {
1209  g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
1210 
1211  newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1212  newTrack->SetStart( g_CurrentTrackSegment->GetEnd());
1213 
1214  g_CurrentTrackList.PushBack( newTrack );
1215  }
1216  }
1217  else
1218  {
1219  if( g_CurrentTrackSegment->Back() )
1220  {
1221  g_CurrentTrackSegment->SetStart( g_CurrentTrackSegment->Back()->GetEnd() );
1222  }
1223  }
1224 
1226 
1227  if( g_CurrentTrackSegment->GetStart() != g_CurrentTrackSegment->GetEnd() )
1228  {
1229  // Reduce aligned segments by one.
1230  TRACK* oldTrack = g_CurrentTrackSegment->Back();
1231 
1232  if( oldTrack && oldTrack->Type() != PCB_VIA_T )
1233  {
1234  dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
1235  dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1236 
1237  dx0 = oldTrack->GetEnd().x - oldTrack->GetStart().x;
1238  dy0 = oldTrack->GetEnd().y - oldTrack->GetStart().y;
1239 
1240  if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1241  {
1242  oldTrack->SetEnd( g_CurrentTrackSegment->GetEnd() );
1243 
1244  delete g_CurrentTrackList.PopBack();
1245  }
1246  }
1247  }
1248  }
1249 }
1250 
1251 
1252 /* Insert the new track created in the list of tracks.
1253  * amend the points of beginning and end of the track so that they are
1254  * connected
1255  * Center on pads even if they are off grid.
1256  */
1257 static void AddNewTrace( AUTOROUTER_CONTEXT& ctx )
1258 {
1259  if( g_FirstTrackSegment == NULL )
1260  return;
1261 
1262  int dx0, dy0, dx1, dy1;
1263  int marge, via_marge;
1264  EDA_DRAW_PANEL* panel = ctx.pcbframe->GetCanvas();
1265  PCB_SCREEN* screen = ctx.pcbframe->GetScreen();
1266 
1267  marge = s_Clearance + ( ctx.pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
1268  via_marge = s_Clearance + ( ctx.pcbframe->GetDesignSettings().GetCurrentViaSize() / 2 );
1269 
1270  dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
1271  dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1272 
1273  // Place on center of pad if off grid.
1274  dx0 = pt_cur_ch->m_PadStart->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
1275  dy0 = pt_cur_ch->m_PadStart->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1276 
1277  // If aligned, change the origin point.
1278  if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1279  {
1280  g_CurrentTrackSegment->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
1281  }
1282  else
1283  {
1284  TRACK* newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1285 
1286  newTrack->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
1287  newTrack->SetStart( g_CurrentTrackSegment->GetEnd() );
1288 
1289  g_CurrentTrackList.PushBack( newTrack );
1290  }
1291 
1293  ENDPOINT_START );
1294 
1295  if( g_FirstTrackSegment->start )
1296  g_FirstTrackSegment->SetState( BEGIN_ONPAD, true );
1297 
1299  ENDPOINT_END );
1300 
1301  if( g_CurrentTrackSegment->end )
1302  g_CurrentTrackSegment->SetState( END_ONPAD, true );
1303 
1304  // Out the new track on the matrix board
1305  for( TRACK* track = g_FirstTrackSegment; track; track = track->Next() )
1306  {
1307  TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
1308  TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
1309  }
1310 
1311  // Insert new segments in real board
1312  int netcode = g_FirstTrackSegment->GetNetCode();
1313  TRACK* firstTrack = g_FirstTrackSegment;
1314  int newCount = g_CurrentTrackList.GetCount();
1315 
1316  // Put entire new current segment list in BOARD
1317  TRACK* track;
1318  TRACK* insertBeforeMe = g_CurrentTrackSegment->GetBestInsertPoint( ctx.board );
1319 
1320  while( ( track = g_CurrentTrackList.PopFront() ) != NULL )
1321  {
1322  ITEM_PICKER picker( track, UR_NEW );
1323  s_ItemsListPicker.PushItem( picker );
1324  ctx.board->m_Track.Insert( track, insertBeforeMe );
1325  }
1326 
1327  DrawTraces( panel, ctx.dc, firstTrack, newCount, GR_OR );
1328 
1329  ctx.pcbframe->TestNetConnection( ctx.dc, netcode );
1330 
1331  screen->SetModify();
1332 }
#define FROM_NORTHWEST
Definition: cell.h:111
int r2
Definition: solve.cpp:182
#define FROM_OTHERSIDE
Definition: cell.h:112
BOARD * board
Board to be routed
Definition: autorout.h:91
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Function AllCuMask returns a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:639
#define g_FirstTrackSegment
first segment created
Definition: pcbnew.h:102
#define g_CurrentTrackSegment
most recently created segment
Definition: pcbnew.h:101
KICAD_T Type() const
Function Type()
Definition: base_struct.h:198
#define VIA_IMPOSSIBLE
Definition: cell.h:48
DIR_CELL * m_DirSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:110
int CalcDist(int x, int y, int z, int side)
Definition: dist.cpp:138
int c1
Definition: solve.cpp:180
#define CURRENT_PAD
Definition: cell.h:49
#define FROM_NORTHEAST
Definition: cell.h:105
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:78
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:79
VIATYPE_T m_CurrentViaType
via type (VIA_BLIND_BURIED, VIA_THROUGH VIA_MICROVIA)
#define SUCCESS
Definition: solve.cpp:93
#define HOLE_NORTHWEST
Definition: cell.h:60
NETCLASSPTR GetDefault() const
Function GetDefault.
#define SHARP_EtoSE
Definition: cell.h:95
#define BLOCK_SOUTHEAST
Definition: solve.cpp:136
long trace
Definition: solve.cpp:232
#define BENT_EtoSW
Definition: cell.h:79
int present
Definition: solve.cpp:233
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: base_struct.h:133
void GRSetDrawMode(wxDC *DC, GR_DRAWMODE draw_mode)
Definition: gr_basic.cpp:290
unsigned GetUnconnectedNetCount() const
Function GetUnconnectedNetCount.
Definition: class_board.h:727
void SetViaType(VIATYPE_T aViaType)
Definition: class_track.h:447
#define BENT_WtoSE
Definition: cell.h:84
This file is part of the common library.
#define CH_UNROUTABLE
Definition: class_netinfo.h:58
void SetEnd(const wxPoint &aEnd)
Definition: class_track.h:117
DLIST< TRACK > g_CurrentTrackList
Definition: pcbnew.cpp:98
EDA_DRAW_PANEL * GetCanvas()
Definition: draw_frame.h:299
void TestNetConnection(wxDC *aDC, int aNetCode)
Function TestNetConnection tests the connections relative to aNetCode.
Definition: connect.cpp:786
#define ANGLE_SWtoNW
Definition: cell.h:89
void Draw(EDA_DRAW_PANEL *aPanel, wxDC *aDC, GR_DRAWMODE aDrawMode, const wxPoint &aOffset=ZeroOffset) override
Function Draw BOARD_ITEMs have their own color information.
static const int ndir[8]
Definition: solve.cpp:124
int OpenNodes
Definition: solve.cpp:85
#define SHARP_NtoNE
Definition: cell.h:93
void GRLine(EDA_RECT *ClipBox, wxDC *DC, int x1, int y1, int x2, int y2, int width, COLOR4D Color)
Definition: gr_basic.cpp:352
#define ANGLE_SEtoSW
Definition: cell.h:88
Class BOARD to handle a board.
#define CORNER_NORTHWEST
Definition: cell.h:70
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
int GetCopperLayerCount() const
Function GetCopperLayerCount.
#define FROM_SOUTH
Definition: cell.h:108
#define ANGLE_NWtoNE
Definition: cell.h:90
int GetDir(int aRow, int aCol, int aSide)
#define FROM_NOWHERE
Definition: cell.h:103
void PushItem(const ITEM_PICKER &aItem)
Function PushItem pushes aItem to the top of the list.
#define WRITE_CELL
Definition: autorout.h:190
#define FROM_NORTH
Definition: cell.h:104
#define FROM_EAST
Definition: cell.h:106
#define ILLEGAL
Definition: autorout.h:52
#define TRIVIAL_SUCCESS
Definition: solve.cpp:94
void ReSetQueue(int, int, int, int, int, int, int)
Definition: queue.cpp:185
#define STOP_FROM_ESC
Definition: solve.cpp:91
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: base_struct.h:132
int GetCurrentViaSize() const
Function GetCurrentViaSize.
static struct @0 selfok2[8]
#define abs(a)
Definition: auxiliary.h:84
#define SHARP_WtoSW
Definition: cell.h:98
static const int delta[8][2]
Definition: solve.cpp:112
const wxPoint & GetEnd() const
Definition: class_track.h:118
#define WRITE_AND_CELL
Definition: autorout.h:193
Functions relatives to tracks, vias and segments used to fill zones.
int GetApxDist(int r1, int c1, int r2, int c2)
Definition: dist.cpp:42
#define HOLE_SOUTH
Definition: cell.h:57
This file contains miscellaneous commonly used macros and functions.
#define HOLE_EAST
Definition: cell.h:55
void PushBack(T *aNewElement)
Function PushBack puts aNewElement at the end of the list sequence.
Definition: dlist.h:250
#define NOSUCCESS
Definition: solve.cpp:90
#define TOP
Definition: autorout.h:49
void InitQueue()
Definition: queue.cpp:75
int c2
Definition: solve.cpp:182
void GetQueue(int *, int *, int *, int *, int *)
Definition: queue.cpp:91
#define BLOCK_SOUTHWEST
Definition: solve.cpp:139
D_PAD * m_PadEnd
Definition: class_netinfo.h:76
int MaxNodes
Definition: solve.cpp:88
#define SHARP_EtoNE
Definition: cell.h:94
static void AddNewTrace(AUTOROUTER_CONTEXT &ctx)
Definition: solve.cpp:1257
static RATSNEST_ITEM * pt_cur_ch
Definition: solve.cpp:80
static int segm_fX
Definition: solve.cpp:78
Class LSET is a set of PCB_LAYER_IDs.
static struct block blocking[8]
Definition: solve.cpp:187
#define BENT_NtoSW
Definition: cell.h:78
#define HOLE_NORTH
Definition: cell.h:53
#define FROM_SOUTHWEST
Definition: cell.h:109
#define HOLE_NORTHEAST
Definition: cell.h:54
void EraseMsgBox()
Definition: draw_frame.cpp:250
int r1
Definition: solve.cpp:180
const wxPoint & GetStart() const
Definition: class_track.h:121
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
LSET GetLayerSet() const override
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
Definition: class_pad.h:235
#define ERR_MEMORY
Definition: solve.cpp:92
#define BENT_StoNW
Definition: cell.h:81
Definition: colors.h:59
DIST_CELL GetDist(int aRow, int aCol, int aSide)
static void OrCell_Trace(AUTOROUTER_CONTEXT &ctx, int col, int row, int side, int orient, int current_net_code)
Definition: solve.cpp:1153
long b1
Definition: solve.cpp:181
const wxSize & GetSize() const
Definition: class_pad.h:182
BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings.
Definition: class_board.h:530
#define DIAG_NEtoSW
Definition: cell.h:73
EDA_RECT * GetClipBox()
virtual BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings returns the BOARD_DESIGN_SETTINGS for the BOARD owned by this frame...
Definition: colors.h:60
#define BENT_NtoSE
Definition: cell.h:77
int GetNet() const
Function GetNet.
Definition: class_netinfo.h:85
void SetDir(int aRow, int aCol, int aSide, int aDir)
#define BLOCK_NORTHEAST
Definition: solve.cpp:133
Class PICKED_ITEMS_LIST is a holder to handle information on schematic or board items.
void SaveCopyInUndoList(BOARD_ITEM *aItemToCopy, UNDO_REDO_T aTypeCommand, const wxPoint &aTransformPoint=wxPoint(0, 0)) override
Function SaveCopyInUndoList Creates a new entry in undo list of commands.
Definition: undo_redo.cpp:172
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
#define BENT_StoNE
Definition: cell.h:82
static long newmask[8]
Definition: solve.cpp:246
wxDC * dc
Drawing context
Definition: autorout.h:97
unsigned GetPadCount() const
Function GetPadCount.
Definition: class_board.h:741
Definition: solve.cpp:178
void SetAbortRequest(bool aAbortRequest)
#define TRACK_AR
Pcbnew: autorouted track.
Definition: base_struct.h:129
int ClosNodes
Definition: solve.cpp:86
D_PAD * m_PadStart
Definition: class_netinfo.h:75
#define CORNER_SOUTHEAST
Definition: cell.h:68
Definition: gr_basic.h:42
int MoveNodes
Definition: solve.cpp:87
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
static int s_Clearance
Definition: solve.cpp:81
int Solve(AUTOROUTER_CONTEXT &aCtx, int aLayersCount)
Definition: solve.cpp:266
const EDA_RECT bbox
Cached board bounding box
Definition: autorout.h:94
#define HOLE_SOUTHWEST
Definition: cell.h:58
#define CORNER_SOUTHWEST
Definition: cell.h:69
PCB_EDIT_FRAME * pcbframe
Parent frame
Definition: autorout.h:88
EDA_DRAW_PANEL * m_canvas
The area to draw on.
Definition: draw_frame.h:92
void AppendMsgPanel(const wxString &textUpper, const wxString &textLower, COLOR4D color, int pad=6)
Append a message to the message panel.
Definition: draw_frame.cpp:734
Class NETINFO_ITEM handles the data for a net.
bool GetAbortRequest() const
void GetWork(int *, int *, int *, int *, int *, RATSNEST_ITEM **)
Definition: work.cpp:102
T * PopBack()
Definition: dlist.h:228
#define HOLE_SOUTHEAST
Definition: cell.h:56
#define SHARP_StoSE
Definition: cell.h:96
#define SHARP_WtoNW
Definition: cell.h:99
static const wxChar * GetChars(const wxString &s)
Function GetChars returns a wxChar* to the actual wxChar* data within a wxString, and is helpful for ...
Definition: macros.h:92
Definition: colors.h:58
void SetDist(int aRow, int aCol, int aSide, DIST_CELL)
long b2
Definition: solve.cpp:183
#define ANGLE_NEtoSE
Definition: cell.h:87
#define LINE_VERTICAL
Definition: cell.h:64
static int segm_fY
Definition: solve.cpp:78
#define CORNER_NORTHEAST
Definition: cell.h:67
double GetOrientation() const
Function GetOrientation returns the rotation angle of the pad in tenths of degrees, but soon degrees.
Definition: class_pad.h:214
int GetX() const
#define COUNT
static long bit[8][9]
Definition: solve.cpp:826
NETINFO_ITEM * FindNet(int aNetcode) const
Function FindNet searches for a net with the given netcode.
void ClearItemsList()
Function ClearItemsList deletes only the list of pickers, NOT the picked data itself.
#define BENT_EtoNW
Definition: cell.h:80
PCB_SCREEN * GetScreen() const override
Function GetScreen returns a pointer to a BASE_SCREEN or one of its derivatives.
char DIR_CELL
Definition: autorout.h:83
Definition: colors.h:49
int GetY() const
void PlacePad(D_PAD *pt_pad, int type, int marge, int op_logic)
Definition: graphpcb.cpp:87
unsigned GetCount() const
Function GetCount returns the number of elements in the list.
Definition: dlist.h:126
static PICKED_ITEMS_LIST s_ItemsListPicker
Definition: solve.cpp:83
void SetStart(const wxPoint &aStart)
Definition: class_track.h:120
static int segm_oY
Definition: solve.cpp:77
#define BOTTOM
Definition: autorout.h:50
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
void TraceSegmentPcb(TRACK *pt_segm, int type, int marge, int op_logic)
Definition: graphpcb.cpp:290
#define BLOCK_NORTHWEST
Definition: solve.cpp:142
Class RATSNEST_ITEM describes a ratsnest line: a straight line connecting 2 pads. ...
Definition: class_netinfo.h:68
DLIST< TRACK > m_Track
Definition: class_board.h:244
const wxString & GetNetname() const
Function GetNetname.
bool SetQueue(int, int, int, int, int, int, int)
Definition: queue.cpp:120
#define FROM_SOUTHEAST
Definition: cell.h:107
void DrawTraces(EDA_DRAW_PANEL *panel, wxDC *DC, TRACK *aStartTrace, int nbsegment, GR_DRAWMODE mode_color)
Function DrawTraces Draws n consecutive track segments in list.
Definition: tr_modif.cpp:48
#define DIAG_SEtoNW
Definition: cell.h:74
int GetCurrentTrackWidth() const
Function GetCurrentTrackWidth.
#define LINE_HORIZONTAL
Definition: cell.h:63
void DisplayError(wxWindow *parent, const wxString &text, int displaytime)
Function DisplayError displays an error or warning message box with aMessage.
Definition: confirm.cpp:69
#define HOLE
Definition: cell.h:40
bool IsOK(wxWindow *aParent, const wxString &aMessage)
Function IsOK displays a yes/no dialog with aMessage and returns the user response.
Definition: confirm.cpp:111
#define BENT_WtoNE
Definition: cell.h:83
static int segm_oX
Definition: solve.cpp:77
#define FROM_WEST
Definition: cell.h:110
static int Autoroute_One_Track(AUTOROUTER_CONTEXT &ctx, int two_sides, int row_source, int col_source, int row_target, int col_target, RATSNEST_ITEM *pt_rat)
Definition: solve.cpp:395
void ClearListAndDeleteItems()
Function ClearListAndDeleteItems deletes the list of pickers, AND the data pointed by m_PickedItem or...
#define HOLE_WEST
Definition: cell.h:59
void Insert(T *aNewElement, T *aElementAfterMe)
Function Insert puts aNewElement just in front of aElementAfterMe in the list sequence.
Definition: dlist.h:200
#define SHARP_NtoNW
Definition: cell.h:100
T * PopFront()
Definition: dlist.h:221
#define SHARP_StoSW
Definition: cell.h:97
#define WRITE_OR_CELL
Definition: autorout.h:191
Definition: colors.h:62
static int Retrace(AUTOROUTER_CONTEXT &ctx, int, int, int, int, int, int net_code)
Definition: solve.cpp:943