Merge pull request #1 from saurabhb17/develop

Added main functions

15 files changed, 6187 insertions, 0 deletions

diff --git a/pcbnew/autorouter/auto_place_footprints.cpp b/pcbnew/autorouter/auto_place_footprints.cpp
new file mode 100644
index 0000000..d6d25a1
--- /dev/null
+++ b/pcbnew/autorouter/auto_place_footprints.cpp
@@ -0,0 +1,1299 @@
+/**
+ * @file auto_place_footprints.cpp
+ * @brief Functions to automatically place Footprints on a board.
+ */
+
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+#include <fctsys.h>
+#include <class_drawpanel.h>
+#include <confirm.h>
+#include <pcbnew.h>
+#include <wxPcbStruct.h>
+#include <gr_basic.h>
+#include <macros.h>
+#include <msgpanel.h>
+
+#include <autorout.h>
+#include <cell.h>
+#include <colors_selection.h>
+
+#include <class_board.h>
+#include <class_module.h>
+#include <class_track.h>
+#include <class_drawsegment.h>
+#include <convert_to_biu.h>
+#include <base_units.h>
+#include <protos.h>
+
+
+#define GAIN            16
+#define KEEP_OUT_MARGIN 500
+
+
+/* Penalty (cost) for CntRot90 and CntRot180:
+ * CntRot90 and CntRot180 are from 0 (rotation allowed) to 10 (rotation not allowed)
+ */
+static const double OrientPenality[11] =
+{
+    2.0,        // CntRot = 0 rotation prohibited
+    1.9,        // CntRot = 1
+    1.8,        // CntRot = 2
+    1.7,        // CntRot = 3
+    1.6,        // CntRot = 4
+    1.5,        // CntRot = 5
+    1.4,        // CntRot = 5
+    1.3,        // CntRot = 7
+    1.2,        // CntRot = 8
+    1.1,        // CntRot = 9
+    1.0         // CntRot = 10 rotation authorized, no penalty
+};
+
+// Cell states.
+#define OUT_OF_BOARD        -2
+#define OCCUPED_By_MODULE   -1
+#define FREE_CELL   0
+
+
+static wxPoint  CurrPosition; // Current position of the current module placement
+double          MinCout;
+
+
+/* generates the Routing matrix, used to fing the best placement
+ * of a footprint.
+ * Allocate a "bitmap" which is an image of the real board
+ * the bitmap handles:
+ * - The free areas
+ * - penalties (cell not occupied, but near occupied areas)
+ * - cells occupied by footprints, board cutout ...
+ */
+int             genPlacementRoutingMatrix(  BOARD* aBrd, EDA_MSG_PANEL* messagePanel );
+
+/* searches for the optimal position of aModule.
+ * return 1 if placement impossible or 0 if OK.
+ */
+static int      getOptimalModulePlacement( PCB_EDIT_FRAME* aFrame,
+                                           MODULE* aModule, wxDC* aDC );
+
+/*
+ * Function compute_Ratsnest_PlaceModule
+ * displays the module's ratsnest during displacement, and assess the "cost"
+ * of the position.
+ *
+ * The cost is the longest ratsnest distance with penalty for connections
+ * approaching 45 degrees.
+ */
+static double   compute_Ratsnest_PlaceModule( BOARD* aBrd );
+
+/* Place a footprint on the Routing matrix.
+ */
+void            genModuleOnRoutingMatrix( MODULE* Module );
+/*
+ * Displays the Placement/Routing matrix on the screen
+ */
+static void     drawPlacementRoutingMatrix( BOARD* aBrd, wxDC* DC );
+
+static int      TstModuleOnBoard( BOARD* Pcb, MODULE* Module, bool TstOtherSide );
+
+static void     CreateKeepOutRectangle( int ux0, int uy0, int ux1, int uy1,
+                                        int marge, int aKeepOut, LSET aLayerMask );
+
+static MODULE*  PickModule( PCB_EDIT_FRAME* pcbframe, wxDC* DC );
+static int      propagate();
+
+void PCB_EDIT_FRAME::AutoPlaceModule( MODULE* Module, int place_mode, wxDC* DC )
+{
+    MODULE*             currModule = NULL;
+    wxPoint             PosOK;
+    wxPoint             memopos;
+    int                 error;
+    LAYER_ID            lay_tmp_TOP, lay_tmp_BOTTOM;
+
+    // Undo: init list
+    PICKED_ITEMS_LIST   newList;
+
+    newList.m_Status = UR_CHANGED;
+    ITEM_PICKER         picker( NULL, UR_CHANGED );
+
+    if( GetBoard()->m_Modules == NULL )
+        return;
+
+    m_canvas->SetAbortRequest( false );
+
+    switch( place_mode )
+    {
+    case PLACE_1_MODULE:
+        currModule = Module;
+
+        if( currModule == NULL )
+            return;
+
+        currModule->SetIsPlaced( false );
+        currModule->SetNeedsPlaced( false );
+        break;
+
+    case PLACE_OUT_OF_BOARD:
+        break;
+
+    case PLACE_ALL:
+
+        if( !IsOK( this, _( "Footprints NOT LOCKED will be moved" ) ) )
+            return;
+
+        break;
+
+    case PLACE_INCREMENTAL:
+
+        if( !IsOK( this, _( "Footprints NOT PLACED will be moved" ) ) )
+            return;
+
+        break;
+    }
+
+    memopos = CurrPosition;
+    lay_tmp_BOTTOM  = g_Route_Layer_BOTTOM;
+    lay_tmp_TOP     = g_Route_Layer_TOP;
+
+    RoutingMatrix.m_GridRouting = (int) GetScreen()->GetGridSize().x;
+
+    // Ensure Board.m_GridRouting has a reasonable value:
+    if( RoutingMatrix.m_GridRouting < Millimeter2iu( 0.25 ) )
+        RoutingMatrix.m_GridRouting = Millimeter2iu( 0.25 );
+
+    // Compute module parameters used in auto place
+    if( genPlacementRoutingMatrix( GetBoard(), m_messagePanel ) == 0 )
+        return;
+
+    int moduleCount = 0;
+    Module = GetBoard()->m_Modules;
+
+    for( ; Module != NULL; Module = Module->Next() )
+    {
+        Module->SetNeedsPlaced( false );
+
+        switch( place_mode )
+        {
+        case PLACE_1_MODULE:
+
+            if( currModule == Module )
+            {
+                // Module will be placed, add to undo.
+                picker.SetItem( currModule );
+                newList.PushItem( picker );
+                Module->SetNeedsPlaced( true );
+            }
+
+            break;
+
+        case PLACE_OUT_OF_BOARD:
+            Module->SetIsPlaced( false );
+
+            if( Module->IsLocked() )
+                break;
+
+            if( !RoutingMatrix.m_BrdBox.Contains( Module->GetPosition() ) )
+            {
+                // Module will be placed, add to undo.
+                picker.SetItem( Module );
+                newList.PushItem( picker );
+                Module->SetNeedsPlaced( true );
+            }
+
+            break;
+
+        case PLACE_ALL:
+            Module->SetIsPlaced( false );
+
+            if( Module->IsLocked() )
+                break;
+
+            // Module will be placed, add to undo.
+            picker.SetItem( Module );
+            newList.PushItem( picker );
+            Module->SetNeedsPlaced( true );
+            break;
+
+        case PLACE_INCREMENTAL:
+
+            if( Module->IsLocked() )
+            {
+                Module->SetIsPlaced( false );
+                break;
+            }
+
+            if( !Module->NeedsPlaced() )
+            {
+                // Module will be placed, add to undo.
+                picker.SetItem( Module );
+                newList.PushItem( picker );
+                Module->SetNeedsPlaced( true );
+            }
+
+            break;
+        }
+
+        if( Module->NeedsPlaced() )    // Erase from screen
+        {
+            moduleCount++;
+            Module->Draw( m_canvas, DC, GR_XOR );
+        }
+        else
+        {
+            genModuleOnRoutingMatrix( Module );
+        }
+    }
+
+    // Undo command: prepare list
+    if( newList.GetCount() )
+        SaveCopyInUndoList( newList, UR_CHANGED );
+
+    int         cnt = 0;
+    wxString    msg;
+
+    while( ( Module = PickModule( this, DC ) ) != NULL )
+    {
+        // Display some info about activity, module placement can take a while:
+        msg.Printf( _( "Place footprint %d of %d" ), cnt, moduleCount );
+        SetStatusText( msg );
+
+        double initialOrient = Module->GetOrientation();
+        // Display fill area of interest, barriers, penalties.
+        drawPlacementRoutingMatrix( GetBoard(), DC );
+
+        error = getOptimalModulePlacement( this, Module, DC );
+        double bestScore = MinCout;
+        double bestRotation = 0.0;
+        int rotAllowed;
+        PosOK = CurrPosition;
+
+        if( error == ESC )
+            goto end_of_tst;
+
+        // Try orientations 90, 180, 270 degrees from initial orientation
+        rotAllowed = Module->GetPlacementCost180();
+
+        if( rotAllowed != 0 )
+        {
+            Rotate_Module( DC, Module, 1800.0, true );
+            error   = getOptimalModulePlacement( this, Module, DC );
+            MinCout *= OrientPenality[rotAllowed];
+
+            if( bestScore > MinCout )    // This orientation is better.
+            {
+                PosOK       = CurrPosition;
+                bestScore   = MinCout;
+                bestRotation = 1800.0;
+            }
+            else
+            {
+                Rotate_Module( DC, Module, initialOrient, false );
+            }
+
+            if( error == ESC )
+                goto end_of_tst;
+        }
+
+        // Determine if the best orientation of a module is 90.
+        rotAllowed = Module->GetPlacementCost90();
+
+        if( rotAllowed != 0 )
+        {
+            Rotate_Module( DC, Module, 900.0, true );
+            error   = getOptimalModulePlacement( this, Module, DC );
+            MinCout *= OrientPenality[rotAllowed];
+
+            if( bestScore > MinCout )    // This orientation is better.
+            {
+                PosOK       = CurrPosition;
+                bestScore   = MinCout;
+                bestRotation = 900.0;
+            }
+            else
+            {
+                Rotate_Module( DC, Module, initialOrient, false );
+            }
+
+            if( error == ESC )
+                goto end_of_tst;
+        }
+
+        // Determine if the best orientation of a module is -90.
+        if( rotAllowed != 0 )
+        {
+            Rotate_Module( DC, Module, 2700.0, true );
+            error   = getOptimalModulePlacement( this, Module, DC );
+            MinCout *= OrientPenality[rotAllowed];
+
+            if( bestScore > MinCout )    // This orientation is better.
+            {
+                PosOK       = CurrPosition;
+                bestScore   = MinCout;
+                bestRotation = 2700.0;
+            }
+            else
+            {
+                Rotate_Module( DC, Module, initialOrient, false );
+            }
+
+            if( error == ESC )
+                goto end_of_tst;
+        }
+
+end_of_tst:
+
+        if( error == ESC )
+            break;
+
+        // Place module.
+        CurrPosition = GetCrossHairPosition();
+        SetCrossHairPosition( PosOK );
+
+        PlaceModule( Module, DC );
+
+        bestRotation += initialOrient;
+
+        if( bestRotation != Module->GetOrientation() )
+            Rotate_Module( DC, Module, bestRotation, false );
+
+        SetCrossHairPosition( CurrPosition );
+
+        Module->CalculateBoundingBox();
+
+        genModuleOnRoutingMatrix( Module );
+        Module->SetIsPlaced( true );
+        Module->SetNeedsPlaced( false );
+    }
+
+    CurrPosition = memopos;
+
+    RoutingMatrix.UnInitRoutingMatrix();
+
+    g_Route_Layer_TOP       = lay_tmp_TOP;
+    g_Route_Layer_BOTTOM    = lay_tmp_BOTTOM;
+
+    Module = GetBoard()->m_Modules;
+
+    for( ; Module != NULL; Module = Module->Next() )
+    {
+        Module->CalculateBoundingBox();
+    }
+
+    GetBoard()->m_Status_Pcb = 0;
+    Compile_Ratsnest( DC, true );
+    m_canvas->ReDraw( DC, true );
+}
+
+
+void drawPlacementRoutingMatrix( BOARD* aBrd, wxDC* DC )
+{
+    int         ii, jj;
+    EDA_COLOR_T color;
+    int         ox, oy;
+    MATRIX_CELL top_state, bottom_state;
+
+    GRSetDrawMode( DC, GR_COPY );
+
+    for( ii = 0; ii < RoutingMatrix.m_Nrows; ii++ )
+    {
+        oy = RoutingMatrix.m_BrdBox.GetY() + ( ii * RoutingMatrix.m_GridRouting );
+
+        for( jj = 0; jj < RoutingMatrix.m_Ncols; jj++ )
+        {
+            ox      = RoutingMatrix.m_BrdBox.GetX() + (jj * RoutingMatrix.m_GridRouting);
+            color   = BLACK;
+
+            top_state       = RoutingMatrix.GetCell( ii, jj, TOP );
+            bottom_state    = RoutingMatrix.GetCell( ii, jj, BOTTOM );
+
+            if( top_state & CELL_is_ZONE )
+                color = BLUE;
+
+            // obstacles
+            if( ( top_state & CELL_is_EDGE ) || ( bottom_state & CELL_is_EDGE ) )
+                color = WHITE;
+            else if( top_state & ( HOLE | CELL_is_MODULE ) )
+                color = LIGHTRED;
+            else if( bottom_state & (HOLE | CELL_is_MODULE) )
+                color = LIGHTGREEN;
+            else    // Display the filling and keep out regions.
+            {
+                if( RoutingMatrix.GetDist( ii, jj, TOP )
+                    || RoutingMatrix.GetDist( ii, jj, BOTTOM ) )
+                    color = DARKGRAY;
+            }
+
+            GRPutPixel( NULL, DC, ox, oy, color );
+        }
+    }
+}
+
+
+int genPlacementRoutingMatrix( BOARD* aBrd, EDA_MSG_PANEL* messagePanel )
+{
+    wxString msg;
+
+    RoutingMatrix.UnInitRoutingMatrix();
+
+    EDA_RECT bbox = aBrd->ComputeBoundingBox( true );
+
+    if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 )
+    {
+        DisplayError( NULL, _( "No PCB edge found, unknown board size!" ) );
+        return 0;
+    }
+
+    RoutingMatrix.ComputeMatrixSize( aBrd, true );
+    int nbCells = RoutingMatrix.m_Ncols * RoutingMatrix.m_Nrows;
+
+    messagePanel->EraseMsgBox();
+    msg.Printf( wxT( "%d" ), RoutingMatrix.m_Ncols );
+    messagePanel->SetMessage( 1, _( "Cols" ), msg, GREEN );
+    msg.Printf( wxT( "%d" ), RoutingMatrix.m_Nrows );
+    messagePanel->SetMessage( 7, _( "Lines" ), msg, GREEN );
+    msg.Printf( wxT( "%d" ), nbCells );
+    messagePanel->SetMessage( 14, _( "Cells." ), msg, YELLOW );
+
+    // Choose the number of board sides.
+    RoutingMatrix.m_RoutingLayersCount = 2;
+
+    RoutingMatrix.InitRoutingMatrix();
+
+    // Display memory usage.
+    msg.Printf( wxT( "%d" ), RoutingMatrix.m_MemSize / 1024 );
+    messagePanel->SetMessage( 24, wxT( "Mem(Kb)" ), msg, CYAN );
+
+    g_Route_Layer_BOTTOM = F_Cu;
+
+    if( RoutingMatrix.m_RoutingLayersCount > 1 )
+        g_Route_Layer_BOTTOM = B_Cu;
+
+    g_Route_Layer_TOP = F_Cu;
+
+    // Place the edge layer segments
+    TRACK TmpSegm( NULL );
+
+    TmpSegm.SetLayer( UNDEFINED_LAYER );
+    TmpSegm.SetNetCode( -1 );
+    TmpSegm.SetWidth( RoutingMatrix.m_GridRouting / 2 );
+
+    EDA_ITEM* PtStruct = aBrd->m_Drawings;
+
+    for( ; PtStruct != NULL; PtStruct = PtStruct->Next() )
+    {
+        DRAWSEGMENT* DrawSegm;
+
+        switch( PtStruct->Type() )
+        {
+        case PCB_LINE_T:
+            DrawSegm = (DRAWSEGMENT*) PtStruct;
+
+            if( DrawSegm->GetLayer() != Edge_Cuts )
+                break;
+
+            TraceSegmentPcb( DrawSegm, HOLE | CELL_is_EDGE,
+                             RoutingMatrix.m_GridRouting, WRITE_CELL );
+            break;
+
+        case PCB_TEXT_T:
+        default:
+            break;
+        }
+    }
+
+    // Mark cells of the routing matrix to CELL_is_ZONE
+    // (i.e. availlable cell to place a module )
+    // Init a starting point of attachment to the area.
+    RoutingMatrix.OrCell( RoutingMatrix.m_Nrows / 2, RoutingMatrix.m_Ncols / 2,
+                          BOTTOM, CELL_is_ZONE );
+
+    // find and mark all other availlable cells:
+    for( int ii = 1; ii != 0; )
+        ii = propagate();
+
+    // Initialize top layer. to the same value as the bottom layer
+    if( RoutingMatrix.m_BoardSide[TOP] )
+        memcpy( RoutingMatrix.m_BoardSide[TOP], RoutingMatrix.m_BoardSide[BOTTOM],
+                nbCells * sizeof(MATRIX_CELL) );
+
+    return 1;
+}
+
+
+/* Place module on Routing matrix.
+ */
+void genModuleOnRoutingMatrix( MODULE* Module )
+{
+    int         ox, oy, fx, fy;
+    LSET        layerMask;
+    D_PAD*      Pad;
+
+    EDA_RECT    fpBBox = Module->GetBoundingBox();
+
+    fpBBox.Inflate( RoutingMatrix.m_GridRouting / 2 );
+    ox  = fpBBox.GetX();
+    fx  = fpBBox.GetRight();
+    oy  = fpBBox.GetY();
+    fy  = fpBBox.GetBottom();
+
+    if( ox < RoutingMatrix.m_BrdBox.GetX() )
+        ox = RoutingMatrix.m_BrdBox.GetX();
+
+    if( ox > RoutingMatrix.m_BrdBox.GetRight() )
+        ox = RoutingMatrix.m_BrdBox.GetRight();
+
+    if( fx < RoutingMatrix.m_BrdBox.GetX() )
+        fx = RoutingMatrix.m_BrdBox.GetX();
+
+    if( fx > RoutingMatrix.m_BrdBox.GetRight() )
+        fx = RoutingMatrix.m_BrdBox.GetRight();
+
+    if( oy < RoutingMatrix.m_BrdBox.GetY() )
+        oy = RoutingMatrix.m_BrdBox.GetY();
+
+    if( oy > RoutingMatrix.m_BrdBox.GetBottom() )
+        oy = RoutingMatrix.m_BrdBox.GetBottom();
+
+    if( fy < RoutingMatrix.m_BrdBox.GetY() )
+        fy = RoutingMatrix.m_BrdBox.GetY();
+
+    if( fy > RoutingMatrix.m_BrdBox.GetBottom() )
+        fy = RoutingMatrix.m_BrdBox.GetBottom();
+
+    if( Module->GetLayer() == F_Cu )
+        layerMask.set( F_Cu );
+
+    if( Module->GetLayer() == B_Cu )
+        layerMask.set( B_Cu );
+
+    TraceFilledRectangle( ox, oy, fx, fy, layerMask,
+                          CELL_is_MODULE, WRITE_OR_CELL );
+
+    // Trace pads + clearance areas.
+    for( Pad = Module->Pads(); Pad != NULL; Pad = Pad->Next() )
+    {
+        int margin = (RoutingMatrix.m_GridRouting / 2) + Pad->GetClearance();
+        ::PlacePad( Pad, CELL_is_MODULE, margin, WRITE_OR_CELL );
+    }
+
+    // Trace clearance.
+    int margin = ( RoutingMatrix.m_GridRouting * Module->GetPadCount() ) / GAIN;
+    CreateKeepOutRectangle( ox, oy, fx, fy, margin, KEEP_OUT_MARGIN, layerMask );
+}
+
+// A minor helper function to draw a bounding box:
+inline void draw_FootprintRect(EDA_RECT * aClipBox, wxDC* aDC, EDA_RECT& fpBBox, EDA_COLOR_T aColor)
+{
+#ifndef USE_WX_OVERLAY
+    GRRect( aClipBox, aDC, fpBBox, 0, aColor );
+#endif
+}
+
+int getOptimalModulePlacement( PCB_EDIT_FRAME* aFrame, MODULE* aModule, wxDC* aDC )
+{
+    int     error = 1;
+    wxPoint LastPosOK;
+    double  min_cost, curr_cost, Score;
+    bool    TstOtherSide;
+    DISPLAY_OPTIONS* displ_opts = (DISPLAY_OPTIONS*)aFrame->GetDisplayOptions();
+    BOARD*  brd = aFrame->GetBoard();
+
+    aModule->CalculateBoundingBox();
+
+    bool showRats = displ_opts->m_Show_Module_Ratsnest;
+    displ_opts->m_Show_Module_Ratsnest = false;
+
+    brd->m_Status_Pcb &= ~RATSNEST_ITEM_LOCAL_OK;
+    aFrame->SetMsgPanel( aModule );
+
+    LastPosOK = RoutingMatrix.m_BrdBox.GetOrigin();
+
+    wxPoint     mod_pos = aModule->GetPosition();
+    EDA_RECT    fpBBox  = aModule->GetFootprintRect();
+
+    // Move fpBBox to have the footprint position at (0,0)
+    fpBBox.Move( -mod_pos );
+    wxPoint fpBBoxOrg = fpBBox.GetOrigin();
+
+    // Calculate the limit of the footprint position, relative
+    // to the routing matrix area
+    wxPoint xylimit = RoutingMatrix.m_BrdBox.GetEnd() - fpBBox.GetEnd();
+
+    wxPoint initialPos = RoutingMatrix.m_BrdBox.GetOrigin() - fpBBoxOrg;
+
+    // Stay on grid.
+    initialPos.x    -= initialPos.x % RoutingMatrix.m_GridRouting;
+    initialPos.y    -= initialPos.y % RoutingMatrix.m_GridRouting;
+
+    CurrPosition = initialPos;
+
+    // Undraw the current footprint
+    aModule->DrawOutlinesWhenMoving( aFrame->GetCanvas(), aDC, wxPoint( 0, 0 ) );
+
+    g_Offset_Module = mod_pos - CurrPosition;
+
+    /* Examine pads, and set TstOtherSide to true if a footprint
+     * has at least 1 pad through.
+     */
+    TstOtherSide = false;
+
+    if( RoutingMatrix.m_RoutingLayersCount > 1 )
+    {
+        LSET    other( aModule->GetLayer() == B_Cu  ? F_Cu : B_Cu );
+
+        for( D_PAD* pad = aModule->Pads(); pad; pad = pad->Next() )
+        {
+            if( !( pad->GetLayerSet() & other ).any() )
+                continue;
+
+            TstOtherSide = true;
+            break;
+        }
+    }
+
+    // Draw the initial bounding box position
+    EDA_COLOR_T color = BROWN;
+    fpBBox.SetOrigin( fpBBoxOrg + CurrPosition );
+    draw_FootprintRect(aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, color);
+
+    min_cost = -1.0;
+    aFrame->SetStatusText( wxT( "Score ??, pos ??" ) );
+
+    for( ; CurrPosition.x < xylimit.x; CurrPosition.x += RoutingMatrix.m_GridRouting )
+    {
+        wxYield();
+
+        if( aFrame->GetCanvas()->GetAbortRequest() )
+        {
+            if( IsOK( aFrame, _( "OK to abort?" ) ) )
+            {
+                displ_opts->m_Show_Module_Ratsnest = showRats;
+                return ESC;
+            }
+            else
+                aFrame->GetCanvas()->SetAbortRequest( false );
+        }
+
+        CurrPosition.y = initialPos.y;
+
+        for( ; CurrPosition.y < xylimit.y; CurrPosition.y += RoutingMatrix.m_GridRouting )
+        {
+            // Erase traces.
+            draw_FootprintRect( aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, color );
+
+            fpBBox.SetOrigin( fpBBoxOrg + CurrPosition );
+            g_Offset_Module = mod_pos - CurrPosition;
+            int keepOutCost = TstModuleOnBoard( brd, aModule, TstOtherSide );
+
+            // Draw at new place
+            color = keepOutCost >= 0 ? BROWN : RED;
+            draw_FootprintRect( aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, color );
+
+            if( keepOutCost >= 0 )    // i.e. if the module can be put here
+            {
+                error = 0;
+                aFrame->build_ratsnest_module( aModule );
+                curr_cost   = compute_Ratsnest_PlaceModule( brd );
+                Score       = curr_cost + keepOutCost;
+
+                if( (min_cost >= Score ) || (min_cost < 0 ) )
+                {
+                    LastPosOK   = CurrPosition;
+                    min_cost    = Score;
+                    wxString msg;
+                    msg.Printf( wxT( "Score %g, pos %s, %s" ),
+                                min_cost,
+                                GetChars( ::CoordinateToString( LastPosOK.x ) ),
+                                GetChars( ::CoordinateToString( LastPosOK.y ) ) );
+                    aFrame->SetStatusText( msg );
+                }
+            }
+        }
+    }
+
+    // erasing the last traces
+    GRRect( aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, 0, BROWN );
+
+    displ_opts->m_Show_Module_Ratsnest = showRats;
+
+    // Regeneration of the modified variable.
+    CurrPosition = LastPosOK;
+
+    brd->m_Status_Pcb &= ~( RATSNEST_ITEM_LOCAL_OK | LISTE_PAD_OK );
+
+    MinCout = min_cost;
+    return error;
+}
+
+
+/* Test if the rectangular area (ux, ux .. y0, y1):
+ * - is a free zone (except OCCUPED_By_MODULE returns)
+ * - is on the working surface of the board (otherwise returns OUT_OF_BOARD)
+ *
+ * Returns OUT_OF_BOARD, or OCCUPED_By_MODULE or FREE_CELL if OK
+ */
+int TstRectangle( BOARD* Pcb, const EDA_RECT& aRect, int side )
+{
+    EDA_RECT rect = aRect;
+
+    rect.Inflate( RoutingMatrix.m_GridRouting / 2 );
+
+    wxPoint start   = rect.GetOrigin();
+    wxPoint end     = rect.GetEnd();
+
+    start   -= RoutingMatrix.m_BrdBox.GetOrigin();
+    end     -= RoutingMatrix.m_BrdBox.GetOrigin();
+
+    int row_min = start.y / RoutingMatrix.m_GridRouting;
+    int row_max = end.y / RoutingMatrix.m_GridRouting;
+    int col_min = start.x / RoutingMatrix.m_GridRouting;
+    int col_max = end.x / RoutingMatrix.m_GridRouting;
+
+    if( start.y > row_min * RoutingMatrix.m_GridRouting )
+        row_min++;
+
+    if( start.x > col_min * RoutingMatrix.m_GridRouting )
+        col_min++;
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    for( int row = row_min; row <= row_max; row++ )
+    {
+        for( int col = col_min; col <= col_max; col++ )
+        {
+            unsigned int data = RoutingMatrix.GetCell( row, col, side );
+
+            if( ( data & CELL_is_ZONE ) == 0 )
+                return OUT_OF_BOARD;
+
+            if( (data & CELL_is_MODULE) )
+                return OCCUPED_By_MODULE;
+        }
+    }
+
+    return FREE_CELL;
+}
+
+
+/* Calculates and returns the clearance area of the rectangular surface
+ * aRect):
+ * (Sum of cells in terms of distance)
+ */
+unsigned int CalculateKeepOutArea( const EDA_RECT& aRect, int side )
+{
+    wxPoint start   = aRect.GetOrigin();
+    wxPoint end     = aRect.GetEnd();
+
+    start   -= RoutingMatrix.m_BrdBox.GetOrigin();
+    end     -= RoutingMatrix.m_BrdBox.GetOrigin();
+
+    int row_min = start.y / RoutingMatrix.m_GridRouting;
+    int row_max = end.y / RoutingMatrix.m_GridRouting;
+    int col_min = start.x / RoutingMatrix.m_GridRouting;
+    int col_max = end.x / RoutingMatrix.m_GridRouting;
+
+    if( start.y > row_min * RoutingMatrix.m_GridRouting )
+        row_min++;
+
+    if( start.x > col_min * RoutingMatrix.m_GridRouting )
+        col_min++;
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    unsigned int keepOutCost = 0;
+
+    for( int row = row_min; row <= row_max; row++ )
+    {
+        for( int col = col_min; col <= col_max; col++ )
+        {
+            // RoutingMatrix.GetDist returns the "cost" of the cell
+            // at position (row, col)
+            // in autoplace this is the cost of the cell, if it is
+            // inside aRect
+            keepOutCost += RoutingMatrix.GetDist( row, col, side );
+        }
+    }
+
+    return keepOutCost;
+}
+
+
+/* Test if the module can be placed on the board.
+ * Returns the value TstRectangle().
+ * Module is known by its bounding box
+ */
+int TstModuleOnBoard( BOARD* Pcb, MODULE* aModule, bool TstOtherSide )
+{
+    int side = TOP;
+    int otherside = BOTTOM;
+
+    if( aModule->GetLayer() == B_Cu )
+    {
+        side = BOTTOM; otherside = TOP;
+    }
+
+    EDA_RECT    fpBBox = aModule->GetFootprintRect();
+    fpBBox.Move( -g_Offset_Module );
+
+    int         diag = TstRectangle( Pcb, fpBBox, side );
+
+    if( diag != FREE_CELL )
+        return diag;
+
+    if( TstOtherSide )
+    {
+        diag = TstRectangle( Pcb, fpBBox, otherside );
+
+        if( diag != FREE_CELL )
+            return diag;
+    }
+
+    int marge = ( RoutingMatrix.m_GridRouting * aModule->GetPadCount() ) / GAIN;
+
+    fpBBox.Inflate( marge );
+    return CalculateKeepOutArea( fpBBox, side );
+}
+
+
+double compute_Ratsnest_PlaceModule( BOARD* aBrd )
+{
+    double  curr_cost;
+    wxPoint start;      // start point of a ratsnest
+    wxPoint end;        // end point of a ratsnest
+    int     dx, dy;
+
+    if( ( aBrd->m_Status_Pcb & RATSNEST_ITEM_LOCAL_OK ) == 0 )
+        return -1;
+
+    curr_cost = 0;
+
+    for( unsigned ii = 0; ii < aBrd->m_LocalRatsnest.size(); ii++ )
+    {
+        RATSNEST_ITEM* pt_local_rats_nest = &aBrd->m_LocalRatsnest[ii];
+
+        if( ( pt_local_rats_nest->m_Status & LOCAL_RATSNEST_ITEM ) )
+            continue; // Skip ratsnest between 2 pads of the current module
+
+        // Skip modules not inside the board area
+        MODULE* module = pt_local_rats_nest->m_PadEnd->GetParent();
+
+        if( !RoutingMatrix.m_BrdBox.Contains( module->GetPosition() ) )
+            continue;
+
+        start   = pt_local_rats_nest->m_PadStart->GetPosition() - g_Offset_Module;
+        end     = pt_local_rats_nest->m_PadEnd->GetPosition();
+
+        // Cost of the ratsnest.
+        dx  = end.x - start.x;
+        dy  = end.y - start.y;
+
+        dx  = abs( dx );
+        dy  = abs( dy );
+
+        // ttry to have always dx >= dy to calculate the cost of the rastsnet
+        if( dx < dy )
+            std::swap( dx, dy );
+
+        // Cost of the connection = lenght + penalty due to the slope
+        // dx is the biggest lenght relative to the X or Y axis
+        // the penalty is max for 45 degrees ratsnests,
+        // and 0 for horizontal or vertical ratsnests.
+        // For Horizontal and Vertical ratsnests, dy = 0;
+        double conn_cost = hypot( dx, dy * 2.0 );
+        curr_cost += conn_cost;    // Total cost = sum of costs of each connection
+    }
+
+    return curr_cost;
+}
+
+
+/**
+ * Function CreateKeepOutRectangle
+ * builds the cost map:
+ * Cells ( in Dist map ) inside the rect x0,y0 a x1,y1 are
+ *  incremented by value aKeepOut
+ *  Cell outside this rectangle, but inside the rectangle
+ *  x0,y0 -marge to x1,y1 + marge are incremented by a decreasing value
+ *  (aKeepOut ... 0). The decreasing value depends on the distance to the first rectangle
+ *  Therefore the cost is high in rect x0,y0 to x1,y1, and decrease outside this rectangle
+ */
+void CreateKeepOutRectangle( int ux0, int uy0, int ux1, int uy1,
+                             int marge, int aKeepOut, LSET aLayerMask )
+{
+    int         row, col;
+    int         row_min, row_max, col_min, col_max, pmarge;
+    int         trace = 0;
+    DIST_CELL   data, LocalKeepOut;
+    int         lgain, cgain;
+
+    if( aLayerMask[g_Route_Layer_BOTTOM] )
+        trace = 1; // Trace on bottom layer.
+
+    if( aLayerMask[g_Route_Layer_TOP] && RoutingMatrix.m_RoutingLayersCount )
+        trace |= 2; // Trace on top layer.
+
+    if( trace == 0 )
+        return;
+
+    ux0 -= RoutingMatrix.m_BrdBox.GetX();
+    uy0 -= RoutingMatrix.m_BrdBox.GetY();
+    ux1 -= RoutingMatrix.m_BrdBox.GetX();
+    uy1 -= RoutingMatrix.m_BrdBox.GetY();
+
+    ux0 -= marge; ux1 += marge;
+    uy0 -= marge; uy1 += marge;
+
+    pmarge = marge / RoutingMatrix.m_GridRouting;
+
+    if( pmarge < 1 )
+        pmarge = 1;
+
+    // Calculate the coordinate limits of the rectangle.
+    row_max = uy1 / RoutingMatrix.m_GridRouting;
+    col_max = ux1 / RoutingMatrix.m_GridRouting;
+    row_min = uy0 / RoutingMatrix.m_GridRouting;
+
+    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
+        row_min++;
+
+    col_min = ux0 / RoutingMatrix.m_GridRouting;
+
+    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
+        col_min++;
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_max >= (RoutingMatrix.m_Nrows - 1) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    if( col_max >= (RoutingMatrix.m_Ncols - 1) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    for( row = row_min; row <= row_max; row++ )
+    {
+        lgain = 256;
+
+        if( row < pmarge )
+            lgain = ( 256 * row ) / pmarge;
+        else if( row > row_max - pmarge )
+            lgain = ( 256 * ( row_max - row ) ) / pmarge;
+
+        for( col = col_min; col <= col_max; col++ )
+        {
+            // RoutingMatrix Dist map containt the "cost" of the cell
+            // at position (row, col)
+            // in autoplace this is the cost of the cell, when
+            // a footprint overlaps it, near a "master" footprint
+            // this cost is hight near the "master" footprint
+            // and decrease with the distance
+            cgain = 256;
+            LocalKeepOut = aKeepOut;
+
+            if( col < pmarge )
+                cgain = ( 256 * col ) / pmarge;
+            else if( col > col_max - pmarge )
+                cgain = ( 256 * ( col_max - col ) ) / pmarge;
+
+            cgain = ( cgain * lgain ) / 256;
+
+            if( cgain != 256 )
+                LocalKeepOut = ( LocalKeepOut * cgain ) / 256;
+
+            if( trace & 1 )
+            {
+                data = RoutingMatrix.GetDist( row, col, BOTTOM ) + LocalKeepOut;
+                RoutingMatrix.SetDist( row, col, BOTTOM, data );
+            }
+
+            if( trace & 2 )
+            {
+                data    = RoutingMatrix.GetDist( row, col, TOP );
+                data    = std::max( data, LocalKeepOut );
+                RoutingMatrix.SetDist( row, col, TOP, data );
+            }
+        }
+    }
+}
+
+
+// Sort routines
+static bool Tri_PlaceModules( MODULE* ref, MODULE* compare )
+{
+    double ff1, ff2;
+
+    ff1 = ref->GetArea() * ref->GetPadCount();
+    ff2 = compare->GetArea() * compare->GetPadCount();
+
+    return ff2 < ff1;
+}
+
+
+static bool sortFootprintsByRatsnestSize( MODULE* ref, MODULE* compare )
+{
+    double ff1, ff2;
+
+    ff1 = ref->GetArea() * ref->GetFlag();
+    ff2 = compare->GetArea() * compare->GetFlag();
+    return ff2 < ff1;
+}
+
+
+/**
+ * Function PickModule
+ * find the "best" module place
+ * The criteria are:
+ * - Maximum ratsnest with modules already placed
+ * - Max size, and number of pads max
+ */
+static MODULE* PickModule( PCB_EDIT_FRAME* pcbframe, wxDC* DC )
+{
+    MODULE* Module;
+    std::vector <MODULE*> moduleList;
+
+    // Build sorted footprints list (sort by decreasing size )
+    Module = pcbframe->GetBoard()->m_Modules;
+
+    for( ; Module != NULL; Module = Module->Next() )
+    {
+        Module->CalculateBoundingBox();
+        moduleList.push_back( Module );
+    }
+
+    sort( moduleList.begin(), moduleList.end(), Tri_PlaceModules );
+
+    for( unsigned ii = 0; ii < moduleList.size(); ii++ )
+    {
+        Module = moduleList[ii];
+        Module->SetFlag( 0 );
+
+        if( !Module->NeedsPlaced() )
+            continue;
+
+        pcbframe->GetBoard()->m_Status_Pcb &= ~RATSNEST_ITEM_LOCAL_OK;
+        pcbframe->SetMsgPanel( Module );
+        pcbframe->build_ratsnest_module( Module );
+
+        // Calculate external ratsnest.
+        for( unsigned ii = 0; ii < pcbframe->GetBoard()->m_LocalRatsnest.size(); ii++ )
+        {
+            if( ( pcbframe->GetBoard()->m_LocalRatsnest[ii].m_Status &
+                  LOCAL_RATSNEST_ITEM ) == 0 )
+                Module->IncrementFlag();
+        }
+    }
+
+    pcbframe->GetBoard()->m_Status_Pcb &= ~RATSNEST_ITEM_LOCAL_OK;
+
+    sort( moduleList.begin(), moduleList.end(), sortFootprintsByRatsnestSize );
+
+    // Search for "best" module.
+    MODULE* bestModule  = NULL;
+    MODULE* altModule   = NULL;
+
+    for( unsigned ii = 0; ii < moduleList.size(); ii++ )
+    {
+        Module = moduleList[ii];
+
+        if( !Module->NeedsPlaced() )
+            continue;
+
+        altModule = Module;
+
+        if( Module->GetFlag() == 0 )
+            continue;
+
+        bestModule = Module;
+        break;
+    }
+
+    if( bestModule )
+        return bestModule;
+    else
+        return altModule;
+}
+
+
+/**
+ * Function propagate
+ * Used only in autoplace calculations
+ * Uses the routing matrix to fill the cells within the zone
+ * Search and mark cells within the zone, and agree with DRC options.
+ * Requirements:
+ * Start from an initial point, to fill zone
+ * The zone must have no "copper island"
+ *  Algorithm:
+ *  If the current cell has a neighbor flagged as "cell in the zone", it
+ *  become a cell in the zone
+ *  The first point in the zone is the starting point
+ *  4 searches within the matrix are made:
+ *          1 - Left to right and top to bottom
+ *          2 - Right to left and top to bottom
+ *          3 - bottom to top and Right to left
+ *          4 - bottom to top and Left to right
+ *  Given the current cell, for each search, we consider the 2 neighbor cells
+ *  the previous cell on the same line and the previous cell on the same column.
+ *
+ *  This function can request some iterations
+ *  Iterations are made until no cell is added to the zone.
+ *  @return added cells count (i.e. which the attribute CELL_is_ZONE is set)
+ */
+int propagate()
+{
+    int     row, col;
+    long    current_cell, old_cell_H;
+    std::vector<long> pt_cell_V;
+    int     nbpoints = 0;
+
+#define NO_CELL_ZONE (HOLE | CELL_is_EDGE | CELL_is_ZONE)
+
+    pt_cell_V.reserve( std::max( RoutingMatrix.m_Nrows, RoutingMatrix.m_Ncols ) );
+    fill( pt_cell_V.begin(), pt_cell_V.end(), 0 );
+
+    // Search from left to right and top to bottom.
+    for( row = 0; row < RoutingMatrix.m_Nrows; row++ )
+    {
+        old_cell_H = 0;
+
+        for( col = 0; col < RoutingMatrix.m_Ncols; col++ )
+        {
+            current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE;
+
+            if( current_cell == 0 )    // a free cell is found
+            {
+                if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[col] & CELL_is_ZONE) )
+                {
+                    RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE );
+                    current_cell = CELL_is_ZONE;
+                    nbpoints++;
+                }
+            }
+
+            pt_cell_V[col] = old_cell_H = current_cell;
+        }
+    }
+
+    // Search from right to left and top to bottom/
+    fill( pt_cell_V.begin(), pt_cell_V.end(), 0 );
+
+    for( row = 0; row < RoutingMatrix.m_Nrows; row++ )
+    {
+        old_cell_H = 0;
+
+        for( col = RoutingMatrix.m_Ncols - 1; col >= 0; col-- )
+        {
+            current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE;
+
+            if( current_cell == 0 )    // a free cell is found
+            {
+                if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[col] & CELL_is_ZONE) )
+                {
+                    RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE );
+                    current_cell = CELL_is_ZONE;
+                    nbpoints++;
+                }
+            }
+
+            pt_cell_V[col] = old_cell_H = current_cell;
+        }
+    }
+
+    // Search from bottom to top and right to left.
+    fill( pt_cell_V.begin(), pt_cell_V.end(), 0 );
+
+    for( col = RoutingMatrix.m_Ncols - 1; col >= 0; col-- )
+    {
+        old_cell_H = 0;
+
+        for( row = RoutingMatrix.m_Nrows - 1; row >= 0; row-- )
+        {
+            current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE;
+
+            if( current_cell == 0 )    // a free cell is found
+            {
+                if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[row] & CELL_is_ZONE) )
+                {
+                    RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE );
+                    current_cell = CELL_is_ZONE;
+                    nbpoints++;
+                }
+            }
+
+            pt_cell_V[row] = old_cell_H = current_cell;
+        }
+    }
+
+    // Search from bottom to top and left to right.
+    fill( pt_cell_V.begin(), pt_cell_V.end(), 0 );
+
+    for( col = 0; col < RoutingMatrix.m_Ncols; col++ )
+    {
+        old_cell_H = 0;
+
+        for( row = RoutingMatrix.m_Nrows - 1; row >= 0; row-- )
+        {
+            current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE;
+
+            if( current_cell == 0 )    // a free cell is found
+            {
+                if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[row] & CELL_is_ZONE) )
+                {
+                    RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE );
+                    current_cell = CELL_is_ZONE;
+                    nbpoints++;
+                }
+            }
+
+            pt_cell_V[row] = old_cell_H = current_cell;
+        }
+    }
+
+    return nbpoints;
+}
diff --git a/pcbnew/autorouter/autorout.cpp b/pcbnew/autorouter/autorout.cpp
new file mode 100644
index 0000000..7c53f0e
--- /dev/null
+++ b/pcbnew/autorouter/autorout.cpp
@@ -0,0 +1,277 @@
+/**
+ * @file autorout.cpp
+ * @brief Autorouting command and control.
+ */
+
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+#include <fctsys.h>
+#include <class_drawpanel.h>
+#include <wxPcbStruct.h>
+#include <gr_basic.h>
+#include <msgpanel.h>
+
+#include <pcbnew.h>
+#include <cell.h>
+#include <zones.h>
+
+#include <class_board.h>
+#include <class_module.h>
+#include <class_track.h>
+#include <convert_to_biu.h>
+
+#include <autorout.h>
+
+
+MATRIX_ROUTING_HEAD RoutingMatrix;     // routing matrix (grid) to route 2-sided boards
+
+/* init board, route traces*/
+void PCB_EDIT_FRAME::Autoroute( wxDC* DC, int mode )
+{
+    int      start, stop;
+    MODULE*  Module = NULL;
+    D_PAD*   Pad    = NULL;
+    int      autoroute_net_code = -1;
+    wxString msg;
+
+    if( GetBoard()->GetCopperLayerCount() > 1 )
+    {
+        g_Route_Layer_TOP    = GetScreen()->m_Route_Layer_TOP;
+        g_Route_Layer_BOTTOM = GetScreen()->m_Route_Layer_BOTTOM;
+    }
+    else
+    {
+        g_Route_Layer_TOP = g_Route_Layer_BOTTOM = B_Cu;
+    }
+
+    switch( mode )
+    {
+    case ROUTE_NET:
+        if( GetScreen()->GetCurItem() )
+        {
+            switch( GetScreen()->GetCurItem()->Type() )
+            {
+            case PCB_PAD_T:
+                Pad = (D_PAD*) GetScreen()->GetCurItem();
+                autoroute_net_code = Pad->GetNetCode();
+                break;
+
+            default:
+                break;
+            }
+        }
+        if( autoroute_net_code <= 0 )
+        {
+            wxMessageBox( _( "Net not selected" ) ); return;
+        }
+        break;
+
+    case ROUTE_MODULE:
+        Module = (MODULE*) GetScreen()->GetCurItem();
+        if( (Module == NULL) || (Module->Type() != PCB_MODULE_T) )
+        {
+            wxMessageBox( _( "Footprint not selected" ) );
+            return;
+        }
+        break;
+
+    case ROUTE_PAD:
+        Pad = (D_PAD*) GetScreen()->GetCurItem();
+
+        if( (Pad == NULL)  || (Pad->Type() != PCB_PAD_T) )
+        {
+            wxMessageBox( _( "Pad not selected" ) );
+            return;
+        }
+
+        break;
+    }
+
+    if( (GetBoard()->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 )
+        Compile_Ratsnest( DC, true );
+
+    /* Set the flag on the ratsnest to CH_ROUTE_REQ. */
+    for( unsigned ii = 0; ii < GetBoard()->GetRatsnestsCount(); ii++ )
+    {
+        RATSNEST_ITEM* ptmp = &GetBoard()->m_FullRatsnest[ii];
+        ptmp->m_Status &= ~CH_ROUTE_REQ;
+
+        switch( mode )
+        {
+        case ROUTE_ALL:
+            ptmp->m_Status |= CH_ROUTE_REQ;
+            break;
+
+        case ROUTE_NET:
+            if( autoroute_net_code == ptmp->GetNet() )
+                ptmp->m_Status |= CH_ROUTE_REQ;
+            break;
+
+        case ROUTE_MODULE:
+        {
+            D_PAD* pt_pad = (D_PAD*) Module->Pads();
+            for( ; pt_pad != NULL; pt_pad = pt_pad->Next() )
+            {
+                if( ptmp->m_PadStart == pt_pad )
+                    ptmp->m_Status |= CH_ROUTE_REQ;
+
+                if( ptmp->m_PadEnd == pt_pad )
+                    ptmp->m_Status |= CH_ROUTE_REQ;
+            }
+
+            break;
+        }
+
+        case ROUTE_PAD:
+            if( ( ptmp->m_PadStart == Pad ) || ( ptmp->m_PadEnd == Pad ) )
+                ptmp->m_Status |= CH_ROUTE_REQ;
+
+            break;
+        }
+    }
+
+    start = time( NULL );
+
+    /* Calculation of no fixed routing to 5 mils and more. */
+    RoutingMatrix.m_GridRouting = (int)GetScreen()->GetGridSize().x;
+
+    if( RoutingMatrix.m_GridRouting < (5*IU_PER_MILS) )
+        RoutingMatrix.m_GridRouting = 5*IU_PER_MILS;
+
+
+    /* Calculated ncol and nrow, matrix size for routing. */
+    RoutingMatrix.ComputeMatrixSize( GetBoard() );
+
+    m_messagePanel->EraseMsgBox();
+
+    /* Map the board */
+    RoutingMatrix.m_RoutingLayersCount = 1;
+
+    if( g_Route_Layer_TOP != g_Route_Layer_BOTTOM )
+        RoutingMatrix.m_RoutingLayersCount = 2;
+
+    if( RoutingMatrix.InitRoutingMatrix() < 0 )
+    {
+        wxMessageBox( _( "No memory for autorouting" ) );
+        RoutingMatrix.UnInitRoutingMatrix();  /* Free memory. */
+        return;
+    }
+
+    SetStatusText( _( "Place Cells" ) );
+    PlaceCells( GetBoard(), -1, FORCE_PADS );
+
+    /* Construction of the track list for router. */
+    RoutingMatrix.m_RouteCount = Build_Work( GetBoard() );
+
+    // DisplayRoutingMatrix( m_canvas, DC );
+
+    Solve( DC, RoutingMatrix.m_RoutingLayersCount );
+
+    /* Free memory. */
+    FreeQueue();
+    InitWork();             /* Free memory for the list of router connections. */
+    RoutingMatrix.UnInitRoutingMatrix();
+    stop = time( NULL ) - start;
+    msg.Printf( wxT( "time = %d second%s" ), stop, ( stop == 1 ) ? wxT( "" ) : wxT( "s" ) );
+    SetStatusText( msg );
+}
+
+
+/* Clear the flag CH_NOROUTABLE which is set to 1 by Solve(),
+ * when a track was not routed.
+ * (If this flag is 1 the corresponding track it is not rerouted)
+ */
+void PCB_EDIT_FRAME::Reset_Noroutable( wxDC* DC )
+{
+    if( ( GetBoard()->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK )== 0 )
+        Compile_Ratsnest( DC, true );
+
+    for( unsigned ii = 0; ii < GetBoard()->GetRatsnestsCount(); ii++ )
+    {
+        GetBoard()->m_FullRatsnest[ii].m_Status &= ~CH_UNROUTABLE;
+    }
+}
+
+
+/* DEBUG Function: displays the routing matrix */
+void DisplayRoutingMatrix( EDA_DRAW_PANEL* panel, wxDC* DC )
+{
+    int dcell0;
+    EDA_COLOR_T color;
+
+    int maxi = 600 / RoutingMatrix.m_Ncols;
+    maxi = ( maxi * 3 ) / 4;
+
+    if( !maxi )
+        maxi = 1;
+
+    GRSetDrawMode( DC, GR_COPY );
+
+    for( int col = 0; col < RoutingMatrix.m_Ncols; col++ )
+    {
+        for( int row = 0; row < RoutingMatrix.m_Nrows; row++ )
+        {
+            color  = BLACK;
+            dcell0 = RoutingMatrix.GetCell( row, col, BOTTOM );
+
+            if( dcell0 & HOLE )
+                color = GREEN;
+
+#if 0
+            int dcell1 = 0;
+
+            if( RoutingMatrix.m_RoutingLayersCount )
+                dcell1 = GetCell( row, col, TOP );
+
+            if( dcell1 & HOLE )
+                color = RED;
+
+            dcell0 |= dcell1;
+#endif
+            if( !color && ( dcell0 & VIA_IMPOSSIBLE ) )
+                color = BLUE;
+
+            if( dcell0 & CELL_is_EDGE )
+                color = YELLOW;
+            else if( dcell0 & CELL_is_ZONE )
+                color = YELLOW;
+
+            #define DRAW_OFFSET_X -20
+            #define DRAW_OFFSET_Y 20
+//            if( color )
+            {
+                for( int i = 0; i < maxi; i++ )
+                    for( int j = 0; j < maxi; j++ )
+                        GRPutPixel( panel->GetClipBox(), DC,
+                                    ( col * maxi ) + i + DRAW_OFFSET_X,
+                                    ( row * maxi ) + j + DRAW_OFFSET_Y, color );
+
+            }
+        }
+    }
+}
diff --git a/pcbnew/autorouter/autorout.h b/pcbnew/autorouter/autorout.h
new file mode 100644
index 0000000..348191f
--- /dev/null
+++ b/pcbnew/autorouter/autorout.h
@@ -0,0 +1,236 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2012 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+/**
+ * @file autorout.h
+ */
+
+#ifndef AUTOROUT_H
+#define AUTOROUT_H
+
+
+#include <base_struct.h>
+#include <layers_id_colors_and_visibility.h>
+
+
+class BOARD;
+class DRAWSEGMENT;
+
+
+#define TOP     0
+#define BOTTOM  1
+#define EMPTY   0
+#define ILLEGAL -1
+
+
+/* Autorouter commands. */
+enum AUTOPLACEROUTE_OPTIONS
+{
+    PLACE_ALL,
+    PLACE_OUT_OF_BOARD,
+    PLACE_INCREMENTAL,
+    PLACE_1_MODULE,
+
+    ROUTE_ALL,
+    ROUTE_NET,
+    ROUTE_MODULE,
+    ROUTE_PAD
+};
+
+#define MAX_ROUTING_LAYERS_COUNT 2
+
+#define FORCE_PADS 1  /* Force placement of pads for any Netcode */
+
+/* search statistics */
+extern int OpenNodes;   /* total number of nodes opened */
+extern int ClosNodes;   /* total number of nodes closed */
+extern int MoveNodes;   /* total number of nodes moved */
+extern int MaxNodes;    /* maximum number of nodes opened at one time */
+
+
+/* Structures useful to the generation of board as bitmap. */
+typedef char MATRIX_CELL;
+typedef int  DIST_CELL;
+typedef char DIR_CELL;
+
+
+/**
+ * class MATRIX_ROUTING_HEAD
+ * handle the matrix routing that describes the actual board
+ */
+class MATRIX_ROUTING_HEAD
+{
+public:
+    MATRIX_CELL* m_BoardSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides
+    DIST_CELL*   m_DistSide[MAX_ROUTING_LAYERS_COUNT];  // the image map of 2 board sides:
+                                                        // distance to cells
+    DIR_CELL*    m_DirSide[MAX_ROUTING_LAYERS_COUNT];   // the image map of 2 board sides:
+                                                        // pointers back to source
+    bool         m_InitMatrixDone;
+    int          m_RoutingLayersCount;          // Number of layers for autorouting (0 or 1)
+    int          m_GridRouting;                 // Size of grid for autoplace/autoroute
+    EDA_RECT     m_BrdBox;                      // Actual board bounding box
+    int          m_Nrows, m_Ncols;              // Matrix size
+    int          m_MemSize;                     // Memory requirement, just for statistics
+    int          m_RouteCount;                  // Number of routes
+
+private:
+    // a pointer to the current selected cell operation
+    void        (MATRIX_ROUTING_HEAD::* m_opWriteCell)( int aRow, int aCol,
+                                                        int aSide, MATRIX_CELL aCell);
+
+public:
+    MATRIX_ROUTING_HEAD();
+    ~MATRIX_ROUTING_HEAD();
+
+    void WriteCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell)
+    {
+        (*this.*m_opWriteCell)( aRow, aCol, aSide, aCell );
+    }
+
+    /**
+     * function GetBrdCoordOrigin
+     * @return the board coordinate corresponding to the
+     * routing matrix origin ( board coordinate offset )
+     */
+    wxPoint GetBrdCoordOrigin()
+    {
+        return m_BrdBox.GetOrigin();
+    }
+
+    /**
+     * Function ComputeMatrixSize
+     * calculates the number of rows and columns of dimensions of \a aPcb for routing and
+     * automatic calculation of area.
+     * @param aPcb = the physical board
+     * @param aUseBoardEdgesOnly = true to use board edges only,
+     *                           = false to use the full board bounding box (default)
+     */
+    bool ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly = false );
+
+    /**
+     * Function InitBoard
+     * initializes the data structures.
+     *
+     * @return the amount of memory used or -1 if default.
+     */
+    int InitRoutingMatrix();
+
+    void UnInitRoutingMatrix();
+
+    // Initialize WriteCell to make the aLogicOp
+    void SetCellOperation( int aLogicOp );
+
+    // functions to read/write one cell ( point on grid routing matrix:
+    MATRIX_CELL GetCell( int aRow, int aCol, int aSide);
+    void SetCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
+    void OrCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
+    void XorCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
+    void AndCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
+    void AddCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
+    DIST_CELL GetDist( int aRow, int aCol, int aSide );
+    void SetDist( int aRow, int aCol, int aSide, DIST_CELL );
+    int GetDir( int aRow, int aCol, int aSide );
+    void SetDir( int aRow, int aCol, int aSide, int aDir);
+
+    // calculate distance (with penalty) of a trace through a cell
+    int CalcDist(int x,int y,int z ,int side );
+
+    // calculate approximate distance (manhattan distance)
+    int GetApxDist( int r1, int c1, int r2, int c2 );
+};
+
+extern MATRIX_ROUTING_HEAD RoutingMatrix;        /* 2-sided board */
+
+
+/* Constants used to trace the cells on the BOARD */
+#define WRITE_CELL     0
+#define WRITE_OR_CELL  1
+#define WRITE_XOR_CELL 2
+#define WRITE_AND_CELL 3
+#define WRITE_ADD_CELL 4
+
+// Functions:
+
+class PCB_EDIT_FRAME;
+class BOARD;
+class D_PAD;
+class RATSNEST_ITEM;
+class TRACK;
+
+
+/* Initialize a color value, the cells included in the board edge of the
+ * pad surface by pt_pad, with the margin reserved for isolation and the
+ * half width of the runway
+ * Parameters:
+ * Pt_pad: pointer to the description of the pad
+ * color: mask write in cells
+ * margin: add a value to the radius or half the score pad
+ * op_logic: type of writing in the cell (WRITE, OR)
+ */
+void PlacePad( D_PAD* pt_pad, int type, int marge, int op_logic );
+
+/* Draws a segment of track on the board. */
+void TraceSegmentPcb( TRACK* pt_segm, int type, int marge, int op_logic );
+void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int type, int marge, int op_logic );
+
+/* Uses the color value of all cells included in the board
+ * coord of the rectangle ux0, uy0 (top right corner)
+ * a ux1, uy1 (lower left corner) (coord PCB)
+ * the rectangle is horizontal (or vertical)
+ * masque_layer = mask layers;
+ * op_logic = WRITE_CELL, WRITE_OR_CELL, WRITE_XOR_CELL, WRITE_AND_CELL
+ */
+void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
+                           LSET side, int color, int op_logic);
+
+
+/* Same as above, but the rectangle is inclined angle angle. */
+void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
+                           double angle, LSET masque_layer,
+                           int color, int op_logic );
+
+/* QUEUE.CPP */
+void FreeQueue();
+void InitQueue();
+void GetQueue( int *, int *, int *, int *, int * );
+bool  SetQueue( int, int, int, int, int, int, int );
+void ReSetQueue( int, int, int, int, int, int, int );
+
+/* WORK.CPP */
+void InitWork();
+void ReInitWork();
+int SetWork( int, int, int , int, int, RATSNEST_ITEM *, int );
+void GetWork( int *, int *, int *, int *, int *, RATSNEST_ITEM ** );
+void SortWork(); /* order the work items; shortest first */
+
+/* routing_matrix.cpp */
+int Build_Work( BOARD * Pcb );
+void PlaceCells( BOARD * Pcb, int net_code, int flag = 0 );
+
+
+#endif  // AUTOROUT_H
diff --git a/pcbnew/autorouter/cell.h b/pcbnew/autorouter/cell.h
new file mode 100644
index 0000000..63b76ae
--- /dev/null
+++ b/pcbnew/autorouter/cell.h
@@ -0,0 +1,116 @@
+/**
+ * @file cell.h
+ */
+
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+
+#ifndef _CELL_H_
+#define _CELL_H_
+
+
+/* Bits characterizing cell */
+#define HOLE           0x01  /* a conducting hole or obstacle */
+#define CELL_is_MODULE 0x02  /* auto placement occupied by a module */
+#define CELL_is_EDGE   0x20  /* Area and auto-placement: limiting cell contour (Board, Zone) */
+#define CELL_is_FRIEND 0x40  /* Area and auto-placement: cell part of the net */
+#define CELL_is_ZONE   0x80  /* Area and auto-placement: cell available */
+
+/* Bit masks for presence of obstacles to autorouting */
+#define OCCUPE            1  /* Autorouting: obstacle tracks and vias. */
+#define VIA_IMPOSSIBLE    2  /* Autorouting: obstacle for vias. */
+#define CURRENT_PAD       4
+
+
+/* traces radiating outward from a hole to a side or corner */
+#define HOLE_NORTH        0x00000002L /* upward       */
+#define HOLE_NORTHEAST    0x00000004L /* upward and right */
+#define HOLE_EAST         0x00000008L /* to the right     */
+#define HOLE_SOUTHEAST    0x00000010L /* downward and right   */
+#define HOLE_SOUTH        0x00000020L /* downward     */
+#define HOLE_SOUTHWEST    0x00000040L /* downward and left    */
+#define HOLE_WEST         0x00000080L /* to the left      */
+#define HOLE_NORTHWEST    0x00000100L /* upward and left  */
+
+/* straight lines through the center */
+#define LINE_HORIZONTAL   0x00000002L /* left-to-right line   */
+#define LINE_VERTICAL     0x00000004L /* top-to-bottom line   */
+
+/* lines cutting across a corner, connecting adjacent sides */
+#define CORNER_NORTHEAST  0x00000008L /* upper right corner   */
+#define CORNER_SOUTHEAST  0x00000010L /* lower right corner   */
+#define CORNER_SOUTHWEST  0x00000020L /* lower left corner    */
+#define CORNER_NORTHWEST  0x00000040L /* upper left corner    */
+
+/* diagonal lines through the center */
+#define DIAG_NEtoSW       0x00000080L /* northeast to southwest */
+#define DIAG_SEtoNW       0x00000100L /* southeast to northwest */
+
+/* 135 degree angle side-to-far-corner lines */
+#define BENT_NtoSE        0x00000200L /* north to southeast   */
+#define BENT_NtoSW        0x00000400L /* north to southwest   */
+#define BENT_EtoSW        0x00000800L /* east to southwest    */
+#define BENT_EtoNW        0x00001000L /* east to northwest    */
+#define BENT_StoNW        0x00002000L /* south to northwest   */
+#define BENT_StoNE        0x00004000L /* south to northeast   */
+#define BENT_WtoNE        0x00008000L /* west to northeast    */
+#define BENT_WtoSE        0x00010000L /* west to southeast    */
+
+/* 90 degree corner-to-adjacent-corner lines */
+#define ANGLE_NEtoSE      0x00020000L /* northeast to southeast */
+#define ANGLE_SEtoSW      0x00040000L /* southeast to southwest */
+#define ANGLE_SWtoNW      0x00080000L /* southwest to northwest */
+#define ANGLE_NWtoNE      0x00100000L /* northwest to northeast */
+
+/* 45 degree angle side-to-near-corner lines */
+#define SHARP_NtoNE       0x00200000L /* north to northeast   */
+#define SHARP_EtoNE       0x00400000L /* east to northeast    */
+#define SHARP_EtoSE       0x00800000L /* east to southeast    */
+#define SHARP_StoSE       0x01000000L /* south to southeast   */
+#define SHARP_StoSW       0x02000000L /* south to southwest   */
+#define SHARP_WtoSW       0x04000000L /* west to southwest    */
+#define SHARP_WtoNW       0x08000000L /* west to northwest    */
+#define SHARP_NtoNW       0x10000000L /* north to northwest   */
+
+/* directions the cell can be reached from (point to previous cell) */
+#define FROM_NOWHERE      0
+#define FROM_NORTH        1
+#define FROM_NORTHEAST    2
+#define FROM_EAST         3
+#define FROM_SOUTHEAST    4
+#define FROM_SOUTH        5
+#define FROM_SOUTHWEST    6
+#define FROM_WEST         7
+#define FROM_NORTHWEST    8
+#define FROM_OTHERSIDE    9
+
+
+#endif    // _CELL_H_
+
diff --git a/pcbnew/autorouter/dist.cpp b/pcbnew/autorouter/dist.cpp
new file mode 100644
index 0000000..5841073
--- /dev/null
+++ b/pcbnew/autorouter/dist.cpp
@@ -0,0 +1,171 @@
+/**
+ * @file dist.cpp
+ * @brief Routines to calculate PCB editor auto routing distances.
+ */
+
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors.
+ *
+ * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+#include <autorout.h>
+#include <cell.h>
+
+
+/* The tables of distances and keep out areas are established on the basis of a
+ * 50 units grid size (the pitch between the cells is 50 units).
+ * The actual distance could be computed by a scaling factor, but this is
+ * not needed, we can use only reduced values
+ */
+
+ /* calculate approximate distance (manhattan distance)
+ */
+int MATRIX_ROUTING_HEAD::GetApxDist( int r1, int c1, int r2, int c2 )
+{
+    int d1, d2; /* row and column deltas */
+
+    if( ( d1 = r1 - r2 ) < 0 ) /* get absolute row delta */
+        d1 = -d1;
+
+    if( ( d2 = c1 - c2 ) < 0 ) /* get absolute column delta */
+        d2 = -d2;
+
+    return ( d1+d2 ) * 50;
+}
+
+
+/* distance to go thru a cell (en mils) */
+static const int dist[10][10] =
+{ /* OT=Otherside, OR=Origin (source) cell */
+/*..........N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
+/* N  */ { 50, 60, 35, 60, 99, 60, 35, 60,   12, 12 },
+/* NE */ { 60, 71, 60, 71, 60, 99, 60, 71,   23, 23 },
+/* E  */ { 35, 60, 50, 60, 35, 60, 99, 60,   12, 12 },
+/* SE */ { 60, 71, 60, 71, 60, 71, 60, 99,   23, 23 },
+/* S  */ { 99, 60, 35, 60, 50, 60, 35, 60,   12, 12 },
+/* SW */ { 60, 99, 60, 71, 60, 71, 60, 71,   23, 23 },
+/* W  */ { 35, 60, 99, 60, 35, 60, 50, 60,   12, 12 },
+/* NW */ { 60, 71, 60, 99, 60, 71, 60, 71,   23, 23 },
+
+/* OT */ { 12, 23, 12, 23, 12, 23, 12, 23,   99, 99 },
+/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 99 }
+};
+
+/* penalty for extraneous holes and corners, scaled by sharpness of turn */
+static const int penalty[10][10] =
+{ /* OT=Otherside, OR=Origin (source) cell */
+/*......... N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
+/* N  */ {  0,  5, 10, 15, 20, 15, 10,  5,   50, 0 },
+/* NE */ {  5,  0,  5, 10, 15, 20, 15, 10,   50, 0 },
+/* E  */ { 10,  5,  0,  5, 10, 15, 20, 15,   50, 0 },
+/* SE */ { 15, 10,  5,  0,  5, 10, 15, 20,   50, 0 },
+/* S  */ { 20, 15, 10,  5,  0,  5, 10, 15,   50, 0 },
+/* SW */ { 15, 20, 15, 10,  5,  0,  5, 10,   50, 0 },
+/* W  */ { 10, 15, 20, 15, 10,  5,  0,  5,   50, 0 },
+/* NW */ {  5, 10, 15, 20, 15, 10,  5,  0,   50, 0 },
+
+/* OT */ { 50, 50, 50, 50, 50, 50, 50, 50,  100, 0 },
+/* OR */ {  0,  0,  0,  0,  0,  0,  0,  0,    0, 0 }
+};
+
+/* penalty pour directions preferencielles */
+#define PN 20
+static const int dir_penalty_TOP[10][10] =
+{
+/* OT=Otherside, OR=Origin (source) cell */
+/*......... N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
+/* N  */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* NE */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* E  */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* SE */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* S  */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* SW */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* W  */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* NW */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+
+/* OT */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 },
+/* OR */ { PN,  0,  0,  0, PN,  0,  0,  0,    0, 0 }
+};
+
+static int dir_penalty_BOTTOM[10][10] =
+{
+/* OT=Otherside, OR=Origin (source) cell */
+/*......... N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
+/* N  */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* NE */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* E  */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* SE */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* S  */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* SW */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* W  */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* NW */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+
+/* OT */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 },
+/* OR */ {  0,  0, PN,  0,  0,  0, PN,  0,    0, 0 }
+};
+
+/*
+** x is the direction to enter the cell of interest.
+** y is the direction to exit the cell of interest.
+** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
+**
+** return the distance of the trace through the cell of interest.
+** the calculation is driven by the tables above.
+*/
+
+
+/* calculate distance (with penalty) of a trace through a cell
+*/
+int MATRIX_ROUTING_HEAD::CalcDist(int x,int y,int z ,int side  )
+{
+    int adjust, ldist;
+
+    adjust = 0; /* set if hole is encountered */
+
+    if( x == EMPTY )
+        x = 10;
+
+    if( y == EMPTY )
+    {
+        y = 10;
+    }
+    else if( y == FROM_OTHERSIDE )
+    {
+        if( z == EMPTY )
+            z = 10;
+
+        adjust = penalty[x-1][z-1];
+    }
+
+    ldist = dist[x-1][y-1] + penalty[x-1][y-1] + adjust;
+
+    if( m_RouteCount > 1 )
+    {
+        if( side == BOTTOM )
+            ldist += dir_penalty_TOP[x-1][y-1];
+
+        if( side == TOP )
+            ldist += dir_penalty_BOTTOM[x-1][y-1];
+    }
+
+    return ldist * 10;
+}
diff --git a/pcbnew/autorouter/graphpcb.cpp b/pcbnew/autorouter/graphpcb.cpp
new file mode 100644
index 0000000..840bfcb
--- /dev/null
+++ b/pcbnew/autorouter/graphpcb.cpp
@@ -0,0 +1,843 @@
+/**
+ * @file graphpcb.cpp
+ * @brief PCB editor autorouting and "graphics" routines.
+ */
+
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+#include <fctsys.h>
+#include <common.h>
+#include <macros.h>
+#include <trigo.h>
+#include <math_for_graphics.h>
+#include <class_board.h>
+#include <class_track.h>
+#include <class_drawsegment.h>
+
+#include <pcbnew.h>
+#include <autorout.h>
+#include <cell.h>
+
+void TracePcbLine( int x0, int y0, int x1, int y1, LAYER_NUM layer, int color );
+
+void TraceArc( int ux0, int uy0,
+               int ux1, int uy1,
+               double ArcAngle,
+               int lg, LAYER_NUM layer, int color,
+               int op_logic );
+
+
+static void DrawSegmentQcq( int ux0, int uy0,
+                            int ux1, int uy1,
+                            int lg, LAYER_NUM layer, int color,
+                            int op_logic );
+
+static void TraceFilledCircle( int    cx, int cy, int radius,
+                               LSET aLayerMask,
+                               int    color,
+                               int    op_logic );
+
+static void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
+                         int color, int op_logic );
+
+// Macro call to update cell.
+#define OP_CELL( layer, dy, dx )                                        \
+    {                                                                   \
+        if( layer == UNDEFINED_LAYER )                                  \
+        {                                                               \
+            RoutingMatrix.WriteCell( dy, dx, BOTTOM, color );           \
+            if( RoutingMatrix.m_RoutingLayersCount > 1 )                \
+                RoutingMatrix.WriteCell( dy, dx, TOP, color );          \
+        }                                                               \
+        else                                                            \
+        {                                                               \
+            if( layer == g_Route_Layer_BOTTOM )                         \
+                RoutingMatrix.WriteCell( dy, dx, BOTTOM, color );       \
+            if( RoutingMatrix.m_RoutingLayersCount > 1 )                \
+                if( layer == g_Route_Layer_TOP )                        \
+                    RoutingMatrix.WriteCell( dy, dx, TOP, color );      \
+        }                                                               \
+    }
+
+void PlacePad( D_PAD* aPad, int color, int marge, int op_logic )
+{
+    int     dx, dy;
+    wxPoint shape_pos = aPad->ShapePos();
+
+    dx = aPad->GetSize().x / 2;
+    dx += marge;
+
+    if( aPad->GetShape() == PAD_SHAPE_CIRCLE )
+    {
+        TraceFilledCircle( shape_pos.x, shape_pos.y, dx,
+                           aPad->GetLayerSet(), color, op_logic );
+        return;
+    }
+
+    dy = aPad->GetSize().y / 2;
+    dy += marge;
+
+    if( aPad->GetShape() == PAD_SHAPE_TRAPEZOID )
+    {
+        dx += abs( aPad->GetDelta().y ) / 2;
+        dy += abs( aPad->GetDelta().x ) / 2;
+    }
+
+    // The pad is a rectangle ( horizontal or vertical )
+    if( int( aPad->GetOrientation() ) % 900 == 0 )
+    {
+        // Orientation turned 90 deg.
+        if( aPad->GetOrientation() == 900  ||  aPad->GetOrientation() == 2700 )
+        {
+            std::swap( dx, dy );
+        }
+
+        TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy,
+                              shape_pos.x + dx, shape_pos.y + dy,
+                              aPad->GetLayerSet(), color, op_logic );
+    }
+    else
+    {
+        TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy,
+                              shape_pos.x + dx, shape_pos.y + dy,
+                              aPad->GetOrientation(),
+                              aPad->GetLayerSet(), color, op_logic );
+    }
+}
+
+
+/* Set to color the cells included in the circle
+ * Parameters:
+ * center: cx, cy.
+ * radius: a value add to the radius or half the score pad
+ * aLayerMask: layer occupied
+ * color: mask write in cells
+ * op_logic: type of writing in the cell (WRITE, OR)
+ */
+void TraceFilledCircle( int cx, int cy, int radius,
+        LSET aLayerMask,  int color,  int op_logic )
+{
+    int   row, col;
+    int   ux0, uy0, ux1, uy1;
+    int   row_max, col_max, row_min, col_min;
+    int   trace = 0;
+    double fdistmin, fdistx, fdisty;
+    int   tstwrite = 0;
+    int   distmin;
+
+    if( aLayerMask[g_Route_Layer_BOTTOM] )
+        trace = 1;       // Trace on BOTTOM
+
+    if( aLayerMask[g_Route_Layer_TOP] )
+        if( RoutingMatrix.m_RoutingLayersCount > 1 )
+            trace |= 2;  // Trace on TOP
+
+    if( trace == 0 )
+        return;
+
+    RoutingMatrix.SetCellOperation( op_logic );
+
+    cx -= RoutingMatrix.GetBrdCoordOrigin().x;
+    cy -= RoutingMatrix.GetBrdCoordOrigin().y;
+
+    distmin = radius;
+
+    // Calculate the bounding rectangle of the circle.
+    ux0 = cx - radius;
+    uy0 = cy - radius;
+    ux1 = cx + radius;
+    uy1 = cy + radius;
+
+    // Calculate limit coordinates of cells belonging to the rectangle.
+    row_max = uy1 / RoutingMatrix.m_GridRouting;
+    col_max = ux1 / RoutingMatrix.m_GridRouting;
+    row_min = uy0 / RoutingMatrix.m_GridRouting;  // if (uy0 > row_min*Board.m_GridRouting) row_min++;
+    col_min = ux0 / RoutingMatrix.m_GridRouting;  // if (ux0 > col_min*Board.m_GridRouting) col_min++;
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_max >= (RoutingMatrix.m_Nrows - 1) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    if( col_max >= (RoutingMatrix.m_Ncols - 1) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    // Calculate coordinate limits of cell belonging to the rectangle.
+    if( row_min > row_max )
+        row_max = row_min;
+
+    if( col_min > col_max )
+        col_max = col_min;
+
+    fdistmin = (double) distmin * distmin;
+
+    for( row = row_min; row <= row_max; row++ )
+    {
+        fdisty  = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) );
+        fdisty *= fdisty;
+
+        for( col = col_min; col <= col_max; col++ )
+        {
+            fdistx  = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) );
+            fdistx *= fdistx;
+
+            if( fdistmin <= ( fdistx + fdisty ) )
+                continue;
+
+            if( trace & 1 )
+                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
+
+            if( trace & 2 )
+                RoutingMatrix.WriteCell( row, col, TOP, color );
+
+            tstwrite = 1;
+        }
+    }
+
+    if( tstwrite )
+        return;
+
+    /* If no cell has been written, it affects the 4 neighboring diagonal
+     * (Adverse event: pad off grid in the center of the 4 neighboring
+     * diagonal) */
+    distmin  = RoutingMatrix.m_GridRouting / 2 + 1;
+    fdistmin = ( (double) distmin * distmin ) * 2; // Distance to center point diagonally
+
+    for( row = row_min; row <= row_max; row++ )
+    {
+        fdisty  = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) );
+        fdisty *= fdisty;
+
+        for( col = col_min; col <= col_max; col++ )
+        {
+            fdistx  = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) );
+            fdistx *= fdistx;
+
+            if( fdistmin <= ( fdistx + fdisty ) )
+                continue;
+
+            if( trace & 1 )
+                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
+
+            if( trace & 2 )
+                RoutingMatrix.WriteCell( row, col, TOP, color );
+        }
+    }
+}
+
+void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int color, int marge, int op_logic )
+{
+    int half_width = ( pt_segm->GetWidth() / 2 ) + marge;
+
+    // Calculate the bounding rectangle of the segment (if H, V or Via)
+    int ux0 = pt_segm->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x;
+    int uy0 = pt_segm->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y;
+    int ux1 = pt_segm->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x;
+    int uy1 = pt_segm->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y;
+
+    LAYER_NUM layer = pt_segm->GetLayer();
+
+    if( color == VIA_IMPOSSIBLE )
+        layer = UNDEFINED_LAYER;
+
+    switch( pt_segm->GetShape() )
+    {
+    // The segment is here a straight line or a circle or an arc.:
+    case S_CIRCLE:
+        TraceCircle( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
+        break;
+
+    case S_ARC:
+        TraceArc( ux0, uy0, ux1, uy1, pt_segm->GetAngle(), half_width, layer, color, op_logic );
+        break;
+
+    // The segment is here a line segment.
+    default:
+        DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
+        break;
+    }
+}
+
+void TraceSegmentPcb( TRACK* aTrack, int color, int marge, int op_logic )
+{
+    int half_width = ( aTrack->GetWidth() / 2 ) + marge;
+
+    // Test if VIA (filled circle need to be drawn)
+    if( aTrack->Type() == PCB_VIA_T )
+    {
+        LSET layer_mask;
+
+        if( aTrack->IsOnLayer( g_Route_Layer_BOTTOM ) )
+            layer_mask.set( g_Route_Layer_BOTTOM );
+
+        if( aTrack->IsOnLayer( g_Route_Layer_TOP ) )
+        {
+            if( !layer_mask.any() )
+                layer_mask = LSET( g_Route_Layer_TOP );
+            else
+                layer_mask.set();
+        }
+
+        if( color == VIA_IMPOSSIBLE )
+            layer_mask.set();
+
+        if( layer_mask.any() )
+            TraceFilledCircle( aTrack->GetStart().x, aTrack->GetStart().y,
+                               half_width, layer_mask, color, op_logic );
+    }
+    else
+    {
+        // Calculate the bounding rectangle of the segment
+        int ux0 = aTrack->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x;
+        int uy0 = aTrack->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y;
+        int ux1 = aTrack->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x;
+        int uy1 = aTrack->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y;
+
+        // Ordinary track
+        LAYER_ID layer = aTrack->GetLayer();
+
+        if( color == VIA_IMPOSSIBLE )
+            layer = UNDEFINED_LAYER;
+
+        DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
+    }
+}
+
+
+/* Draws a line, if layer = -1 on all layers
+ */
+void TracePcbLine( int x0, int y0, int x1, int y1, LAYER_NUM layer, int color, int op_logic  )
+{
+    int  dx, dy, lim;
+    int  cumul, inc, il, delta;
+
+    RoutingMatrix.SetCellOperation( op_logic );
+
+    if( x0 == x1 )  // Vertical.
+    {
+        if( y1 < y0 )
+            std::swap( y0, y1 );
+
+        dy  = y0 / RoutingMatrix.m_GridRouting;
+        lim = y1 / RoutingMatrix.m_GridRouting;
+        dx  = x0 / RoutingMatrix.m_GridRouting;
+
+        // Clipping limits of board.
+        if( ( dx < 0 ) || ( dx >= RoutingMatrix.m_Ncols ) )
+            return;
+
+        if( dy < 0 )
+            dy = 0;
+
+        if( lim >= RoutingMatrix.m_Nrows )
+            lim = RoutingMatrix.m_Nrows - 1;
+
+        for( ; dy <= lim; dy++ )
+        {
+            OP_CELL( layer, dy, dx );
+        }
+
+        return;
+    }
+
+    if( y0 == y1 )  // Horizontal
+    {
+        if( x1 < x0 )
+            std::swap( x0, x1 );
+
+        dx  = x0 / RoutingMatrix.m_GridRouting;
+        lim = x1 / RoutingMatrix.m_GridRouting;
+        dy  = y0 / RoutingMatrix.m_GridRouting;
+
+        // Clipping limits of board.
+        if( ( dy < 0 ) || ( dy >= RoutingMatrix.m_Nrows ) )
+            return;
+
+        if( dx < 0 )
+            dx = 0;
+
+        if( lim >= RoutingMatrix.m_Ncols )
+            lim = RoutingMatrix.m_Ncols - 1;
+
+        for( ; dx <= lim; dx++ )
+        {
+            OP_CELL( layer, dy, dx );
+        }
+
+        return;
+    }
+
+    // Here is some perspective: using the algorithm LUCAS.
+    if( abs( x1 - x0 ) >= abs( y1 - y0 ) ) // segment slightly inclined/
+    {
+        if( x1 < x0 )
+        {
+            std::swap( x1, x0 );
+            std::swap( y1, y0 );
+        }
+
+        dx  = x0 / RoutingMatrix.m_GridRouting;
+        lim = x1 / RoutingMatrix.m_GridRouting;
+        dy  = y0 / RoutingMatrix.m_GridRouting;
+        inc = 1;
+
+        if( y1 < y0 )
+            inc = -1;
+
+        il    = lim - dx; cumul = il / 2;
+        delta = abs( y1 - y0 ) / RoutingMatrix.m_GridRouting;
+
+        for( ; dx <= lim; )
+        {
+            if( ( dx >= 0 ) && ( dy >= 0 ) &&
+                ( dx < RoutingMatrix.m_Ncols ) &&
+                ( dy < RoutingMatrix.m_Nrows ) )
+            {
+                OP_CELL( layer, dy, dx );
+            }
+
+            dx++;
+            cumul += delta;
+
+            if( cumul > il )
+            {
+                cumul -= il;
+                dy    += inc;
+            }
+        }
+    }
+    else
+    {
+        if( y1 < y0 )
+        {
+            std::swap( x1, x0 );
+            std::swap( y1, y0 );
+        }
+
+        dy  = y0 / RoutingMatrix.m_GridRouting;
+        lim = y1 / RoutingMatrix.m_GridRouting;
+        dx  = x0 / RoutingMatrix.m_GridRouting;
+        inc = 1;
+
+        if( x1 < x0 )
+            inc = -1;
+
+        il    = lim - dy;
+        cumul = il / 2;
+        delta = abs( x1 - x0 ) / RoutingMatrix.m_GridRouting;
+
+        for( ; dy <= lim; )
+        {
+            if( ( dx >= 0 ) && ( dy >= 0 ) && ( dx < RoutingMatrix.m_Ncols ) && ( dy < RoutingMatrix.m_Nrows ) )
+            {
+                OP_CELL( layer, dy, dx );
+            }
+
+            dy++;
+            cumul += delta;
+
+            if( cumul > il )
+            {
+                cumul -= il;
+                dx    += inc;
+            }
+        }
+    }
+}
+
+
+void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
+                           LSET aLayerMask, int color, int op_logic )
+{
+    int  row, col;
+    int  row_min, row_max, col_min, col_max;
+    int  trace = 0;
+
+    if( aLayerMask[g_Route_Layer_BOTTOM] )
+        trace = 1;     // Trace on BOTTOM
+
+    if( aLayerMask[g_Route_Layer_TOP] && RoutingMatrix.m_RoutingLayersCount > 1 )
+        trace |= 2;    // Trace on TOP
+
+    if( trace == 0 )
+        return;
+
+    RoutingMatrix.SetCellOperation( op_logic );
+
+    ux0 -= RoutingMatrix.GetBrdCoordOrigin().x;
+    uy0 -= RoutingMatrix.GetBrdCoordOrigin().y;
+    ux1 -= RoutingMatrix.GetBrdCoordOrigin().x;
+    uy1 -= RoutingMatrix.GetBrdCoordOrigin().y;
+
+    // Calculating limits coord cells belonging to the rectangle.
+    row_max = uy1 / RoutingMatrix.m_GridRouting;
+    col_max = ux1 / RoutingMatrix.m_GridRouting;
+    row_min = uy0 / RoutingMatrix.m_GridRouting;
+
+    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
+        row_min++;
+
+    col_min = ux0 / RoutingMatrix.m_GridRouting;
+
+    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
+        col_min++;
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    for( row = row_min; row <= row_max; row++ )
+    {
+        for( col = col_min; col <= col_max; col++ )
+        {
+            if( trace & 1 )
+                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
+
+            if( trace & 2 )
+                RoutingMatrix.WriteCell( row, col, TOP, color );
+        }
+    }
+}
+
+
+void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
+                           double angle, LSET aLayerMask, int color, int op_logic )
+{
+    int  row, col;
+    int  cx, cy;    // Center of rectangle
+    int  radius;     // Radius of the circle
+    int  row_min, row_max, col_min, col_max;
+    int  rotrow, rotcol;
+    int  trace = 0;
+
+    if( aLayerMask[g_Route_Layer_BOTTOM] )
+        trace = 1;     // Trace on BOTTOM
+
+    if( aLayerMask[g_Route_Layer_TOP] )
+    {
+        if( RoutingMatrix.m_RoutingLayersCount > 1 )
+            trace |= 2;  // Trace on TOP
+    }
+
+    if( trace == 0 )
+        return;
+
+    RoutingMatrix.SetCellOperation( op_logic );
+
+    ux0 -= RoutingMatrix.GetBrdCoordOrigin().x;
+    uy0 -= RoutingMatrix.GetBrdCoordOrigin().y;
+    ux1 -= RoutingMatrix.GetBrdCoordOrigin().x;
+    uy1 -= RoutingMatrix.GetBrdCoordOrigin().y;
+
+    cx    = (ux0 + ux1) / 2;
+    cy    = (uy0 + uy1) / 2;
+    radius = KiROUND( Distance( ux0, uy0, cx, cy ) );
+
+    // Calculating coordinate limits belonging to the rectangle.
+    row_max = ( cy + radius ) / RoutingMatrix.m_GridRouting;
+    col_max = ( cx + radius ) / RoutingMatrix.m_GridRouting;
+    row_min = ( cy - radius ) / RoutingMatrix.m_GridRouting;
+
+    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
+        row_min++;
+
+    col_min = ( cx - radius ) / RoutingMatrix.m_GridRouting;
+
+    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
+        col_min++;
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    for( row = row_min; row <= row_max; row++ )
+    {
+        for( col = col_min; col <= col_max; col++ )
+        {
+            rotrow = row * RoutingMatrix.m_GridRouting;
+            rotcol = col * RoutingMatrix.m_GridRouting;
+            RotatePoint( &rotcol, &rotrow, cx, cy, -angle );
+
+            if( rotrow <= uy0 )
+                continue;
+
+            if( rotrow >= uy1 )
+                continue;
+
+            if( rotcol <= ux0 )
+                continue;
+
+            if( rotcol >= ux1 )
+                continue;
+
+            if( trace & 1 )
+                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
+
+            if( trace & 2 )
+                RoutingMatrix.WriteCell( row, col, TOP, color );
+        }
+    }
+}
+
+
+/* Fills all cells inside a segment
+ * half-width = lg, org = ux0,uy0 end = ux1,uy1
+ * coordinates are in PCB units
+ */
+void DrawSegmentQcq( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
+                     int color, int op_logic )
+{
+    int  row, col;
+    int  inc;
+    int  row_max, col_max, row_min, col_min;
+    int  demi_pas;
+
+    int  cx, cy, dx, dy;
+
+    RoutingMatrix.SetCellOperation( op_logic );
+
+    // Make coordinate ux1 tj > ux0 to simplify calculations
+    if( ux1 < ux0 )
+    {
+        std::swap( ux1, ux0 );
+        std::swap( uy1, uy0 );
+    }
+
+    // Calculating the incrementing the Y axis
+    inc = 1;
+
+    if( uy1 < uy0 )
+        inc = -1;
+
+    demi_pas = RoutingMatrix.m_GridRouting / 2;
+
+    col_min = ( ux0 - lg ) / RoutingMatrix.m_GridRouting;
+
+    if( col_min < 0 )
+        col_min = 0;
+
+    col_max = ( ux1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
+
+    if( col_max > ( RoutingMatrix.m_Ncols - 1 ) )
+        col_max = RoutingMatrix.m_Ncols - 1;
+
+    if( inc > 0 )
+    {
+        row_min = ( uy0 - lg ) / RoutingMatrix.m_GridRouting;
+        row_max = ( uy1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
+    }
+    else
+    {
+        row_min = ( uy1 - lg ) / RoutingMatrix.m_GridRouting;
+        row_max = ( uy0 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
+    }
+
+    if( row_min < 0 )
+        row_min = 0;
+
+    if( row_min > ( RoutingMatrix.m_Nrows - 1 ) )
+        row_min = RoutingMatrix.m_Nrows - 1;
+
+    if( row_max < 0 )
+        row_max = 0;
+
+    if( row_max > ( RoutingMatrix.m_Nrows - 1 ) )
+        row_max = RoutingMatrix.m_Nrows - 1;
+
+    dx = ux1 - ux0;
+    dy = uy1 - uy0;
+
+    double angle;
+    if( dx )
+    {
+        angle = ArcTangente( dy, dx );
+    }
+    else
+    {
+        angle = 900;
+
+        if( dy < 0 )
+            angle = -900;
+    }
+
+    RotatePoint( &dx, &dy, angle );   // dx = length, dy = 0
+
+    for( col = col_min; col <= col_max; col++ )
+    {
+        int cxr;
+        cxr = ( col * RoutingMatrix.m_GridRouting ) - ux0;
+
+        for( row = row_min; row <= row_max; row++ )
+        {
+            cy = (row * RoutingMatrix.m_GridRouting) - uy0;
+            cx = cxr;
+            RotatePoint( &cx, &cy, angle );
+
+            if( abs( cy ) > lg )
+                continue;             // The point is too far on the Y axis.
+
+            /* This point a test is close to the segment: the position
+             * along the X axis must be tested.
+             */
+            if( ( cx >= 0 ) && ( cx <= dx ) )
+            {
+                OP_CELL( layer, row, col );
+                continue;
+            }
+
+            // Examination of extremities are rounded.
+            if( ( cx < 0 ) && ( cx >= -lg ) )
+            {
+                if( ( ( cx * cx ) + ( cy * cy ) ) <= ( lg * lg ) )
+                    OP_CELL( layer, row, col );
+
+                continue;
+            }
+
+            if( ( cx > dx ) && ( cx <= ( dx + lg ) ) )
+            {
+                if( ( ( ( cx - dx ) * ( cx - dx ) ) + ( cy * cy ) ) <= ( lg * lg ) )
+                    OP_CELL( layer, row, col );
+
+                continue;
+            }
+        }
+    }
+}
+
+
+/* Fills all cells of the routing matrix contained in the circle
+ * half-width = lg, center = ux0, uy0, ux1,uy1 is a point on the circle.
+ * coord are in PCB units.
+ */
+void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
+                  int color, int op_logic )
+{
+    int radius, nb_segm;
+    int x0, y0,             // Starting point of the current segment trace.
+        x1, y1;             // End point.
+    int ii;
+    int angle;
+
+    radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) );
+
+    x0 = x1 = radius;
+    y0 = y1 = 0;
+
+    if( lg < 1 )
+        lg = 1;
+
+    nb_segm = ( 2 * radius ) / lg;
+
+    if( nb_segm < 5 )
+        nb_segm = 5;
+
+    if( nb_segm > 100 )
+        nb_segm = 100;
+
+    for( ii = 1; ii < nb_segm; ii++ )
+    {
+        angle = (3600 * ii) / nb_segm;
+        x1    = KiROUND( cosdecideg( radius, angle ) );
+        y1    = KiROUND( sindecideg( radius, angle ) );
+        DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic );
+        x0 = x1;
+        y0 = y1;
+    }
+
+    DrawSegmentQcq( x1 + ux0, y1 + uy0, ux0 + radius, uy0, lg, layer, color, op_logic );
+}
+
+
+/* Fills all routing matrix cells contained in the arc
+ * angle = ArcAngle, half-width lg
+ * center = ux0,uy0, starting at ux1, uy1.  Coordinates are in
+ * PCB units.
+ */
+void TraceArc( int ux0, int uy0, int ux1, int uy1, double ArcAngle, int lg,
+               LAYER_NUM layer, int color, int op_logic )
+{
+    int radius, nb_segm;
+    int x0, y0,             // Starting point of the current segment trace
+        x1, y1;             // End point
+    int ii;
+    double angle, StAngle;
+
+
+    radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) );
+
+    x0 = ux1 - ux0;
+    y0 = uy1 - uy0;
+    StAngle = ArcTangente( uy1 - uy0, ux1 - ux0 );
+
+    if( lg < 1 )
+        lg = 1;
+
+    nb_segm = ( 2 * radius ) / lg;
+    nb_segm = ( nb_segm * std::abs( ArcAngle ) ) / 3600;
+
+    if( nb_segm < 5 )
+        nb_segm = 5;
+
+    if( nb_segm > 100 )
+        nb_segm = 100;
+
+    for( ii = 1; ii <= nb_segm; ii++ )
+    {
+        angle  = ( ArcAngle * ii ) / nb_segm;
+        angle += StAngle;
+
+        NORMALIZE_ANGLE_POS( angle );
+
+        x1 = KiROUND( cosdecideg( radius, angle ) );
+        y1 = KiROUND( cosdecideg( radius, angle ) );
+        DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic );
+        x0 = x1;
+        y0 = y1;
+    }
+}
diff --git a/pcbnew/autorouter/move_and_route_event_functions.cpp b/pcbnew/autorouter/move_and_route_event_functions.cpp
new file mode 100644
index 0000000..5e9f319
--- /dev/null
+++ b/pcbnew/autorouter/move_and_route_event_functions.cpp
@@ -0,0 +1,200 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+/**
+ * @file move_and_route_event_functions.cpp
+ * @brief Routines for automatic displacement and rotation of modules.
+ */
+
+#include <algorithm>
+
+#include <fctsys.h>
+#include <class_drawpanel.h>
+#include <confirm.h>
+#include <kicad_string.h>
+#include <pcbnew.h>
+#include <wxPcbStruct.h>
+#include <kicad_device_context.h>
+
+#include <autorout.h>
+#include <cell.h>
+#include <pcbnew_id.h>
+#include <class_board.h>
+#include <class_module.h>
+
+
+typedef enum {
+    FIXE_MODULE,
+    FREE_MODULE,
+    FIXE_ALL_MODULES,
+    FREE_ALL_MODULES
+} SelectFixeFct;
+
+
+
+wxString ModulesMaskSelection = wxT( "*" );
+
+
+/* Called on events (popup menus) relative to automove and autoplace footprints
+ */
+void PCB_EDIT_FRAME::OnPlaceOrRouteFootprints( wxCommandEvent& event )
+{
+    int        id = event.GetId();
+
+    if( m_mainToolBar == NULL )
+        return;
+
+    INSTALL_UNBUFFERED_DC( dc, m_canvas );
+
+    switch( id )
+    {
+    case ID_POPUP_PCB_AUTOROUTE_SELECT_LAYERS:
+        return;
+
+    case ID_POPUP_PCB_AUTOPLACE_FIXE_MODULE:
+        LockModule( (MODULE*) GetScreen()->GetCurItem(), true );
+        return;
+
+    case ID_POPUP_PCB_AUTOPLACE_FREE_MODULE:
+        LockModule( (MODULE*) GetScreen()->GetCurItem(), false );
+        return;
+
+    case ID_POPUP_PCB_AUTOPLACE_FREE_ALL_MODULES:
+        LockModule( NULL, false );
+        return;
+
+    case ID_POPUP_PCB_AUTOPLACE_FIXE_ALL_MODULES:
+        LockModule( NULL, true );
+        return;
+
+    case ID_POPUP_CANCEL_CURRENT_COMMAND:
+        if( m_canvas->IsMouseCaptured() )
+        {
+            m_canvas->CallEndMouseCapture( &dc );
+        }
+
+        break;
+
+    default:   // Abort a current command (if any)
+        m_canvas->EndMouseCapture( ID_NO_TOOL_SELECTED, m_canvas->GetDefaultCursor() );
+        break;
+    }
+
+    // Erase ratsnest if needed
+    if( GetBoard()->IsElementVisible(RATSNEST_VISIBLE) )
+        DrawGeneralRatsnest( &dc );
+
+    GetBoard()->m_Status_Pcb |= DO_NOT_SHOW_GENERAL_RASTNEST;
+
+    switch( id )
+    {
+    case ID_POPUP_PCB_AUTOPLACE_CURRENT_MODULE:
+        AutoPlaceModule( (MODULE*) GetScreen()->GetCurItem(), PLACE_1_MODULE, &dc );
+        break;
+
+    case ID_POPUP_PCB_AUTOPLACE_ALL_MODULES:
+        AutoPlaceModule( NULL, PLACE_ALL, &dc );
+        break;
+
+    case ID_POPUP_PCB_AUTOPLACE_NEW_MODULES:
+        AutoPlaceModule( NULL, PLACE_OUT_OF_BOARD, &dc );
+        break;
+
+    case ID_POPUP_PCB_AUTOPLACE_NEXT_MODULE:
+        AutoPlaceModule( NULL, PLACE_INCREMENTAL, &dc );
+        break;
+
+    case ID_POPUP_PCB_SPREAD_ALL_MODULES:
+        if( !IsOK( this,
+                   _("Not locked footprints inside the board will be moved. OK?") ) )
+            break;
+        // Fall through
+    case ID_POPUP_PCB_SPREAD_NEW_MODULES:
+        if( GetBoard()->m_Modules == NULL )
+        {
+            DisplayError( this, _( "No footprint found!" ) );
+            return;
+        }
+
+        SpreadFootprints( id == ID_POPUP_PCB_SPREAD_NEW_MODULES );
+        break;
+
+    case ID_POPUP_PCB_AUTOROUTE_ALL_MODULES:
+        Autoroute( &dc, ROUTE_ALL );
+        break;
+
+    case ID_POPUP_PCB_AUTOROUTE_MODULE:
+        Autoroute( &dc, ROUTE_MODULE );
+        break;
+
+    case ID_POPUP_PCB_AUTOROUTE_PAD:
+        Autoroute( &dc, ROUTE_PAD );
+        break;
+
+    case ID_POPUP_PCB_AUTOROUTE_NET:
+        Autoroute( &dc, ROUTE_NET );
+        break;
+
+    case ID_POPUP_PCB_AUTOROUTE_RESET_UNROUTED:
+        Reset_Noroutable( &dc );
+        break;
+
+    default:
+        wxMessageBox( wxT( "OnPlaceOrRouteFootprints command error" ) );
+        break;
+    }
+
+    GetBoard()->m_Status_Pcb &= ~DO_NOT_SHOW_GENERAL_RASTNEST;
+    Compile_Ratsnest( &dc, true );
+}
+
+
+/* Set or reset (true or false) Lock attribute of aModule or all modules if aModule == NULL
+ */
+void PCB_EDIT_FRAME::LockModule( MODULE* aModule, bool aLocked )
+{
+    if( aModule )
+    {
+        aModule->SetLocked( aLocked );
+        SetMsgPanel( aModule );
+        OnModify();
+    }
+    else
+    {
+        aModule = GetBoard()->m_Modules;
+
+        for( ; aModule != NULL; aModule = aModule->Next() )
+        {
+            if( WildCompareString( ModulesMaskSelection, aModule->GetReference() ) )
+            {
+                aModule->SetLocked( aLocked );
+                OnModify();
+            }
+        }
+    }
+}
+
diff --git a/pcbnew/autorouter/queue.cpp b/pcbnew/autorouter/queue.cpp
new file mode 100644
index 0000000..0cf1977
--- /dev/null
+++ b/pcbnew/autorouter/queue.cpp
@@ -0,0 +1,220 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2015 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors.
+ *
+ * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+
+/**
+ * @file queue.cpp
+ */
+
+#include <fctsys.h>
+#include <common.h>
+
+#include <pcbnew.h>
+#include <autorout.h>
+#include <cell.h>
+
+
+struct PcbQueue /* search queue structure */
+{
+    struct PcbQueue* Next;
+    int              Row;       /* current row                  */
+    int              Col;       /* current column               */
+    int              Side;      /* 0=top, 1=bottom              */
+    int              Dist;      /* path distance to this cell so far        */
+    int              ApxDist;   /* approximate distance to target from here */
+};
+
+static long             qlen = 0;   /* current queue length */
+static struct PcbQueue* Head = NULL;
+static struct PcbQueue* Tail = NULL;
+static struct PcbQueue* Save = NULL;    /* hold empty queue structs */
+
+
+/* Free the memory used for storing all the queue */
+void FreeQueue()
+{
+    struct PcbQueue* p;
+
+    InitQueue();
+
+    while( (p = Save) != NULL )
+    {
+        Save = p->Next;
+        delete p;
+    }
+}
+
+
+/* initialize the search queue */
+void InitQueue()
+{
+    struct PcbQueue* p;
+
+    while( (p = Head) != NULL )
+    {
+        Head    = p->Next;
+        p->Next = Save; Save = p;
+    }
+
+    Tail = NULL;
+    OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
+}
+
+
+/* get search queue item from list */
+void GetQueue( int* r, int* c, int* s, int* d, int* a )
+{
+    struct PcbQueue* p;
+
+    if( (p = Head) != NULL )  /* return first item in list */
+    {
+        *r = p->Row; *c = p->Col;
+        *s = p->Side;
+        *d = p->Dist; *a = p->ApxDist;
+
+        if( (Head = p->Next) == NULL )
+            Tail = NULL;
+
+        /* put node on free list */
+        p->Next = Save; Save = p;
+        ClosNodes++; qlen--;
+    }
+    else /* empty list */
+    {
+        *r = *c = *s = *d = *a = ILLEGAL;
+    }
+}
+
+
+/* add a search node to the list
+ *  :
+ *      1 - OK
+ *      0 - Failed to allocate memory.
+ */
+bool SetQueue( int r, int c, int side, int d, int a, int r2, int c2 )
+{
+    struct PcbQueue* p, * q, * t;
+    int i, j;
+
+    j = 0;                      // gcc warning fix
+
+    if( (p = Save) != NULL )    /* try free list first */
+    {
+        Save = p->Next;
+    }
+    else if( ( p = (PcbQueue*) operator new( sizeof( PcbQueue ), std::nothrow ) ) == NULL )
+    {
+        return 0;
+    }
+
+    p->Row  = r;
+    p->Col  = c;
+    p->Side = side;
+    i = (p->Dist = d) + (p->ApxDist = a);
+    p->Next = NULL;
+
+    if( (q = Head) != NULL ) /* insert in proper position in list */
+    {
+        if( q->Dist + q->ApxDist > i ) /* insert at head */
+        {
+            p->Next = q; Head = p;
+        }
+        else   /* search for proper position */
+        {
+            for( t = q, q = q->Next; q && i > ( j = q->Dist + q->ApxDist ); t = q, q = q->Next )
+                ;
+
+            if( q && i == j && q->Row == r2 && q->Col == c2 )
+            {
+                /* insert after q, which is a goal node */
+                if( ( p->Next = q->Next ) == NULL )
+                    Tail = p;
+
+                q->Next = p;
+            }
+            else  /* insert in front of q */
+            {
+                if( ( p->Next = q ) == NULL )
+                    Tail = p;
+
+                t->Next = p;
+            }
+        }
+    }
+    else /* empty search list */
+    {
+        Head = Tail = p;
+    }
+
+    OpenNodes++;
+
+    if( ++qlen > MaxNodes )
+        MaxNodes = qlen;
+
+    return 1;
+}
+
+
+/* reposition node in list */
+void ReSetQueue( int r, int c, int s, int d, int a, int r2, int c2 )
+{
+    struct PcbQueue* p, * q;
+
+    /* first, see if it is already in the list */
+    for( q = NULL, p = Head; p; q = p, p = p->Next )
+    {
+        if( p->Row == r && p->Col == c && p->Side == s )
+        {
+            /* old one to remove */
+            if( q )
+            {
+                if( ( q->Next = p->Next ) == NULL )
+                    Tail = q;
+            }
+            else if( ( Head = p->Next ) == NULL )
+            {
+                Tail = NULL;
+            }
+
+            p->Next = Save;
+            Save = p;
+            OpenNodes--;
+            MoveNodes++;
+            qlen--;
+            break;
+        }
+    }
+
+    if( !p )            /* not found, it has already been closed once */
+        ClosNodes--;    /* we will close it again, but just count once */
+
+    /* if it was there, it's gone now; insert it at the proper position */
+    bool res = SetQueue( r, c, s, d, a, r2, c2 );
+    (void) res;
+}
diff --git a/pcbnew/autorouter/rect_placement/RectanglePlacement.txt b/pcbnew/autorouter/rect_placement/RectanglePlacement.txt
new file mode 100644
index 0000000..cecbf2e
--- /dev/null
+++ b/pcbnew/autorouter/rect_placement/RectanglePlacement.txt
@@ -0,0 +1,38 @@
+A class that fits subrectangles into a power-of-2 rectangle
+
+(C) Copyright 2000-2002 by Javier Arevalo
+This code is free to use and modify for all purposes
+
+You have a bunch of rectangular pieces. You need to arrange them in a
+rectangular surface so that they don't overlap, keeping the total area of the
+rectangle as small as possible. This is fairly common when arranging characters
+in a bitmapped font, lightmaps for a 3D engine, and I guess other situations as
+well.
+
+The idea of this algorithm is that, as we add rectangles, we can pre-select
+"interesting" places where we can try to add the next rectangles. For optimal
+results, the rectangles should be added in order. I initially tried using area
+as a sorting criteria, but it didn't work well with very tall or very flat
+rectangles. I then tried using the longest dimension as a selector, and it
+worked much better. So much for intuition...
+
+These "interesting" places are just to the right and just below the currently
+added rectangle. The first rectangle, obviously, goes at the top left, the next
+one would go either to the right or below this one, and so on. It is a weird way
+to do it, but it seems to work very nicely.
+
+The way we search here is fairly brute-force, the fact being that for most off-
+line purposes the performance seems more than adequate. I have generated a
+japanese font with around 8500 characters and all the time was spent generating
+the bitmaps.
+
+Also, for all we care, we could grow the parent rectangle in a different way
+than power of two. It just happens that power of 2 is very convenient for
+graphics hardware textures.
+
+I'd be interested in hearing of other approaches to this problem. Make sure
+to post them on http://www.flipcode.com
+
+See also
+http://www.flipcode.com/archives/Rectangle_Placement.shtml
+http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing
diff --git a/pcbnew/autorouter/rect_placement/rect_placement.cpp b/pcbnew/autorouter/rect_placement/rect_placement.cpp
new file mode 100644
index 0000000..f562c2b
--- /dev/null
+++ b/pcbnew/autorouter/rect_placement/rect_placement.cpp
@@ -0,0 +1,259 @@
+// ----------------------------------------------------------------------------------------
+// Name        : rect_placement.cpp
+// Description : A class that fits subrectangles into a power-of-2 rectangle
+// (C) Copyright 2000-2002 by Javier Arevalo
+// This code is free to use and modify for all purposes
+// ----------------------------------------------------------------------------------------
+
+/*
+ *  You have a bunch of rectangular pieces. You need to arrange them in a
+ *  rectangular surface so that they don't overlap, keeping the total area of the
+ *  rectangle as small as possible. This is fairly common when arranging characters
+ *  in a bitmapped font, lightmaps for a 3D engine, and I guess other situations as
+ *  well.
+ *
+ *  The idea of this algorithm is that, as we add rectangles, we can pre-select
+ *  "interesting" places where we can try to add the next rectangles. For optimal
+ *  results, the rectangles should be added in order. I initially tried using area
+ *  as a sorting criteria, but it didn't work well with very tall or very flat
+ *  rectangles. I then tried using the longest dimension as a selector, and it
+ *  worked much better. So much for intuition...
+ *
+ *  These "interesting" places are just to the right and just below the currently
+ *  added rectangle. The first rectangle, obviously, goes at the top left, the next
+ *  one would go either to the right or below this one, and so on. It is a weird way
+ *  to do it, but it seems to work very nicely.
+ *
+ *  The way we search here is fairly brute-force, the fact being that for most off-
+ *  line purposes the performance seems more than adequate. I have generated a
+ *  japanese font with around 8500 characters and all the time was spent generating
+ *  the bitmaps.
+ *
+ *  Also, for all we care, we could grow the parent rectangle.
+ *
+ *  I'd be interested in hearing of other approaches to this problem. Make sure
+ *  to post them on http://www.flipcode.com
+ */
+
+#include "rect_placement.h"
+
+// --------------------------------------------------------------------------------
+// Name        :
+// Description :
+// --------------------------------------------------------------------------------
+void CRectPlacement::Init( int w, int h )
+{
+    End();
+    m_size = TRect( 0, 0, w, h );
+    m_vPositions.push_back( TPos( 0, 0 ) );
+    m_area = 0;
+}
+
+
+// --------------------------------------------------------------------------------
+// Name        :
+// Description :
+// --------------------------------------------------------------------------------
+void CRectPlacement::End()
+{
+    m_vPositions.clear();
+    m_vRects.clear();
+    m_size.w = 0;
+}
+
+
+// --------------------------------------------------------------------------------
+// Name        : IsFree
+// Description : Check if the given rectangle is partially or totally used
+// --------------------------------------------------------------------------------
+bool CRectPlacement::IsFree( const TRect& r ) const
+{
+    if( !m_size.Contains( r ) )
+        return false;
+
+    for( CRectArray::const_iterator it = m_vRects.begin();
+         it != m_vRects.end(); ++it )
+    {
+        if( it->Intersects( r ) )
+            return false;
+    }
+
+    return true;
+}
+
+
+// --------------------------------------------------------------------------------
+// Name        : AddPosition
+// Description : Add new anchor point
+// --------------------------------------------------------------------------------
+void CRectPlacement::AddPosition( const TPos& p )
+{
+    // Try to insert anchor as close as possible to the top left corner
+    // So it will be tried first
+    bool bFound = false;
+    CPosArray::iterator it;
+
+    for( it = m_vPositions.begin();
+         !bFound && it != m_vPositions.end();
+         ++it )
+    {
+        if( p.x + p.y < it->x + it->y )
+            bFound = true;
+    }
+
+    if( bFound )
+        m_vPositions.insert( it, p );
+    else
+        m_vPositions.push_back( p );
+}
+
+
+// --------------------------------------------------------------------------------
+// Name        : AddRect
+// Description : Add the given rect and updates anchor points
+// --------------------------------------------------------------------------------
+void CRectPlacement::AddRect( const TRect& r )
+{
+    m_vRects.push_back( r );
+    m_area += r.w * r.h;
+
+    // Add two new anchor points
+    AddPosition( TPos( r.x, r.y + r.h ) );
+    AddPosition( TPos( r.x + r.w, r.y ) );
+}
+
+
+// --------------------------------------------------------------------------------
+// Name        : AddAtEmptySpot
+// Description : Add the given rectangle
+// --------------------------------------------------------------------------------
+bool CRectPlacement::AddAtEmptySpot( TRect& r )
+{
+    // Find a valid spot among available anchors.
+    bool bFound = false;
+    CPosArray::iterator it;
+
+    for( it = m_vPositions.begin();
+         !bFound && it != m_vPositions.end();
+         ++it )
+    {
+        TRect Rect( it->x, it->y, r.w, r.h );
+
+        if( IsFree( Rect ) )
+        {
+            r = Rect;
+            bFound = true;
+            break; // Don't let the loop increase the iterator.
+        }
+    }
+
+    if( bFound )
+    {
+        int x, y;
+
+        // Remove the used anchor point
+        m_vPositions.erase( it );
+
+        // Sometimes, anchors end up displaced from the optimal position
+        // due to irregular sizes of the subrects.
+        // So, try to adjut it up & left as much as possible.
+        for( x = 1; x <= r.x; x++ )
+        {
+            if( !IsFree( TRect( r.x - x, r.y, r.w, r.h ) ) )
+                break;
+        }
+
+        for( y = 1; y <= r.y; y++ )
+        {
+            if( !IsFree( TRect( r.x, r.y - y, r.w, r.h ) ) )
+                break;
+        }
+
+        if( y > x )
+            r.y -= y - 1;
+        else
+            r.x -= x - 1;
+
+        AddRect( r );
+    }
+
+    return bFound;
+}
+
+#include <stdio.h>
+// --------------------------------------------------------------------------------
+// Name        : AddAtEmptySpotAutoGrow
+// Description : Add a rectangle of the given size, growing our area if needed
+// Area grows only until the max given.
+// Returns the placement of the rect in the rect's x,y coords
+// --------------------------------------------------------------------------------
+bool CRectPlacement::AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH )
+{
+    double growing_factor = 1.2;    // Must be > 1.0, and event > 1.1 for fast optimization
+
+    #define GROW(x) ((x * growing_factor) + 1)
+
+    if( pRect->w <= 0 )
+        return true;
+
+    int orgW    = m_size.w;
+    int orgH    = m_size.h;
+
+    // Try to add it in the existing space
+    while( !AddAtEmptySpot( *pRect ) )
+    {
+        int pw  = m_size.w;
+        int ph  = m_size.h;
+
+        // Sanity check - if area is complete.
+        if( pw >= maxW && ph >= maxH )
+        {
+            m_size.w    = orgW;
+            m_size.h    = orgH;
+            return false;
+        }
+
+        // Try growing the smallest dim
+        if( pw < maxW && ( pw < ph || ( (pw == ph) && (pRect->w >= pRect->h) ) ) )
+            m_size.w = GROW( pw );
+        else
+            m_size.h = GROW( ph );
+
+        if( AddAtEmptySpot( *pRect ) )
+            break;
+
+        // Try growing the other dim instead
+        if( pw != m_size.w )
+        {
+            m_size.w = pw;
+
+            if( ph < maxW )
+                m_size.h = GROW( ph );
+        }
+        else
+        {
+            m_size.h = ph;
+
+            if( pw < maxW )
+                m_size.w = GROW( pw );
+        }
+
+        if( pw != m_size.w || ph != m_size.h )
+            if( AddAtEmptySpot( *pRect ) )
+                break;
+
+
+
+        // Grow both if possible, and reloop.
+        m_size.w    = pw;
+        m_size.h    = ph;
+
+        if( pw < maxW )
+            m_size.w = GROW( pw );
+
+        if( ph < maxH )
+            m_size.h = GROW( ph );
+    }
+
+    return true;
+}
diff --git a/pcbnew/autorouter/rect_placement/rect_placement.h b/pcbnew/autorouter/rect_placement/rect_placement.h
new file mode 100644
index 0000000..b89b538
--- /dev/null
+++ b/pcbnew/autorouter/rect_placement/rect_placement.h
@@ -0,0 +1,104 @@
+// --------------------------------------------------------------------------------
+// Name        : rect_placement.h
+// Description : A class that allocates subrectangles into power-of-2 rectangles
+// (C) Copyright 2000-2002 by Javier Arevalo
+// This code is free to use and modify for all purposes
+// --------------------------------------------------------------------------------
+
+/**
+ * @file rect_placement.h
+ */
+
+#ifndef _RECT_PLACEMENT_H_
+#define _RECT_PLACEMENT_H_
+
+#include <vector>
+
+// --------------------------------------------------------------------------------
+// --------------------------------------------------------------------------------
+
+class CRectPlacement
+{
+public:
+
+    // Helper classes
+    struct TPos
+    {
+        int x, y;
+
+        TPos() : x( 0 ), y( 0 ) { }
+        TPos( int _x, int _y ) : x( _x ), y( _y ) { }
+
+        bool operator ==( const TPos& p ) const { return x == p.x && y == p.y; }
+    };
+
+    struct TRect : public TPos
+    {
+        int w, h;
+
+        TRect() : w( 0 ), h( 0 ) { }
+        TRect( int _x, int _y, int _w, int _h ) : TPos( _x, _y ), w( _w > 0 ? _w : 0 ), h(
+                _h > 0 ? _h : 0 ) { }
+
+        bool Contains( const TPos& p )  const
+        {
+            return p.x >= x && p.y >= y && p.x < (x + w) && p.y < (y + h);
+        }
+        bool Contains( const TRect& r ) const
+        {
+            return r.x >= x && r.y >= y &&
+                   (r.x + r.w) <= (x + w) && (r.y + r.h) <= (y + h);
+        }
+        bool Intersects( const TRect& r ) const
+        {
+            return w > 0 && h > 0 && r.w > 0 && r.h > 0
+                   && ( (r.x + r.w) > x && r.x < (x + w) && (r.y + r.h) > y && r.y < (y + h) );
+        }
+
+        // static bool Greater(const TRect &a, const TRect &b)
+        //  { return a.w*a.h > b.w*b.h; }
+        // Greater rect area. Not as good as the next heuristic:
+        // Greater size in at least one dim.
+        static bool Greater( const TRect&   a, const TRect&   b )
+        {
+            return (a.w > b.w && a.w > b.h) || (a.h > b.w && a.h > b.h);
+        }
+    };
+
+    // ---------------------
+
+    typedef std::vector<TPos>   CPosArray;
+    typedef std::vector<TRect>  CRectArray;
+
+    // ---------------------
+
+    CRectPlacement()                    { Init(); }
+    ~CRectPlacement()                   { End(); }
+
+    void    Init( int w = 1, int h = 1 );
+    void    End();
+
+    bool      IsOk() const { return m_size.w > 0; }
+
+    int       GetW() const { return m_size.w; }
+    int       GetH() const { return m_size.h; }
+    double    GetArea() const { return m_area; }
+    double    GetTotalArea() const { return (double)m_size.w * m_size.h; }
+
+    bool AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH );
+
+private:
+    TRect       m_size;
+    CRectArray  m_vRects;
+    CPosArray   m_vPositions;
+    double      m_area;
+
+    // ---------------------
+
+    bool    IsFree( const TRect& r ) const;
+    void    AddPosition( const TPos& p );
+    void    AddRect( const TRect& r );
+    bool    AddAtEmptySpot( TRect& r );
+};
+
+#endif    // _RECT_PLACEMENT_H_
diff --git a/pcbnew/autorouter/routing_matrix.cpp b/pcbnew/autorouter/routing_matrix.cpp
new file mode 100644
index 0000000..2c97f0d
--- /dev/null
+++ b/pcbnew/autorouter/routing_matrix.cpp
@@ -0,0 +1,550 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+/**
+ * @file routing_matrix.cpp
+ * @brief Functions to create autorouting maps
+ */
+
+#include <fctsys.h>
+#include <common.h>
+
+#include <pcbnew.h>
+#include <cell.h>
+#include <autorout.h>
+
+#include <class_board.h>
+#include <class_module.h>
+#include <class_track.h>
+#include <class_drawsegment.h>
+#include <class_edge_mod.h>
+#include <class_pcb_text.h>
+
+
+MATRIX_ROUTING_HEAD::MATRIX_ROUTING_HEAD()
+{
+    m_BoardSide[0] = m_BoardSide[1] = NULL;
+    m_DistSide[0] = m_DistSide[1] = NULL;
+    m_DirSide[0] = m_DirSide[1] = NULL;
+    m_opWriteCell        = NULL;
+    m_InitMatrixDone     = false;
+    m_Nrows              = 0;
+    m_Ncols              = 0;
+    m_MemSize            = 0;
+    m_RoutingLayersCount = 1;
+    m_GridRouting        = 0;
+    m_RouteCount         = 0;
+}
+
+
+MATRIX_ROUTING_HEAD::~MATRIX_ROUTING_HEAD()
+{
+}
+
+
+bool MATRIX_ROUTING_HEAD::ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly )
+{
+    aPcb->ComputeBoundingBox( aUseBoardEdgesOnly );
+
+    // The boundary box must have its start point on routing grid:
+    m_BrdBox = aPcb->GetBoundingBox();
+
+    m_BrdBox.SetX( m_BrdBox.GetX() - ( m_BrdBox.GetX() % m_GridRouting ) );
+    m_BrdBox.SetY( m_BrdBox.GetY() - ( m_BrdBox.GetY() % m_GridRouting ) );
+
+    // The boundary box must have its end point on routing grid:
+    wxPoint end = m_BrdBox.GetEnd();
+
+    end.x -= end.x % m_GridRouting;
+    end.x += m_GridRouting;
+
+    end.y -= end.y % m_GridRouting;
+    end.y += m_GridRouting;
+
+    m_BrdBox.SetEnd( end );
+
+    aPcb->SetBoundingBox( m_BrdBox );
+
+    m_Nrows = m_BrdBox.GetHeight() / m_GridRouting;
+    m_Ncols = m_BrdBox.GetWidth() / m_GridRouting;
+
+    // gives a small margin
+    m_Ncols += 1;
+    m_Nrows += 1;
+
+    return true;
+}
+
+
+int MATRIX_ROUTING_HEAD::InitRoutingMatrix()
+{
+    if( m_Nrows <= 0 || m_Ncols <= 0 )
+        return 0;
+
+    m_InitMatrixDone = true;     // we have been called
+
+    // give a small margin for memory allocation:
+    int ii = (RoutingMatrix.m_Nrows + 1) * (RoutingMatrix.m_Ncols + 1);
+
+    int side = BOTTOM;
+    for( int jj = 0; jj < m_RoutingLayersCount; jj++ )  // m_RoutingLayersCount = 1 or 2
+    {
+        m_BoardSide[side] = NULL;
+        m_DistSide[side]  = NULL;
+        m_DirSide[side]   = NULL;
+
+        // allocate matrix & initialize everything to empty
+        m_BoardSide[side] = (MATRIX_CELL*) operator new( ii * sizeof(MATRIX_CELL) );
+        memset( m_BoardSide[side], 0, ii * sizeof(MATRIX_CELL) );
+
+        if( m_BoardSide[side] == NULL )
+            return -1;
+
+        // allocate Distances
+        m_DistSide[side] = (DIST_CELL*) operator new( ii * sizeof(DIST_CELL) );
+        memset( m_DistSide[side], 0, ii * sizeof(DIST_CELL) );
+
+        if( m_DistSide[side] == NULL )
+            return -1;
+
+        // allocate Dir (chars)
+        m_DirSide[side] = (char*) operator new( ii );
+        memset( m_DirSide[side], 0, ii );
+
+        if( m_DirSide[side] == NULL )
+            return -1;
+
+        side = TOP;
+    }
+
+    m_MemSize = m_RouteCount * ii * ( sizeof(MATRIX_CELL)
+                + sizeof(DIST_CELL) + sizeof(char) );
+
+    return m_MemSize;
+}
+
+
+void MATRIX_ROUTING_HEAD::UnInitRoutingMatrix()
+{
+    int ii;
+
+    m_InitMatrixDone = false;
+
+    for( ii = 0; ii < MAX_ROUTING_LAYERS_COUNT; ii++ )
+    {
+        // de-allocate Dir matrix
+        if( m_DirSide[ii] )
+        {
+            delete m_DirSide[ii];
+            m_DirSide[ii] = NULL;
+        }
+
+        // de-allocate Distances matrix
+        if( m_DistSide[ii] )
+        {
+            delete m_DistSide[ii];
+            m_DistSide[ii] = NULL;
+        }
+
+        // de-allocate cells matrix
+        if( m_BoardSide[ii] )
+        {
+            delete m_BoardSide[ii];
+            m_BoardSide[ii] = NULL;
+        }
+    }
+
+    m_Nrows = m_Ncols = 0;
+}
+
+
+/**
+ * Function PlaceCells
+ * Initialize the matrix routing by setting obstacles for each occupied cell
+ * a cell set to HOLE is an obstacle for tracks and vias
+ * a cell set to VIA_IMPOSSIBLE is an obstacle for vias only.
+ * a cell set to CELL_is_EDGE is a frontier.
+ * Tracks and vias having the same net code as net_code are skipped
+ * (htey do not are obstacles)
+ *
+ * For single-sided Routing 1:
+ * BOTTOM side is used, and Route_Layer_BOTTOM = Route_Layer_TOP
+ *
+ * If flag == FORCE_PADS: all pads will be put in matrix as obstacles.
+ */
+void PlaceCells( BOARD* aPcb, int net_code, int flag )
+{
+    int     ux0 = 0, uy0 = 0, ux1, uy1, dx, dy;
+    int     marge, via_marge;
+    LSET    layerMask;
+
+    // use the default NETCLASS?
+    NETCLASSPTR nc = aPcb->GetDesignSettings().GetDefault();
+
+    int     trackWidth = nc->GetTrackWidth();
+    int     clearance  = nc->GetClearance();
+    int     viaSize    = nc->GetViaDiameter();
+
+    marge     = clearance + (trackWidth / 2);
+    via_marge = clearance + (viaSize / 2);
+
+    // Place PADS on matrix routing:
+    for( unsigned i = 0; i < aPcb->GetPadCount(); ++i )
+    {
+        D_PAD* pad = aPcb->GetPad( i );
+
+        if( net_code != pad->GetNetCode() || (flag & FORCE_PADS) )
+        {
+            ::PlacePad( pad, HOLE, marge, WRITE_CELL );
+        }
+
+        ::PlacePad( pad, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+    }
+
+    // Place outlines of modules on matrix routing, if they are on a copper layer
+    // or on the edge layer
+
+    for( MODULE* module = aPcb->m_Modules; module; module = module->Next() )
+    {
+        for( BOARD_ITEM* item = module->GraphicalItems(); item; item = item->Next() )
+        {
+            switch( item->Type() )
+            {
+            case PCB_MODULE_EDGE_T:
+            {
+                EDGE_MODULE* edge = (EDGE_MODULE*) item;
+                EDGE_MODULE tmpEdge( *edge );
+
+                if( tmpEdge.GetLayer() == Edge_Cuts )
+                    tmpEdge.SetLayer( UNDEFINED_LAYER );
+
+                TraceSegmentPcb( &tmpEdge, HOLE, marge, WRITE_CELL );
+                TraceSegmentPcb( &tmpEdge, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+            }
+            break;
+
+            default:
+                break;
+            }
+        }
+    }
+
+    // Place board outlines and texts on copper layers:
+    for( BOARD_ITEM* item = aPcb->m_Drawings; item; item = item->Next() )
+    {
+        switch( item->Type() )
+        {
+        case PCB_LINE_T:
+            {
+                DRAWSEGMENT* DrawSegm;
+
+                int          type_cell = HOLE;
+                DrawSegm = (DRAWSEGMENT*) item;
+                DRAWSEGMENT tmpSegm( DrawSegm );
+
+                if( DrawSegm->GetLayer() == Edge_Cuts )
+                {
+                    tmpSegm.SetLayer( UNDEFINED_LAYER );
+                    type_cell |= CELL_is_EDGE;
+                }
+
+                TraceSegmentPcb( &tmpSegm, type_cell, marge, WRITE_CELL );
+            }
+            break;
+
+        case PCB_TEXT_T:
+            {
+                TEXTE_PCB* PtText = (TEXTE_PCB*) item;
+
+                if( PtText->GetText().Length() == 0 )
+                    break;
+
+                EDA_RECT textbox = PtText->GetTextBox( -1 );
+                ux0 = textbox.GetX();
+                uy0 = textbox.GetY();
+                dx  = textbox.GetWidth();
+                dy  = textbox.GetHeight();
+
+                // Put bounding box (rectangle) on matrix
+                dx /= 2;
+                dy /= 2;
+
+                ux1 = ux0 + dx;
+                uy1 = uy0 + dy;
+
+                ux0 -= dx;
+                uy0 -= dy;
+
+                layerMask = LSET( PtText->GetLayer() );
+
+                TraceFilledRectangle( ux0 - marge, uy0 - marge, ux1 + marge,
+                                      uy1 + marge, PtText->GetOrientation(),
+                                      layerMask, HOLE, WRITE_CELL );
+
+                TraceFilledRectangle( ux0 - via_marge, uy0 - via_marge,
+                                      ux1 + via_marge, uy1 + via_marge,
+                                      PtText->GetOrientation(),
+                                      layerMask, VIA_IMPOSSIBLE, WRITE_OR_CELL );
+            }
+            break;
+
+        default:
+            break;
+        }
+    }
+
+    // Put tracks and vias on matrix
+    for( TRACK* track = aPcb->m_Track; track; track = track->Next() )
+    {
+        if( net_code == track->GetNetCode() )
+            continue;
+
+        TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
+        TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+    }
+}
+
+
+int Build_Work( BOARD* Pcb )
+{
+    RATSNEST_ITEM*  pt_rats;
+    D_PAD*          pt_pad;
+    int             r1, r2, c1, c2, current_net_code;
+    RATSNEST_ITEM*  pt_ch;
+    int             demi_pas = RoutingMatrix.m_GridRouting / 2;
+    wxString        msg;
+
+    InitWork(); // clear work list
+    int cellCount = 0;
+
+    for( unsigned ii = 0; ii < Pcb->GetRatsnestsCount(); ii++ )
+    {
+        pt_rats = &Pcb->m_FullRatsnest[ii];
+
+        /* We consider here only ratsnest that are active ( obviously not yet routed)
+         * and routables (that are not yet attempt to be routed and fail
+         */
+        if( (pt_rats->m_Status & CH_ACTIF) == 0 )
+            continue;
+
+        if( pt_rats->m_Status & CH_UNROUTABLE )
+            continue;
+
+        if( (pt_rats->m_Status & CH_ROUTE_REQ) == 0 )
+            continue;
+
+        pt_pad = pt_rats->m_PadStart;
+
+        current_net_code = pt_pad->GetNetCode();
+        pt_ch = pt_rats;
+
+        r1 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY() + demi_pas )
+            / RoutingMatrix.m_GridRouting;
+
+        if( r1 < 0 || r1 >= RoutingMatrix.m_Nrows )
+        {
+            msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r1,
+                        pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        c1 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas ) / RoutingMatrix.m_GridRouting;
+
+        if( c1 < 0 || c1 >= RoutingMatrix.m_Ncols )
+        {
+            msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c1,
+                        pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        pt_pad = pt_rats->m_PadEnd;
+
+        r2 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY()
+               + demi_pas ) / RoutingMatrix.m_GridRouting;
+
+        if( r2 < 0 || r2 >= RoutingMatrix.m_Nrows )
+        {
+            msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r2,
+                        pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        c2 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas )
+             / RoutingMatrix.m_GridRouting;
+
+        if( c2 < 0 || c2 >= RoutingMatrix.m_Ncols )
+        {
+            msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c2,
+                        pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        SetWork( r1, c1, current_net_code, r2, c2, pt_ch, 0 );
+        cellCount++;
+    }
+
+    SortWork();
+    return cellCount;
+}
+
+// Initialize m_opWriteCell member to make the aLogicOp
+void MATRIX_ROUTING_HEAD::SetCellOperation( int aLogicOp )
+{
+    switch( aLogicOp )
+    {
+    default:
+    case WRITE_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::SetCell;
+        break;
+
+    case WRITE_OR_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::OrCell;
+        break;
+
+    case WRITE_XOR_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::XorCell;
+        break;
+
+    case WRITE_AND_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::AndCell;
+        break;
+
+    case WRITE_ADD_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::AddCell;
+        break;
+    }
+}
+
+
+/* return the value stored in a cell
+ */
+MATRIX_CELL MATRIX_ROUTING_HEAD::GetCell( int aRow, int aCol, int aSide )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    return p[aRow * m_Ncols + aCol];
+}
+
+
+/* basic cell operation : WRITE operation
+ */
+void MATRIX_ROUTING_HEAD::SetCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] = x;
+}
+
+
+/* basic cell operation : OR operation
+ */
+void MATRIX_ROUTING_HEAD::OrCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] |= x;
+}
+
+
+/* basic cell operation : XOR operation
+ */
+void MATRIX_ROUTING_HEAD::XorCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] ^= x;
+}
+
+
+/* basic cell operation : AND operation
+ */
+void MATRIX_ROUTING_HEAD::AndCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] &= x;
+}
+
+
+/* basic cell operation : ADD operation
+ */
+void MATRIX_ROUTING_HEAD::AddCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] += x;
+}
+
+
+// fetch distance cell
+DIST_CELL MATRIX_ROUTING_HEAD::GetDist( int aRow, int aCol, int aSide ) // fetch distance cell
+{
+    DIST_CELL* p;
+
+    p = RoutingMatrix.m_DistSide[aSide];
+    return p[aRow * m_Ncols + aCol];
+}
+
+
+// store distance cell
+void MATRIX_ROUTING_HEAD::SetDist( int aRow, int aCol, int aSide, DIST_CELL x )
+{
+    DIST_CELL* p;
+
+    p = RoutingMatrix.m_DistSide[aSide];
+    p[aRow * m_Ncols + aCol] = x;
+}
+
+
+// fetch direction cell
+int MATRIX_ROUTING_HEAD::GetDir( int aRow, int aCol, int aSide )
+{
+    DIR_CELL* p;
+
+    p = RoutingMatrix.m_DirSide[aSide];
+    return (int) (p[aRow * m_Ncols + aCol]);
+}
+
+
+// store direction cell
+void MATRIX_ROUTING_HEAD::SetDir( int aRow, int aCol, int aSide, int x )
+{
+    DIR_CELL* p;
+
+    p = RoutingMatrix.m_DirSide[aSide];
+    p[aRow * m_Ncols + aCol] = (char) x;
+}
diff --git a/pcbnew/autorouter/solve.cpp b/pcbnew/autorouter/solve.cpp
new file mode 100644
index 0000000..c10e57f
--- /dev/null
+++ b/pcbnew/autorouter/solve.cpp
@@ -0,0 +1,1348 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+/* see "Autorouting With the A* Algorithm" (Dr.Dobbs journal)
+*/
+
+/**
+ * @file solve.cpp
+ */
+
+#include <fctsys.h>
+#include <class_drawpanel.h>
+#include <confirm.h>
+#include <wxPcbStruct.h>
+#include <gr_basic.h>
+#include <macros.h>
+
+#include <class_board.h>
+#include <class_track.h>
+
+#include <pcbnew.h>
+#include <protos.h>
+#include <autorout.h>
+#include <cell.h>
+
+
+static int Autoroute_One_Track( PCB_EDIT_FRAME* pcbframe,
+                                wxDC*           DC,
+                                int             two_sides,
+                                int             row_source,
+                                int             col_source,
+                                int             row_target,
+                                int             col_target,
+                                RATSNEST_ITEM*  pt_rat );
+
+static int Retrace( PCB_EDIT_FRAME* pcbframe,
+                    wxDC*           DC,
+                    int,
+                    int,
+                    int,
+                    int,
+                    int,
+                    int              net_code );
+
+static void OrCell_Trace( BOARD* pcb,
+                          int    col,
+                          int    row,
+                          int    side,
+                          int    orient,
+                          int    current_net_code );
+
+static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC );
+
+
+static int            segm_oX, segm_oY;
+static int            segm_fX, segm_fY; /* Origin and position of the current
+                                         * trace segment. */
+static RATSNEST_ITEM* pt_cur_ch;
+static int            s_Clearance;  // Clearance value used in autorouter
+
+static PICKED_ITEMS_LIST s_ItemsListPicker;
+
+int OpenNodes;       // total number of nodes opened
+int ClosNodes;       // total number of nodes closed
+int MoveNodes;       // total number of nodes moved
+int MaxNodes;        // maximum number of nodes opened at one time
+
+#define NOSUCCESS       0
+#define STOP_FROM_ESC   -1
+#define ERR_MEMORY      -2
+#define SUCCESS         1
+#define TRIVIAL_SUCCESS 2
+
+/*
+** visit neighboring cells like this (where [9] is on the other side):
+**
+**  +---+---+---+
+**  | 1 | 2 | 3 |
+**  +---+---+---+
+**  | 4 |[9]| 5 |
+**  +---+---+---+
+**  | 6 | 7 | 8 |
+**  +---+---+---+
+*/
+
+/* for visiting neighbors on the same side: increments/decrements coord of
+ * [] [0] = row [] (1] = col was added to the coord of the midpoint for
+ * Get the coord of the 8 neighboring points.
+ */
+static const int delta[8][2] =
+{
+    {  1, -1 },     // northwest
+    {  1, 0  },     // north
+    {  1, 1  },     // northeast
+    {  0, -1 },     // west
+    {  0, 1  },     // east
+    { -1, -1 },     // southwest
+    { -1, 0  },     // south
+    { -1, 1  }      // southeast
+};
+
+static const int ndir[8] =
+{
+    // for building paths back to source
+    FROM_SOUTHEAST, FROM_SOUTH,     FROM_SOUTHWEST,
+    FROM_EAST,      FROM_WEST,
+    FROM_NORTHEAST, FROM_NORTH,     FROM_NORTHWEST
+};
+
+// blocking masks for neighboring cells
+#define BLOCK_NORTHEAST ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
+                          | ANGLE_NEtoSE | ANGLE_NWtoNE         \
+                          | SHARP_NtoNE | SHARP_EtoNE | HOLE )
+#define BLOCK_SOUTHEAST ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
+                          | ANGLE_NEtoSE | ANGLE_SEtoSW         \
+                          | SHARP_EtoSE | SHARP_StoSE | HOLE )
+#define BLOCK_SOUTHWEST ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
+                          | ANGLE_SEtoSW | ANGLE_SWtoNW         \
+                          | SHARP_StoSW | SHARP_WtoSW | HOLE )
+#define BLOCK_NORTHWEST ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
+                          | ANGLE_SWtoNW | ANGLE_NWtoNE         \
+                          | SHARP_WtoNW | SHARP_NtoNW | HOLE )
+#define BLOCK_NORTH     ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW      \
+                          | BENT_EtoNW | BENT_WtoNE                    \
+                          | BENT_StoNE | BENT_StoNW                    \
+                          | CORNER_NORTHEAST | CORNER_NORTHWEST        \
+                          | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \
+                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
+                          | SHARP_NtoNE | SHARP_NtoNW                  \
+                          | SHARP_EtoNE | SHARP_WtoNW | HOLE )
+#define BLOCK_EAST      ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW    \
+                          | BENT_NtoSE | BENT_StoNE                    \
+                          | BENT_WtoNE | BENT_WtoSE                    \
+                          | CORNER_NORTHEAST | CORNER_SOUTHEAST        \
+                          | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \
+                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
+                          | SHARP_EtoNE | SHARP_EtoSE                  \
+                          | SHARP_NtoNE | SHARP_StoSE | HOLE )
+#define BLOCK_SOUTH     ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW      \
+                          | BENT_EtoSW | BENT_WtoSE                    \
+                          | BENT_NtoSE | BENT_NtoSW                    \
+                          | CORNER_SOUTHEAST | CORNER_SOUTHWEST        \
+                          | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \
+                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
+                          | SHARP_StoSE | SHARP_StoSW                  \
+                          | SHARP_EtoSE | SHARP_WtoSW | HOLE )
+#define BLOCK_WEST      ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE    \
+                          | BENT_NtoSW | BENT_StoNW                    \
+                          | BENT_EtoSW | BENT_EtoNW                    \
+                          | CORNER_SOUTHWEST | CORNER_NORTHWEST        \
+                          | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \
+                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
+                          | SHARP_WtoSW | SHARP_WtoNW                  \
+                          | SHARP_NtoNW | SHARP_StoSW | HOLE )
+
+struct block
+{
+    int  r1, c1;
+    long b1;
+    int  r2, c2;
+    long b2;
+};
+
+// blocking masks for diagonal traces
+static struct block blocking[8] =
+{ {
+      0, -1,
+      BLOCK_NORTHEAST,
+      1, 0,
+      BLOCK_SOUTHWEST
+  },
+  {
+      0, 0, 0,
+      0, 0, 0
+  },
+  {
+      1, 0,
+      BLOCK_SOUTHEAST,
+      0, 1,
+      BLOCK_NORTHWEST
+  },
+  {
+      0, 0, 0,
+      0, 0, 0
+  },
+  {
+      0, 0, 0,
+      0, 0, 0
+  },
+  {
+      0, -1,
+      BLOCK_SOUTHEAST,
+      -1, 0,
+      BLOCK_NORTHWEST
+  },
+  {
+      0, 0, 0,
+      0, 0, 0
+  },
+  {
+      -1, 0,
+      BLOCK_NORTHEAST,
+      0, 1,
+      BLOCK_SOUTHWEST
+  } };
+
+// mask for hole-related blocking effects
+static struct
+{
+    long trace;
+    int  present;
+} selfok2[8] =
+{
+    { HOLE_NORTHWEST, 0 },
+    { HOLE_NORTH,     0 },
+    { HOLE_NORTHEAST, 0 },
+    { HOLE_WEST,      0 },
+    { HOLE_EAST,      0 },
+    { HOLE_SOUTHWEST, 0 },
+    { HOLE_SOUTH,     0 },
+    { HOLE_SOUTHEAST, 0 }
+};
+
+static long newmask[8] =
+{
+    // patterns to mask out in neighbor cells
+    0,
+    CORNER_NORTHWEST | CORNER_NORTHEAST,
+    0,
+    CORNER_NORTHWEST | CORNER_SOUTHWEST,
+    CORNER_NORTHEAST | CORNER_SOUTHEAST,
+    0,
+    CORNER_SOUTHWEST | CORNER_SOUTHEAST,
+    0
+};
+
+
+/* Route all traces
+ * :
+ *  1 if OK
+ * -1 if escape (stop being routed) request
+ * -2 if default memory allocation
+ */
+int PCB_EDIT_FRAME::Solve( wxDC* DC, int aLayersCount )
+{
+    int           current_net_code;
+    int           row_source, col_source, row_target, col_target;
+    int           success, nbsucces = 0, nbunsucces = 0;
+    NETINFO_ITEM* net;
+    bool          stop = false;
+    wxString      msg;
+    int           routedCount = 0;      // routed ratsnest count
+    bool          two_sides = aLayersCount == 2;
+
+    m_canvas->SetAbortRequest( false );
+
+    s_Clearance = GetBoard()->GetDesignSettings().GetDefault()->GetClearance();
+
+    // Prepare the undo command info
+    s_ItemsListPicker.ClearListAndDeleteItems();  // Should not be necessary, but...
+
+    // go until no more work to do
+    GetWork( &row_source, &col_source, &current_net_code,
+             &row_target, &col_target, &pt_cur_ch ); // First net to route.
+
+    for( ; row_source != ILLEGAL; GetWork( &row_source, &col_source,
+                                           &current_net_code, &row_target,
+                                           &col_target,
+                                           &pt_cur_ch ) )
+    {
+        // Test to stop routing ( escape key pressed )
+        wxYield();
+
+        if( m_canvas->GetAbortRequest() )
+        {
+            if( IsOK( this, _( "Abort routing?" ) ) )
+            {
+                success = STOP_FROM_ESC;
+                stop    = true;
+                break;
+            }
+            else
+            {
+                m_canvas->SetAbortRequest( false );
+            }
+        }
+
+        EraseMsgBox();
+
+        routedCount++;
+        net = GetBoard()->FindNet( current_net_code );
+
+        if( net )
+        {
+            msg.Printf( wxT( "[%8.8s]" ), GetChars( net->GetNetname() ) );
+            AppendMsgPanel( wxT( "Net route" ), msg, BROWN );
+            msg.Printf( wxT( "%d / %d" ), routedCount, RoutingMatrix.m_RouteCount );
+            AppendMsgPanel( wxT( "Activity" ), msg, BROWN );
+        }
+
+        segm_oX = GetBoard()->GetBoundingBox().GetX() + (RoutingMatrix.m_GridRouting * col_source);
+        segm_oY = GetBoard()->GetBoundingBox().GetY() + (RoutingMatrix.m_GridRouting * row_source);
+        segm_fX = GetBoard()->GetBoundingBox().GetX() + (RoutingMatrix.m_GridRouting * col_target);
+        segm_fY = GetBoard()->GetBoundingBox().GetY() + (RoutingMatrix.m_GridRouting * row_target);
+
+        // Draw segment.
+        GRLine( m_canvas->GetClipBox(), DC,
+                segm_oX, segm_oY, segm_fX, segm_fY,
+                0, WHITE );
+        pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_OR | GR_HIGHLIGHT );
+        pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_OR | GR_HIGHLIGHT );
+
+        success = Autoroute_One_Track( this, DC,
+                                       two_sides, row_source, col_source,
+                                       row_target, col_target, pt_cur_ch );
+
+        switch( success )
+        {
+        case NOSUCCESS:
+            pt_cur_ch->m_Status |= CH_UNROUTABLE;
+            nbunsucces++;
+            break;
+
+        case STOP_FROM_ESC:
+            stop = true;
+            break;
+
+        case ERR_MEMORY:
+            stop = true;
+            break;
+
+        default:
+            nbsucces++;
+            break;
+        }
+
+        msg.Printf( wxT( "%d" ), nbsucces );
+        AppendMsgPanel( wxT( "OK" ), msg, GREEN );
+        msg.Printf( wxT( "%d" ), nbunsucces );
+        AppendMsgPanel( wxT( "Fail" ), msg, RED );
+        msg.Printf( wxT( "  %d" ), GetBoard()->GetUnconnectedNetCount() );
+        AppendMsgPanel( wxT( "Not Connected" ), msg, CYAN );
+
+        // Delete routing from display.
+        pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_AND );
+        pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_AND );
+
+        if( stop )
+            break;
+    }
+
+    SaveCopyInUndoList( s_ItemsListPicker, UR_UNSPECIFIED );
+    s_ItemsListPicker.ClearItemsList(); // s_ItemsListPicker is no more owner of picked items
+
+    return SUCCESS;
+}
+
+
+/* Route a trace on the BOARD.
+ * Parameters:
+ * 1 side / 2 sides (0 / 1)
+ * Coord source (row, col)
+ * Coord destination (row, col)
+ * Net_code
+ * Pointer to the ratsnest reference
+ *
+ * Returns:
+ * SUCCESS if routed
+ * TRIVIAL_SUCCESS if pads are connected by overlay (no track needed)
+ * If failure NOSUCCESS
+ * Escape STOP_FROM_ESC if demand
+ * ERR_MEMORY if memory allocation failed.
+ */
+static int Autoroute_One_Track( PCB_EDIT_FRAME* pcbframe,
+                                wxDC*           DC,
+                                int             two_sides,
+                                int             row_source,
+                                int             col_source,
+                                int             row_target,
+                                int             col_target,
+                                RATSNEST_ITEM*  pt_rat )
+{
+    int          r, c, side, d, apx_dist, nr, nc;
+    int          result, skip;
+    int          i;
+    long         curcell, newcell, buddy, lastopen, lastclos, lastmove;
+    int          newdist, olddir, _self;
+    int          current_net_code;
+    int          marge;
+    LSET         padLayerMaskStart;    // Mask layers belonging to the starting pad.
+    LSET         padLayerMaskEnd;      // Mask layers belonging to the ending pad.
+
+    LSET         topLayerMask( g_Route_Layer_TOP );
+
+    LSET         bottomLayerMask( g_Route_Layer_BOTTOM );
+
+    LSET         routeLayerMask;       // Mask two layers for routing.
+
+    LSET         tab_mask[2];           // Enables the calculation of the mask layer being
+                                        // tested. (side = TOP or BOTTOM)
+    int          start_mask_layer = 0;
+    wxString     msg;
+
+    // @todo this could be a bottle neck
+    LSET all_cu = LSET::AllCuMask( pcbframe->GetBoard()->GetCopperLayerCount() );
+
+    wxBusyCursor dummy_cursor;      // Set an hourglass cursor while routing a
+                                    // track
+
+    result = NOSUCCESS;
+
+    marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
+
+    // clear direction flags
+    i = RoutingMatrix.m_Nrows * RoutingMatrix.m_Ncols * sizeof(DIR_CELL);
+
+    if( two_sides )
+        memset( RoutingMatrix.m_DirSide[TOP], FROM_NOWHERE, i );
+    memset( RoutingMatrix.m_DirSide[BOTTOM], FROM_NOWHERE, i );
+
+    lastopen = lastclos = lastmove = 0;
+
+    // Set tab_masque[side] for final test of routing.
+    if( two_sides )
+        tab_mask[TOP] = topLayerMask;
+    tab_mask[BOTTOM] = bottomLayerMask;
+
+    // Set active layers mask.
+    routeLayerMask = topLayerMask | bottomLayerMask;
+
+    pt_cur_ch = pt_rat;
+
+    current_net_code  = pt_rat->GetNet();
+    padLayerMaskStart = pt_cur_ch->m_PadStart->GetLayerSet();
+
+    padLayerMaskEnd = pt_cur_ch->m_PadEnd->GetLayerSet();
+
+
+    /* First Test if routing possible ie if the pads are accessible
+     * on the routing layers.
+     */
+    if( ( routeLayerMask & padLayerMaskStart ) == 0 )
+        goto end_of_route;
+
+    if( ( routeLayerMask & padLayerMaskEnd ) == 0 )
+        goto end_of_route;
+
+    /* Then test if routing possible ie if the pads are accessible
+     * On the routing grid (1 grid point must be in the pad)
+     */
+    {
+        int cX = ( RoutingMatrix.m_GridRouting * col_source )
+                 + pcbframe->GetBoard()->GetBoundingBox().GetX();
+        int cY = ( RoutingMatrix.m_GridRouting * row_source )
+                 + pcbframe->GetBoard()->GetBoundingBox().GetY();
+        int dx = pt_cur_ch->m_PadStart->GetSize().x / 2;
+        int dy = pt_cur_ch->m_PadStart->GetSize().y / 2;
+        int px = pt_cur_ch->m_PadStart->GetPosition().x;
+        int py = pt_cur_ch->m_PadStart->GetPosition().y;
+
+        if( ( ( int( pt_cur_ch->m_PadStart->GetOrientation() ) / 900 ) & 1 ) != 0 )
+            std::swap( dx, dy );
+
+        if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
+            goto end_of_route;
+
+        cX = ( RoutingMatrix.m_GridRouting * col_target )
+             + pcbframe->GetBoard()->GetBoundingBox().GetX();
+        cY = ( RoutingMatrix.m_GridRouting * row_target )
+             + pcbframe->GetBoard()->GetBoundingBox().GetY();
+        dx = pt_cur_ch->m_PadEnd->GetSize().x / 2;
+        dy = pt_cur_ch->m_PadEnd->GetSize().y / 2;
+        px = pt_cur_ch->m_PadEnd->GetPosition().x;
+        py = pt_cur_ch->m_PadEnd->GetPosition().y;
+
+        if( ( ( int( pt_cur_ch->m_PadEnd->GetOrientation() ) / 900) & 1 ) != 0 )
+            std::swap( dx, dy );
+
+        if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
+            goto end_of_route;
+    }
+
+    // Test the trivial case: direct connection overlay pads.
+    if( row_source == row_target  && col_source == col_target &&
+            ( padLayerMaskEnd & padLayerMaskStart & all_cu ).any() )
+    {
+        result = TRIVIAL_SUCCESS;
+        goto end_of_route;
+    }
+
+    // Placing the bit to remove obstacles on 2 pads to a link.
+    pcbframe->SetStatusText( wxT( "Gen Cells" ) );
+
+    PlacePad( pt_cur_ch->m_PadStart, CURRENT_PAD, marge, WRITE_OR_CELL );
+    PlacePad( pt_cur_ch->m_PadEnd, CURRENT_PAD, marge, WRITE_OR_CELL );
+
+    // Regenerates the remaining barriers (which may encroach on the
+    // placement bits precedent)
+    i = pcbframe->GetBoard()->GetPadCount();
+
+    for( unsigned ii = 0; ii < pcbframe->GetBoard()->GetPadCount(); ii++ )
+    {
+        D_PAD* ptr = pcbframe->GetBoard()->GetPad( ii );
+
+        if( ( pt_cur_ch->m_PadStart != ptr ) && ( pt_cur_ch->m_PadEnd != ptr ) )
+        {
+            PlacePad( ptr, ~CURRENT_PAD, marge, WRITE_AND_CELL );
+        }
+    }
+
+    InitQueue(); // initialize the search queue
+    apx_dist = RoutingMatrix.GetApxDist( row_source, col_source, row_target, col_target );
+
+    // Initialize first search.
+    if( two_sides )   // Preferred orientation.
+    {
+        if( abs( row_target - row_source ) > abs( col_target - col_source ) )
+        {
+            if( ( padLayerMaskStart & topLayerMask ).any() )
+            {
+                start_mask_layer = 2;
+
+                if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
+                              row_target, col_target ) == 0 )
+                {
+                    return ERR_MEMORY;
+                }
+            }
+
+            if( ( padLayerMaskStart & bottomLayerMask ).any() )
+            {
+                start_mask_layer |= 1;
+
+                if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
+                              row_target, col_target ) == 0 )
+                {
+                    return ERR_MEMORY;
+                }
+            }
+        }
+        else
+        {
+            if( ( padLayerMaskStart & bottomLayerMask ).any() )
+            {
+                start_mask_layer = 1;
+
+                if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
+                              row_target, col_target ) == 0 )
+                {
+                    return ERR_MEMORY;
+                }
+            }
+
+            if( ( padLayerMaskStart & topLayerMask ).any() )
+            {
+                start_mask_layer |= 2;
+
+                if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
+                              row_target, col_target ) == 0 )
+                {
+                    return ERR_MEMORY;
+                }
+            }
+        }
+    }
+    else if( ( padLayerMaskStart & bottomLayerMask ).any() )
+    {
+        start_mask_layer = 1;
+
+        if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, row_target, col_target ) == 0 )
+        {
+            return ERR_MEMORY;
+        }
+    }
+
+    // search until success or we exhaust all possibilities
+    GetQueue( &r, &c, &side, &d, &apx_dist );
+
+    for( ; r != ILLEGAL; GetQueue( &r, &c, &side, &d, &apx_dist ) )
+    {
+        curcell = RoutingMatrix.GetCell( r, c, side );
+
+        if( curcell & CURRENT_PAD )
+            curcell &= ~HOLE;
+
+        if( (r == row_target) && (c == col_target)  // success if layer OK
+           && (tab_mask[side] & padLayerMaskEnd).any() )
+        {
+            // Remove link.
+            GRSetDrawMode( DC, GR_XOR );
+            GRLine( pcbframe->GetCanvas()->GetClipBox(),
+                    DC,
+                    segm_oX,
+                    segm_oY,
+                    segm_fX,
+                    segm_fY,
+                    0,
+                    WHITE );
+
+            // Generate trace.
+            if( Retrace( pcbframe, DC, row_source, col_source,
+                         row_target, col_target, side, current_net_code ) )
+            {
+                result = SUCCESS;   // Success : Route OK
+            }
+
+            break;                  // Routing complete.
+        }
+
+        if( pcbframe->GetCanvas()->GetAbortRequest() )
+        {
+            result = STOP_FROM_ESC;
+            break;
+        }
+
+        // report every COUNT new nodes or so
+        #define COUNT 20000
+
+        if( ( OpenNodes - lastopen > COUNT )
+           || ( ClosNodes - lastclos > COUNT )
+           || ( MoveNodes - lastmove > COUNT ) )
+        {
+            lastopen = OpenNodes;
+            lastclos = ClosNodes;
+            lastmove = MoveNodes;
+            msg.Printf( wxT( "Activity: Open %d   Closed %d   Moved %d" ),
+                        OpenNodes, ClosNodes, MoveNodes );
+            pcbframe->SetStatusText( msg );
+        }
+
+        _self = 0;
+
+        if( curcell & HOLE )
+        {
+            _self = 5;
+
+            // set 'present' bits
+            for( i = 0; i < 8; i++ )
+            {
+                selfok2[i].present = 0;
+
+                if( curcell & selfok2[i].trace )
+                    selfok2[i].present = 1;
+            }
+        }
+
+        for( i = 0; i < 8; i++ ) // consider neighbors
+        {
+            nr = r + delta[i][0];
+            nc = c + delta[i][1];
+
+            // off the edge?
+            if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
+                nc < 0 || nc >= RoutingMatrix.m_Ncols )
+                continue;  // off the edge
+
+            if( _self == 5 && selfok2[i].present )
+                continue;
+
+            newcell = RoutingMatrix.GetCell( nr, nc, side );
+
+            if( newcell & CURRENT_PAD )
+                newcell &= ~HOLE;
+
+            // check for non-target hole
+            if( newcell & HOLE )
+            {
+                if( nr != row_target || nc != col_target )
+                    continue;
+            }
+            // check for traces
+            else if( newcell & HOLE & ~(newmask[i]) )
+            {
+                continue;
+            }
+
+            // check blocking on corner neighbors
+            if( delta[i][0] && delta[i][1] )
+            {
+                // check first buddy
+                buddy = RoutingMatrix.GetCell( r + blocking[i].r1, c + blocking[i].c1, side );
+
+                if( buddy & CURRENT_PAD )
+                    buddy &= ~HOLE;
+
+                if( buddy & HOLE )
+                    continue;
+
+//              if (buddy & (blocking[i].b1)) continue;
+                // check second buddy
+                buddy = RoutingMatrix.GetCell( r + blocking[i].r2, c + blocking[i].c2, side );
+
+                if( buddy & CURRENT_PAD )
+                    buddy &= ~HOLE;
+
+                if( buddy & HOLE )
+                    continue;
+
+//              if (buddy & (blocking[i].b2)) continue;
+            }
+
+            olddir  = RoutingMatrix.GetDir( r, c, side );
+            newdist = d + RoutingMatrix.CalcDist( ndir[i], olddir,
+                                    ( olddir == FROM_OTHERSIDE ) ?
+                                    RoutingMatrix.GetDir( r, c, 1 - side ) : 0, side );
+
+            // if (a) not visited yet, or (b) we have
+            // found a better path, add it to queue
+            if( !RoutingMatrix.GetDir( nr, nc, side ) )
+            {
+                RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
+                RoutingMatrix.SetDist( nr, nc, side, newdist );
+
+                if( SetQueue( nr, nc, side, newdist,
+                              RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
+                              row_target, col_target ) == 0 )
+                {
+                    return ERR_MEMORY;
+                }
+            }
+            else if( newdist < RoutingMatrix.GetDist( nr, nc, side ) )
+            {
+                RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
+                RoutingMatrix.SetDist( nr, nc, side, newdist );
+                ReSetQueue( nr, nc, side, newdist,
+                            RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
+                            row_target, col_target );
+            }
+        }
+
+        //* Test the other layer. *
+        if( two_sides )
+        {
+            olddir = RoutingMatrix.GetDir( r, c, side );
+
+            if( olddir == FROM_OTHERSIDE )
+                continue;   // useless move, so don't bother
+
+            if( curcell )   // can't drill via if anything here
+                continue;
+
+            // check for holes or traces on other side
+            if( ( newcell = RoutingMatrix.GetCell( r, c, 1 - side ) ) != 0 )
+                continue;
+
+            // check for nearby holes or traces on both sides
+            for( skip = 0, i = 0; i < 8; i++ )
+            {
+                nr = r + delta[i][0]; nc = c + delta[i][1];
+
+                if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
+                    nc < 0 || nc >= RoutingMatrix.m_Ncols )
+                    continue;  // off the edge !!
+
+                if( RoutingMatrix.GetCell( nr, nc, side ) /* & blocking2[i] */ )
+                {
+                    skip = 1; // can't drill via here
+                    break;
+                }
+
+                if( RoutingMatrix.GetCell( nr, nc, 1 - side ) /* & blocking2[i] */ )
+                {
+                    skip = 1; // can't drill via here
+                    break;
+                }
+            }
+
+            if( skip )      // neighboring hole or trace?
+                continue;   // yes, can't drill via here
+
+            newdist = d + RoutingMatrix.CalcDist( FROM_OTHERSIDE, olddir, 0, side );
+
+            /*  if (a) not visited yet,
+             *  or (b) we have found a better path,
+             *  add it to queue */
+            if( !RoutingMatrix.GetDir( r, c, 1 - side ) )
+            {
+                RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
+                RoutingMatrix.SetDist( r, c, 1 - side, newdist );
+
+                if( SetQueue( r, c, 1 - side, newdist, apx_dist, row_target, col_target ) == 0 )
+                {
+                    return ERR_MEMORY;
+                }
+            }
+            else if( newdist < RoutingMatrix.GetDist( r, c, 1 - side ) )
+            {
+                RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
+                RoutingMatrix.SetDist( r, c, 1 - side, newdist );
+                ReSetQueue( r, c,
+                            1 - side,
+                            newdist,
+                            apx_dist,
+                            row_target,
+                            col_target );
+            }
+        }     // Finished attempt to route on other layer.
+    }
+
+end_of_route:
+    PlacePad( pt_cur_ch->m_PadStart, ~CURRENT_PAD, marge, WRITE_AND_CELL );
+    PlacePad( pt_cur_ch->m_PadEnd, ~CURRENT_PAD, marge, WRITE_AND_CELL );
+
+    msg.Printf( wxT( "Activity: Open %d   Closed %d   Moved %d"),
+                OpenNodes, ClosNodes, MoveNodes );
+    pcbframe->SetStatusText( msg );
+
+    return result;
+}
+
+
+static long bit[8][9] =
+{
+    // OT=Otherside
+    // N, NE, E, SE, S, SW, W, NW, OT
+// N
+    { LINE_VERTICAL,
+      BENT_StoNE,
+      CORNER_SOUTHEAST,
+      SHARP_StoSE,
+      0,
+      SHARP_StoSW,
+      CORNER_SOUTHWEST,
+      BENT_StoNW,
+      ( HOLE | HOLE_SOUTH )
+    },
+// NE
+    {
+        BENT_NtoSW,
+        DIAG_NEtoSW,
+        BENT_EtoSW,
+        ANGLE_SEtoSW,
+        SHARP_StoSW,
+        0,
+        SHARP_WtoSW,
+        ANGLE_SWtoNW,
+        ( HOLE | HOLE_SOUTHWEST )
+    },
+// E
+    {
+        CORNER_NORTHWEST,
+        BENT_WtoNE,
+        LINE_HORIZONTAL,
+        BENT_WtoSE,
+        CORNER_SOUTHWEST,
+        SHARP_WtoSW,
+        0,
+        SHARP_WtoNW,
+        ( HOLE | HOLE_WEST )
+    },
+// SE
+    {
+        SHARP_NtoNW,
+        ANGLE_NWtoNE,
+        BENT_EtoNW,
+        DIAG_SEtoNW,
+        BENT_StoNW,
+        ANGLE_SWtoNW,
+        SHARP_WtoNW,
+        0,
+        ( HOLE | HOLE_NORTHWEST )
+    },
+// S
+    {
+        0,
+        SHARP_NtoNE,
+        CORNER_NORTHEAST,
+        BENT_NtoSE,
+        LINE_VERTICAL,
+        BENT_NtoSW,
+        CORNER_NORTHWEST,
+        SHARP_NtoNW,
+        ( HOLE | HOLE_NORTH )
+    },
+// SW
+    {
+        SHARP_NtoNE,
+        0,
+        SHARP_EtoNE,
+        ANGLE_NEtoSE,
+        BENT_StoNE,
+        DIAG_NEtoSW,
+        BENT_WtoNE,
+        ANGLE_NWtoNE,
+        ( HOLE | HOLE_NORTHEAST )
+    },
+// W
+    {
+        CORNER_NORTHEAST,
+        SHARP_EtoNE,
+        0,
+        SHARP_EtoSE,
+        CORNER_SOUTHEAST,
+        BENT_EtoSW,
+        LINE_HORIZONTAL,
+        BENT_EtoNW,
+        ( HOLE | HOLE_EAST )
+    },
+// NW
+    {
+        BENT_NtoSE,
+        ANGLE_NEtoSE,
+        SHARP_EtoSE,
+        0,
+        SHARP_StoSE,
+        ANGLE_SEtoSW,
+        BENT_WtoSE,
+        DIAG_SEtoNW,
+        ( HOLE | HOLE_SOUTHEAST )
+    }
+};
+
+
+/* work from target back to source, actually laying the traces
+ *  Parameters:
+ *      start on side target_side, of coordinates row_target, col_target.
+ *      arrive on side masque_layer_start, coordinate row_source, col_source
+ * The search is done in reverse routing, the point of arrival (target) to
+ * the starting point (source)
+ * The router.
+ *
+ * Target_side = symbol (TOP / BOTTOM) of departure
+ * = Mask_layer_source mask layers Arrival
+ *
+ * Returns:
+ * 0 if error
+ * > 0 if Ok
+ */
+static int Retrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC,
+                    int row_source, int col_source,
+                    int row_target, int col_target, int target_side,
+                    int current_net_code )
+{
+    int  r0, c0, s0;
+    int  r1, c1, s1;    // row, col, starting side.
+    int  r2, c2, s2;    // row, col, ending side.
+    int  x, y = -1;
+    long b;
+
+    r1 = row_target;
+    c1 = col_target;    // start point is target ( end point is source )
+    s1 = target_side;
+    r0 = c0 = s0 = ILLEGAL;
+
+    wxASSERT( g_CurrentTrackList.GetCount() == 0 );
+
+    do
+    {
+        // find where we came from to get here
+        r2 = r1; c2 = c1; s2 = s1;
+        x  = RoutingMatrix.GetDir( r1, c1, s1 );
+
+        switch( x )
+        {
+        case FROM_NORTH:
+            r2++;
+            break;
+
+        case FROM_EAST:
+            c2++;
+            break;
+
+        case FROM_SOUTH:
+            r2--;
+            break;
+
+        case FROM_WEST:
+            c2--;
+            break;
+
+        case FROM_NORTHEAST:
+            r2++;
+            c2++;
+            break;
+
+        case FROM_SOUTHEAST:
+            r2--;
+            c2++;
+            break;
+
+        case FROM_SOUTHWEST:
+            r2--;
+            c2--;
+            break;
+
+        case FROM_NORTHWEST:
+            r2++;
+            c2--;
+            break;
+
+        case FROM_OTHERSIDE:
+            s2 = 1 - s2;
+            break;
+
+        default:
+            wxMessageBox( wxT( "Retrace: internal error: no way back" ) );
+            return 0;
+        }
+
+        if( r0 != ILLEGAL )
+            y = RoutingMatrix.GetDir( r0, c0, s0 );
+
+        // see if target or hole
+        if( ( ( r1 == row_target ) && ( c1 == col_target ) ) || ( s1 != s0 ) )
+        {
+            int p_dir;
+
+            switch( x )
+            {
+            case FROM_NORTH:
+                p_dir = HOLE_NORTH;
+                break;
+
+            case FROM_EAST:
+                p_dir = HOLE_EAST;
+                break;
+
+            case FROM_SOUTH:
+                p_dir = HOLE_SOUTH;
+                break;
+
+            case FROM_WEST:
+                p_dir = HOLE_WEST;
+                break;
+
+            case FROM_NORTHEAST:
+                p_dir = HOLE_NORTHEAST;
+                break;
+
+            case FROM_SOUTHEAST:
+                p_dir = HOLE_SOUTHEAST;
+                break;
+
+            case FROM_SOUTHWEST:
+                p_dir = HOLE_SOUTHWEST;
+                break;
+
+            case FROM_NORTHWEST:
+                p_dir = HOLE_NORTHWEST;
+                break;
+
+            case FROM_OTHERSIDE:
+            default:
+                DisplayError( pcbframe, wxT( "Retrace: error 1" ) );
+                return 0;
+            }
+
+            OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, p_dir, current_net_code );
+        }
+        else
+        {
+            if( ( y == FROM_NORTH || y == FROM_NORTHEAST
+                  || y == FROM_EAST || y == FROM_SOUTHEAST
+                  || y == FROM_SOUTH || y == FROM_SOUTHWEST
+                  || y == FROM_WEST || y == FROM_NORTHWEST )
+               && ( x == FROM_NORTH || x == FROM_NORTHEAST
+                    || x == FROM_EAST || x == FROM_SOUTHEAST
+                    || x == FROM_SOUTH || x == FROM_SOUTHWEST
+                    || x == FROM_WEST || x == FROM_NORTHWEST
+                    || x == FROM_OTHERSIDE )
+               && ( ( b = bit[y - 1][x - 1] ) != 0 ) )
+            {
+                OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, b, current_net_code );
+
+                if( b & HOLE )
+                    OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, HOLE, current_net_code );
+            }
+            else
+            {
+                wxMessageBox( wxT( "Retrace: error 2" ) );
+                return 0;
+            }
+        }
+
+        if( ( r2 == row_source ) && ( c2 == col_source ) ) // see if source
+        {
+            int p_dir;
+
+            switch( x )
+            {
+            case FROM_NORTH:
+                p_dir = HOLE_SOUTH;
+                break;
+
+            case FROM_EAST:
+                p_dir = HOLE_WEST;
+                break;
+
+            case FROM_SOUTH:
+                p_dir = HOLE_NORTH;
+                break;
+
+            case FROM_WEST:
+                p_dir = HOLE_EAST;
+                break;
+
+            case FROM_NORTHEAST:
+                p_dir = HOLE_SOUTHWEST;
+                break;
+
+            case FROM_SOUTHEAST:
+                p_dir = HOLE_NORTHWEST;
+                break;
+
+            case FROM_SOUTHWEST:
+                p_dir = HOLE_NORTHEAST;
+                break;
+
+            case FROM_NORTHWEST:
+                p_dir = HOLE_SOUTHEAST;
+                break;
+
+            case FROM_OTHERSIDE:
+            default:
+                wxMessageBox( wxT( "Retrace: error 3" ) );
+                return 0;
+            }
+
+            OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, p_dir, current_net_code );
+        }
+
+        // move to next cell
+        r0 = r1;
+        c0 = c1;
+        s0 = s1;
+        r1 = r2;
+        c1 = c2;
+        s1 = s2;
+    } while( !( ( r2 == row_source ) && ( c2 == col_source ) ) );
+
+    AddNewTrace( pcbframe, DC );
+    return 1;
+}
+
+
+/* This function is used by Retrace and read the autorouting matrix data cells to create
+ * the real track on the physical board
+ */
+static void OrCell_Trace( BOARD* pcb, int col, int row,
+                          int side, int orient, int current_net_code )
+{
+    if( orient == HOLE )  // placement of a via
+    {
+        VIA *newVia = new VIA( pcb );
+
+        g_CurrentTrackList.PushBack( newVia );
+
+        g_CurrentTrackSegment->SetState( TRACK_AR, true );
+        g_CurrentTrackSegment->SetLayer( F_Cu );
+
+        g_CurrentTrackSegment->SetStart(wxPoint( pcb->GetBoundingBox().GetX() +
+                                                ( RoutingMatrix.m_GridRouting * row ),
+                                                pcb->GetBoundingBox().GetY() +
+                                                ( RoutingMatrix.m_GridRouting * col )));
+        g_CurrentTrackSegment->SetEnd( g_CurrentTrackSegment->GetStart() );
+
+        g_CurrentTrackSegment->SetWidth( pcb->GetDesignSettings().GetCurrentViaSize() );
+        newVia->SetViaType( pcb->GetDesignSettings().m_CurrentViaType );
+
+        g_CurrentTrackSegment->SetNetCode( current_net_code );
+    }
+    else    // placement of a standard segment
+    {
+        TRACK *newTrack = new TRACK( pcb );
+        int    dx0, dy0, dx1, dy1;
+
+
+        g_CurrentTrackList.PushBack( newTrack );
+
+        g_CurrentTrackSegment->SetLayer( g_Route_Layer_BOTTOM );
+
+        if( side == TOP )
+            g_CurrentTrackSegment->SetLayer( g_Route_Layer_TOP );
+
+        g_CurrentTrackSegment->SetState( TRACK_AR, true );
+        g_CurrentTrackSegment->SetEnd( wxPoint( pcb->GetBoundingBox().GetX() +
+                                         ( RoutingMatrix.m_GridRouting * row ),
+                                         pcb->GetBoundingBox().GetY() +
+                                         ( RoutingMatrix.m_GridRouting * col )));
+        g_CurrentTrackSegment->SetNetCode( current_net_code );
+
+        if( g_CurrentTrackSegment->Back() == NULL ) // Start trace.
+        {
+            g_CurrentTrackSegment->SetStart( wxPoint( segm_fX, segm_fY ) );
+
+            // Placement on the center of the pad if outside grid.
+            dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
+            dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
+
+            dx0 = pt_cur_ch->m_PadEnd->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
+            dy0 = pt_cur_ch->m_PadEnd->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
+
+            // If aligned, change the origin point.
+            if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
+            {
+                g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
+            }
+            else    // Creation of a supplemental segment
+            {
+                g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
+
+                newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
+                newTrack->SetStart( g_CurrentTrackSegment->GetEnd());
+
+                g_CurrentTrackList.PushBack( newTrack );
+            }
+        }
+        else
+        {
+            if( g_CurrentTrackSegment->Back() )
+            {
+                g_CurrentTrackSegment->SetStart( g_CurrentTrackSegment->Back()->GetEnd() );
+            }
+        }
+
+        g_CurrentTrackSegment->SetWidth( pcb->GetDesignSettings().GetCurrentTrackWidth() );
+
+        if( g_CurrentTrackSegment->GetStart() != g_CurrentTrackSegment->GetEnd() )
+        {
+            // Reduce aligned segments by one.
+            TRACK* oldTrack = g_CurrentTrackSegment->Back();
+
+            if( oldTrack &&  oldTrack->Type() != PCB_VIA_T )
+            {
+                dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
+                dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
+
+                dx0 = oldTrack->GetEnd().x - oldTrack->GetStart().x;
+                dy0 = oldTrack->GetEnd().y - oldTrack->GetStart().y;
+
+                if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
+                {
+                    oldTrack->SetEnd( g_CurrentTrackSegment->GetEnd() );
+
+                    delete g_CurrentTrackList.PopBack();
+                }
+            }
+        }
+    }
+}
+
+
+/* Insert the new track created in the list of tracks.
+ * amend the points of beginning and end of the track so that they are
+ * connected
+ * Center on pads even if they are off grid.
+ */
+static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC )
+{
+    if( g_FirstTrackSegment == NULL )
+        return;
+
+    int dx0, dy0, dx1, dy1;
+    int marge, via_marge;
+    EDA_DRAW_PANEL* panel = pcbframe->GetCanvas();
+    PCB_SCREEN* screen = pcbframe->GetScreen();
+
+    marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
+    via_marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentViaSize() / 2 );
+
+    dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
+    dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
+
+    // Place on center of pad if off grid.
+    dx0 = pt_cur_ch->m_PadStart->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
+    dy0 = pt_cur_ch->m_PadStart->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
+
+    // If aligned, change the origin point.
+    if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
+    {
+        g_CurrentTrackSegment->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
+    }
+    else
+    {
+        TRACK* newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
+
+        newTrack->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
+        newTrack->SetStart( g_CurrentTrackSegment->GetEnd() );
+
+        g_CurrentTrackList.PushBack( newTrack );
+    }
+
+    g_FirstTrackSegment->start = pcbframe->GetBoard()->GetPad( g_FirstTrackSegment,
+            ENDPOINT_START );
+
+    if( g_FirstTrackSegment->start )
+        g_FirstTrackSegment->SetState( BEGIN_ONPAD, true );
+
+    g_CurrentTrackSegment->end = pcbframe->GetBoard()->GetPad( g_CurrentTrackSegment,
+            ENDPOINT_END );
+
+    if( g_CurrentTrackSegment->end )
+        g_CurrentTrackSegment->SetState( END_ONPAD, true );
+
+    // Out the new track on the matrix board
+    for( TRACK* track = g_FirstTrackSegment; track; track = track->Next() )
+    {
+        TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
+        TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+    }
+
+    // Insert new segments in  real board
+    int    netcode    = g_FirstTrackSegment->GetNetCode();
+    TRACK* firstTrack = g_FirstTrackSegment;
+    int    newCount   = g_CurrentTrackList.GetCount();
+
+    // Put entire new current segment list in BOARD
+    TRACK* track;
+    TRACK* insertBeforeMe = g_CurrentTrackSegment->GetBestInsertPoint( pcbframe->GetBoard() );
+
+    while( ( track = g_CurrentTrackList.PopFront() ) != NULL )
+    {
+        ITEM_PICKER picker( track, UR_NEW );
+        s_ItemsListPicker.PushItem( picker );
+        pcbframe->GetBoard()->m_Track.Insert( track, insertBeforeMe );
+    }
+
+    DrawTraces( panel, DC, firstTrack, newCount, GR_OR );
+
+    pcbframe->TestNetConnection( DC, netcode );
+
+    screen->SetModify();
+}
diff --git a/pcbnew/autorouter/spread_footprints.cpp b/pcbnew/autorouter/spread_footprints.cpp
new file mode 100644
index 0000000..52b7106
--- /dev/null
+++ b/pcbnew/autorouter/spread_footprints.cpp
@@ -0,0 +1,362 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2013 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2013 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2013 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2015 KiCad Developers, see AUTHORS.txt for contributors.
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+/**
+ * @file spread_footprints.cpp
+ * @brief functions to spread footprints on free areas outside a board.
+ * this is usefull after reading a netlist, when new footprints are loaded
+ * and stacked at 0,0 coordinate.
+ * Often, spread them on a free area near the board being edited make more easy
+ * their selection.
+ */
+
+#include <algorithm>
+
+#include <fctsys.h>
+#include <convert_to_biu.h>
+#include <class_drawpanel.h>
+#include <confirm.h>
+#include <pcbnew.h>
+#include <wxPcbStruct.h>
+#include <class_board.h>
+#include <class_module.h>
+
+#include <rect_placement/rect_placement.h>
+
+struct TSubRect : public CRectPlacement::TRect
+{
+    int n;      // Original index of this subrect, before sorting
+
+    TSubRect() : TRect(),
+        n( 0 )
+    {
+    }
+
+    TSubRect( int _w, int _h, int _n ) :
+        TRect( 0, 0, _w, _h ), n( _n ) { }
+};
+
+typedef std::vector<TSubRect> CSubRectArray;
+
+// Use 0.01 mm units to calculate placement, to avoid long calculation time
+const int scale = (int)(0.01 * IU_PER_MM);
+
+// Populates a list of rectangles, from a list of modules
+void fillRectList( CSubRectArray& vecSubRects, std::vector <MODULE*>& aModuleList )
+{
+    vecSubRects.clear();
+
+    for( unsigned ii = 0; ii < aModuleList.size(); ii++ )
+    {
+        EDA_RECT fpBox = aModuleList[ii]->GetBoundingBox();
+        TSubRect fpRect( fpBox.GetWidth()/scale, fpBox.GetHeight()/scale, ii );
+        vecSubRects.push_back( fpRect );
+    }
+}
+
+// Populates a list of rectangles, from a list of EDA_RECT
+void fillRectList( CSubRectArray& vecSubRects, std::vector <EDA_RECT>& aRectList )
+{
+    vecSubRects.clear();
+
+    for( unsigned ii = 0; ii < aRectList.size(); ii++ )
+    {
+        EDA_RECT& rect = aRectList[ii];
+        TSubRect fpRect( rect.GetWidth()/scale, rect.GetHeight()/scale, ii );
+        vecSubRects.push_back( fpRect );
+    }
+}
+
+
+
+// Spread a list of rectangles inside a placement area
+void spreadRectangles( CRectPlacement& aPlacementArea,
+                      CSubRectArray& vecSubRects,
+                      int areaSizeX, int areaSizeY )
+{
+    areaSizeX/= scale;
+    areaSizeY/= scale;
+
+    // Sort the subRects based on dimensions, larger dimension goes first.
+    std::sort( vecSubRects.begin(), vecSubRects.end(), CRectPlacement::TRect::Greater );
+
+    // gives the initial size to the area
+    aPlacementArea.Init( areaSizeX, areaSizeY );
+
+    // Add all subrects
+    CSubRectArray::iterator it;
+    for( it = vecSubRects.begin(); it != vecSubRects.end(); )
+    {
+        CRectPlacement::TRect r( 0, 0, it->w, it->h );
+
+        bool bPlaced = aPlacementArea.AddAtEmptySpotAutoGrow( &r, areaSizeX, areaSizeY );
+
+        if( !bPlaced )   // No room to place the rectangle: enlarge area and retry
+        {
+            areaSizeX = ceil(areaSizeX * 1.1);
+            areaSizeY = ceil(areaSizeY * 1.1);
+            aPlacementArea.Init( areaSizeX, areaSizeY );
+            it = vecSubRects.begin();
+            continue;
+        }
+
+        // When correctly placed in a placement area, the coords are returned in r.x and r.y
+        // Store them.
+        it->x   = r.x;
+        it->y   = r.y;
+
+        it++;
+    }
+}
+
+
+void moveFootprintsInArea( CRectPlacement& aPlacementArea,
+                           std::vector <MODULE*>& aModuleList, EDA_RECT& aFreeArea,
+                           bool aFindAreaOnly  )
+{
+    CSubRectArray   vecSubRects;
+
+    fillRectList( vecSubRects, aModuleList );
+    spreadRectangles( aPlacementArea, vecSubRects,
+                      aFreeArea.GetWidth(), aFreeArea.GetHeight() );
+
+    if( aFindAreaOnly )
+        return;
+
+    for( unsigned it = 0; it < vecSubRects.size(); ++it )
+    {
+        wxPoint pos( vecSubRects[it].x, vecSubRects[it].y );
+        pos.x *= scale;
+        pos.y *= scale;
+
+        MODULE * module = aModuleList[vecSubRects[it].n];
+
+        EDA_RECT fpBBox = module->GetBoundingBox();
+        wxPoint mod_pos = pos + ( module->GetPosition() - fpBBox.GetOrigin() )
+                          + aFreeArea.GetOrigin();
+
+        module->Move( mod_pos - module->GetPosition() );
+    }
+}
+
+static bool sortModulesbySheetPath( MODULE* ref, MODULE* compare );
+
+/* Function to move components in a rectangular area format 4 / 3,
+ * starting from the mouse cursor
+ * The components with the FIXED status set are not moved
+ */
+void PCB_EDIT_FRAME::SpreadFootprints( bool aFootprintsOutsideBoardOnly )
+{
+    EDA_RECT bbox = GetBoard()->ComputeBoundingBox( true );
+    bool     edgesExist = ( bbox.GetWidth() || bbox.GetHeight() );
+
+    // no edges exist
+    if( aFootprintsOutsideBoardOnly && !edgesExist )
+    {
+        DisplayError( this,
+                      _( "Could not automatically place footprints. No board outlines detected." ) );
+        return;
+    }
+
+    // if aFootprintsOutsideBoardOnly is true, and if board outline exists,
+    // wue have to filter footprints to move:
+    bool outsideBrdFilter = aFootprintsOutsideBoardOnly && edgesExist;
+
+    // Build candidate list
+    // calculate also the area needed by these footprints
+    MODULE* module = GetBoard()->m_Modules;
+    std::vector <MODULE*> moduleList;
+
+    for( ; module != NULL; module = module->Next() )
+    {
+        module->CalculateBoundingBox();
+
+        if( outsideBrdFilter )
+        {
+            if( bbox.Contains( module->GetPosition() ) )
+                continue;
+        }
+
+        if( module->IsLocked() )
+            continue;
+
+        moduleList.push_back(module);
+    }
+
+    if( moduleList.size() == 0 )    // Nothing to do
+        return;
+
+    // sort footprints by sheet path. we group them later by sheet
+    sort( moduleList.begin(), moduleList.end(), sortModulesbySheetPath );
+
+    // Undo command: init undo list
+    PICKED_ITEMS_LIST  undoList;
+    undoList.m_Status = UR_CHANGED;
+    ITEM_PICKER        picker( NULL, UR_CHANGED );
+
+    for( unsigned ii = 0; ii < moduleList.size(); ii++ )
+    {
+        module = moduleList[ii];
+
+        // Undo: add copy of module to undo list
+        picker.SetItem( module );
+        picker.SetLink( module->Clone() );
+        undoList.PushItem( picker );
+    }
+
+    // Extract and place footprints by sheet
+    std::vector <MODULE*> moduleListBySheet;
+    std::vector <EDA_RECT> placementSheetAreas;
+    double subsurface;
+    double placementsurface = 0.0;
+
+    wxPoint placementAreaPosition = GetCrossHairPosition();
+
+    // We do not want to move footprints inside an existing board.
+    // move the placement area position outside the board bounding box
+    // to the left of the board
+    if( edgesExist )
+    {
+        if( placementAreaPosition.x < bbox.GetEnd().x &&
+            placementAreaPosition.y < bbox.GetEnd().y )
+        {
+            placementAreaPosition.x = bbox.GetEnd().x;
+            placementAreaPosition.y = bbox.GetOrigin().y;
+        }
+    }
+
+    // The placement uses 2 passes:
+    // the first pass creates the rectangular areas to place footprints
+    // each sheet in schematic creates one rectangular area.
+    // the second pass moves footprints inside these areas
+    for( int pass = 0; pass < 2; pass++ )
+    {
+        int subareaIdx = 0;
+        moduleListBySheet.clear();
+        subsurface = 0.0;
+
+        for( unsigned ii = 0; ii < moduleList.size(); ii++ )
+        {
+            module = moduleList[ii];
+            bool islastItem = false;
+
+            if( ii == moduleList.size() - 1 ||
+                ( moduleList[ii]->GetPath().BeforeLast( '/' ) !=
+                  moduleList[ii+1]->GetPath().BeforeLast( '/' ) ) )
+                islastItem = true;
+
+            moduleListBySheet.push_back( module );
+            subsurface += module->GetArea();
+
+            if( islastItem )
+            {
+                // end of the footprint sublist relative to the same sheet path
+                // calculate placement of the current sublist
+                EDA_RECT freeArea;
+                int Xsize_allowed = (int) ( sqrt( subsurface ) * 4.0 / 3.0 );
+                int Ysize_allowed = (int) ( subsurface / Xsize_allowed );
+
+                freeArea.SetWidth( Xsize_allowed );
+                freeArea.SetHeight( Ysize_allowed );
+                CRectPlacement placementArea;
+
+                if( pass == 1 )
+                {
+                    wxPoint areapos = placementSheetAreas[subareaIdx].GetOrigin()
+                                      + placementAreaPosition;
+                    freeArea.SetOrigin( areapos );
+                }
+
+                bool findAreaOnly = pass == 0;
+                moveFootprintsInArea( placementArea, moduleListBySheet,
+                                      freeArea, findAreaOnly );
+
+                if( pass == 0 )
+                {
+                    // Populate sheet placement areas list
+                    EDA_RECT sub_area;
+                    sub_area.SetWidth( placementArea.GetW()*scale );
+                    sub_area.SetHeight( placementArea.GetH()*scale );
+                    // Add a margin around the sheet placement area:
+                    sub_area.Inflate( Millimeter2iu( 1.5 ) );
+
+                    placementSheetAreas.push_back( sub_area );
+
+                    placementsurface += (double) sub_area.GetWidth()*
+                                        sub_area.GetHeight();
+                }
+
+                // Prepare buffers for next sheet
+                subsurface  = 0.0;
+                moduleListBySheet.clear();
+                subareaIdx++;
+            }
+        }
+
+        // End of pass:
+        // At the end of the first pass, we have to find position of each sheet
+        // placement area
+        if( pass == 0 )
+        {
+            int Xsize_allowed = (int) ( sqrt( placementsurface ) * 4.0 / 3.0 );
+            int Ysize_allowed = (int) ( placementsurface / Xsize_allowed );
+            CRectPlacement placementArea;
+            CSubRectArray  vecSubRects;
+
+            fillRectList( vecSubRects, placementSheetAreas );
+            spreadRectangles( placementArea, vecSubRects, Xsize_allowed, Ysize_allowed );
+
+            for( unsigned it = 0; it < vecSubRects.size(); ++it )
+            {
+                TSubRect& srect = vecSubRects[it];
+                wxPoint pos( srect.x*scale, srect.y*scale );
+                wxSize size( srect.w*scale, srect.h*scale );
+                placementSheetAreas[srect.n].SetOrigin( pos );
+                placementSheetAreas[srect.n].SetSize( size );
+            }
+        }
+    }   // End pass
+
+    // Undo: commit list
+    SaveCopyInUndoList( undoList, UR_CHANGED );
+    OnModify();
+
+    m_canvas->Refresh();
+}
+
+
+// Sort function, used to group footprints by sheet.
+// Footprints are sorted by their sheet path.
+// (the full sheet path restricted to the time stamp of the sheet itself,
+// without the time stamp of the footprint ).
+static bool sortModulesbySheetPath( MODULE* ref, MODULE* compare )
+{
+    if( ref->GetPath().Length() == compare->GetPath().Length() )
+        return ref->GetPath().BeforeLast( '/' ).Cmp( compare->GetPath().BeforeLast( '/' ) ) < 0;
+
+    return ref->GetPath().Length() < compare->GetPath().Length();
+}
diff --git a/pcbnew/autorouter/work.cpp b/pcbnew/autorouter/work.cpp
new file mode 100644
index 0000000..68aa48c
--- /dev/null
+++ b/pcbnew/autorouter/work.cpp
@@ -0,0 +1,164 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
+ *
+ * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
+ *
+ * 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, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+
+/**
+ * @file work.cpp
+ * @brief Automatic routing routines
+ */
+
+#include <fctsys.h>
+#include <common.h>
+
+#include <pcbnew.h>
+#include <autorout.h>
+#include <cell.h>
+
+
+struct CWORK    // a unit of work is a source-target to connect
+                // this is a ratsnest item in the routing matrix world
+{
+    int             m_FromRow;      // source row
+    int             m_FromCol;      // source column
+    int             m_ToRow;        // target row
+    int             m_ToCol;        // target column
+    RATSNEST_ITEM*  m_Ratsnest;     // Corresponding ratsnest
+    int             m_NetCode;      // m_NetCode
+    int             m_ApxDist;      // approximate distance
+    int             m_Cost;         // cost for sort by length
+    int             m_Priority;     // route priority
+
+    // the function that calculates the cost of this ratsnest:
+    void CalculateCost();
+};
+
+
+// the list of ratsnests
+static std::vector <CWORK> WorkList;
+static unsigned Current = 0;
+
+
+// initialize the work list
+void InitWork()
+{
+    WorkList.clear();
+    Current = 0;
+}
+
+
+/* add a unit of work to the work list
+ * :
+ *  1 if OK
+ *  0 if memory allocation failed
+ */
+
+int SetWork( int r1, int c1,
+             int n_c,
+             int r2, int c2,
+             RATSNEST_ITEM* pt_ch, int pri )
+{
+    CWORK item;
+    item.m_FromRow    = r1;
+    item.m_FromCol    = c1;
+    item.m_NetCode    = n_c;
+    item.m_ToRow      = r2;
+    item.m_ToCol      = c2;
+    item.m_Ratsnest   = pt_ch;
+    item.m_ApxDist    = RoutingMatrix.GetApxDist( r1, c1, r2, c2 );
+    item.CalculateCost();
+    item.m_Priority   = pri;
+    WorkList.push_back( item );
+    return 1;
+}
+
+
+/* fetch a unit of work from the work list */
+void GetWork( int* r1, int* c1,
+              int* n_c,
+              int* r2, int* c2,
+              RATSNEST_ITEM** pt_ch )
+{
+    if( Current < WorkList.size() )
+    {
+        *r1     = WorkList[Current].m_FromRow;
+        *c1     = WorkList[Current].m_FromCol;
+        *n_c    = WorkList[Current].m_NetCode;
+        *r2     = WorkList[Current].m_ToRow;
+        *c2     = WorkList[Current].m_ToCol;
+        *pt_ch  = WorkList[Current].m_Ratsnest;
+        Current++;
+    }
+    else    /* none left */
+    {
+        *r1     = *c1 = *r2 = *c2 = ILLEGAL;
+        *n_c    = 0;
+        *pt_ch  = NULL;
+    }
+}
+
+
+// order the work items; shortest (low cost) first:
+bool sort_by_cost( const CWORK& ref, const CWORK& item )
+{
+    if( ref.m_Priority == item.m_Priority )
+        return ref.m_Cost < item.m_Cost;
+
+    return ref.m_Priority >= item.m_Priority;
+}
+
+void SortWork()
+{
+    sort( WorkList.begin(), WorkList.end(), sort_by_cost );
+}
+
+
+/* Calculate the cost of a ratsnest:
+ *   cost = (| dx | + | dy |) * disability
+ *   disability = 1 if dx or dy = 0, max if | dx | # | dy |
+ */
+void CWORK::CalculateCost()
+{
+    int     dx, dy, mx, my;
+    double  incl = 1.0;
+
+    dx  = abs( m_ToCol - m_FromCol );
+    dy  = abs( m_ToRow - m_FromRow );
+    mx  = dx;
+    my  = dy;
+
+    if( mx < my )
+    {
+        mx = dy; my = dx;
+    }
+
+    if( mx )
+        incl += (2 * (double) my / mx);
+
+    m_Cost = (int) ( ( dx + dy ) * incl );
+}