Target-oriented And Active Obstacle-avoided PCB Routing Algorithm

Target-oriented and active obstacle-avoided PCB auto routing algorithm is proposed.It's one of the grid-less algorithm,it inherits the advantages of grid-less algorithm,and needs small amount of storage memory.The complexity of the information depends on the PCB circuit board itself.The algorithm is compatible with irregular polygon,and use active obstacle-avoided method to decrease exploring time,as well as find the shorter line with optimization method.This paper improved the PCB routing algorithm,and presented a new PCB routing algorithm.It contains the following contents in this thesis:1.Deeply analyzed several classic auto-routing algorithm,and then proposed a new auto-routing algorithm based on the grid-less line-exploring routing algorithm theory.The new auto-routing algorithm in this thesis inherited and optimized the advantages of less memory and faster computing.2.The target-oriented and active obstacle-avoided PCB routing algorithm changed the traditional passive obstacle-avoided method to active obstacle-avoided method,this made the routing more initiative,thus reduced the aimless exploring,and also decreased the exploring times.In addition,because of target-oriented during the whole process of exploring,the algorithm reduced the exploring scope,and improved the computing efficiency.3.Routing twice times in both negative and positive direction,then choose the better one with less Manhattan distance and less line points.4.Programed the code of the auto-routing software,and it achieved the algorithm in this thesis.The algorithm performance is well,it's good adapt for the irregular polygon obstacles,and 100% routing rate during the experiment.In some situations,the algorithm has greater efficiency than Altium DXP software.