4 ms·
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 c
by nhaehnle 10y ago
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.
- karussell 10y agoI'm curious: what does "global router (for EDA)" mean? And yes, A* & landmarks is really nice :) !
- jononor 10y agoLikely an algorithm/tool that can automatically lay out the traces on a PCB for electronics production. EDA=electronics design automation
- nhaehnle 10y agoIn 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.
- rasz_pl 10y agoits something no remotely competent engineer uses, but tool providers love to dick wave around https://teespring.com/shop/autorouter https://teespring.com/shop/autorouter
- taneq 10y agoEven 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.
- nhaehnle 10y agoYou do know EDA is about more than just PCBs, right? Good luck routing millions of nets in a microprocessor design by hand... The really competent engineers use the tools for the bulk of the problem, and fix up by hand where it makes sense.
- rasz_pl 10y agoYeah, 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).