3D LineExplore: a 3D line exploration method for multi-layer PCB geometric routing

With the rapid advancement of electronic technology and the growing complexity of integrated circuit design, Printed Circuit Board (PCB) routing has become increasingly challenging. Current multi-layer PCB routing mainly relies on grid-based methods like A*, which face resolution limitations and high computational cost, especially with fine grids required for high routability. Although grid-less approaches such as the line-expansion method have been proposed, they are largely limited to 2D and unsuitable for multi-layer routing. To address this, we propose a 3D line-exploration-based geometric routing method for multi-layer PCBs that overcomes grid resolution constraints, improves efficiency, and natively supports multi-layer routing. The method comprises three key components: a "radar"-inspired scanning algorithm that automatically identifies exploration points based on design rules and surrounding obstacles; an obstacle-avoidance heuristic path optimization algorithm that enables optimal path planning, including layer transitions and obstacle bypassing from the current exploration points; and a multi-pin net repair and wire-shape optimization module, which enhances routing capability and path smoothness while ensuring compliance with design constraints. Experiments on an open-source PCB dataset show that the proposed 3D LineExplore achieves over 98% routing success, with shorter wire lengths and higher efficiency than state-of-the-art methods and commercial tools including FreeRouting, ELECTRA, DeepPCB, and Optimized-3D-A*.