ネブラスカの問題

Casey MuratoriはThe Witnessのプログラマーの一人です。 ゲームを開発する過程で、彼は自分のブログで直面した技術的な問題に関する投稿を公開しました。 以下は、これらの投稿の1つの翻訳です。



プログラマーとしての私のキャリアを通して、1つの原則は変わっていません。常に時間をかけて自分自身に問いかけます。 これは、単純なソフトウェア構成の作成から高度なアルゴリズムまで、常に発生しています。 根深いアイデアでさえ間違っていることがよくあります。これらのアイデアを疑うことで、驚くべき重要な発見を思いつくことができます。



したがって、何かに取り組むとき、その背後にある理由を再帰的に検討し始めます。 そして、草を植えることも例外ではありませんでした。



先週説明したコードは、草のシステムに対する他の多くの無関係な修正とともに、すでにウィットネスのソースツリーに組み込まれています。これについては、来週お話しします。 それは明らかな問題に対する合理的な解決策であり、時間がなくなっていたので、より深い問題を解決する時間がないことを知っていました。 しかし、私の頭の中で、次回パターンの生成に取り組むときは、「なぜ」という質問をする必要があると心に留めました。 この記事に割り当てられた時間のおかげで、私はこの機会を得ました。



この場合の「なぜ」という質問は非常に単純です。なぜブルーノイズを使用して芝生を配置するのでしょうか。



ブルーノイズは素晴らしいノイズパターンです。 草に関する最初の記事で述べたように、それは見栄えの良いプロパティを持っています。 しかし、ブルーノイズをより効率的にするためにウィットネスの芝生システムを変更したとき、最初にコードを書いた人を繰り返しました。 しかし、誰がブルーノイズを選ぶのが良い決定だと言ったのでしょうか？ 彼はどのような問題を解決したかったのですか？ブルーノイズが最良の解決策でしたか？ 以前は、草のようなものにブルーノイズを使用していましたが、現在の環境では最適な配置戦略になると確信していましたか？



前の2つの 記事と、これらのスキームを生成するために使用されたコードを書いたとき、これらの質問に対する答えはほとんどないということに気付きました。 私たちのアプローチには理論的な問題があると言ったとき、私は以前の記事でこれをほのめかしました、そして今、私はこの問題が何であるかを明確に言うことができます。

トウモロコシの行

以下に、ブルートフォースと近傍のサンプリングのための元の手法によって作成されたパターンのスクリーンショットをいくつか示します。









これらのパターンが普通のプレーヤーの観点からどのように見えるかを以下に示します。









そして最後に、パターンがどのように見えるか、各ポイントに植物看板があります：









ご覧のとおり、それらの間に大きな違いはありません。つまり、私たちは良い仕事をして、 The Witnessで十分に速く動作できるブルートフォースアルゴリズムを作成しました。 しかし、これらのスクリーンショットをもう少し見てみると、ブルーノイズが全体的にどれだけ良いかを理解するのが少し難しいことがわかります。 実際、これらのパターンがどれほど悪いか、良いかはわかりません。 同様の画像を比較する出発点はありません。 より良い結果を生み出すよく知られたスキームなしで、パターンがどれほど優れていると言えるのでしょうか？



直感的に、ブルーノイズは空間を非常に効果的にカバーしているように思えました。 より高いレベルでは、草を配布するタスクは、「最小数のポイントを使用して、目的のエリアの視覚的に快適なカバレッジを作成する」と定式化できます。 他のリアルタイムレンダリングタスクの場合と同様に、スペースを適切に視覚的にカバーするために必要なポイントが少ないほど、各フレームで草をレンダリングするコストが少なくなるため、「最小ポイント数」と言います。 コストが低いほど、グラフィックスシステムは他のものをレンダリングするためにより強力になります。 そして、エホバの証人には、すべてのフレームでレンダリングする必要のあるものがたくさんあります、私を信頼してください。



そのため、一部の場所を塗りつぶしたくない場合は、レンダリングパワーを増やすことでブルーノイズの密度を上げることができますが、カバレッジをより密にすることができます。









しかし、可能な限り低い密度を目指して努力し、同時に説得力のあるコーティングを作成する必要があることは明らかです。そのため、目的のレベルは記事の最初のスクリーンショットと同じである必要があることに気付きました。 ポイントの数が多すぎると、プレーヤーの近くの空のスポットを避けることができない場合がありますが、彼から少し離れると、理想的なパターンが草を美しく飽和させます。



しかし、先週、パターンを試したときに、非常に不快なことに気付きました。 同じパターンで、カメラを特定のポイントに回転させると、パターンの一部がほぼ均等な行を作成し、明確なボイドがカメラから遠くても顕著になります。理想的には、十分に重複した植生があるはずです。









これは、両方の手法を使用する場合に顕著であるため、一般的なブルーノイズの特性、または少なくともポアソンスポット法で生成されるすべてのタイプのブルーノイズの特性に似ています。



私が今開示しない理由のために、私はネブラスカの車の後部座席に座って、世界で最も退屈な高速道路を旅しなければなりませんでした（ネブラスカのほとんどすべての道路はそれと呼ぶことができます）。 窓からトウモロコシ畑を見ると、トウモロコシの列が同じ特性を持っていることがわかります。多くの角度からはトウモロコシ畑のように見えますが、正しい角度を見ると、突然非常に繰り返されることがわかります。 行間の長くて狭いギャップが表示されます。 これはとうもろこし畑では非常に普通のことですが、草が密生しているように錯覚させる必要がある場合はあまり良くありません。



トウモロコシ畑の特性に類似しているため、このブルーノイズ問題を「ネブラスカ問題」と呼びました。



ネブラスカの問題が草の分布を妨げることは望みませんでした。 私の知る限り、これは理論上の問題です。ブルーノイズアルゴリズム自体に問題はないからです。 この場合、実践は絶対に正しいものであり、理論だけでは不十分です。



私はこの問題に対処できるノイズの理論を知らず、その存在について言及した記事にも出会わなかったため、ネブラスカの問題を自分で解決できるかどうかを確認するために、ブルーノイズの規則に違反して実験することにしました。

充填率の実験

新しいタスクの探索を開始するたびに、それについて明確なアイデアがありません。 私は問題が存在することを理解していますが、まだ明確に定義されていないので、明白なことをランダムに試します。



私が最初に試みたのは、近隣選択アルゴリズムによるポイントの選択方法を変更することでした。 前回の記事では、このアルゴリズムがテストするポイントを選択する方法の詳細には触れませんでした。 基点からランダムな方向に「rから2rまで」のランダムなポイントを取るようにしました。



これはさまざまな方法で実行できます。 最も簡単な方法は、rと2rの範囲で角度と距離を均一に選択し、それらを直接使用することです。 ただし、この方法で選択したポイントを適用すると、それらのポイントが円の中心から大きく外れていることがわかります。









ここで何が起こっていますか？ これについて考えると、円の半径が大きいほど、角度が変化したときに円上でポイントがより遠くに移動することが明らかになります。 これは、ランダムな点のユークリッド密度が同じである大きな円の周囲をカバーするには、小さな円をカバーする場合よりも多くのランダムな角度を取る必要があることを意味します。 つまり、ランダムな角度とランダムな半径をランダムに取得すると、結果として、小さな半径は常に大きな半径よりも密になります。 円内で均一な密度のポイントを実際に選択するには、角度と半径を均一ではなく選択するか、半径の増加に伴う角度の変化効果を考慮するか、より単純に、正方形内のポイントを単に均一に選択し、該当しないポイントを破棄する必要があります円。



さて、なぜこれについて話しているのですか？ 隣人を選択するアルゴリズムを実装するとき、私は通常、中心に近づくときにバイアスを残します。 そのため、結果はより速くなり、視覚的には完成したパターンに影響を与えないことがわかりました。 しかし、私のタスクはパターンを変更することだったので、考えなければなりませんでした。ポイントの選択をさらに偏らせるようにしたらどうでしょうか。



したがって、私は「パッキング率」の概念を導入することにしました。 基点からrから2rまでの距離にある点を選択する代わりに、パラメーターを2に等しくしました。したがって、選択したすべての点を基点に近づけることができます。理論的には、パターンの平均距離を短くし、より密なパッケージを作成します。









残念ながら、密な包装がネブラスカの問題をさらに強調したため、この試みはすぐに無益であることが判明しました。 パターンを見ると、これを理解できます。パッケージがより密になると、隣接を選択するためのアルゴリズムの2つの「分岐」が互いに平行になり、その間に空きスペースを希釈する確率的なパターンを作成する可能性がなくなります。

ギャップを考慮します

したがって、パッケージングの実験は非生産的であり、論理的でした。 密に充填されていないスペースでは、ドットをより柔軟にするのに十分ではないと考え始めました。 おそらく、より自由な配置半径で元のブルーノイズパターンの上に2回目のパスを作成すると、整列した行が顕著なギャップを作成する場所を埋めることができます。









これが実際に機能することが判明しました。 少なくとも、それは一見したように見えました。 しかし、ポイントの数を数えたとき、実際には、ギャップを埋めるときと同じ数のポイントでブルーノイズパターンを作成すると、それも非常に高密度になり、問題を回避できないことがわかりました。









つまり、元のパターンのギャップをなくすことは実を結ぶことができますが、この方法を効率的に機能させる方法をすぐに見ることができました。実際、ポイントの数が増え、既存のポイントの分布に関する問題を排除しませんでした。

線に沿って草を植えます

ブルーノイズのいくつかの修正に失敗したので、ブルーノイズの特性をまったく持たない、とんでもないアプローチを試してみました。興味深いものがあるかどうかを確認するだけです。 最初のコンセプトに戻って、私が考えたのは、もし私の目標がスペースのある視線を避けることであるなら、この原理に基づいてパターンを生成する価値があるかもしれないということです。 そのため、領域内のランダムな可視性の線を選択するアルゴリズムを作成しました。 彼はそれぞれの線に沿って歩き、特定の距離が交点なしで通過する線の長さを探しました。









残念なことに、アルゴリズムはランダムな行を選択するため、2つの行を非常にうまく並べて選択することができます。これにより、再びネブラスカ問題に戻ります。 パターンの一部では非常にうまく機能しますが、線がほぼ平行である部分では、ネブラスカの問題が完全に明らかになります。

選択的削除

前の方法と同様に、私は反対のアプローチを試す価値があると考えました：ホワイトノイズによって生成された領域の密なカバレッジから始めて、空のスペースの長く連続したラインを正確に作成しないポイントのみを削除します。 各ポイントは多数の方向でチェックする必要があり、アルゴリズムはこれらの線に沿って順方向と逆方向の最初の「ヒット」が発生する場所を決定しました。 チェックしたすべての線に沿った距離が短い場合、このポイントを削除しました。 これらの線のいずれかに沿った結果の距離が大きすぎる場合、ポイントを残しました：









残念ながら、これにより以前の試みと同様の結果が得られました。1つの方法でパラメーターを設定すると、ネブラスカの問題は消えましたが、サンプリングが濃すぎました。 異なる設定では、ネブラスカの問題を意図的に回避しようとしても、サンプリングがあまりにもまばらで、どこにも顕著なギャップがありました。



その瞬間、私はすでに推測しなければなりませんでした。 何が起こっているのか、しかしこれは起こらなかった。 おそらく水曜日の真ん中だったと考える価値があり、私は証人の締め切りまでに時間がないことに気づいたので、少し夢中になり始めました。 十分に明確ではないと思います。 どうすればいいですか？ プッシュを続けるか、単に電話して発言する必要があります。「だから、アルゴリズムに問題があります。それを解決する方法を知っていれば、気が滅入るでしょう。 素敵な環境があります。 クリスマスがキャンセルされました！」



みなさんがサンタクロースにとってどれほど重要かを知っています。 毎日ではなく、太くて笑顔のひげを生やした祖父がひそかに家に入って、一年中「従う」子供たちに「贈り物」を残します。 クリスマスをキャンセルした人になりたいですか？



いいえ、もちろんそうではありません。私は決めました-クリスマスは元に戻せません。 クリスマスはキャンセルされません。 クリスマスはほんの少しだけ延期されました。

リラクゼーション

だから、大丈夫、問題ありません。 クリスマスが遅れています。 水曜日だったので、木曜日に開催されるかもしれません。 または金曜日に。 仕事に戻ります。



グラフィックス研究に関する記事を読むと、おそらく私が言うことに同意するでしょう。人々がアルゴリズムが明らかにうまくいかない状況にいることに気づいたら、間違いなくリラックスする必要があります。 必要な場所にドットを配置できませんか？ リラックス！ ドットを必要な場所に配置する方法が見つからない場合は、自分でドットを見つけさせます。



そこで、緩和段階を追加しました。 そして、私はリラクゼーションのために2つの異なる「エネルギー関数」を使用しようとしました。その最初は、「自分から他のポイントを追い払う」の単純なバージョンでした。









2つ目は「隣接する線を破る」バージョンでした。彼女は同じ線上にある3つ以上の点のセットを探し、内部点の1つをより広いスペースのある側の方向に移動しようとしました。









図からわかるように、これらの戦略はいずれも有望に見えませんでした。 それらは完全に状況依存であり、より良い結果を得るためにそれを調整することができましたが、リラクゼーション戦略の大きな意味を語る予備結果には何も見ませんでした。 どのようにポイントを移動しようとしても、古いコーンを壊したり、それらの間のスペースが大きすぎてさらに悪くなったとしても、ランダムに新しいコーンの列を作成したように見えました。



水曜日の夕方で、夕食の時間でした。 しかし、それは異常な環境であったため、夕食も異常になったはずです。 実際、マッド・ウェンズデーでした。つまり、クレイジーな水曜日のディナーの時間でした。

方向の制限

クレイジー水曜日は特別な曜日です（多くの場合、水曜日には行われませんが、その理由は言いません）。 ショーンバレット 、 ファビアンギーセン 、 ジェフロバーツ 、そして私が完全にクレイジーな時間を過ごすつもりです。レストランで1時間、特定の技術的な問題の詳細について話し合います。 そして、これがあなたにとって十分にクレイジーに聞こえない場合、特にそのマッドウェンズデーに特別ゲストのTommy Refenesがいたので、彼女は以前よりもクレイジーになることを知っていました。



クレイジー環境への訪問は、他の人と問題を話し合うことができ、多分私は新鮮な外観を得るので、役に立つでしょう。 そしてそれが起こった。



問題を説明した後、ファビアンとショーンは、最初に、隣人を選択するための元のアルゴリズムが線を作成しないようにして、パターンを修正する作業を回避することが最善であるという結論に達しました。 元のランダム生成アルゴリズムが行を作成しない場合、行を削除することはグローバルな問題であるため、結果はプロセス後に行を修正した後よりも良いパターンになる可能性があります：パターンを劇的に変更できるようにポイントを移動する必要があります。 最初に行を作成しない場合、パターン全体が行なしになります。つまり、グローバルな問題は単純に消えます。



したがって、たとえば、新しいポイントがそれぞれ前のポイントと同じラインに沿っていないことを確認するなど、線の作成を防ぐためにヒューリスティックを試しました。









残念ながら、私はまだネブラスカの問題を抱えていました。 隣接選択アルゴリズムの直接分岐が行を作成しなかったとしても、隣接分岐が互いに共謀して行を作成したようです！



それはすでにばかげているようになっていた。 各アルゴリズムが同じアーティファクトを生成するのはどうですか？ 何が起こっているの？

湾曲した六角形のパッケージ

私はまだ真剣な洞察を追い越しませんでしたが、私は間違いが何であるかを理解し始めました。 私は一歩後退し、あまりにも多くのドットを使用しないトウモロコシの列のないパターンを作成するために必要なものを考えました。 私は実際に曲線が必要だと結論付け始めました。 一連のポイントの2つの曲線は線形空間が決して表示されないパターンであるため、生成されたラインが常にポイントベンドを与えるようにしたかったのです。 ランダムに配置すると、ポイントの相互影響が実際に発生し、隣接するラインが作成されます。両側に3つのポイントしかない場合でも、ネブラスカの問題を示すにはこれで十分です。 したがって、スペースの保証された不在を作成するアルゴリズムは、まったくランダムではなく、一定である場合があります。



これは問題に対する私のアプローチを完全に変えました。 この間ずっと、私は良いカバレッジのためにランダム性が必須だと思った。 しかし、今、問題を慎重に検討した後、私にはチャンスが実際に悪い可能性があるように思われました。



だから、私は必要な特性を持つかもしれないパターンを繰り返すことを考え始めました。 それらは、普通のプレーヤー（芝生に立っている）の視点から見た場合、明らかに反復しているように見えるべきではありませんでした。 ドットの連続した直線を含めることはできません。 スペースを効果的にカバーする必要があります。



円の最も高密度のパッケージには六角形のパッケージがあることがわかりました。









したがって、スペースを効果的にカバーする必要がある場合は、六角形のパッケージングから開始するのが最善であると判断しました。これは、使用するポイントの数を最小限に抑えながら、カバレッジに視覚的に最適な距離に各ポイントを配置するためです。



しかし、六角形のパック自体は明らかにひどいものです。なぜなら、これらは異なる方向のトウモロコシの列であり、つまり、私が必要とするものではないからです。 だから私は考えた-六角形のパッケージを曲げたらどうなりますか？ 極座標で六角形のパッキングを解釈して、曲線の行を取得しようとしました。









また、オリジナルの隣接選択アルゴリズムに似たさまざまな回転パターンを試しました。このアルゴリズムでは、ランダムにまたは連続的に回転する六角形パターンの新しいポイントを分岐させました。



残念ながら、16進パックも機能しませんでした。 スペースを残したり、混雑したり、いずれかの方向に線を引いたりしました。 しかし、幸いなことに、まさに私の目標が何であるかに目を開いたのは彼らでした。



参照-配布は平面上で実行されます。 平面には常に2つの直交ベースがあります。 したがって、極座標を使用して六角形のパッキングを湾曲させるために使用した1つの曲率軸の使用は決して行いません。線を作成できる軸の1つを湾曲させますが、他の軸は湾曲させません。 実際、2つの曲率軸を持つ点の分布が必要でした。そのため、文字通り、あらゆる周波数で空間に線を作成する方法はありませんでした。

オフセット同心円交差パッケージ

まあ、2つの曲率軸、問題ありません。 2つの円を取り、パターン内のポイントを配置します。これらの円の同心円の輪が交差します。









きれいに見えました。 私はすでに解決策に近づいていると感じました。 分布を異なる角度から見ると、ポイント間のスペースを視覚的に隠すために曲率が少し弱かったため、主な問題は曲率がまだ見えることであることがわかりました。 曲率を大きくすることは可能だと思っていましたが、その後、たとえば、円の3つごとの同心円状のリングを移動するとどうなるでしょうか？ 同心円状に均等に分布するリングの代わりに、各3番目のリングの半径がわずかにオフセットされてノイズが発生し、パターンの顕著な再現性がわずかに低下します。 これは完全に決定論的なバイアスであり、実際には事故はないことを思い出してください。









ビンゴ これはまさに私が必要とするコーティングです！ 密集した可視範囲と、立っている場所以外のスペースに絶対に気付かないこと（もちろん、ドットの数を増やしてスペースを文字通り完全にカバーすること以外は修正できません）。 アルゴリズムに表示される問題のある表示領域をオフセットなしで完全に排除することができました。









また、ボーナスもあります。スペースのあるブルーノイズに対して使用したポイントよりもはるかに少ないポイントを使用して、視覚的に優れたカバレッジを得ることができます。

なぜそんなに多くの失敗があるのですか？

最も複雑な問題の場合のように、その問題に没頭すると、多くの場合、物事の正しい見方を見つけることができません。 これが「ダイビング」と呼ばれる理由です。 過去数日間を振り返ってみると、私のアプローチに根本的な誤りがあります。



私はかなり良いランダムなカバーから始めました-ブルーノイズで、それを洗練したかったです。 しかし、ランダム性とは何か、どのように機能するかを思い出せば、かなり明白な真実を認識することができます。ランダム性は決して最適ではありません。 一連の基準について、最適な入力データのセットがランダムに選択されることはほとんどありません。 100個のサイコロを取り、それらを転がすと、600は得られません。おそらく決してありません（D20サイコロを使用することはできますが、この比phorは明確で、D＆Dをプレイしないでください）。 ランダム性を制限することもできません。 すべてのキューブを取り、すべてのユニット、2、3、4を6に置き換えても、つまり、キューブに残っているのは5と6だけです。600を投げることはほとんどありません。あなたがすべての6を得るまで、それは7回です。



したがって、何か最適なことをしたい場合は、ランダムアルゴリズムを超える必要がある可能性があります。 私は偶然から楽観主義を生み出すパターンを探し続けましたが、それは非常にありそうにありませんでした。 ブルーノイズは私の目的にとって非常に良いパターンであるため、ランダム性の転換点を見つけようとしましたが、より良いランダムパターンがなかったため、各回路が故障する運命にありました。 この飛躍を実現するために、私はカオスから秩序に移行し、最適なものを直接制御する必要がありました。



これは実際、この経験から学ぶことができる非常に重要な教訓です。 パターン自体はそれほど重要ではありません。 タスクが最適化に関連しているかどうかを理解することが重要です。関連している場合、他の何らかの理由でランダム性を使用する必要がありますか？ その場合は、最適でないものを選択する必要があります。 そうでない場合、次に進むには、チャンスをあきらめなければなりません。



多くの発見で起こるように、あなたがそれについて考えるならば、それは非常に簡単で、実際にそれ自身を説明します。 しかし、多くの場合、頭の中に落ち着くように実際の経験に直面する必要があり、それを直感的に理解し、有用な新しい条件に適用することができます。

忍者ワーミング

それで、忍者のプログラミング、私たちは何を学びましたか？ことわざにあるように、「永続的な忍者は常にワームを捕まえる」と思う。このことわざがあなたに馴染みのないものなら、あなたはおそらく私と同じように日本の歴史文学を知らないでしょう。これは正常です。夏が近づいているので、夏の読書リストにケンブリッジ日本語歴史コースを追加できます。



ワームを捕まえる私の場合、パターンのある状況が私の強迫観念になっているように思えます。ゲームに新しいパターンを適用する必要があるかどうかは定かではありません。また、他の植物との作業に潜在的な問題があるため、The Witnessで使用する価値があるかどうかもわかりません。しかし、前のセクションで説明したように、私はこの経験から多くのことを学びました。技術的なタスクを開始し、あきらめることを拒否するときはいつも起こるからです。



私にとって、このようなタスクの作業は、実際に解決策を見つける必要性とはほとんど関係ありません。「十分な」結果を得るには、ブルーノイズで十分であることがわかりました。しかし、「より良い」解決策があり、「十分な」ものの後ろに隠れていると感じている場合、私は通常それを見つけようとします。この場合、パターンについての新しい考え方を教えてくれたので、成功したことを非常に嬉しく思います。また、将来このパターンを使用しなくても、繰り返しパターンとランダムパターンの違いをより深く理解することで、他の多くの状況で利益が得られると思います。