Autorouterを開発する前に知っておきたかったこと
(blog.autorouting.com)"世界最速の自動配線器（Autorouter）を作るための重要な教訓"
A*アルゴリズムをあらゆる場所で活用する
- A*は探索問題において最も強力で柔軟なアルゴリズムである
- 単純な2Dグリッドだけでなく、さまざまな問題で利用できる
- A*はBFSよりも高速かつ効率的に、目的地に近いノードを優先探索する「情報に基づく探索」である
- 既存コードで使っているDFSやBFSの多くはA*に置き換えられる
- 性能改善のために複数のA*インスタンスを実行し、その中で性能の良い設定により多くのリソースを割り当てる手法を使う
プログラミング言語よりアルゴリズムのほうが重要
- autorouterをJavascriptで開発してもまったく問題なかった
- 最適化の核心は反復回数を減らすこと
- 言語性能よりも「どれだけ賢いアルゴリズムをどれだけ速く作れるか」のほうが重要である
- Javascriptは高速な反復処理よりもスマートなアルゴリズムに向いている
ツリー構造よりSpatial Hash Indexingのほうが効率的
- Quadtreeなどのツリーベースのデータ構造は一般に遅い
- Spatial Hash Indexはオブジェクトの位置をハッシュ化し、空間的に近いオブジェクト同士をまとめて処理する
- ハッシュベースの構造はO(1)に近い探索性能を提供する
- Cellサイズを適切に選ぶ必要があり、適切なサイズ選びはそれほど難しくない
空間分割とキャッシュはアルゴリズムより1000倍重要
- 複雑な回路基板も大半は繰り返しパターンを持っている
- ゲーム開発のように事前計算した結果をキャッシュすることで、性能を飛躍的に向上できる
- キャッシュ可能な構造と空間分割が将来のautorouterの中核になる
- ストレージは急速に安価になっており、数GBのキャッシュでも大きな性能向上が可能である
可視化なしでは問題解決は不可能
- あらゆる問題に対して、まず可視化ツールを作ってから始める
- 可視化によってデバッグ速度を10倍以上向上させられた
- 単純なアルゴリズムの段階でも可視化すれば、問題原因を素早く把握できる
Javascriptのプロファイリングツールは非常に有用
- Chrome開発者ツールのPerformanceタブでコードごとの所要時間を確認できる
- 別途フレームワークがなくても、Flame Chartやメモリ使用量などを簡単に分析できる
- 性能デバッグに非常に役立つツールである
再帰関数は使わないこと
- 再帰関数は一般に同期的で、A*への切り替えが難しい
- 反復ベースの実装のほうが速く、訪問済みノードの追跡もしやすい
- 再帰関数では状態変更が難しく非効率である
- できる限りループベースで書くこと
Monte Carloアルゴリズムは避けること
- ランダム性ベースのアルゴリズムは非決定的でデバッグが難しい
- ドメイン特化のヒューリスティックのほうが常に優れた性能を発揮する
- ランダムに線を引くPCBデザイナーはいない → 現実的なアプローチではない
- ただし、初期段階で感触をつかむ用途には有用なこともある
アルゴリズムの各段階を実際の問題空間に固定する
- サブアルゴリズムを原点基準で正規化すると、全体の流れを把握しにくくなる
- 各段階の入出力を可視化して、どの段階がエラーを引き起こしているかを把握する
- 座標系の一貫性を保ちながらアルゴリズムの流れを維持することが重要
反復過程をアニメーションで可視化する
- アルゴリズムがどれほど非効率に探索しているかを視覚的に把握できる
- アニメーションは反復回数を減らし、効率を高めるのに非常に効果的である
- 問題状況を簡単に捉えられる（例: 無限ループに陥った探索など）
グリッドなしでも交差判定の数学で十分
- グリッドを使う代わりにベクトル数学を活用すると、はるかに高速である
- メモリアクセスより数学演算のほうが速い場合も多い
- LLMのおかげで交差判定の数学も簡単に実装できるようになった
- 不要なグリッド利用は性能低下の原因になる
各段階の失敗確率を測定して、解決可能性を優先順位付けする
- 各空間分割ノードで失敗確率を推定できる
- その後の段階で失敗する可能性が高いノードを優先的に再構成または再探索する
- 失敗確率は明確に測定でき、ヒューリスティックより改善の余地が大きい
- 全体の解決可能性を高めることは、最適化そのものを目指すより効果的な場合がある
Weighted A*で速度を100倍向上できる
- 標準のA*は最適経路を保証するが、速度は遅い
- Weighted A*はより貪欲に探索することで、速度を大幅に向上できる
f(n) = g(n) + w * h(n)のように重みを設定するだけで実装できる- 最適性を多少犠牲にしても、はるかに高速に問題を解ける
- ゲーム開発分野でもよく使われる手法で、参考にする価値がある
1件のコメント
Hacker Newsの意見
Monte-Carlo法を早々に切り捨てるのは大きな間違い
「自動ルーターを信じるな」という立場
記事は可視化とキャッシュ効果に関する重要な点に触れている
自動配線についてのすばらしい議論
焦点の95%は反復回数を減らすことに向けるべき
QuadTreeと一般的な木構造データは非常に遅い
ほとんどすべてがゲーム開発のヒューリスティックと一致している
「空間ハッシュインデクシング > 木構造データ」はこの分野では有効だが、世界普遍の真理として受け取るべきではない
大学で習ったキーワードを覚えている
2D/3Dの空間問題に直接関わっていない者として、可視化の価値が最大の教訓