Planning Point Directed Exploring Tree Routing Algorithm

PCB routing is a crucial link in modern electronic design automation. The A-star algorithm demonstrates good performance in the routing field. However, when addressing routing problems in large-scale complex scenarios, the algorithm suffers from low efficiency and a long running time. In this paper, we propose a Planning Point Directed Exploring Tree routing algorithm (PPDT). First, we grid and preprocess the routing space to generate Planning Points for each Forbidden Area (FA). Subsequently, with the starting point as the root node, the end point as the guidance, and the Planning Points as the search target, the A -star algorithm is utilized to generate a search tree. If the end point is reached, the path from the start point to the end point is found by backtracking from the end point. Finally, we postprocess the path and correct it to the specified routing direction. Compared with the A-star algorithm, we do not require exploring a large number of nodes around the current point; instead, we only search for the Planning Points of specific <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$F A$</tex>, significantly reducing the search space and enhancing the algorithm efficiency. In comparison with the A-star algorithm, it achieves an acceleration of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$3,000-77,000$</tex> times on a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1000 \times 2000$</tex> scale map, with the algorithm efficiency being markedly improved.