I wonder if any games use a landmark approach to bound their A* search.
The basic idea of landmarks is that you choose a small number of landmarks (e.g. four corners of a map) and for every landmark, you pre-compute the distances to every node. You can then use this information to get a lower-bound for the distance to the target via the triangle inequality: d(p,t) >= |d(p,LM) - d(t,LM)|.
This is obviously weaker than the goal bounding explained in the video, but the precomputing only takes O(n). We used it quite successfully in a global router (for EDA), where the heuristic lower-bound is often much better than a standard A-star heuristic based on geometric distances, because edges could have wildly different costs.
In this particular case not a PCB but microprocessors.
Global routing is a high-level routing approach: routing millions of nets (= connections usually between 1 output pin of a gate and N input pins of other gates) on a grid graph with potentially billions of nodes is an extremely difficult Steiner tree problem.
To get good solutions, a common approach is to first solve the problem on a much coarser graph where edges have capacities. I.e. instead of having to place all connections disjointly, edges in the graph can accommodate a number of parallel connections.
A later detailed routing step will produce the actual disjoint routes while following the outline that was obtained during global routing.
Even back 15 years ago, EAGLE's autorouter was pretty decent if you used it right. Lay out power traces, ground planes and anything high speed or sensitive (analogue signals etc.) yourself, then let it do the busywork of hooking up all your blinkenlights and push buttons.
There are certainly things you shouldn't delegate to an autorouter, but in the same way, the trend towards hair-shirt-wearing insistence that everything be done manually is a productivity cost.
It's no different to programmers who insist on hand-optimizing assembler: Rarely necessarily any more and usually done more out of ego.
Yeah, I automatically went into what I know :/ Its impossible to route manually there days, which doesnt mean automagic tools are even remotely good, same goes for synthesis (fpga).
The basic idea of landmarks is that you choose a small number of landmarks (e.g. four corners of a map) and for every landmark, you pre-compute the distances to every node. You can then use this information to get a lower-bound for the distance to the target via the triangle inequality: d(p,t) >= |d(p,LM) - d(t,LM)|.
This is obviously weaker than the goal bounding explained in the video, but the precomputing only takes O(n). We used it quite successfully in a global router (for EDA), where the heuristic lower-bound is often much better than a standard A-star heuristic based on geometric distances, because edges could have wildly different costs.